基于混合变异的萤火虫群优化算法

张小琼　秦亮曦

(广西大学计算机与电子信息学院　广西 南宁 530004)



基于混合变异的萤火虫群优化算法

张小琼秦亮曦

(广西大学计算机与电子信息学院广西 南宁 530004)

摘要基本萤火虫群优化GSO(Glowworm Swarm Optimization)算法在求解函数全局寻优问题时，存在后期收敛速度慢、容易陷入局部极值等问题。为此，提出一种基于混合变异的萤火虫群优化算法。该算法用混沌变异和边界变异来增加种群的多样性，避免算法陷入局部最优，且能使算法获得精度更高的解。运用六个标准测试函数进行测试，结果表明，改进后的萤火虫群优化算法比基本GSO算法具有更高的寻优速度、寻优精度和收敛率。

关键词萤火虫群优化算法混沌变异边界变异混合变异函数优化

GLOWWORM SWARM OPTIMISATION BASED ON HYBRID MUTATION

Zhang XiaoqiongQin Liangxi

(School of Computer and Electronic Information,Guangxi University,Nanning 530004,Guangxi,China)

AbstractWhile basic glowworm swarm optimisation (GSO) is applied to solving the problem of global optimisation of functions, it has the problems of slow convergence in later period and being prone to falling into local optimum. Therefore we put forward a hybrid mutation-based algorithm of glowworm swarm optimisation. The algorithm uses chaotic mutation and boundary mutation to improve the diversity of the population, and prevents the algorithm from falling into local optimum; moreover this enables the algorithm to achieve a more accurate solution. Six standard test functions are applied to the test, results show that the improved glowworm swarm optimisation is better than the basic GSO in terms of the optimisation speed and precision and the convergence rate.

KeywordsGlowworm swarm optimisation (GSO)Chaotic mutationBoundary mutationHybrid mutationFunction optimisation

0引言

萤火虫群优化GSO算法是印度学者K N Krishnanand和Debasish Ghose于2005年模拟自然界萤火虫求偶或觅食行为而提出的一种新型仿生群体智能优化算法[1]。该算法通过萤火虫个体之间的相互吸引达到寻优的目的，其计算速度快，需要调节的参数少，简单易于实现，具有很强的通用性，已逐渐成为计算智能研究领域一个新的研究方向，并成功应用于传感器的噪声测试[2]、聚类分析[3]、模拟机器人[4]、函数优化[5]等。但与其他群智能算法一样，也存在着后期收敛速度慢、容易陷入局部极值、求解精度不高等问题。

针对这些问题，文献[5]提出一种基于荧光因子的自适应调整步长的方法，使得萤火虫算法寻优的解获得了更高的精度。文献[6]提出了一种带交尾行为的混沌萤火虫优化算法，通过混沌进行初始化，提高了初始解的质量，又在GSO算法中引入交配行为，进一步提高了萤火虫群优化算法的收敛速度和求解精度。文献[7,8]分别运用高斯变异和自适应t分布变异的方法增加萤火虫种群的多样性，提高了解的精度和寻优的速度。本文采用混沌变异和边界变异的混合变异策略，对陷入局部极值的萤火虫利用混沌变异的方法搜索周围的最优解来代替本身；对飞出边界的萤火虫进行边界变异，避免边界萤火虫聚集的行为，提高种群的效率。

1基本萤火虫群优化算法

基本萤火虫群优化算法思想来源于自然界的萤火虫用闪光来吸引其他萤火虫，借此进行沟通、求偶等。闪光越亮代表萤火虫吸引力越大，最后形成萤火虫聚集在亮度较大的萤火虫周围。萤火虫闪光的亮度取决于萤火虫携带的的荧光素值，荧光素值越大，萤火虫的闪光越亮。

算法初始时在D维解空间内随机生成N只萤火虫，萤火虫i的当前位置表示为Xi(t)，初始时每只萤火虫都携带相同的萤火素值l0，并且具有相同的决策半径r0。在萤火虫移动的过程中，如果萤火虫j在萤火虫i的决策范围内，并且萤火虫j荧光素值比萤火虫i的高，萤火虫i就以一定的概率向其邻居萤火虫j移动。萤火虫所在位置对应一个适应度值，荧光素的大小与萤火虫所在位置的适应度值有关，荧光素值越大，所在位置越好，即有较好的适应度值。最后，萤火虫会聚集在适应度值较高的萤火虫周围。在完成初始化后，GSO每次迭代包括三个过程：荧光素更新、位置更新、感知范围更新。

1) 荧光素更新阶段

荧光素与萤火虫所在位置密切相关，所在位置越好，荧光素值就越大，闪光越亮；荧光素除了受所在位置影响，还与萤火虫上一时刻所携带的荧光素值和挥发速度有关。荧光素值根据下式进行更新：

li(t)=(1-ρ)li(t-1)+γf(Xi(t))

(1)

式中，li(t)表示在t时刻萤火虫i的荧光素值，ρ(0<ρ<1)为常数，表示荧光素的挥发速度，γ也为常数，表示荧光素更新率，f(Xi(t))表示在t时刻萤火虫i所在位置的适应度值。

2) 位置更新阶段

萤火虫i的移动方向由其所有邻居萤火虫的荧光素决定，邻居萤火虫是在萤火虫i的决策范围内荧光素值比萤火虫i的荧光素值大的萤火虫集合，即：

Ni(t)={j:‖Xj(t)-Xi(t)‖

(2)

式中，‖·‖表示欧氏距离，ri(t)表示t时刻萤火虫i的决策半径。对所有邻居萤火虫j，根据下式计算t时刻萤火i向萤火虫j移动的概率：

(3)

萤火虫i根据Pij(t)选择移动方向为j，然后根据下式更新萤火虫i的位置：

(4)

其中，s为移动步长。

3) 感知范围更新

移动后，每只萤火虫根据邻居萤火虫的数量动态地更新各自的感知范围，如果邻居萤火虫数量多，则减小感知范围，反之增大感知范围，如下式更新：

ri(t+1)=min{rs,max[0,ri(t)+β(nt-|Ni(t)|)]}

(5)

其中，rs是控制萤火虫感知范围阀值，β是领域变化率，ri(t)(0

2混合变异优化GSO算法

2.1种群混沌变异机制

文献[8]提出的ATM-AGSO算法进行变异时，非最优萤火虫采用自适应t分布变异，最优萤火虫采用高斯变异，即：

Xi(t)=Xi(t)×[1+k×H(t)]k=1-(t-1)/(Tmax-1)t=1,2,…,Tmax

(6)

其中，k为变异控制因子，当i为非最优萤火虫时，H(t)为以迭代次数t为参数自由度的t分布，当i是最优萤火虫时，H(t)为服从均值为0方差为1的高斯分布。但这种变异方法变异的幅度相对较大，容易错过附近更优解。为提高算法局部搜索的遍历性和效率，本文采用混沌立方映射[9]产生混沌变量来代替ATM-AGSO算法中的随机变量H(t)，进行混沌变异。该策略表示为：

Xi n(t) = Xi(t)×[1 + k×Z(n)]n = 1,2,…,Mk = 1-(t-1)/Tmaxt = 1,2,…,Tmax

(7)

式中，t表示当前迭代次数，Tmax表示算法最大迭代次数，Z(n)为混沌序列。

混沌是自然界广泛存在的非线性现象，是一种状似随机混乱，却具有遍历性和规律性的非随机运动，能按自身规律在一定范围内不重复地遍历所有状态[10]。运用混沌运动的这些特性对GSO算法进行优化搜索，有助于算法跳出局部最优，增加种群的多样性，增强算法的全局搜索能力。混沌立方映射产生的是(-1，1)之间的序列，只要立方映射的迭代初值不为0，混沌就会发生。首先在D维解空间内根据式(8)随机产生一个(-1，1)之间的D维向量，作为第一个混沌变量：

Z(1)=1-2rand(1,D)

(8)

然后根据下式对每一维迭代M-1次，最后得到M个混沌序列。

Z(n+1)=4Z(n)3-3Z(n)-1≤Z(n)≤1n=1,2,…,M-1

(9)

利用产生的混沌序列根据式(7)进行变异，比较变异扰动前、后的的适应度值。若变异产生的最优适应度值优于原有个体的适应度值，就用该最优适应度值所处的状态取代原有个体状态。这样根据已有个体状态增加混沌扰动项Xi×k×Z(n)，获得有更好适应度值的个体，种群的多样性得到了保证，也赋予了算法跳出局部极值的能力，同时提高了搜索能力。

2.2边界变异

在其他一些GSO算法中，当萤火虫飞出搜索区域后，通常将搜索空间的边界值赋值给该萤火虫：

ifXi(t)>XmaxXi(t)=Xmax

或者

ifXi(t)

其中，Xmax、Xmin分别是搜索区域的最大和最小边界值。经过这样的处理后，所有越界的萤火虫会在边界聚集，其状态将趋于相同，不仅降低了种群的多样性，也会影响算法的全局搜索能力；如果边界附近存在局部最优，还使得算法容易陷入局部极值。

文献[11]把边界变异引入到量子粒子群算法中，有效控制了粒子越界的行为，提高了算法的全局搜索能力。同理，我们也可以把边界变异引入到萤火虫群算法中，在每代萤火虫越界时进行边界变异，该变异策略可表示为：

ifXi(t)>XmaxXi(t)=Xmax×(1-c×rand())

或者

ifXi(t)

其中，c=0.01。从上述变异过程可以看出，对越界萤火虫进行变异操作后，萤火虫不再聚集在边界处，而是分布在搜索区域内，克服了萤火虫聚集边界的缺点，同时增加了种群的多样性，避免了萤火虫陷入局部极值，提高了算法的整体搜索速度。

2.3HM-GSO混合变异描述

HM-GSO算法是将混沌变异和边界变异相结合，在算法迭代过程中，随着种群的不断进化，个体之间的差异逐渐变小，并出现萤火虫严重聚集的现象，导致算法极容易陷入局部极值。此时对种群中的每只萤火虫进行混沌变异搜索，对搜索过程中越界的萤火虫进行边界变异，最后用混沌扰动后的最优状态更新为当前萤火虫的状态。每次萤火虫群变异后用最优萤火虫的状态和适应度值和公告板上的最优萤火虫比较，公告板将记录更优的萤火虫的状态和适应度值。当公告板上的适应度值在连续三次迭代中没有改变或者改变很小(|变化量|

2.4HM-GSO算法步骤

HM-GSO算法的具体步骤设计如下：

1) 初始化ρ、γ、β、s、l0、r0、rs、nt、N、D、Tmax、u等参数，并随机初始化萤火虫种群；

2) 计算所有萤火虫的适应度值，初始化公告板；

3) 根据式(1)对所有萤火虫进行荧光素更新；

4) 用式(2)计算所有萤火虫的邻居集合，式(3)计算萤火虫的选择概率，然后用轮盘赌方法选择移动目标，根据式(4)进行位置更新；

5) 用式(5)更新萤火虫的感知半径；

6) 计算当前种群每个个体的适应度值，若最优适应度值优于公告板，则更新公告板的状态和适应度值；

7) 判断是否陷入局部最优值，如果公告板上的最优适应度值在连续三次迭代中没有发生改变或者改变很小(|变化量|

图1　HM-GSO算法流程图

8) 在每个萤火虫周围进行混沌变异，对飞出边界的萤火虫用边界变异策略控制在搜索范围内，计算混沌扰动后的适应度值，取最优适应度值与原适应度值比较，若优于原有适应度值，则用扰动后最优适应度值所在的位置取代原有位置。比较变异后萤火虫群的最优萤火虫和公告板的最优萤火虫，如果由优于公告板，则更新公告板的状态和适应度值；

9) 完成一次迭代，判断终止条件是否满足(迭代次数达到Tmax)，如果满足，记录结果，退出迭代，否则转步骤3)，进入下一次迭代。

HM-GSO算法的流程如图1所示。

3HM-GSO算法性能测试与分析

3.1实验测试函数

为了验证HM-GSO算法的收敛速度、收敛率和求解精度等，将本文提出的基于混合变异的萤火虫群(HM-GSO)算法与基本GSO算法及文献[8]提出的基于自适应t分布混合变异的人工萤火虫(ATM-AGSO)算法进行性能比较，采用了6个标准测试函数进行对比测试实验。6个测试函数如下：

标准测试函数如表1所列。

表1　标准测试函数

3.2实验参数设置

在GSO算法中，步长s根据经验选取，F1、F3中取为5，F2、F4、F5和F6中取为1，对于ATM-AGSO算法和HM-GSO算法，s取值为0.3，其他实验参数设置如表2所示。

表2　实验参数设置

3.3实验平台

本实验的运行测试环境为：处理器为Intel(R) Core(TM) i3-3110M CPU，主频2.4 GHz，内存4 GB，操作系统：Windows 7，集成开发环境为Matlab R2012a。

3.4实验仿真结果与分析

仿真实验中对这三种算法用这6个标准测试函数分别进行20次独立实验，对每一个函数求得这三种算法的最优值、最差值、均值、收敛迭代次数、平均收敛时间和收敛率等，并通过收敛曲线来比较三种算法的收敛速度和求解精度，从而测试本文算法的有效性。在给出收敛精度ε=10-5的情况下，如果满足|Fitnessbest-Fitness|<ε，则认为算法收敛；否则为不收敛。其中，Fitnessbest为实际求得的最优解，Fitness为理论上的最优解。

从表3、表4可以看出，GSO对6个函数都没有收敛，HM-GSO和ATM-AGSO测试6个函数时的收敛率达到100%，收敛精度以HM-GSO最大，ATM-AGSO次之，GSO最小。对于函数F1，HM-GSO的平均最优解精度比GSO提高了42个数量级，平均收敛迭代次数比ATM-AGSO减少了65次。对于函数F2，HM-GSO的平均最优解精度比GSO提高了30个数量级，比ATM-AGSO提高了20个数量级，平均收敛迭代次数比ATM-AGSO减少了85次。对于函数多个F3，HM-GSO的最优解精度达到了e-75，平均最优解精度远优于GSO，比ATM-AGSO提高了40个数量级，平均收敛迭代次数比ATM-AGSO减少了47次。对于函数F4，HM-GSO的平均最优解精度比GSO提高了63个数量级，比ATM-AGSO提高了45个数量级，平均收敛迭代次数比ATM-AGSO减少了61次。对于函数F5，HM-GSO的平均最优解精度比GSO提高了52个数量级，比ATM-AGSO提高了33个数量级，平均收敛迭代次数比ATM-AGSO减少了44次。对于函数F6，HM-GSO的最优解精度达到了e-102，平均最优解精度比ATM-AGSO提高了26个数量级，平均收敛迭代次数比ATM-AGSO减少了12次。

表3　三种算法收敛情况对比

表4　三种算法最优解对比

结合图2-图7分析，HM-GSO的寻优曲线更加稳定。随着迭代次数的增加，在增加不到50时，HM-GSO的最优函数值就到达了收敛精度。HM-GSO的平均收敛时间也比ATM-AGSO更少，且在同一次迭代里面。HM-GSO获得的最优函数值比GSO和ATM-AGSO更优，说明HM-GSO比GSO和ATM-AGSO具有更快的收敛速度，更高的求解精度。可见，HM-GSO算法在搜索过程中通过混沌变异和边界变异混合变异的方法增加了种群的多样性，避免了算法陷入局部最优、容易聚集边界的缺点，克服了过早收敛的问题。因而全局寻优能力、求解精度、收敛速度和稳定性等方面比其他两种算法都得到了提高，具有更好的寻优能力。

图2　F1函数寻优收敛曲线　　图3　F2函数寻优收敛曲线

图4　F3函数寻优收敛曲线　　图5　F4函数寻优收敛曲线

图6　F5函数寻优收敛曲线　　图7　F6函数寻优收敛曲线

4结语

本文提出了一种基于混合变异的萤火虫群优化算法。算法中运用混沌的方法进行变异，并对越界的萤火虫进行边界变异，使算法避免陷入局部极值，提高了寻优速度和求解精度。通过函数优化实验可以看出，改进后的算法优于基本萤火虫群优化算法，较ATM-AGSO算法有更快的收敛速度和更精确的函数值。下一步我们将融合其他算法，并应用于求解实际问题中。

参考文献

[1] Krishnanand K N,Ghose D.Glowworm swarm optimization:a new method for optimizing multi-modal functions[J].International Journal of Computational Intelligence Studies,2009,1(1):93-119.

[2] Krishnanand K N,Ghose D.A glowworm swarm optimization based multi-robot system for signal source localization[M]//Liu D K,Wang L F,Tan K C.Design and Control of Intelligent Robotic Systems.Berlin:Springer,2009:53-74.

[3] Huang Z X,Zhou Y Q.Using glowworm swarm optimization algorithm for clustering analysis[J].Journal of Convergence Information Technology,2011,6(2):78-85.

[4] Krishnanand K N,Ghose D.Chasing multiple mobile signal sources:a glowworm swarm optimization approach[C]//Third Indian International Conference on Artificial Intelligence (IICAI 07).Indian,2007.

[5] 欧阳喆,周永权.自适应步长萤火虫优化算法[J].计算机应用,2011,31(7):1804-1807.

[6] 黄凯,周永权.带交尾行为的混沌人工萤火虫优化算法[J].计算机科学,2012,39(3):231-234.

[7] 莫愿斌,刘付永,张宇楠.带高斯变异的人工萤火虫优化算法[J].计算机应用研究,2013,30(1):121-123.

[8] 杜晓昕,张剑飞,孙明.基于自适应t分布混合变异的人工萤火虫算法[J].计算机应用,2013,33(7):1922-1925.

[9] 冯艳红,刘建芹,贺毅朝.基于混沌理论的动态种群萤火虫算法[J].计算机应用,2013,33(3):796-799.

[10] 郁书好,苏守宝.混沌萤火虫优化算法的研究及应用[J].计算机科学与探索,2014(3):1-6.

[11] 宋建立,谭阳红,熊智挺.非对称边界变异的分层并行量子粒子群算法[J].计算机应用研究,2013,30(6):1630-1632.

中图分类号TP183

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.063

收稿日期：2014-07-28。张小琼，硕士生，主研领域：智能算法与智能CAD技术。秦亮曦，教授。