摘 要：作为一种新兴的群智能优化方法，萤火虫算法具有简单易懂、参数少和易实现等优点，已经在诸多领域取得了较好的应用。为了使该算法能够更有效地解决不同的优化问题，需要对标准萤火虫算法进行改进或混合其他算法。介绍了萤火虫算法的原理及其应用领域，重点分析了算法的改进策略，并提出了算法进一步研究的方向。
关键词：群智能；萤火虫算法；混合算法；优化
0 引言
　　群智能是一种通过简单个体的行为，以某种形式聚集协同，使群体在没有集中控制的情况下所表现出的智能行为[1]。群智能优化算法是一种对自然界中生物的群体行为的模拟，并用数学形式表达出来的方法。典型的群智能优化算法有两个，即蚁群优化算法（Ant Colony Optimization，ACO）和粒子群优化算法（Particle Swarm Optimization，PSO）。
　　剑桥学者Yang Xinshe根据萤火虫个体的发光特性和相互吸引的行为，于2008年提出了萤火虫算法（Firefly Algorithm，FA）[2]。FA是继PSO和ACO之后，又一新颖的群智能启发式优化算法，具有概念简单、需要调整的参数少、易于应用和实现等优点。萤火虫算法是一种高效的优化算法，已成为众多学者研究的热点，在诸多领域得到了较好的应用。但标准萤火虫算法无法有效解决不同的优化问题，因此需要对其进行改进研究。
1 标准萤火虫算法
　　萤火虫算法是基于以下三个理想化的特征提出的：（1）萤火虫不分性别，即萤火虫之间的相互吸引只考虑个体发光的亮度；（2）吸引力与发光亮度成正比，与个体之间的距离成反比；（3）萤火虫的亮度由待优化的目标函数值决定，即Ii=f（xi）。
　　FA的关键思想是亮度小的萤火虫被亮度大的萤火虫吸引而向其移动，并更新自身的位置。萤火虫的发光亮度取决于自身所处位置的目标值，亮度越高所表示的目标值越好，吸引其他萤火虫的能力也越强。若相邻的个体亮度相同，萤火虫则随机移动。为了方便算法模型的建立，给出如下定义[2]：
　　定义1 亮度

其中，I0为初始光强度，即在光源（r=0）处的光强度。
　　定义2 吸引力

　　其中，m值通常取2；为最大吸引力，即光源（r=0）处的吸引力，对于大多数的应用问题，可取为1；参数是空气对光的吸收率，影响吸引力的变化，值的选取对算法性能有很大的影响，理论上∈[0，∞），但在实际应用中，常取∈[0.1，10]。rij为萤火虫i到j的笛卡尔距离，表达式为：

　　参考文献[2]指出，在实际应用中，吸引力函数可以是任何一种单调递减函数，例如：

　　定义3 位置更新公式
　　萤火虫j被萤火虫i吸引而向i移动更新自己的位置：

　　其中，t为算法迭代次数；xi、xj为萤火虫和j所处的位置；为随机步长，一般取值范围为[0，1]；εj通常是由高斯分布、均匀分布或其他分布生成的随机数向量。标准萤火虫算法需要执行算法初始化、萤火虫位置更新、萤火虫亮度更新、解的评估等操作，算法流程如图1所示。

2 萤火虫算法的研究与改进
　　FA的提出吸引了很多学者对其进行研究。Yang Xinshe用FA优化带有奇点的测试函数，结果显示FA能有效解决这类优化问题[3]，并将FA成功应用到压力管道设计优化问题中。但是，标准FA中的参数都是事先设定的，会导致算法收敛早熟，或因参数设置不当而导致算法无法收敛。为了使算法具有较好的优化性能，需要对标准FA进行改进。
　　Yang Xinshe首先把Levy Flight引入到式（5）的随机部分，构建了具有Levy Flight的萤火虫算法（Levy-Flight Firefly Algorithm，LFA）[4]。分别用LFA和遗传算法（Genetic Algorithm，GA）优化标准测试函数，结果显示LFA能更高效、准确地搜索全局最优值。FATEEN S E K等人提出智能萤火虫算法（Intelligent Firefly Algorithm，IFA）[5]，该算法将萤火虫按亮度排列后，确定适应度较好的个体的比例及顶部萤火虫数量，每次迭代萤火虫都向顶部萤火虫移动并更新位置。实验证明IFA能高效解决全局优化问题，避免算法收敛早熟。此外，学者们还提出了各自不同的改进方法。
2.1 基于自适应策略的FA
　　FARAHANI S M等人[6]采用自适应步长改进了FA的随机部分，给随机步长定义一个依赖于迭代次数的系数，迭代初期采用较大的步长，搜索较大的区域，迭代后期减小步长，使算法快速收敛于全局最优点。同时还提出了萤火虫的定向移动，即在没有局部更亮的个体时，萤火虫向全局最优点移动。这种改进提高了算法精度，也减少了萤火虫的无效运动。实验结果表明，改进算法的优化效果优于标准FA。
　　FA对宽搜索区域和高维度优化问题存在吸引力很弱难以影响位置更新的现象。据此，董静提出根据rij调节随机参数的方法，用2rij（rand-1/2）取代式（5）中的随机部分。随机步长随rij变化，当rij较大时，吸引力则较小，萤火虫本身在[-rij，rij]范围内自由移动，加强了算法的探索能力；当rij较小时，算法进行局部寻优，此时吸引力对位置更新占主导作用。这种改进提高了算法的寻优精度和收敛速度。Yan Xiaohui等人则提出压缩距离的方法[8]。式（2）中，令m∈（0，1），此时若rij值很大，则rijm的值就会相应变小，保证在合理范围之内。其中，k是常数，通常取O（1），D代表维度，R代表搜索范围，对于不同的优化问题，m值各不相同。改进后的FA在解决高维优化问题时，效果明显优于标准FA、PSO和差分进化算法（Differential Evolution，DE）。
　　Yu Shuhao等人提出了根据每只萤火虫的历史信息和当前位置信息来确定随机步长的策略[9]，使靠近最优解的个体具有较小的步长，而远离最优解的个体具有大一些的步长，从而更新萤火虫的位置。因此，每只萤火虫下一次迭代的步长都是自适应的，且由当前最优值与群体最优值之间的差异决定。这种改进方法能避免算法收敛早熟，提高了萤火虫算法的准确度。
2.2 基于参数调节的FA
　　dos Santos Coelho L在标准FA中引入混沌思想，用混沌序列调节参数，避免算法陷入局部最优，并用该算法优化可靠性冗余分配问题，取得了更好的结果。FARAHANI S M等人在标准FA中引入自动学习机调节参数]，使得算法能够根据环境随时调整参数值。实验结果表明，改进后的FA在优化性能上有很大提升。基于参数调节的FA在解决动态优化问题方面取得了比PSO更好的结果。
2.3 混合萤火虫算法
　　FARAHANI S M等人将GA混合到FA中来提高萤火虫算法的全局搜索能力[11]。混合算法将种群分为两个子群，分别执行FA和GA操作，在每次迭代的最后，两个子群相互交换并进入下一次迭代，同时采用高斯随机步长使萤火虫在搜索空间移动，克服了标准FA中随机步长固定不变的缺点。GA的引入使FA的勘探和开采能力得到平衡，该改进算法具有优于标准FA和PSO的优化能力。
　　ABDULLAH A等人将DE算法融入标准FA中[12]。该混合算法将萤火虫个体按适应度值分为两个子群，第一个子群中包含适应度较好的个体，执行标准FA操作；第二个子群中则包含适应度不好的个体，执行DE算法的交叉、变异、选择操作，最后从两个子群中选取最优解。该混合算法增加了萤火虫之间的信息共享，避免算法陷入局部最优，提高了算法搜索效率。
　　Guo Lihong等人融合了标准FA与和声搜索（Harmony Search，HS）算法[13]，将HS的勘探能力与标准FA的开采能力相结合，HS的引入可以看作是变异操作，保证了种群的多样性，使得算法具有更好的寻优性能。同时，还采用了顶部萤火虫方案，降低了算法复杂度。经实验验证，混合HS的萤火虫算法比其他优化算法能更好地利用有用信息来发现最优解。
2.4 其他形式的FA
　　SAYADI M等人提出用于解决离散优化问题的离散萤火虫算法（Discrete Firefly Algorithm，DFA）[14]，并用其成功解决了置换流水车间调度中最小化完工时间问题，其处理结果比ACO得到的结果更优，实验结果显示DFA能很好地优化不同规模的调度问题。
　　FARAHANI S M针对动态优化问题提出了一种基于多群体的萤火虫算法[15]。该算法将萤火虫种群分为一系列相互影响的子群体，由排斥因子和抗收敛因子分别控制进行局部寻优和全局寻优，这样可以保证每个子群的群体多样性，有效避免算法陷入局部最优。用多群萤火虫算法处理动态优化问题，其能力优于PSO。
　　Yang Xinshe提出了多目标萤火虫算法[16]（Multiobjective Firefly Algorithm，MOFA），该算法根据Pareto支配关系确定萤火虫的亮度大小，在迭代过程中求得Pareto最优解。用MOFA处理焊接梁工程优化问题，优化结果表明，MOFA是一种有效的优化器。董静也提到了MOFA，用外部档案保存Pareto解，并用自适应网格法维护外部档案[7]。此方法为多目标萤火虫优化提供了方向。
3 萤火虫算法的应用
　　萤火虫算法主要应用于优化、工程应用及分类问题。优化问题又分连续优化、组合优化、约束优化、多目标优化及动态或含噪声优化。MAUDER T等人用FA解决连铸工艺优化问题[17]，在满足约束条件的情况下，得到了满意的结果；FISTER Jr I等人用混合局部搜索的FA解决图三着色问题，并取得较好的结果[18]，该结果显示了FA在解决其他组合优化问题方面的潜力。SENTHILNATH J等人用萤火虫算法解决聚类问题[19]，并得出FA是处理聚类的有效方法。作为一种优化工具，FA及其改进算法还成功地应用于图像处理、路径规划、天线设计等领域，均取得了较好的结果。随着萤火虫算法的不断完善，其应用领域也将会不断扩大。
4 结论
　　FA是一种高效的启发式优化算法，但仍有许多方面需要进一步研究。参数的设置会影响FA的性能，很多文献都提出了有效的改进方法，对参数进行选择和控制，提高了算法的优化能力。寻找高效的参数控制方法，是FA研究的一个重要方向。混合萤火虫算法能在一定程度上克服FA自身的缺点，大大提高算法的性能。目前FA已与GA、DE、HS等算法融合，寻找能够有效结合的混合算法也是研究热点之一。在应用方面，FA及其改进算法已广泛应用到诸多领域，但在分类与识别问题方面的应用偏少。将FA与机器学习结合应用也是很有意义的。此外，如何用FA更好地解决动态优化问题也是值得研究的。最后，FA的数学理论尚不完善，算法的复杂度和收敛性分析仍然具有研究性。
参考文献
　　[1] CHRISTIAN B， DANIEL M（Eds）.群智能[M].龙飞，译，北京：国防工业出版社，2011.
　　[2] Yang Xinshe. Nature-inspired metaheuristic algorithms[M]. Luniver press， 2010.
　　[3] Yang Xinshe. Firefly algorithm， stochastic test functions and design optimisation[J]. International Journal of Bio-Inspired Computation， 2010，2（2）：78-84.
　　[4] Yang Xinshe. Firefly algorithm， Levy flights and global optimization[M]. Research and Development in Intelligent Systems XXVI， London： Springer， 2010.
　　[5] FATEEN S E K， BONILLA-PETRICIOLET A. Intelligent firefly algorithm for global optimization[M]. Cuckoo Search and Firefly Algorithm， Springer International Publishing， 2014.
　　[6] FARAHANI S M， ABSHOURI A A， NASIRI B， et al. An improved firefly algorithm with directed movement[C]. Proceedings of 4th IEEE International Conference on Computer Science and Information Technology， Chengdu， 2011： 248-251.
　　[7] 董静.萤火虫算法研究及其在水下潜器路径规划中的应用[D].哈尔滨：哈尔滨工程大学，2013.
　　[8] Yan Xiaohui， Zhu Yunlong， Wu Junwei， et al. An improved firefly algorithm with adaptive strategies[J]. Advanced Science Letters， 2012， 16（1）： 249-254.
　　[9] Yu Shuhao， Yang Shanlin， Su Shoubao. Self-adaptive step firefly algorithm[J]. Journal of Applied Mathematics， 2013.
　　[10] dos Santos Coelho L， de Andrade Bernert D L， Mariani V C. A chaotic firefly algorithm applied to reliability-redundancy optimization[C]. 2011 IEEE Congress on Evolutionary Computation（CEC）， IEEE， 2011： 517-521.
　　[11] FARAHANI S M， ABSHOURI A A， NASIRI B， et al. Some hybrid models to improve firefly algorithm performance[J]. International Journal of Artificial Intelligence， 2012， 8（S12）： 97-117.
　　[12] ABDULLAH A， DERIS S， MOHAMAD M S， et al. A new hybrid firefly algorithm for complex and nonlinear problem[M]. Distributed Computing and Artificial Intelligence， Berlin Heidelberg Springer： 2012.
　　[13] Guo Lihong， Wang Gaige， Wang Heqi， et al. An effective hybrid firefly algorithm with harmony search for global numerical optimization[J]. The Scientific World Journal，2013， Article ID 125625，9.
　　[14] SAYADI M， RAMEZANIAN R， GHAFFARI-NASAB N. A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems[J]. International Journal of Industrial Engineering Computations， 2010，1（1）：1-10.
　　[15] FARAHANI S M， NASIRI B， MEYBODI M R. A multiswarm based firefly algorithm in dynamic environments[C].Third International Conference on Signal Processing Systems（ICSPS2011）， 2011，3：68-72.
　　[16] Yang Xinshe. Multiobjective firefly algorithm for continuous optimization[J]. Engineering with Computers， 2013，29（2）： 175-184.
　　[17] MAUDER T， SANDERA C， STETINA J， et al. Optimization of the quality of continuously cast steel slabs using the firefly algorithm[J]. Materials and technology， 2011，45（4）：347-350
　　[18] FISTER Jr I， Yang Xinshe， FISTER I， et al. Memetic firefly algorithm for combinatorial optimization[J]. arXiv preprint arXiv：1204.5165， 2012.
　　[19] SENTHILNATH J， OMKAR S N， MANI V. Clustering using firefly algorithm： Performance study[J]. Swarm and Evolutionary Computation， 2011，1（3）：164-171.