一种改进的进化模型和混沌优化的萤火虫算法∗

李肇基 程 科 王万耀 崔庆华

（江苏科技大学计算机学院 镇江 212000）

1 引言

萤火虫算法（Firefly Algorithm，FA）是2008 年由Xin-She Yang［1］提出的一种元启发式算法，其思想来源于萤火虫的发光行为。萤火虫会向亮度更强且更为靠近自己的萤火虫移动，通过这种方式进行种群进化，进而实现寻优。目前，萤火虫算法已成功应用到数值优化、工程技术、资源管理等领域［2～6］，并且表现出良好的性能和适应性。与大多数随机算法相同，传统萤火虫算法同样存在后期收敛速度慢、易陷入局部最优等缺点。

针对传统算法的缺点，众多学者对其进行了研究与改进。Gandomi［7］等用不同的混沌映射模型对光强吸收系数与吸引度系数进行混沌映射，实验证明正弦映射与高斯映射能有效提高萤火虫算法的全局优化能力。但是，仅对光强吸收系数与吸引度因子采用混沌优化，没有充分体现混沌思想对萤火虫算法的种群与进化过程的优化作用；冯艳红［8］等将立方映射所产生的混沌序列引入到萤火虫算法，提出一种基于混沌理论的动态种群萤火虫算法，减少了萤火虫的无效运动提高了算法精度。但是采用随机方式替换掉种群中的个体，容易破坏原种群结构，使优化结果变差；符强［9］等分析了萤火虫算法的进化计算机制，提出一种基于新型进化计算模式的改进型萤火虫优化算法（IEFA），并利用高斯变异改善个体的多样性，有效改善萤火虫算法过早进化停滞的问题，但是对整个种群进行变异扰动，可能会使种群多样性降低，而且增加了算法的计算时间；郁书好［10］将自适应步长运用到萤火虫算法的位置更新公式中，提出自适应步长萤火虫优化算法，有效地提高了算法的综合性能。但是单纯地改变步长机制，并不能有效解决初始种群分布不均和进化过程中的域约束等问题。

基于标准萤火虫算法存在的缺陷，并受近年来一些改进思想的启发，提出一种改进的进化模型和混沌优化的萤火虫算法（Firefly Algorithm Based on Improved Evolutionary Model and Chaos Optimization，FAEC），该算法通过混沌映射对种群进行初始化，在迭代过程中采用惯性权重和动态步长平衡算法的局部寻优与全局搜索性能，并通过种群最优个体引导其他个体进行移动，实现萤火虫之间的信息共享，对超出搜索区域的萤火虫，引入对称边界变异操作，提高了种群多样性。最后标准测试函数的结果表明，与标准萤火虫算法相比所提算法具有更高的寻优精度和更快的收敛速度，同时能够避免因迭代过早停滞而陷入局部最优的问题。

2 传统萤火虫算法

2.1 算法的仿生原理与数学描述

传统萤火虫算法是一种仿生智能优化算法，具体的仿生原理如下［11］。

1）萤火虫总是不分雄雌地向着比较亮的萤火虫移动，最亮的萤火虫随机移动。

2）萤火虫之间的相对吸引力决定了萤火虫的移动距离，吸引力与萤火虫个体的亮度成正比关系，与萤火虫之间的距离成反比关系。

3）对于函数优化问题，可以将目标函数的值作为萤火虫亮度的评判标准，将萤火虫的位置作为目标函数的解。萤火虫的亮度越高，表明目标函数值越优，通过种群进化，最终亮度最高的萤火虫的位置，便是待优化的目标函数趋近理论最优值的解。

在FA 算法中，亮度和吸引度是萤火虫个体的两个重要特征。其中，亮度的高低代表了萤火虫所处位置的优劣并决定了萤火虫个体的移动方向，吸引度则直接影响了萤火虫个体的移动距离，通过亮度和吸引度的不断更新和迭代来寻找目标函数的最优解。在FA 算法中萤火虫i 到萤火虫j 的距离rij，通常用欧氏距离计算，即:

其中d表示搜索空间的维度。

由定义萤火虫i对萤火虫j的吸引力和萤火虫i对萤火虫j的相对亮度成正比，可得萤火虫i对萤火虫j的吸引力为

式中，β0为最大吸引力，表示光源处（r=0）萤火虫的吸引力，通常 β0=1。γ 为光强吸收系数，它的取值对FA 算法的收敛速度和优化效果有很大的影响。

萤火虫i相对萤火虫j的荧光亮度公式为

式中，Ii是萤火虫i 的绝对亮度，对应萤火虫i 所处位置的目标函数值；γ 为光强吸收系数，描述了荧光随着距离增加和传播介质的吸收而逐渐减弱的光学特性，可设为常量。

萤火虫j被萤火虫i吸引，j向i移动来更新原有的位置，j位置的更新公式为

式中，t为算法的迭代次数，xj(t+1)代表萤火虫j在第t+1次迭代的位置；βij是萤火虫i对萤火虫j的吸引力；α 为常数，取 α ∈［0，1］；rand 是在［0，1］上服从均匀分布的随机因子。

算法寻优过程为:采用随机方式在搜索空间生成萤火虫种群，萤火虫个体的亮度由其所在的空间位置决定，通过比较式（3）可得，萤火虫会向比自己亮度更高的个体移动，通过计算式（2）所得的吸引力是影响移动距离的主要因素，移动后的新位置根据式（4）来计算，在位置更新公式中增加了随机扰动项，避免种群过早陷入局部最优，经过若干次迭代寻优后，种群个体将会运动到亮度最高的萤火虫的位置，算法得到全局最优解。

2.2 算法的局限性分析

在实际问题中很多待优化函数通常具有多峰、高维、地形复杂等，表现为大量的局部极值分布在全局最优值周围，传统萤火虫算法在优化这类问题时容易早熟收敛，寻优精度难以提高。造成这种现象的原因是由于传统萤火虫算法通过萤火虫个体之间的相互吸引来实现寻优，而个体不具备变异特性，很容易陷入局部极值。尤其在进化前期，种群中的超级个体通常会吸引其他个体快速聚集到其周围，造成种群多样性降低，而且，随着个体逐渐接近全局最优值，种群的收敛速度会明显下降甚至出现进化停滞现象，丧失了进一步进化的能力，往往这种现象发生时，算法尚未收敛到全局最优值。因此，保证种群在整个进化过程中具有持续优化能力，提高种群多样性，是提高传统萤火虫算法性能的重要途径。

3 一种改进的进化模型和混沌优化的萤火虫算法

3.1 基于混沌优化策略的种群初始化

在非线性系统中，存在一种特有的非周期运动现象被称为混沌现象，其特点是行为复杂，与随机现象类似，但是存在内在的规律性。利用混沌运动的随机性、遍历性和初值敏感性来提高随机优化算法的效率就是混沌优化［12］。基本思想为利用混沌变量的遍历性和随机性，通过混沌映射规则将待优化变量映射到混沌变量的取值区间内，将获得的混沌序列，通过线性变换转化到目标函数的搜索空间。

在多种混沌序列的模型中，逻辑自映射函数产生的混沌序列遍历性要优于常用的Logistics 映射［13］。采用逻辑自映射函数生成混沌序列，如式（5）所示:

其中，为避免混沌序列出现全为1 或0.5 的情况，所以初始值不能取0 和0.5，d 表示D 维搜索空间的第d维。

初始化混沌种群的过程描述如下:

步骤1 对于D 维空间的M 个萤火虫个体，根据逻辑自映射函数的性质，首先初始化混沌变量，在(-1,1)区间随机产生初始变量。

步骤2 按照式（5）迭代，将逻辑自映射生成的MaxGeneration *D-1 个混沌变量，与初始混沌变量一起对应全部MaxGeneration*D 个萤火虫个体。

步骤3 将产生的混沌变量序列按式（6）变换到目标函数的搜索空间，生成萤火虫初始种群的M个个体，公式如下:

式中，Lb 和Ub 分别表示搜索空间第d维的下限和上限，yn,d是根据式（6）产生的第i个萤火虫对应的第d 维混沌变量，xi,d为第i 个萤火虫在搜索空间中第d维的坐标值。

传统萤火虫算法的随机种群初始化效果如图1 所示，基于混沌优化策略的种群初始化效果如图2所示。

图1 随机种群初始化

图2 基于混沌优化策略的种群初始化

从图1 和图2 的初始化种群分布对比可以看出，采用混沌优化策略的初始种群，种群分布的均匀性要明显优于采用随机策略的初始化种群。

3.2 基于惯性权重的进化计算模型

由式（2）可知，随着种群的持续迭代，个体之间距离不断减小，个体间的相对吸引力逐渐增大，降低了算法的局部搜索能力。式（4）中加入了带有特定系数的随机项，加大了搜索范围，避免算法过早陷入局部最优，但可能需要迭代多次才能达到精度要求，使得算法在迭代次数受限的情况下，无法满足精度要求。为了提高算法的局部搜索和全局搜索能力，在式（4）中引入惯性权重，并增加种群中最优个体对其他个体的牵引作用［9］。改进的位置更新公式如式（7）所示:式中，第一项ω(t)×xj(t)表示萤火虫个体的前一次迭代位置对当前位置的影响，第四项ω(t)×rand()×(xbest(t)-xj(t))表示当前迭代的种群最优个体对种群中个体提供的牵引作用，用来控制当前种群最优个体对其他个体的影响程度，以及当前个体对前代个体的继承情况。惯性权重分为固定权重和时变权重，在粒子群算法研究中，自适应权重［14］是常用的时变权重之一。为充分利用目标函数信息，加强搜索方向的指导性，进一步提高个体移动速度［15］，提出一种新型的自适应惯性权重，计算公式如式（8）所示:

式中，f(xbest(t)) 为第t 次迭代的全局最优值，fi(t-1)和 fi(t-2)分别为 i 萤火虫第 t-1 和 t-2 次迭代的值，M(f)=f(xi(t))为第t 次迭代的种群目标函数值的平均值。

萤火虫的移动距离受到惯性权重的影响，分析式（8）可得，在每一次迭代中，惯性权重根据上一次迭代产生的全体目标函数值与i萤火虫前两次迭代的目标函数值计算所得，从而减少惯性权重变化的盲目性。由于在惯性权重的求解过程中充分利用了目标函数的信息，使得萤火虫算法的搜索方向具有指导性，萤火虫个体向高质量区域快速移动。在算法迭代后期，萤火虫个体已经接近最优解，且相邻两次迭代差值减小，此时惯性权重变小，萤火虫的移动距离随之减小，加快了算法的收敛速度，提高了搜索能力，从而改善算法的寻优性能。

3.3 基于高斯分布的种群变异操作

萤火虫种群陷入局部最优的特征是进化出现停滞，即连续多次迭代并未使种群最优值发生变化。通过实验总结初步设定，当经过连续6 次迭代，种群的全局最优值未发生变化，则判定其进化停滞，已经陷入局部最优区域。为了帮助萤火虫种群脱离局部最优值束缚，本文采用高斯分布对萤火虫种群进行变异操作。高斯概率分布被广泛应于工程应用中，对工程优化与设计具有良好的促进作用。高斯分布的概率密度函数如式（9）所示。

其中，σ 为高斯分布的方差，μ 为期望。

将种群中的全部萤火虫个体按目标函数值的大小进行排序，利用最优的10%×n 个萤火虫将排名最后的10%×n 个萤火虫群体进行状态替换更新，同时对更新萤火虫群体的状态进行高斯变异处理，变异公式如式（10）所示。

其中，N(0,1)为随机向量，并且为服从期望为0、方差为1的高斯分布。

当经过6 次迭代后，全局最优值没有发生改变时，未执行种群变异操作的种群分布如图3 所示，执行基于高斯分布的种群变异操作的种群分布如图4所示。

图3 未执行种群变异操作的种群分布

图4 进行种群变异操作的种群分布

从图3 和图4 圈出的区域对比可以看出，图3中被圈出的点分布较密集，已经陷入局部最优区域，种群未执行高斯种群变异操作，陷入局部最优区域的个体无法跳出局部最优值的束缚，图4 为已经执行高斯种群变异操作，种群个体能够跳出局部极值区域。

3.4 动态步长与域约束机制

步长在萤火虫优化算法中扮演着重要的角色，设置合适的步长值会直接影响到算法的全局搜索和局部搜索能力。标准FA 算法采用固定的步长值，在一定程度上无法体现出个体的差异性，递减步长能够动态调节个体的移动幅度，使个体在迭代前期以较大的步长进行全局搜索，而后期则以较小步长进行局部寻优。本文采用随着迭代次数非线性递减的方式计算步长。如式（11）所示:

式中，Δαt为步长的动态衰减系数，并且Δαt=1-(10-4/0.9)(1/t)，t表示迭代次数。随着迭代次数t的增大，Δαt逐渐增大，（1- Δαt）减小，使得t+1 代的步长逐渐减小。

采用固定步长和非线性递减步长的曲线走势如图5和图6所示。

图5 固定步长曲线

图6 非线性递减步长曲线

在萤火虫算法的迭代过程中，为了保证种群个体能够在搜索空间中进行有效搜索，当萤火虫的位置超出目标函数的可行域时，一般是将萤火虫的位置替换为超出的边界值，此时域约束公式如式（12）所示:

式中，xmin为搜索空间下限，xmax为搜索空间上限。这种边界控制策略容易使算法陷入局部最优，而且超出边界的点全部约束在边界处，有可能会使算法在边界处过早收敛，降低算法的寻优率。因此，引入一种对称边界变异操作［16］，此时的域约束公式如式（13）所示:

对称边界变异操作能够使种群中萤火虫的位置始终保持在可行域内，避免了萤火虫算法在边界处陷入局部最优，同时在一定程度上提高了种群的多样性，动态步长与边界变异操作有效地提高了萤火虫算法的收敛速度和寻优率。

3.5 算法流程

基于标准萤火虫算法，将混沌优化策略、惯性权重、种群最优个体引导、动态步长和域约束机制等引入萤火虫算法，提出一种改进的进化模型和混沌优化的萤火虫算法，其算法的执行流程描述如下:

步骤1:初始化参数。设置萤火虫数目m，问题维度d，光强吸收系数γ，步长因子初始值α，最大吸引度因子 β0，最大迭代次数MaxGeneration，搜索精度ε。

步骤2:初始化种群。采用式（5）生成初始混沌序列，然后根据式（6）将混沌序列映射到萤火虫算法的解空间，生成萤火虫种群的初始位置xi(i=1,2,…,m)。

步骤3:根据种群中个体的位置计算各萤火虫的目标函数值，作为萤火虫个体各自的最大荧光亮度I0，对种群中的萤火虫个体按照目标函数值排序并记录最优值 fbest，同时记录最优个体位置。

步骤4:根据式（3）计算种群中萤火虫个体之间的距离rij，再由式（1）计算种群中萤火种个体的相对荧光亮度Iij(rij)，并比较邻域内萤火虫亮度的大小，确定萤火虫个体的移动方向。

步骤5:根据式（2）计算萤火虫个体的吸引度βij(rij)，再由式（8）计算当前第t 次迭代的惯性权重ω(t)，最后根据式（7）更新萤火虫的空间位置。

步骤6:由式（11）对迭代步长进行更新，并根据式（13）对种群中的萤火虫个体进行域约束操作。

步骤7:重新计算移动后的萤火虫种群的目标函数值，并记录种群的最优目标函数值 fbest和最优个体位置xbest(t)。当连续6次迭代一直未更新，则将种群中最差的10%×m 个萤火虫的状态替换为最优的10%×m 个萤火虫的状态，并通过式（10）对过渡种群进行高斯变异操作。

步骤8:当满足搜索精度或者达到最大迭代次数，转步骤9，否则转步骤3。

步骤9:算法迭代完成，输出结果。

4 实验仿真与分析

在六个标准测试函数上分析和验证FAEC 算法的收敛速度与寻优能力，对文献［9］中的基于改进型进化机制的IEFA 算法和传统FA 算法进行对比测试。仿真实验环境基于Windows 10 操作系统，2.5GH 主频的 Intel 处理器，4G 内存，利用 MatlabR2015a进行编程测试。

1）Sphere Model 函数

2）Rastrigin函数

3）Ackley函数

4）Griewank函数

5）Rosenbrock函数

6）Zakharov函数

4.1 寻优精度分析

对FAEC、IEFA 和FA 算法的公共参数设置如下:初始萤火虫个体数目为20，迭代次数为500，最大吸引度因子β0=1，初始步长因子α=0.2，光强吸收因子γ =1。其中，对于IEFA，惯性权重从1.1 到0.4线性递减，步长衰减系数△α=0.97。

函数 f1和 f2的维数为2，函数 f3的维数为15，函数 f4、f5和 f6的维数为30。以上六个标准测试函数经过30次试验，平均测试结果如表1所示。

表 1 所列为 FA 算法、IEFA 算法和 FAEC 算法对6 个标准测试函数独立运行30 次的统计结果。可以看出，对于低维测试函数 f1和 f2，3 种算法的寻优精度均很高，而且IEFA 算法和FAEC 算法的最优值、最差值、平均值和标准差均明显优于标准FA 算法。对于函数 f3、f4和 f6，由于均为高维而且含有大量的局部极值，FAEC 算法的最优值与最差值要比标准FA 算法高出3 个数量级以上，而且综合性能均优于IEFA 算法，f5为单峰高维，虽然三个函数的测试结果均不理想，但FAEC 在最优值、平均值和标准差上要优于标准FA 和IEFA。对于6 个标准测试函数，FAEC 算法的标准差均低于FA 和IEFA，显示了其较稳定的寻优过程。因此，与标准FA 和IEFA 算法相比，FAEC 算法具有较高的寻优精度和较稳定的迭代过程。

表1 FA和IEFA，FAEC算法对6个测试函数的计算结果比较

4.2 寻优速度分析

针对以上6 个标准测试函数进行寻优速度分析，算法的参数设置与4.1节一致。

图7～12 为三种算法在测试函数 f1至 f6上的寻优曲线。

图7 f1 函数寻优过程（D=2）

图8 f2 函数寻优过程（D=2）

图9 f3 函数寻优过程（D=15）

图10 f4 函数寻优过程（D=30）

图11 f5 函数寻优过程（D=30）

图12 f6 函数寻优过程（D=30）

图 7～12 显示了 FAEC 算法、IEFA 算法和 FA 算法的寻优过程。从图7～12 可以看出，与传统FA 算法和IEFA算法相比，FAEC算法能够在较少的迭代次数下搜索到全局最优解，具有更快的迭代速度和更高的寻优精度。其中，从图7、图8、图11、图12中可以直观地看出，FAEC 算法在50 次迭代内就能收敛并趋于稳定，在图8中，虽然FAEC算法在迭代初期的迭代曲线劣于IEFA，但最终仍以较少的迭代次数趋于稳定，从图9、图10、图11 可以看出，与使用随机种群初始化的IEFA算法相比，FAEC算法采用混沌种群初始化方法，并利用非线性递减步长与对称边界变异操作，有助于算法跳出局部最优，平衡和局部寻优与全局搜索，并在一定程度上增加了种群的多样性，表现出较快的收敛速度和寻优精度。

5 结语

针对FA 算法易陷入局部极值、后期收敛速度慢、寻优精度较低等问题，引入混沌优化策略、进化模型和惯性权重等概念，提出一种改进的进化模型和混沌优化的萤火虫算法。引入改进的逻辑自映射混沌模型提高种群多样性；加强种群中最优萤火虫个体对其他个体的引导作用以及个体对前代位置的继承情况，采用惯性权重对两者进行平衡调整，克服早熟收敛问题，增强全局搜索与局部搜索能力，提高收敛速度与寻优精度；在迭代过程中，采用非线性递减步长与对称边界变异，提高了收敛速度，增加了种群多样性。实验结果验证了算法的有效性和优越性。今后相关工作主要侧重于FAEC算法的理论推导与实际问题应用研究。