具备生命周期和信息共享机制的萤火虫算法设计

陈国保，杨 波，谢智峰

（1江西科技学院信息工程学院 江西 南昌 330098）

（2江西科技学院人工智能学院 江西 南昌 330098）

0 引言

群智能算法是一种随机优化算法族，包含各类仿生算法。如1995年，Kennedy与Eberhart模拟鸟群捕食行为提出的萤火虫算法（Particle Swarm Optimization,PSO）、2005年，Karaboga模拟蜜蜂采蜜提出的人工蜂群算法（Artificial Bee Colony,ABC）以及2018年，Yang模拟萤火虫发光特性提出的萤火虫算法（Firfly Algorithm, FA）。

群智能算法在解决各领域的优化问题时表现出良好性能，但依然存在不足之处，如对参数敏感、收敛速度慢及易陷入局部最优。针对其存在的问题，学者们提出了各种改进策略来提高群智能算法的性能。

针对粒子群优化算法的不足，吴大飞等[1]通过制定游离粒子位置更新和精英粒子附近衍生爆炸粒子策略，通过二者策略融合，对比实验表明，算法的寻优性能有较大改善；王晓艳等[2]为了克服粒子群优化算法过早停滞、寻优精度低等缺点，将种群划分为进步和停退子种群，进步子种群保持固有的进化方式，停退子种群依据适应值采取不同更新方式，结合动态优化的权重，提高算法全局探索和局部开采的能力；TAO等[3]设计了交叉操作来更新粒子位置，并采用变异机制避免算法陷入局部最优，通过计算得到的最短运输时间，将改进算法与其他智能优化算法进行比较。实验结果表明，该算法能够提高AGV在物料运输中的效率，并验证了相关改进机制的有效性；LIU等[4]为了解决旅行商问题，研究了一种基于迁移学习的粒子群优化算法，该算法利用历史问题的最优信息来引导群体快速找到最优路径，引入具有自适应交叉和聚类引导变异的粒子更新策略，以增强所提出算法的搜索能力；XIA等[5]为粒子的更新添加了一个“亚社会学习”部分的新组件，并基于其适应度为每代粒子分配了三个角色，针对不同角色引入了三种不同学习权重，在进化过程中，引入了两个调整运算符来调整粒子以求得最优解，提出基于适应度的多角色粒子群优化算法；WANG等[6]为解决粒子群算法存在计算量大、精度不高、容易陷入局部最优等问题，提出了动态变化速度衰减因子和惯性权重因子的特殊表达形式，并在算法中在迭代公式中加入一些随机参数，应用于算法迭代公式中，以提高算法的优化速度和优化效果，通过计算机仿真实验证明了算法的有效性和正确性，算法迭代初期获得高效的全局搜索能力和迭代后期获得更好的局部优化性能，实验结果表明算法优化性能表现优异。

针对人工蜂群算法的不足，REN等[7]提出了一种基于柯西OBL的人工蜂群算法，在初始化和邻域搜索阶段，分别使用柯西OBL群与传统初始群竞争，选择优秀个体形成改进的初始群和加入柯西OBL过程，提高种群的质量、多样性、全局探索能力，同时为了加快收敛速度，引入了全局最优解和多维更新策略，仿真结果表明，改进后的算法易于跳出局部优化，具有更高的搜索精度和更快的收敛速度；CAO等[8]提出了基于对立学习蜂群算法，采用解搜索方程对蜜蜂相位进行改进，以此保证迭代过程中种群的多样性，当新生成的解的适应度值小于当前解时，生成相反的解，然后应用贪心选择策略更新解，并且采用自适应权重策略动态调整权重，平衡算法的全局探索和局部探索能力，基准函数实验表明算法具有更好的收敛速度和优化精度；YANG等[9]提出一种改进搜索策略的人工蜂群算法，为了提高初始种群质量，增强整体搜索能力，采用混沌映射和逆向学习的方法对种群进行初始化和基于局部最优和全局最优的位置更新公式来提高迭代优化过程的效率，标准测试函数仿真实验表明算法寻优性能取得较好表现；LIN等[10]引入交叉和变异算子对采用的蜜蜂和旁观蜂相位进行修改，对每个解的多个维度进行修改，既省去了将连续值转换为离散值的过程，又减少了计算资源。此外，一种新颖的贪心选择策略可以选择具有更高准确性和更少特征的特征子集，有助于算法快速收敛；ZHOU等[11]提出的改进算法使用多精英指导，其优点是利用精英个体的有价值信息来指导搜索，同时又不失种群多样性。首先，通过选择一些精英个体来构建精英群体，然后在精英群体的基础上分别将两个改进的解搜索方程引入雇佣蜂阶段和旁观蜂阶段，最后，还利用精英群体开发了一个改进的邻域搜索算子，旨在实现探索能力和开发能力之间的更好权衡，测试结果说明改进算法整体性得到极大改善。

针对萤火虫算法的不足，LI等[12]在FA的更新公式中加入了自适应对数惯性权重，分别引入萤火虫的最小吸引力和一个步长减小因子来动态调整随机步长项，仿真结果表明改进算法对于许多优化问题也具有高性能和最佳效率；ElSHORBAGY等[13]提出了遗传算法和FA两种元启发式算法的混合算法，以克服FA的缺陷，新一代的个体不仅通过遗传算法过程形成，而且通过FA机制形成，以防止陷入局部最优。引入足够的解的多样性，并在探索之间取得平衡趋势，计算结果表明，混合算法具有竞争力。

萤火虫算法参数少、模型简单、易于实现，已广泛应用于优化、分类和工程实践等领域。如在优化领域，主要应用于连续、组合、约束和多目标优化等；在分类领域，主要应用于数据挖掘、机器学习和神经网络等；在工程实践领域，主要应用于工业、农业和商业优化等。

1 标准萤火虫算法

萤火虫算法是一种基于群智能的随机搜索技术，其思想源于萤火虫向比自身更亮的萤火虫移动这一生物学特性。在搜索空间，萤火虫的位置表示优化问题的解，亮度对应优化问题的适应值。萤火虫不断向更亮的萤火虫移动，直至达到预设的算法终止条件，完成寻优任务。算法可以描述为：群体规模为N，N个萤火虫构成种群PN，第i（i=1，2，…，N）个萤火虫在D维空间中的位置可以表示为Xi=（xi1，xi2，…，xiD）。每只萤火虫都具备光亮强度I和吸引度β。其中，光亮强度决定萤火虫学习行为，即学习或被学习；吸引度决定萤火虫的学习距离。通过迭代寻优，当满足一定的终止条件时，输出全局最优萤火虫，完成种群寻优任务。

对于任意两只萤火虫和，它们之间的欧氏距离定义如下：

其中，定义萤火虫的总维度，分别定义萤火虫和当前的位置。

萤火虫的光亮强度和吸引度定义如下：

其中，分别定义萤火虫距离时的光亮强度和吸引度，是光吸收系数。

萤火虫在第代的位置定义如下：

其中，t定义种群当前进化代数，xid（t）和xjd（t）表示萤火虫i和j在当前的位置，参数ε=（rand()-1/2）是随机值，rand()取值空间为[0,1]，a（t）参数是步长因子，取值空间为[0,1]。

算法流程如下所示。

a.初始化萤火虫种群并记录种群的初始位置和适应值；

b.利用式（4）对萤火虫位置进行更新；

c.计算和评价萤火虫亮度（适应值）；

d.累计种群适应值的评价次数；

e.检验是否满足终止条件，若满足，则停止迭代，输出全局最优位置及其对应的适应值，否则转到b。

2 建立生命周期机制和信息共享机制

2.1 生命周期机制

在各类群智能算法中，种群的进化过程类似于人类不同生命周期阶段的学习过程。在幼年生命周期阶段，人类通过模仿外界的行为而学习；在少年生命周期阶段，人类开始有自我意识，在外界的指导和自我意识下而学习；在中年生命周期阶段，人类具备超强的自主意识，不断地自主学习；在老年生命周期阶段，人类积累了丰富的学习经验，向外界传授学习经验。

在萤火虫算法的种群进化过程中，主要为早期和后期2个进化阶段。在早期进化阶段，种群盲目地向外界种群探索式学习；在后期进化阶段，种群以自我为中心，引导外界种群开采式学习。种群的早期阶段对应于人类的幼年生命阶段，后期阶段对应于人类的老年生命阶段。为使种群的进化过程更加地符合人类不同生命阶段的学习过程，在早期和后期进化阶段之间，设置了种群的类少年生命进化阶段和类中年生命进化阶段。

种群的早期和后期阶段保持原有的进化策略——探索式进化和开采式进化。在种群的类少年生命周期阶段，因种群已具备一定的学习能力，可为该阶段制订融合学习策略，即种群在自我学习的过程中，同时向外界种群学习。在种群的类中年生命周期阶段，制订贪婪式突变学习策略，即保留突变后优异的种群。

其中，种群在早期和后期阶段按照式（4）保持固有的进化方式，进行探索式进化和开采式进化；在类少年期，种群已具备一定的学习能力，可结合粒子群算法的进化方式，根据式（5）开展自我学习和社会学习；在后期，整个种群进入即将收敛的状态，此阶段采用贪婪策略，完成搜索全局最优解任务。

其中，γ（xjd（t）-xbestd（t））表示社会学习项目，表示萤火虫xi向最优萤火虫xbest学习，γ是外部学习因子。

2.2 信息共享机制

为增强种群间信息的充分交流，基于上述种群的四个生命进化周期，建立信息共享机制。在种群进化过程中，将前阶段的优势信息作为输入，传递给下阶段，通过各阶段的信息共享，最后筛选某个或者若干个子种群作为全局最优解。基于生命周期机制，种群进化分为四个生命周期，各阶段按照既定的进化方式执行搜索。为充分利用各阶段积累的优势信息，在种群协作进化过程中，通过各阶段间的正负反馈策略，选择性保留各阶段的局部优势信息，最终完成后期进化，获取全局最优信息，即为整个种群的最优解。

3 两种机制设计

首先，以萤火虫算法为群智能研究对象，分析其进化策略的搜索特征，选择合适的进化策略来建立信息反馈机制；其次，针对群体在搜索过程中的不同状态，建立种群生命周期机制；最后，通过数值实验的反馈结果，修正算法，设计具备信息反馈和生命周期机制的萤火虫算法。

4 结论

生命周期机制是对种群进化阶段的划分。在进化过程中，为每个阶段设计独特的搜索策略，保证各阶段具有良好的进化特性，是提高算法性能的关键。种群在进化过程中，积累了大量的优势进化信息。为了充分利用种群间的优势信息，在划分生命周期的基础之上，引入信息共享机制。在各生命周期阶段，种群通过协作和共享，加速种群进化。

针对各类群智能算法易陷入局部最优、普适性差等问题，开展各类群智能算法的进化策略和种群信息传递机制研究，提出具备生命周期和信息共享机制的萤火虫算法。下一步的研究重点工作是探求类少年期和类中年期的搜索策略，以期改进算法性能，拓展算法的应用领域。