启发信息引导的改进萤火虫算法

崔家瑞　李擎　杨柳祎　王恒　张博钰

摘要：萤火虫算法（FA）是一种群体智能优化算法，它基于萤火虫的闪烁和吸引特征模拟萤火虫的社会行为。为解决萤火虫算法后期收敛速度慢，易陷入局部最优的不足，对算法进行了改进。提出了两种启发信息引导算法收敛：第一种借鉴粒子群算法中“全局最优”的思想，将当前最优点的位置作为启发信息，形成了基于当前全局最优的萤火虫算法（FAGO）;第二种将贝叶斯估计计算出的最优移动方向作为启发信息，形成了基于贝叶斯估计的萤火虫算法（FABE）。最后，将本文算法在多个常见函数上进行了测试，并与经典萤火虫算法、近年其他文献改进萤火虫算法进行了对比研究，结果表明本文所提算法能够加快收敛速度，提高收敛精度。

关键词：萤火虫算法;启发信息;全局最优;贝叶斯估计;数值优化

DOI：10.15938/j.jhust.2019.01.015

中图分类号： TP18

文献标志码： A

文章编号： 1007-2683（2019）01-0092-07

Improved Firefly Algorithm Based on Heuristic Information

CUI Jia rui，LI Qing，YANG Liu yi，WANG Heng，ZHANG Bo yu

（School of Automation and Electrical Engineering， University of Science and Technology Beijing， Beijing 100083， China）

Abstract：Firefly Algorithm （FA） is an optimization algorithm based on swarm intelligence which mimics the social behavior of fireflies based on the flashing and attraction characteristics of fireflies With the aim to address the disadvantages of the firefly algorithm of slow convergence speed and ease of falling into the local optimum in the later period of the evolution process， the firefly algorithm is improved herein Two kinds of heuristic information are proposed into the algorithm to guide the convergence of the algorithm The first one takes the current global best as the heuristic information referencing the “global optimal” idea in particle swarm optimization， therefore， an algorithm called FAGO （Firefly Algorithm based on Global Optimization） is formed The second one is called FABE （Firefly Algorithm based on Bayesian Estimation） using the optimal moving direction calculated by Bayesian estimation as heuristic information The improved algorithms in this study are applied to numerical simulations of several classical test functions and compared with traditional FA and some other′s research are carried out The simulation results show that the proposed algorithms can well accelerate the convergence speed and improve the convergence accuracy

Keywords：firefly algorithm; heuristic information; global optimal; Bayesian estimation; numerical optimization

0引言

螢火虫算法（Firefly Algorithm，FA）是一种典型的启发式优化算法，由Yang XS于2008年提出[1]，在图像处理[2]、光谱数据分类[3]、流水线调度[4]等方面得到广泛应用。经典萤火虫算法参数少、原理清晰且易于实现，同时也存在后期收敛速度慢、收敛精度不高、易陷入局部最优的缺陷，为弥补这种缺陷，大量学者对其进行了改进，并取得了一些研究成果。具有代表性的改进方法包括基于参数动态调整的改进算法和基于融合思想的改进算法。文[5]介绍了典型的动态调整参数方法，将萤火虫算法和Levy飞行策略结合，利用Levy飞行重尾分布的特性，对萤火虫算法的随机移动步长进行了改进，提出了Levy飞行萤火虫算法（Levy flight Firefly Algorithm，LFA）;文[6]提出了将萤火虫算法与差分进化方法融合的思路，将较差的萤火虫个体组成新种群，利用差分进化方法进行迭代，较优个体保持原算法不变，提高了算法摆脱局部最优的能力，称为混合进化萤火虫算法（Hybrid Evolutionary Firefly Algorithm，HEFA）。

本文借鉴粒子群算法，引入全局最优位置作为启发信息;结合贝叶斯公式基于先验概率能最大化后验概率的优点，引入计算出的最优移动方向作为启发信息。实验结果表明，两种启发信息各有优势和适用环境，但都能在一定程度上解决后期易陷入局部最优的问题。与现有算法相比，本文所提出的改进方法在很大程度上提高了算法最优解和整体平均解的收敛精度，减少了达到最优解所需的迭代次数。

1经典萤火虫算法

萤火虫算法模拟自然界中萤火虫个体发光的生物学特性发展而来，其核心思想是：分布在解空间中的萤火虫基于适应度的大小发出不同亮度的光，亮度高的萤火虫会吸引亮度低的萤火虫向其靠拢[7]，若将萤火虫个体的位置作为其对应的解，亮度作为该解的适应度，亮度高的个体持续吸引亮度低的个体从而进行迭代，在迭代的最后，亮度最高的个体所处的位置即为得到的最优可行解（以下简称最优解）。

经典萤火虫算法步骤如下：

步骤1：初始化，定义算法参数，包括迭代次数、萤火虫群体规模等;

步骤2：在解空间的不同位置随机生成萤火虫，给出初始亮度;

步骤3：对一只萤火虫，观察其他萤火虫到自身的相对亮度，向吸引度大于自身亮度的萤火虫个体进行移动，完成一只萤火虫的一次迭代过程;

萤火虫到其自身距离r处的相对亮度I r由下式表示：

I r=I 0 e  -γr 2 （1）

上式中，I 0表示萤火虫在自身位置处的亮度（即适应度），与待优化问题有关，γ为光吸收因子，表征了传播媒介对于光强的吸收能力。

k+1时刻，萤火虫i向着萤火虫j移动，其位置更新公式为：

s k+1 i=s k i+β 0 e  -γr ij 2 （s k j-s k i）+αε k+1 i（2）

上式中，r ij 为萤火虫i与j之间的欧式距离，α是步长因子，取值范围一般为[0，1]，服从高斯分布或者均匀分布;ε k+1 i是该时刻萤火虫i对应的随机向量，决定了在每个维度上进行移动的方向。

步骤4：对所有萤火虫个体执行步骤3中操作，完成整个萤火虫群体的一次迭代;

步骤5：根据情况选择合适的终止条件，判断是否满足，不满足则转步骤3;

步骤6：满足终止条件时，找出此时亮度最大的萤火虫所处的位置，即为得到的最优解。

2萤火虫算法的改进

2.1启发信息引入的必要性

标准萤火虫算法中，个体的移动以亮度作为依据，向更亮个体移动的策略保证了算法能够收敛至一个较小的区域内，但无法保证解空间的多样性，极易陷入局部最优，为此，算法提出者在萤火虫个体的移动策略中增加了随机移动项以扩展其全局搜索能力。但现有的随机移动机制导致萤火虫个体容易丢失其已经获得的最优解优势，降低搜索效率，导致算法收敛速度过慢。

基于此，有必要引入其他启发信息，为萤火虫个体提供除亮度外的移动依据。本文设计了两种不同的启发信息，形成了两种不同的改进萤火虫算法。两种引入启发信息的萤火虫算法步骤相同，如图1所示：

2.2基于全局最優引导的萤火虫算法

在粒子群优化算法中，每个粒子的速度更新利用了其自身的历史最佳位置 p best 和整个种群的历史最佳位置g best [8]，也就是说，粒子群算法中的粒子是有记忆的，这大大加快了粒子群算法的收敛速度。基于以上理论，本文为萤火虫算法引入“全局最优”概念，认为历史中出现过的最亮萤火虫的位置对群体有着持续的吸引力，使萤火虫个体不但朝着当前最优移动，还向着当前全局最优移动一定距离，这就是基于全局最优的萤火虫算法（Firefly Algorithm Based on Global Optimization，FAGO）的基本思路。具体到算法本身，将原位置更新公式（2）改为

s k+1 i=s k i+β 0 e  -γr ij 2 （s k j-s k i）+

w（g k best -s k i）+αε k+1 i（3）

式中：g k best 为k时刻记录的全局最优解的位置;w为随迭代次数增加而减小的系数：

w=k  max -kk  max （4）

式中：k为当前迭代次数;k  max 为最大迭代次数。

2.3基于贝叶斯估计的萤火虫算法

萤火虫的移动行为由方向和在该方向上的位移组成。在标准萤火虫算法中，个体随机移动项的移动方向是完全随机的，这保证了算法跳出局部最优解的可能，然而，在既定情境下，最优解所处方向一般是固定的，完全随机的移动方式未考虑最优解的方向信息，相当程度上减缓了算法收敛速度。由此，本文考虑为随机移动的方向增加启发信息，保证算法跳出局部最优能力的同时加快收敛速度。

分析算法中萤火虫的移动过程，每只萤火虫个体进行移动后，可以统计出在每个方向进行移动的概率值，适应度的变化情况也可通过适应度函数计算得知，这样，得知了萤火虫在某个方向上移动的概率和在该方向上移动后适应度增加的概率，要求得适应度增加的前提下向该方向移动的概率，就是根据先验概率计算后验概率的问题，贝叶斯估计（Bayesian estimation）正是解决这一问题的方法。贝叶斯估计[9]指出，若存在 ∪ n i=1 A i= Ω ，A iA j=， P（A i） >0，则称A 1，…，A n为完备事件组，可由贝叶斯公式计算出事件B发生的情况下A i 发生的概率：

P（A i|B）=P（A i）*P（B|A i）∑n i=1 P（B|A i）*P（A i）（5）

扩展到萤火虫算法，记解空间的维度数为m，萤火虫总个数为N，在一次迭代中相对亮度大于萤火虫j的个体数为n，则萤火虫移动的方向集合c 1，c 2，…，c 2m 为一个完备事件组，对于萤火虫个体j，在方向i上，若有p只萤火虫亮度大于其自身，则萤火虫j会在方向i上移动p次，认为萤火虫数量足够多，可根据大数定理，用萤火虫向方向i移动的频率近似代替概率，有：

P（A=c i）=∑ N-1 k=1 I（A k=c i）n=∑p k=1 I（A k=c i）n

i=1，2，…，2m（6）

I（·）为指示函数，在·为真和假時分别取值1和0。

同理，记萤火虫适应度增加为事件B，若统计出

萤火虫j向每个方向移动后适应度是否增加，就可以计算出条件概率P（B|A=c i）的值：

P（B|A=c i）=∑p k=1 I（B，A k=c i）∑K k=1 I（A k=c i）（7）

将式（6）和式（7）的结果代入式（5），就可以计算出萤火虫j在适应度增加的前提下向方向i移动的概率P（A=c i|B），选择使得该概率最大的前m 项所对应的方向进行移动，为萤火虫个体的移动带来启发信息。这就是基于贝叶斯估计的萤火虫算法（firefly algorithm based on Bayesian estimation，FABE）的核心思想。

另外，注意到式（5）中分母部分对于所有i均相同，是常数项，因此可以省略这一部分，以分子代替整体值，这样可以大大减小计算量，减少算法运行时间。

3仿真实验

为说明本文提出改进算法的有效性，对4种典型的测试函数进行了测试[10]，如表1所示。

仿真实验在Anaconda3 Spyder平台下运行，运行环境为Win10系统下Intel（R） Core（TM） i5 7300HQ处理器。萤火虫个数 N =25，算法终止条件为满足最大迭代次数 k  max =200。除Schaffer函数外，x的维度均选取为20维，根据文献[1]给出的建议，算法参数选取为： α=0 6，β=1，γ 值由函数定义域确定，Griewank选取为0 001，其余函数中均取0 01。对4个函数分别采用FA、LFA、HEFA、FAGO、FABE进行对比实验，为克服实验的随机性，每个函数分别以不同的初始随机值运行10次，每种方法采用相同初始随机值以进行对比。

各函数的具体情况分析如下。

3 1Sphere函数

Sphere函数是简单的单峰函数，五种算法在同一维度下的最优值、平均值、耗时及对应方差如表2所示。

图2展示了最优值和平均值的变化曲线，横轴为迭代次数，纵轴为函数值的对数。

从表2中可以看出：

1）在最优值和平均值方差上，LFA较大，FAGO和FABE相对较小，说明FAGO和FABE更为稳定;

2）在最优解收敛精度上， FAGO、 FABE比其他算法提升1～2个数量级，FAGO略优于FABE;

3）在平均解收敛精度上，FAGO和FABE优势较为明显，比其他算法提升2～3个数量级;LFA通过动态修改萤火虫算法的参数，提高了算法最优值的收敛速度和精度，但无法保证整体均值收敛速度和精度增加。

4）在耗时上，五种算法均处于同一数量级，FA耗时最短，FABE次之，FAGO和LFA耗时长度相近，HEFA耗时最长。

从图2中可以看出，FA最早收敛但过早陷入局部最优，FAGO收敛速度较快且取得了较高的精度。

3 2Schaffer函数

Schaffer函数是多峰函数，局部极小值分布较为集中。测试结果如表3及图3所示，为方便展示，图3最优值变化曲线纵坐标为函数值的对数，平均值变化曲线纵坐标为函数值本身。

从表3中可以看出：

1）五种算法中，在最优值和平均值上，FABE均最为稳定;

2）在最优值敛精度上，FAGO最优值精度最高，FABE次之，仅低于FAGO一个数量级，平均值的精度方面FAGO和FABE基本相同，均领先其他算法约4个数量级;

3）在耗时上，FAGO、FABE、 LFA三者较为接近，且均短于HEFA。图3中可以看出，FABE最快收敛，FAGO收敛速度略慢于FABE。

3 3Griewank函数

Griewank函数是多峰函数，局部极小值分布较为广泛。五种算法在20维下最优值、平均值、耗时的测试结果如表4和图4所示。

从表4中可以看出：

1）相比上文中提到的两个函数，5种算法的方差均有所增加，说明测试Griewank函数时稳定性有所下降，相对而言，FAGO和FABE稳定性较好;

2）在最优值收敛精度上，FABE最高，LFA其次，FAGO低于FABE近两个数量级且收敛速度快于FABE，说明过早陷入局部最优，分析原因， FAGO采用当前全局最优作为启发信息，容易被分布较为广泛且彼此相差不大的局部极小值迷惑，寻优能力相对较差;

3）在耗时上，FABE和LFA接近，FAGO耗时较短，三者均明显快于HEFA。

从图4中可以看出，FA过早收敛于较差的局部最优解，HEFA、FAGO收敛速度较快但精度较差，FABE收敛精度大于HEFA，但收敛速度略慢。

3 4Rosenbrock函数

Rosenbrock函数是常见的复杂单峰函数，在其空间内走势平缓，全局最优点处于抛物线的顶点，所以很难收敛到全局最优。测试结果如表5及图5所示。从表5可以看出：

1）对于Rosenbrock函数，几种算法稳定性均较差，FABE和HEFA稳定性最好，FAGO次之，LFA稳定性较差;

2）在收敛精度上，最优值中FABE和FAGO精度最高且结果相似，在平均值中FABE精度略高于FAGO;

3）在耗时上与Griewank函数中的结论类似，HEFA耗时最长，FABE和LFA其次，FAGO耗时较短，FA最快。

从图5可以看出，在收斂速度上，FAGO、FABE收敛速度均快于其他算法。

4结论

本文为萤火虫算法引入了全局最优和贝叶斯估计两种启发信息，提高了算法最优值和平均值的收敛精度，在一定程度上加快了算法收敛速度。仿真实验结果表明：

LFA、HEFA、FAGO、FABE最优值的求解精度均优于经典萤火虫算法，FAGO、FABE精度普遍高于LFA、HEFA，且具有良好的稳定性，LFA方差较大。无论是单峰还是多峰函数，FAGO、FABE平均值精度明显高于LFA、HEFA和FA，且稳定性强于其他算法。

在完成固定迭代次数情况下，FAGO与LFA耗时接近， FABE耗时略长，但明显快于HEFA。不考虑过早陷入局部最优的情况，FAGO、FABE两种算法平均值、最优值达到各自的最小值所需迭代次数均小于其他算法，即收敛速度较快，在多数情况下，FAGO比FABE更快。FAGO更适合处理单峰问题和局部极小值分布较为集中的多峰问题，极小值分布相对分散的多峰问题更适合选用FABE。

参 考 文 献：

[1]YANG X S. Firefly Algorithms for Multimodal Optimization[C]// Berlin， Heidelberg， International symposium on stochastic algorithms. Springer， 2009： 169.

[2]HUSSELMANN A V， HAWICK K A. Parallel Parametric Optimization with Firefly Algorithms on Graphical Processing Units[C]// Las Vegas， USA， CSREA （16-19 July 2012）. 2012： 77.

[3]ATTIA K A M， NASSAR M W I， El ZEINY M B， et al. Firefly Algorithm Versus Genetic Algorithm as Powerful Variable Selection Tools and Their Effect on Different Multivariate Calibration Models in Spectroscopy： A Comparative Study[J]. Spectrochemical Acta Part A： Molecular and Biomolecular Spectroscopy， 2017， 170： 117.

[4]刘长平， 叶春明. 置换流水车间调度问题的萤火虫算法求解[J]. 工业工程与管理， 2012（3）： 56-59+ 65.

[5]YANG X S. Firefly Algorithm， Levy Flights and Global Optimization[C]// London， Springer， 2010： 209.

[6]ABDULLAH A，DERIS S， MOHAMAD M S， et al. A New Hybrid Firefly Algorithm for Complex and Nonlinear Problem[C]// Berlin， Heidelberg， Springer， 2012： 673.

[7]YANG X S，Nature Inspired Optimization Algorithms[M]. Amsterdam， Elsevier Science Publishers， 2014.

[8]CHENG S， LU H， LEI X， et al. A Quarter Century of Particle Swarm Optimization[J]. Complex & Intelligent Systems， 2018，1（3）： 1.

[9]AlMUTAIRI A O. Bayesian Estimation Using （Linex） for Generalized Power Function Distribution[J]. Lobachevskii Journal of Mathematics， 2018， 39（3）： 297.

[10]Surjanovic， S. Bingham， D. Virtual Library of Simulation Experiments： Test Functions and Datasets[EB/OL]. http：//www.sfu.ca/～ssurjano 2017-08-01 / 2018-09-01.