飞蛾扑火优化算法的研究及改进

汪雪莹，贺兴时

（西安工程大学理学院，西安 710600）

优化是工程数学问题，优化过程就是对特定问题找到最优解决方案的过程.群智能优化算法便属于随机优化方法的范畴.群智能算法一般来源于对自然界中一些生物群体行为的模仿，具有操作简单、易于并行处理、鲁棒性强等特点，已发展成为优化问题中的研究热点.比较典型的群智能算法有粒子群优化算法（Particle Swarm Optimization，PSO）［1］、萤火虫算法（Firefly Algorithm，FA）［2-3］、花授粉算法［4］（Flower Pollination Algorithm，FPA）、布谷鸟优化算法（Cuckoo Optimization Algorithm，COA）［5］、人工蜂群算法（Artificial Bee Colony Algorithm，ABC）［6］、人工鱼群算法（Artificial Fish Swarms Algorithm，AFSA）［7］等.

飞蛾扑火算法（Moth-Flame Optimization Algorithm，MFO）是Mirjalili［8］于2015年提出的一种新型智能优化算法.其灵感来源于一种特殊的导航机制—横向定位导航机制，该算法具有模型简单、参数少、局部搜索能力强、并行优化能力强、全局性优且不易落入局部极值的性能特征，因此在诸多领域有着其他智能优化算法不具备的潜力，也逐渐引起了学术界和工程界的关注［9］.飞蛾在晚上飞行时，因其与月亮相距较远，所以飞蛾与月亮保持固定的角度即可保证自己沿直线飞行.文献［10］通过引入混沌理论，利用Sinusoidal混沌函数对MFO算法的收敛因子进行调整，分析证明该策略可以更好地平衡算法的全局探索与局部开发能力.文献［11］中结合Levy飞行搜索策略提出了LMFO算法，Levy飞行搜索策略具有多数小步移动、偶尔大步移动的特点，使MFO的搜索范围扩大.文献［12］提出纵横交叉混沌捕焰优化算法，此算法运用了纵横交叉机制，使得火焰之间以及火焰的不同维度之间互相结合，并引入混沌算子，提高算法精确度和跳出局部最优能力.文献［13］提出基于折射原理反向学习的飞蛾扑火算法（ROBL-MFO），将历史最优火焰的平均值、反向学习策略以及折射操作引入到该算法中，能够使火焰间的信息相互交流、跳出局部最优解，从而提高算法的寻优性能.

在求解复杂的峰值函数优化问题时，对于MFO算法的收敛精度不高、收敛速度慢、易于陷入局部最优等特点，上述改进仍具有局限性，因此需要设计一种新的改进的MFO算法来提高MFO的全局优化性能.针对以上问题，本文提出自适应飞蛾扑火优化算法（AMFO），改进策略如下：首先，在飞蛾与火焰的距离中加入动态自适应步长因子，提高算法的全局寻优的能力；其次，在火焰位置加入动态自适应权重因子，更新寻优方式，从而可以达到全局寻优与局部寻优相平衡，解决易于陷入局部最优的缺陷，使得飞蛾的更新方式更加具有灵活性，促使算法沿着正确的方向进行搜索.通过以上改进，可以显著地改善算法的收敛精度和收敛速度以及易于陷入局部最优的不足.

1 标准飞蛾扑火算法

1.1 MFO算法

在MFO算法中，飞蛾个体表示着优化问题的候选解，飞蛾在优化空间的位置代表求解优化问题的变量，通过在优化空间中改变位置向量来向全局最佳点靠拢，火焰便是飞蛾到当前迭代次数所找到的最佳位置［14］.MFO算法中，矩阵M表示飞蛾的位置.

其中：n代表飞蛾的个数；d代表控制变量的数量（维度）.矩阵OM存储飞蛾的适应度值，表示如下：

其中：n代表飞蛾的个数.

MFO算法中要求每只飞蛾仅利用与之对应的唯一火焰更新其自身位置，从而避免算法陷入局部极值情况，大大增强了算法的全局搜索能力.因此，搜索空间中飞蛾位置与火焰位置是相同维度的变量矩阵.矩阵F表示火焰的位置，火焰的适应度值存储在矩阵OF中：

其中：n代表飞蛾的个数；d代表控制变量的数量（维度）.

飞蛾实际上是在搜索空间内移动的搜索个体，每一只飞蛾个体环绕在一个火焰的周围，一旦搜索到更好的解，便更新为下一代中火焰的位置.

MFO算法是近似于优化问题中全局最佳的三元组：

I是产生一个随机的飞蛾种群和相应的适应度值的函数.其系统模型如下：

P是使飞蛾在搜索空间里移动的主函数.P接受矩阵M，并返回更新后的M.

如果满足终止准则，T函数返回真；如果不满足，则T函数则返回假.

飞蛾扑火算法的一般框架为：

M=I()，

WhileT(M)is equal to false，

M=P(M)，

end.

函数I初始化后，利用函数P使飞蛾在搜索空间内的位置发生改变，输出更新后的飞蛾矩阵，对更新后的飞蛾个体位置做出判断.继续进行迭代或者终止算法并输出结果，迭代运行直至函数T返回真.

1.2 位置更新机制

1）扑焰行为.自然界中具有趋光特性的飞蛾Mi会朝着距离自身最近的亮光（火焰）Fj移动［15］.飞蛾扑焰的移动轨迹为选取了对数螺线曲线，算法的对数螺旋曲线定义如下：

其中：S(Mi,Fj)为飞蛾更新后的位置；Di表示的是第i个飞蛾的位置与第j个火焰的位置之间的距离；b是常量，该常量与螺旋形状相关；t是随机生成的数字，取值区间为［-1，1］，当t=-1时飞蛾离火焰最远，当t=1时飞蛾离火焰最近.

其中：Di为飞蛾Mi与火焰Fj的距离.

2）弃焰行为.MFO算法通过弃焰行为自适应减少火焰数量，直到保持一个最优的火焰位置为止，火焰减少过程如式（11）所示：

其中：N为火焰数量的最大值；l为当前迭代次数；T为最大迭代次数.

2 改进的飞蛾扑火算法

2.1 动态自适应步长因子

传统的MFO算法中飞蛾位置的更新机制是通过对数螺旋线函数实现的，但此函数只是对飞蛾飞向烛火进行定义，这就易使飞蛾陷入局部最优，在全局寻优时存在一定的不足.本文引进文献［16］采用的非线性动态自适应步长方法，飞蛾在靠近烛火寻找最优解时，自适应步长的值较大时，表明算法可以搜索的范围较大，搜索力度也较大从而能够使飞蛾搜索能力增强，提高飞蛾的全局寻优能力.自适应步长的公式如下：

将公式（12）应用于飞蛾Mi与火焰Fj的距离中，其更新后的公式为：

其中：l为当前迭代次数；T为最大迭代次数；ϑ为参数.

图1 非线性变化动态步长因子α曲线图Fig.1 Dynamic step size factorαcurve of nonlinear change

2.2 动态自适应权重因子

惯性权重ω是一个可以改变搜索范围的参数，当ω减小时，在算法后期的探测能力增强，从而能够在最优解附近进行仔细地搜索.

MFO算法采用螺旋函数作为飞蛾的更新函数，但在解决大规模高维复杂优化问题时，算法不能保证收敛速度，针对这一问题，采用动态自适应权重因子.飞蛾在靠近火焰寻找最优解时，用动态自适应权重因子对飞蛾算法进行改进［17］，动态自适应权重因子ω的表达式为：

其中：l为当前迭代次数；T为最大迭代次数.

通过引入动态自适应权重因子改变了火焰更新系数恒为1的状态，又因为余弦函数的最大值为1，因而飞蛾算法的速度更新系数就由恒定值1变为在［0，2］之间动态变化的值，从而全局搜索和局部搜索得到平衡.将公式（14）应用到更新火焰位置的对数螺旋线函数中表达式为：

动态自适应权重和第j个火焰相乘，是随着迭代次数的增加从1到0非线性自适应减小的，使得飞蛾朝着正确的搜索方向进行，并能够有效地提高算法的精度.

2.3 改进后的算法（AMFO）步骤

Step1：初始化参数：设置飞蛾的种群大小n、搜索空间的维度d、空间上界ub和下界lb、最大迭代次数T以及火焰数量N；

Step2：在可行域空间内初始化飞蛾的位置；

Step3：对每只飞蛾的适应度值进行计算，对得到的适应度值按从小到大进行排序，找出最优的飞蛾位置并将其赋值给火焰；

Step4：利用式（14）更新动态自适应惯性权重以及火焰的位置；

Step5：利用式（12）更新动态自适应步长，按式（13）更新飞蛾与火焰的距离Di；

Step6：利用式（15）更新飞蛾的位置；

Step7：利用式（11）减少火焰的数量，迭代次数l=l+1；

Step8：判断是否满足终止条件.若不满足，则返回Step3继续进行迭代搜索；若满足，则输出整个迭代过程中火焰的最优位置以及所对应的适应度值，停止迭代搜索即算法结束.

3 仿真实验

3.1 测试函数

为了验证改进的算法AMFO的寻优效果，本文采用群智能算法常用的8个测试函数对其仿真实验.表1给出了这8个测试函数的表达式、维度、搜索空间范围以及最优值，其中f1～f4为多峰函数，f5～f8为单峰函数.单峰函数有且仅有一个全局最优值，所以更加适合对算法的收敛程度进行检测；而多峰函数则存在着大量的局部最优值，因此它们对检测算法的局部最优起着极其重要的作用［18-19］.实验中所用的8个测试函数如表1所示.

表1 测试函数Tab.1 Test functions

3.2 测试结果分析比较

将AMFO算法与基本的MFO算法、基于混沌飞蛾火焰优化［20］（Chaotic Moth-Flame Optimization Algorithm，CMFO）、布谷鸟算法［21］（Cuckoo Search Algorithm，CS）、蝙蝠算法［22］（Bat Algorithm，BA）四种不同的算法进行对比分析.将算法的参数设置为：飞蛾数量n设为25，最大迭代次数设为1000次，分别将函数维度设为10维、50维、100维进行测试，且每个测试函数均独立运行50次，分别求出标准差（Std.）、最优值（best）、平均值（mean）、最劣值（worst）作为测试结果，然后对AMFO算法进行评估，测试对比结果见表2～表9.

表2 f1函数测试结果Tab.2 Test results of f1 function

表3 f2函数测试结果Tab.3 Test results of f2 function

表4 f3函数测试结果Tab.4 Test results of f3 function

表5 f4函数测试结果Tab.5 Test results of f 4 function

表6 f5函数测试结果Tab.6 Test results of f5 function

表7 f6函数测试结果Tab.7 Test results of f6 function

表8 f7函数测试结果Tab.8 Test results of f7 function

表9 f8函数测试结果Tab.9 Test results of f8 function

从表2～表9可以看出，无论是多峰函数还是单峰函数，AMFO算法都比MFO算法具有更好的寻优能力，在精度上AMFO也表现得更为显著.随着维度的增加，AMFO算法表现出更为卓越的搜索能力和更加稳定的收敛能力.CMFO算法、MFO算法、CS算法、BA算法在维度增加的过程中，求解精度会发生明显的下降，且无法找到全局的最优点.CMFO算法与AMFO算法相比较，当维度为10维时，有着寻优精度上的差别，但是在50维和100维的情况下，CMFO算法则无法找到全局的最优点.

经过1000次迭代，函数f4和函数f6没有收敛到理论最优值，但是AMFO算法与CMFO算法、MFO算法、CS算法、BA算法相比较，AMFO算法的精度始终很高，表现出了良好的求解能力.函数f6在维度50、100时，CS算法的标准差明显高于AMFO算法，则在单峰函数f6的情况下维数越高，CS算法比AMFO算法更稳定.与其他算法对比发现，AMFO算法的标准差小于其他四种算法，说明AMFO算法的鲁棒性更强，且算法的稳定性更高.在平均值方面，AMFO算法的平均值最小，可以看出AMFO算法的收敛精度优于其他四种算法.

对于多峰函数f1、f2、f3，AMFO算法直接收敛到了最小值0，但是其他四种算法都容易陷入局部最优值.在维度为10维时，对于函数f4在最优解的精度上提高了120个数量级，函数f5提高了33个数量级，函数f6提高了175个数量级，函数f7提高了34个数量级，函数f8提高了33个数量级.

综上所述，改进后的飞蛾算法AMFO算法具有更高的收敛精度、更强的稳定性、更快的收敛速度.

3.3 算法收敛曲线分析

为了方便更加直观地比较算法的性能，图2～图9给出了8个测试函数下五种算法的收敛曲线.

图2 函数f1的收敛曲线图Fig.2 Convergence curves of f1 function

图4 函数f3的收敛曲线图Fig.4 Convergence curves of f3 function

图5 函数f4的收敛曲线图Fig.5 Convergence curves of f 4 function

图6 函数f5的收敛曲线图Fig.6 Convergence curves of f5 function

图7 函数f6的收敛曲线图Fig.7 Convergence curves of f6 function

图8 函数f7的收敛曲线图Fig.8 Convergence curves of f7 function

图9 函数f8的收敛曲线图Fig.9 Convergence curves of f8 function

以上收敛曲线图均为函数在维度为10维时所做的测试.从图2～图9可以看出，AMFO算法的收敛速度明显优于其他四种算法，并且基本在迭代100次以内均可收敛至全局最优，由此说明AMFO算法在收敛速度和收敛精度方面要比其他四种算法好得多.如图2所示，AMFO算法的收敛速度和收敛精度明显优于其他四种算法，并且BA算法的收敛精度最差；从图3、图6、图8和图9可以看出，在迭代50次时，AMFO算法收敛到最优值；在图4和图7中，AMFO算法的收敛曲线几乎垂直，收敛速度非常快，在很短的时间内找到了全局最优的解，因此AMFO算法可以较快的速度获得高质量的解，从而有效地避免了算法早熟和局部收敛的缺陷.

由上述对这五种算法的收敛曲线比对分析能够看出，无论多峰函数还是单峰函数，AMFO算法都具有较好的寻优能力和较快的收敛速度.

4 结语

本文在标准的MFO算法的基础上引入了动态自适应步长因子和动态自适应权重这两个优化策略，提出了一种自适应飞蛾扑火算法（AMFO），有效地避免了飞蛾扑火算法陷入局部最优、收敛精度低且收敛速度慢等问题.通过8个测试函数在不同维度下，对AMFO算法进行仿真验证，可以清楚地看出AMFO算法的寻优能力、求解精度以及收敛速度等方面都有大幅度的改进，能够克服早熟收敛和陷入局部最优等缺陷，对于维数较高、较复杂的非线性函数，有着较好的寻优精度和收敛速度，并且算法的稳定性、鲁棒性也相对较好.