杨小东 蔡泽凡 牛俊英

顺德职业技术学院电子与信息工程学院 广东佛山 528333

萤火虫粒子群混合算法

杨小东 蔡泽凡 牛俊英

顺德职业技术学院电子与信息工程学院 广东佛山 528333

本文把萤火虫算法和粒子群优化算法进行混合，在两种算法平行进化的基础上引入共享机制，使两种算法优点互补。仿真证明，混合算法提升了算法的全局搜索能力和收敛速度，适应性更强，可以应用于复杂的优化问题。

萤火虫算法；粒子群优化算法；混合算法；混沌

一、引言

萤火虫算法[1-2]（Firefly Algorithm，FA）是一种启发式算法，由剑桥大学的XinsheYang于2008年提出，灵感来自于萤火虫闪烁的行为。萤火虫的闪光，其主要目的是作为一个信号系统，以吸引其他的萤火虫。

粒子群优化算法[3-5]（ParticleSwarmOptimiztion，PSO）是模仿鸟群觅食行为的一种群体智能算法，该算法1995年由美国学者J.Kennedy和R.C.Eberhart提出。PSO算法包括一个速度更新方程和一个位置更新方程，需要调整的参数较少，程序容易实现。

不管是FA还是PSO，得益于它们的简单性和有效性，它们从诞生之日起就引起了国内外学者的关注，并掀起了研究热潮，在诸多领域得到了成功的应用。[6-16]它们对于某些复杂问题，都存在搜索不到满足精度要求的最优解，其性能需要进一步的改善。本文结合FA和PSO的优点，引入两种算法的共享机制，形成了萤火虫粒子群混合算法（Firefly Algor ithm and Particle Swarm Optimization Mixed Algorithm，FAPSOMA），FAPSOMA大大提升了全局搜索能力和收敛速度。

二、萤火虫算法

FA是一种仿生的群体智能算法，该算法模拟了自然界中萤火虫靠发光来寻找食物的行为，是一种随机优化算法。萤火虫个体利用发光特性来搜索附近某个区域，并向区域内位置较优的萤火虫移动，从而实现位置进化。在寻优过程中，萤火虫亮度和吸引度是萤火虫进化的两个关键因素。其中，萤火虫的亮度取决于自身位置的优劣性，在实际应用中，亮度用目标函数值代替，亮度越高说明萤火虫的位置越好。萤火虫的吸引度决定了萤火虫的移动方向，萤火虫的吸引度越大，则越容易吸引四周的萤火虫向着自身的位置靠近。萤火虫的亮度和吸引度与萤火虫个体之间的距离成反比，都随着距离的增长而减小。通过吸引度与亮度的不断更新变化，从而使算法达到寻优的效果。[1-2,6]

假设有N只萤火虫，搜索空间的维度为D维，那么第i只萤火虫在D维空间的初始位置可表示为 。

定义1第i只萤火虫的相对亮度。

其中 ，表示光强吸引因子，取值与区域面积相关，一般设为常数，表示第i只萤火虫和第j只萤火虫的空间距离，的值随着 的增大而减少，当 时达到最大的亮度

的值一般正比于目标函数。

定义2萤火虫的相对吸引度。

其中，表示第i只萤火虫的最大吸引度，表示萤火虫i对萤火虫j的吸引度，随着距离的增大而减少。

定义3寻优过程中萤火虫i被萤火虫j吸引的位置更新公式。

其中，为步长因子，rand为[0，1]上服从均匀分布的随机因子。为了加大搜索空间范围，提高群体的多样性，防止过早收敛，加入了随机扰动项 。

基本萤火虫的算法步骤如下：[1-2,6-7]

（1）随机初始化萤火虫种群；

（2）计算各只萤火虫的目标函数值（代表了亮度）；

（3）比较目标函数值的优劣性，如果萤火虫j优于萤火虫i，则根据式（3）移动萤火虫i的位置并使其位置落在限定的区域；

（4）更新萤火虫的最优位置和目标函数值；

（5）如果迭代次数达到最大值或者目标函数达到设定的精度则终止，否则跳到步骤（2）继续执行。

三、粒子群优化算法

PSO的基本思想是将每个粒子视为优化问题的一个可行解，粒子的好坏由一个事先设定的目标函数值函数来确定。每个粒子在可行解空间中运动，并由一个速度变量决定其方向和距离。在每一代进化中，粒子跟踪两个极值：一个是粒子本身迄今为止找到的最优解，另一个是整个群体迄今为止找到的最优解，最终获得问题的全局最优解。

假设粒子群的规模为N，搜索空间为D维，则粒子i在t时刻的状态属性设置如下：

粒子i在t+1时刻的位置通过式（4）和（5）更新，

式中，r1、r2为[0，1]区间均匀分布的随机数；c1、c2为学习因子，一般c1=c2=2。

原始PSO算法具有四个步骤：

（1）粒子群初始化。设定PSO算法中涉及的各类参数，初始化各个粒子的位置xi和速度vi，计算其目标函数值Fi；初始化个体自身极值和全局极值。

（2）评价粒子群。计算每个粒子的目标函数值Fi，更新粒子的目标函数值极值、位置极值pi，更新全局目标函数值极值、位置极值pg。

（3）更新粒子群。用式（4）和（5）对每一个粒子的速度和位置进行更新，并对速度的范围进行限制。

（4）判断是否满足结束条件。判断是否达到精度或迭代终止条件，若达到，则停止迭代，输出最优解，否则转到步骤（2）。

四、FA、PSO混合算法FAPSOMA

单一的仿生优化群算法的适应性是有限的，某种算法在解决某个问题时很成功，在处理另外一个问题时则有可能捉襟见肘，而另外一种算法的适应情况可能恰好相反。把两种性能上具有互补性的优化算法进行混合，能够彼此取长补短，提升算法的总体性能。

（一）FAPSOMA算法模型

在FAPSOMA算法中，FA和PSO既有分工也有合作，它们首先平行地单独进化，然后每隔一定的代数彼此共享最优个体，从而改善算法的全局搜索能力。FAPSOMA的流程如图1所示，主要包含以下7个步骤：

（1）初始化。分别初始化FA和PSO，FA和PSO的族群数和个体的维数相同，目标函数也一致。

（2）平行进化。利用FA和PSO分别搜索最优值，两种算法独立的进化，FA和PSO各自保存自己族群的最优个体。

（3）选择共享时刻。判断是否到达FA和PSO共享的时刻，这里规定每当算法迭代mg代以后，FA和PSO就进行共享。若到达共享的时刻则进入步骤（4），否则跳到步骤（5）。

（4）共享优秀个体。把FA和PSO两者最好的m个个体替换对方最差的m个个体，注意m的值不能超过族群规模的一半，以免发生交换过去的个体又被原封不动的交换回来的现象。随着算法的进化，FA和PSO都可能发生聚集的情况，所以随着算法的进行应该进一步提高族群的多样性，所以m的值宜采取递增的情况，这里采用式（6）进行计算，

其中，N为族群大小；t为当前迭代数，tmax为最大迭代数；r0为比例控制常数，1r0＞0.51；符号 表示向下取整数。

交换时，需要注意FA和PSO两种算法的不同，在FA中，只需要保存位置和目标函数值，而在PSO中，除了需要保存位置和目标函数值以外，还需要保存速度。因此当用FA优秀的个体替换PSO中差的个体时，位置和目标函数值可以直接替换，但是FA中没有速度信息，我们利用PSO本身最优个体的速度采用混沌模式产生相应的速度序列替换PSO这些较差个体的速度，混沌模式[17-19]采用式（7）的形式。

其中，yit是[0,1]中的一个随机数；t是迭代的代数；是一个控制参数，一般取4，这时系统将处于一个完全混沌的状态。

（5）保存全局最优值。每次进化后，判断FA和PSO两者搜索到的最优值哪一个更优，把其中最优的那一个保存下来。

（6）判断算法进程。判断算法是否满足结束条件（达到收敛精度或者最大迭代次数），满足则进入下一步，否则返回步骤（2）。

（7）输出结果。输出最终的最优值结果，算法结束。

图1 FAPSOMA流程图

（二）FAPSOMA算法仿真测试

为了验证FAPSOMA算法的有效性，对FAPSOMA进行仿真测试，仿真测试平台为WIN7+MATLAB R2012b，测试函数采用表1所示的6个标准测试函数，f1～f3为单峰函数，f4～f6为多峰函数。仿真时，族群数N=30，个体维数D=20，各维变量的范围为[-20,20]，函数的收敛精度设为 =10-5，最大迭代数设为tmax=2000，每个仿真单独运行30次。替换代数间隔预设为mg=10，式（6）中的替换比例控制常数预设为r0=0.6，30次测试的结果如表2所示。从表2和表3可以看出，FA和PSO混合而成的新算法FAPSOMA在全局搜索能力和收敛精度这两个方面都得到了提升。需要注意的是，对于有些问题，FAPSOMA仍然不能100%地搜索到满足精度要求的最优解，这主要是因为对于这些问题，FA和PSO都不能够100%地搜索到最优解，因此我们在选择不同的算法进行混合时，应该尽可能地选择在全局搜索能力方面能够完全互补的算法。表3是对成功率和成功时的收敛速度来考察的，现在我

们再来看看它们的平均性能，以标准测试函数f2和f5为例，利用FA、PSO和FAPSOMA这3种算法迭代2000次，重复30次以后取平均值，对应的平均最好目标值曲线如图2和图3所示。

表1：标准测试函数

表2：FAPSOMA和PSO、FA的仿真对比情况

表3 函数f2～f6的仿真结果汇总表

由图2可见，虽然PSO在能够搜索到最优值所需要的迭代次数是最少的，但是因为其成功率最低，因此多次实验所得的平均收敛速度是最慢的。FAPSOMA的收敛速度、收敛精度最快。图3的情况有所差别，前1000次，FA的平均收敛速度最慢，FAPSOMA最快，1000次以后，PSO的平均收敛速度最慢，FA最快。

综合表3、图2和图3的信息，我们可以得到这样的结论：从总体性能上来看，这3种算法的排序为FAPSOMA＞FA＞PSO。

图2 函数f2的平均最优目标值曲线

图3 函数f5的平均最优目标值曲线

五、结论

单一的仿生优化群算法无法适应所有的优化问题，不同的优化算法具有各自适合的场合，将两种或以上的仿生算法进行混合，可以做到扬长避短，提升算法的适应性。FAPSOMA结合了FA、PSO两者的优点，六种标准测试函数仿真情况表明，FAPSOMA的性能明显好于PSO和FA，不管是处理简单的单峰函数，还是复杂的多峰函数，FAAPSO的全局搜索能力和收敛速度都更加优越，表现了良好的鲁棒性。

[1]Yang X S.Nature-Inspired Metaheuristic Algorithm[M].Luniver Press,2008.

[2]Yang XS.Cuckoo Search and Firefly AlgorithmTheory and Applications[M].Springer,2014.

[3]Kennedy J,EberhartR.Particle swarm optimization[c].IEEE International Conference on Neral Networks,1995,4:1942-1948.

[4]Shi Y,Eberhart R.A Modified Particle Swarm Optimi-