(以下描述,均不是学术用语,仅供大家快乐的阅读) 飞蛾扑火算法(Moth-Flame Optimization)是受飞蛾围绕火焰飞行启发而提出的算法。算法提出于2015年5月(投稿日期),虽可算作一个新算法,不过无数研究者就像飞蛾见了火一样,发表了如此之多的论文,惊了。 飞蛾扑火算法中有两种个体,飞蛾和火焰,飞蛾选择并围绕火焰以螺线方式飞行搜索,搜索完后,火焰将移动位置,以保持火焰是飞蛾和火焰群体中最优的位置。 算法的流程简单,螺线搜索在之前的鲸鱼算法中也出现过,这里会较为详细的记录记录螺线搜索的具体情况。
显然,飞蛾扑火算法中有两种角色,飞蛾与火焰。初始时飞蛾与火焰的数量均为N。为了方便查看,将飞蛾的位置表示为XM ,火焰的位置为 XF。 初始化时,会在解空间内初始化N个飞蛾与M(M=N)个火焰。在算法过程中,飞蛾将会围绕它所选择的火焰飞行,之后将这N个飞蛾与M个火焰按优劣排序,并将M个火焰移动到较优的前M个个体的位置。其中火焰的数量M会随着迭代次数的改变而不断变化,论文中阶梯递减至1。 算法的主要步骤如下: 1. 飞蛾选择火焰(将火焰分配给飞蛾)。 2. 飞蛾围绕火焰飞行。 3. 移动火焰到相应位置。 从步骤可以看出,算法中飞蛾的飞行是一种无贪心算法的操作,而火焰的移动则是一种变相的贪心操作。
初始化时,会有N个飞蛾和N个火焰(M=N),故每只飞蛾都可以选择互不相同的火焰。随着迭代次数的递增,火焰的数量会递减。其数量根据以下公式计算得出:
其图像如下图所示:
其实就是将火焰数量M线性递减到1,由于火焰数量是正数,故图像呈阶梯状。 随着迭代次数增加,火焰数量递减,每只飞蛾无法选择互不相同的火焰,此时可以随机选择火焰或者飞蛾群体按顺序依次往后选取,类似于取模。两种方式的差别不大。
该步骤是算法的核心计算步骤。 对于飞蛾 ,它围绕火焰 飞行后到达的新位置XM_new根据以下公式计算得出:
其图像如下
而算法中的飞行轨迹应该是这样的:
取出一维看看
其中i为计算次数。
图像就是cos函数图像的变形。考虑到飞蛾与火焰之间的距离会越来越短,其飞行图像应该与上图相反,即振幅越来越小,局部搜索能力越来越强。
N只飞蛾围绕M个火焰飞行后,会到N个新位置,计算这N个新位置的适应度值,将这N个新位置与M个火焰这(N+M)个位置按优劣排序,并将其中较优的M个位置作为下一轮中火焰的位置。
其飞蛾扑火算法流程图如下:
由于飞蛾扑火算法可以说是对蚁狮算法和鲸鱼算法的结合,这里就看看算法的图像,不再做其他处理了。 适应度函数 。
实验一:
从结果看来,飞蛾扑火算法的性能稳定也优于蚁狮算法,从图像看算法收敛性不如蚁狮算法但局部搜索性能要强于蚁狮算法。 可见螺线的局部搜索能力还是强于随机游走的,不过其全局搜索要弱于随机游走。相比蚁狮算法,飞蛾扑火算法更容易陷入局部最优(其实与蚁狮差不多,只要火焰/蚁狮陷入局部最优基本完蛋,不过蚁狮数量恒定,火焰数量递减,所有火焰更容易局部最优)。
飞蛾扑火算法是根据飞蛾围绕火焰飞行的行为而提出的算法。算法的结构比较简单,与蚁狮算法类似,只是搜索步骤将随机游走替换成了螺线搜索(当然还有跟多细节上的不同,可以看看原文)。算法的局部搜索能力非常强,依靠螺线就提供了全局搜索和局部搜索能力,其全局搜索和局部搜索能力强弱由其极半径决定,算法中由b决定。不过算法缺少跳出局部最优的能力,在平滑函数中的效果非常好,在局部最优较多的函数中效果中规中矩。
参考文献 Mirjalili S . Moth-flame optimization algorithm: A novel nature-inspired heuristic paradigm[J]. Knowledge-Based Systems, 2015, 89(NOV.):228-249.. 提取码:koy9 以下指标纯属个人yy,仅供参考
目录 上一篇 优化算法笔记(二十四)帝王蝶算法 下一篇 优化算法笔记(二十六)和声搜索算法