基于连续空间的萤火虫算法改进

刘晨旻，王亚刚

(上海理工大学 光电信息与计算机工程学院,上海 200093)

启发式算法是当代全局优化算法、智能计算以及软计算的重要组成部分。这类算法的灵感大多来源于科学家们对自然界多种机构之间交互方式的观察，其中又以基于种群的启发式搜索算法[1]为主。这些算法在使用测试函数进行全局优化问题试验时，表现出不同的特性[2]，这是由其基本原理决定的。粒子群算法是基于鸟类和鱼类的群居行为提出的[3]。蚁群算法于1992年提出，源于蚂蚁觅食过程中的搜索行为[4]。布谷鸟算法模拟部分布谷鸟的寄生育雏行为[5]，常用于在性能与全局寻优方面与其它启发式算法进行比较[6]。在这类算法中，萤火虫算法(Firefly Algorithm，FA)在处理多模态全局优化问题上较为有效。

萤火虫算法是一种源于热带萤火虫发光行为的启发式算法[7]。该算法的原理为萤火虫寻找伙伴时的趋光性。萤火虫在空间中会向附近最亮的萤火虫移动，相互吸引，以此对其位置进行更新[8]。目前国内外都对萤火虫算法进行了一定的研究。文献[9]提出了基于萤火虫算法的新颖图像检索方法，用以提高检索反馈样本的性能。文献[10]引入多种群技术及权重系数因子来细分萤火虫种群。这些研究使得萤火虫算法在图像处理、控制优化、生产管理、电力系统、神经网络训练等领域得到了应用。

但是，萤火虫算法存在着收敛精度低以及容易陷入局部最优等缺点。针对上述缺陷，研究人员从多个角度对萤火虫算法进行了改进和应用，包括参数、移动方式、新的吸引策略、算法混合以及算法的学科应用。

为了增加算法的全局搜索能力，文献[11]通过将交叉熵(Cross Entropy，CE)嵌入萤火虫算法，提出了一种新型的混合元启发式算法。文献[9]在萤火虫算法中引入相对亮度差异来动态调整其步长，并将改进的萤火虫算法与用户反馈结果相结合，优化特征选择并对支持向量机(Support Vector Machine，SVM)进行参数寻优，以提高图像检索精度。文献[12]先采用新的吸引度模型来确定被吸引的萤火虫数量，再设计新的搜索运算符进行优化，用以增强其全局寻优能力。文献[13]采用部分吸引力模型和快速吸引力计算策略，用以保留群体多样性并充分利用个人信息，确保了个人之间的信息共享，提高了收敛精度。文献[14]融合了粒子群(Particle Swarm Optimization，PSO)算法与萤火虫算法，提出了3种新颖的算子，将混合算法的种群分为两个子种群，分别选择FA和PSO作为其基本算法来进行优化过程。该算法通过两个子群体交换信息，以便充分利用PSO和FA的优点，但整个算法的停滞程度超过了预定义的阈值。

文献[15]将萤火虫算法引入人工智能领域，提出一种具有高斯干扰和局部搜索能力的FA算法。然后，使用随机吸引模型更新群体，将粒子的当前位置与粒子的历史最佳位置进行比较。该方法增强了种群多样性，且提高了优化精度。文献[16]将潮汐力公式用于修改萤火虫算法，在新的算法中不再使用吸光系数，提高了算法性能和效率。文献[17]对萤火虫种群进行分组，每个萤火虫都会根据与之相距最近的组的亮度进行寻优，而每个组之间又可以进行信息交换。各组别中，适应度最高的萤火虫之间相互吸引，从而寻找全局最优。

上述改进方法表明，传统萤火虫算法存在着缺陷。在迭代过程中，萤火虫算法在全局寻优方面的表现不佳。现有研究多致力于将萤火虫算法与其它鲁棒性优异的算法相结合，构建新的混合算法[18]，并以此嵌入到FA的薄弱环节中，提高FA的性能。混合算法着重于强调多组的概念[19]，以FA以及PSO为基础算法对种群进行优化。混合算法也可通过使用新颖的吸引度计算式或改变其移动策略来降低算法复杂度[20]。除此以外，使用精英策略加速算法收敛也是一种研究方向，但是该改进对传统算法结构简单、可操作性强的优点会造成负面影响，且对算法性能的改善也不够完备[21]。

终上所述，本文将从理论上对传统算法的缺陷进行改进，采用多种经典测试函数验证改进后的算法，并将新方法与传统算法进行对比。

1 萤火虫算法原理

在萤火虫算法中，每个萤火虫都对应着一个解空间中的可行解。萤火虫在此位置的亮度表示萤火虫在该位置的适应度，萤火虫亮度越高则表明越接近最优解[22]。萤火虫之间也会互相吸引，越亮的萤火虫吸引力越大。解空间存在传播介质吸收光，所以距离越近的萤火虫吸引力越大[23]。在实现算法前需要完成几个假设[24]：

假设1萤火虫雌雄同体，所以一只萤火虫会被其他萤火虫吸引这种属性与性别无关[25]；

假设2吸引力与亮度成正比，并且随着距离的增加而减小。因此，对于任何两只闪烁的萤火虫，较暗的那只会向较亮的那只移动。如果没有比那只萤火虫更亮的萤火虫，则这只萤火虫将随机移动；

假设3萤火虫的亮度是由设计的目标函数决定的。

萤火虫之间的相对吸引度计算式为

β(r)=β0e-γr2

(1)

式中，β0为萤火虫之间的初始吸引度；γ为解空间介质的吸光系数；r为萤火虫之间的距离。萤火虫i会被另外一个更亮的个体所吸引，其移动方式由式(2)决定

(2)

种群中适应度最高(亮度最大)的个体移动方式由式(3)决定。其中，αt会随萤火虫代数增加而减小[27]。

(3)

传统萤火虫算法的基本步骤如下：

步骤1初始化种群；

步骤2计算萤火虫个体适应度值，适应度越高的萤火虫亮度越高；

步骤3每个萤火虫向比自己亮度更高的萤火虫飞行；

步骤4最亮的萤火虫更新自身位置；

步骤5到达最大迭代次数时输出结果，否则返回步骤2。

传统萤火虫算法存在着许多问题：(1)算法过早收敛，导致陷入局部最优；(2)控制参数选取不合适，导致无法收敛；(3)难以解决多目标优化或含有多个约束条件的问题[28]。

2 算法优化

当迭代需要计算萤火虫种群吸引度时，不再仅仅对离散的个体计算其吸引度或是吸引度分量。实际应用中，萤火虫个体之间产生吸引时，其对周围空间也产生一定的影响，那么萤火虫的移动方式就不仅受到当前适应度最高个体的影响。

萤火虫在寻优过程中不应仅以限定步长向更优解跳动。为了保证其快速性与收敛性，步长应当随着迭代次数的增加而下降，渐渐形变为微调的方式前进。

由于最亮点仅以随机方式运动，为了避免在迭代后期由于仅跟随有限个较优个体而陷入局部最优，个体在选取前进方向时应当将多个优于自身的解纳入考虑范畴之内。

2.1 问题维度分解

本文将适应度函数中的变量个数作为萤火虫算法解空间的维度。以适应度函数为f(x1,x2)=(x1-a)2+(x2-b)2的问题为例，建立一个以X和Y为轴的二维参数空间。将N×N个萤火虫个体均匀分布在二维空间内，此时萤火虫种群的初始坐标(Xi0,Yi0)为

(4)

式中，XL为X轴定义域的左边界；YL为Y轴定义域的左边界；Int(·)为取整函数；lX和lY为X和Y轴经过N等分后的单个区间长度。

2.2 吸引度计算

根据萤火虫当前所处位置计算此时解空间内的吸引度分布情况。定义萤火虫个体所处位(X,Y)的吸引度为

βi(Xs,Ys)=β0e-γ[(Xs-Xi)2+(Ys-Yi)2]

(5)

式中，β0为萤火虫之间的初始吸引度；γ为解空间介质的吸光系数。

根据当前个体所处区域的位置，计算空间内所有萤火虫对应的适应度，并按照适应度的大小对萤火虫群重新排序编号，从1至N2。此时适应度比个体i高的所有萤火虫对i在X轴区域内的总吸引度可以用式(6)来表示。

(6)

同理，适应度高于个体i的所有萤火虫对i在Y轴区域内的总吸引度可以表示为

(7)

式中，XL和XR为X轴定义域的左右边界；YL和YR为Y轴定义域的左右边界；lX、lY分别为X、Y轴N等分后的单区间长度。使用所有适应度高于个体i的点，计算它们对个体的总吸引度的方式，利用其替代仅使用适应度最高点计算吸引度的方式。这样操作可以降低寻优时的随机性，避免陷入局部最优。

2.3 个体移动方法

萤火虫个体i的移动受到其它所有比它亮的萤火虫的影响，个体i在X和Y轴上的运动为

(8)

αt=α0δt,0<δ<1

(9)

式中，α0是初始随机因子；δ为冷却因子；t为种群迭代次数。对于大多是情况下，δ取0.95～0.97。

基本流程如图1所示。

图1 算法流程图

3 实例研究及仿真结果

为了演示优化后算法的工作情况，并将其与原始算法做比较，本文在MATLAB中进行仿真，并使用多种测试函数验证优化后的算法。仿真实验中适应度函数为f(x1,x2)=(x1-a)2+(x2-b)2，a=-3，b=3。其它相关参数设置如下：萤火虫数量(种群数)n为100，最大迭代次数为60，初始吸引度β0=1，介质吸光系数γ=1，冷却因子δ=0.97，扰动方式采用[0,1]之间的正态分布。实验中优化算法的仿真如图2所示，其与传统算法的结果对比如表1所示。

(a) (b)

表1 萤火虫算法的参数及辨识结果

使用传统萤火虫算法以及本文算法寻优后的结果分布区间如表1所示。实验结果表明本文算法的结果分布区间均优于传统算法，证明了本文优化算法的有效性。仿真结果得到传统萤火虫算法的平均值为(-3.000 3,2.995 6)，而优化后的算法平均值为(-2.999 9,2.999 8)，算法精确度得到了提高。

为了对新算法的全局寻优能力进行演示并与传统萤火虫算法比较，本文选取Michalewicz函数为测试函数。Michalewicz函数是一个多模态的函数，具体为

(10)

式中，d为问题的维度，本文取值为2；xi为输入域；参数m定义了函数谷和脊的陡度，其值越大，搜索的难度就越大，本文采用其推荐值m=10。考虑到某些实际情况下，函数的最优值与其周围值差异不明显，因此需要在难以收敛到最优值的情况下求解。本文分别使用两种算法搜索函数的最小值以及最大值，以判断其是否易陷入局部最优。图3和图4分别为传统算法和优化后萤火虫算法的仿真结果。

(a) (b)

仿真中的相关参数设置如下：萤火虫数量(种群数)n为36，最大迭代次数为60，初始吸引度β0=1，介质吸光系数β=1，冷却因子δ=0.97。对比图3(a)以及图4(a)可知，在寻找Michalewicz函数最小值时，传统算法与本文算法都能找到全局最优解，无个体陷入局部最优。对比图3(b)以及图4(b)发现，在寻找函数最大值时，传统萤火虫算法有部分个体陷入局部最优，未能找到全局最优解，而本文算法没有陷入局部最优，成功找到最优解。该结果说明，相较于传统方法，本文算法寻找全局最优的能力得到了较大改善。

上述两项仿真说明了本文算法在全局寻优以及精确度上的改善。本文还使用了其他测试函数进行仿真，用于对比传统萤火虫算法与本文算法的性能。仿真过程中，每种测试函数均进行了多次运行。本文取运行次数的平均值进行统计分析。

表2中，1.781 4±0.015 0表示函数输出的平均值为1.781 4，标准值为0.015 0。从表中可以看出，优化萤火虫算法在全局寻优时的总体性能优于传统算法，且传统算法在仿真时易陷于局部最优。

表2 实验数据对比

近年来对萤火虫算法的优化方向大致可以分为以下几种方式：(1)对参数的改善；(2)对个体移动方式的改善；(3)优化吸引策略；(4)算法混合。为了进一步验证本文算法的性能，本文研究了近年来不同改进方法，包括一种基于混合种群的全局优化算法、基于概率吸引模型的改进FA、基于光强差的修正FA以及一种带有混沌闪烁机制的双种群协同进化的改进算法[29-33]，并在同一测试函数下加以实现。各改进算法结果的平均值如表2所示。结果表明，对比其它改进算法，本文算法在全局寻优的能力上表现出一定的优越性。

4 结束语

为了提高萤火虫算法在寻优过程中的性能，本文在计算萤火虫吸引度时，将离散问题连续化，以所有适应度更高的萤火虫对当前个体所在区间的总吸引度来代替单个萤火虫对当前个体的吸引度。萤火虫种群的运动总体效果是在连续的解空间内逐渐收敛至最优解附近，个体的吸引度函数对所有解空间的区域均存在作用，且作用强度随距离增加而减小。通过这种方法实现的算法改进不仅提高了种群的全局寻优能力，还降低了传统算法运行过程中，因参数设置或者步长过长等问题导致出现的提前收敛或错过最优解的情况。然而，相较于传统算法，本文算法运行过程消耗时间较长，下一步将针对该问题进行重点研究。