自适应步长萤火虫优化算法

收稿日期:2011-01-10;修回日期:2011-03-02。基金项目:广西自然科学基金资助项目（0991086）。

作者简介:欧阳矗1988-），女，江西吉安人,硕士研究生，主要研究方向：智能计算； 周永权（1962-）,男,陕西旬邑人,教授，博士，主要研究方向：神经网络、计算智能。

文章编号:1001-9081（2011）07-1804-04doi:10.3724/SP.J.1087.2011.01804

（广西民族大学 数学与计算机科学学院，南宁 530006）

（）

摘 要:针对基本萤火虫算法优化多峰函数时求解精度不高和后期收敛较慢的问题，引入萤光因子以自适应调整萤火虫的步长，提出一种自适应步长萤火虫优化算法。通过8个标准测试函数测试，测试结果表明，改进后的自适应步长萤火虫算法比基本萤火虫算法具有较快的寻优速度和较高的寻优精度。

关键词:多峰函数；萤火虫优化算法；自适应;步长；萤光因子

中图分类号:TP183文献标志码:A

Self-adaptive step glowworm swarm optimization algorithm

OUYANG Zhe,ZHOU Yong-quan

（College of Mathematics and Computer Science，Guangxi University for Nationalities，Nanning Guangxi 530006，China）

Abstract: According to the problem that Glowworm Swarm Optimization （GSO） cannot acquire solutions exactly and converge slowly in the later period for solving the multimodal function，an improved GSO algorithm combined with luciferin-factor, which can adaptively adjust step, was proposed. The simulation results show that the improved Self-Adaptive Step Glowworm Swarm Optimization （ASGSO） can search for global optimization more quickly and precisely.

Key words: multimodal function; Glowworm Swarm Optimization （GSO） algorithm; self-adaptive; step; luciferin-factor

0 引言

萤火虫优化（Glowworm Swarm Optimization,GSO）算法是2005年由K.N. Krishnanand和Debasish Ghose提出的一种新的群智能优化算法。GSO主要是模拟萤火虫发光吸引同伴，萤火虫发光越大，吸引的同伴越多这一现象，通过各个萤火虫个体，在视野范围内寻找最亮的萤火虫，向最亮的萤火虫移动来实现寻优的目的［1-2］。

多峰函数一般是指有多个峰值点的函数［3］。多峰函数的优化问题在实践中大量存在，例如求解非线性方程组，依据密度的山峰聚类算法、神经网络训练等。但在实际中，有时无法求出全局最优值点作为最优方案，因此求出在局部最优值点函数作为次优解。因此需要进行多峰优化，找到函数全局最优值的同时也能找到多个局部最优值，但许多经典的算法往往容易陷入局部最优［4］。所以研究有效快速的多模态函数的优化算法成为一个研究热点。

基本萤火虫算法在优化多峰函数时，能够同时获得多个极值点。但是算法后期收敛速度慢，寻优精度不高，降低了算法的效率。针对这些不足，本文提出了基于自适应步长的萤火虫算法（self-Adaptive Step Glowworm Swarm Optimization,ASGSO），引入了萤光因子对萤火虫算法的步长进行自适应调整。仿真结果表明，自适应步长的萤火虫算法具有计算精度较高、搜索速度较快等特点。

1 基本萤火虫算法

在基本GSO中，把n个萤火虫个体随机分布在一个D维目标搜索空间中。每个萤火虫都携带了萤光素li。萤火虫个体都发出一定量的萤光相互影响周围的萤火虫个体，并且拥有各自的决策域rid（0

萤光素更新 每只萤火虫i在t迭代的位置xi（t）对应的目标函数值J（xi（t））转化为荧光素值li（t）：

li（t）（1-ρ）li（t-1）+γJ（xi（t））（1）

其中γ为荧光素更新率。

概率选择 每个个体在其动态决策域半径rid（t）内，选择荧光素值比自己高的个体组成其邻域集Ni（t）{j:dij（t）

pij（t）（2）

位置更新：

xi（t+1）xi（t）+s（3）

其中s为移动步长。

动态决策域半径更新：

rid（t+1）min{rs,max{0,rid（t）+β（nt－Ni（t））}}（4）

简单地说，GSO算法主要包括萤火虫的初始分布、萤光素更新、萤火虫的移动和决策域的更新四个阶段［5］。

2 自适应步长萤火虫算法

2.1 动态自适应步长调整策略

在基本萤火虫算法中，存在容易陷入局部最优，后期收敛较慢且求解精度不高的问题。在搜索的过程中，步长越大，越容易搜索全局最优，但同时降低了搜索精度，有时会出现震荡现象；步长越小，搜索速度降低，求解精度提高。针对这个问题，需要根据不同阶段的搜索结果，动态调整步长的大小，处理好全局寻优能力和寻优精度之间的关系。

为此，引入萤光因子

Hi（5）

式中：Xi表示第i只萤火虫个体的状态,Xext表示此时萤光素浓度最大的萤火虫个体的状态,dmax表示最优萤火虫距其余所有萤火虫的距离的最大值。

基于萤光因子的自适应调整步长策略：

sismin+（smax－smin）Hi（6）

式中smax和smin分别表示步长的最大值和最小值。

根据式（5）、（6）动态调整步长。当第i只萤火虫越接近萤光素浓度最大的萤火虫，距离越近，则Xi－Xext越小，根据式（5），所求得的Hi值越小，因此根据式（6）得出的si也越小。当萤火虫个体向目标萤火虫个体移动时，一个较小的步长si可以让萤火虫个体更好地靠近目标萤火虫个体，而不至于由于步长太大而跳过最优解，从而提高搜索精度。当第i只萤火虫个体距离萤光素浓度最大的萤火虫个体较远时，则Xi－Xext越大，Hi值越大，si值增大，当萤火虫个体以较大步长搜索时，可提高搜索速度，更快搜索寻优。这样，根据上一次迭代的结果来动态更新本次迭代的移动步长，具有更好的自适应性。同时，给定步长的最大值和最小值smax和smin，让步长在一定范围内变化，可以避免萤火虫分散过大导致步长太小等问题。对于标准的萤火虫算法，由于步长s固定，在初始化s时，随机性强，步长太大则会影响求解精度，太小则又降低搜索速度。所以，只有根据求解的情况动态地调整步长，才能更好地提高算法的搜索速度和寻优精度。

因此，在自适应步长的萤火虫算法运行前期，采用较大的步长，可以保证离最优萤火虫较远的个体具有更大的步长，使萤火虫在大范围内进行粗搜索，从而可以更快搜索全局最优的邻域；而在最优邻域附近的个体具有较小的步长，算法逐步演化为局部搜索进行精确搜索，可以更精确地搜索极值［6-9］。

2.2 算法描述

基于自适应步长的萤火虫算法的流程可以描述如下。

步骤1 初始化群体：随机生成n个萤火虫个体形成初始萤火虫种群，搜索空间维数m，萤火虫的初始荧光素大小l0和感知范围r0，萤火虫感知最大半径rs，最大迭代次数iter_max，初始步长si（0），最大步长smax，最小步长smin，随机产生萤火虫初始位置xi（0），萤光素挥发系数ρ，萤光素更新率γ；

步骤2 对种群中每一个萤火虫个体i，执行以下操作：

2.1）使用式（1）把萤火虫i在第t次迭代的位置xi（t）对应的目标函数值J（xi（t）） 转化为荧光素值li（t）；

2.2）每只萤火虫在其动态决策域半径rid（t）内，选择荧光素值比自己高的个体组成其邻域集Ni（t），其中0

2.3）利用式（2）计算萤火虫i 移向邻域集内个体j的概率pij（t）；

2.4）利用赌的方法选择个体j；

2.5）据式（5）计算每个萤火虫个体的萤光因子，用式（6）计算移动步长；

2.6）进行移动，根据式（3）更新位置；

2.7）根据式（4）更新动态决策域半径的值。

步骤3 判断算法是否到达指定的最大迭代次数，如果是则转向步骤4,否则转向步骤2；

步骤4 输出结果，程序结束。

3 实验结果与分析

3.1 实验操作平台

本实验的程序运行环境为：处理器CPU T5300,主频1.73GHz，内存1GB，操作系统:Windows XP，集成开发环境为 Matlab 7.0。

3.2 实验结果

算法参数设计如下：萤火虫算法种群规模n为50，萤光素挥发系数ρ0.4，萤光素更新率γ0.6，初始荧光素大小l05，感知范围r010，初始步长si（0）0.03，最大步长smax1，最小步长smin10－4,β0.08,nt5，最大迭代次数200。粒子群算法种群规模n为50，惯性权重ω0.5，学习因子c1c22，最大迭代次数200。

对函数F1（x）～F8（x）进行20次独立实验［10］，维数为10。表1列出了这些标准函数的名称及最优值等参数。这8个测试函数如下：

F1（x）∑ni1〖x2i－10cos（2πxi）〗+10

F2（x）∑ni1（0.2x2i+0.1x2isin 2xi）

F3（x）1+∑ni1x2i－∏ni1cos

F4（x）∑n－1i1〖100（xi+1－x2i）2+（xi－1）2〗

F5（x）0.5+－0.5（1+0.001（x21+x22））2

F6（x）∑n－1i1（x2i+x2i+1）0.25×

〖sin（50×（x2i+x2i+2）0.1）+1〗

F7（x）x21+2x22－0.3cos（3πx1）－0.4cos（4πx2）+0.7

F8（x）x21+2x22－0.3cos（3πx1）cos（4πx2）+0.3

表1 标准测试函数

表2列出算法优化函数的最差值、最优值、平均值和平均迭代次数，并与基本萤火虫算法及粒子群算法（Partical Swarm Optimization，PSO）的结果进行比较，其中平均迭代次数为分别进行20次独立实验所求迭代次数的平均值。

表2 GSO与ASGSO,PSO的性能比较

图1～8分别为GSO和ASGSO求函数F1（x）～F8（x）的最小值时函数随迭代次数变化。

图1 函数F1（x）函数值随迭代次数变化

图2 函数F2（x）函数值随迭代次数变化

3.3 结果分析

从表1中可以看出，与基本萤火虫算法相比，自适应步长的萤火虫算法搜索最优值的能力更好，求解的最优值也更接近标准值。对于粒子群算法，基本萤火虫算法和自适应步长的萤火虫算法在高维空间求解能力更强，粒子群算法在二维空间有比较好的搜索能力。对于高维尖峰函数F1（x），ASGSO的最优值为0，求解精度比GSO提高了2个数量级，平均迭代次数减少了26次；而粒子群算法在最大迭代次数内，没有求出理想的解，搜索速度和搜索能力都不及GSO和ASGSO。对于函数F2（x），ASGSO的最优值精度达到e－32，平均求解精度比GSO提高了4个数量级，平均迭代次数减少了15次；而粒子群算法的最优值精度为e－10，比GSO和ASGSO的最优精度都低。对于函数F3（x），ASGSO的最优值为0，平均求解精度比GSO提高了7个数量级，平均迭代次数减少了近一半；而粒子群算法的最优解的精度和基本萤火虫算法相同。对于函数F4（x），ASGSO的最优值精度达到e－7，平均求解精度比GSO提高了1个数量级，但是平均迭代次数相较GSO稍微多几代；粒子群算法在最大迭代次数内，没有求解出来。对于函数F5（x），ASGSO的最优值精度达到e－8，平均求解精度比GSO提高了2个数量级，平均迭代次数减少了20次；粒子群算法最优值为0，求解精度和速度都明显高于GSO和ASGSO。对于函数F6（x），ASGSO的最优值精度达到e－3，平均求解精度比GSO提高了1个数量级，平均迭代次数减少了14次；粒子群算法有较高的求解精度，比ASGSO高了5个数量级。二维多峰函数F7（x）和F8（x），ASGSO的最优值求解精度都达到e－9，平均精度都比GSO提高了4个和3个数量级，迭代次数也有所减少；粒子群算法在二维空间就更具有优势，最优值为0，求解精度提高，迭代次数减少。对于ASGSO和GSO，在高维空间求解多峰函数时，相比于粒子群算法具有更高的精度和速度，ASGSO的寻优能力比GSO更高些；而在二维空间时，粒子群算法的求解精度和寻优速度要比ASGSO和GSO要高很多。

图3 函数F3（x）函数值随迭代次数变化

图4 函数F4（x）函数值随迭代次数变化

从图1可看到ASGSO收敛曲线的下降速度比GSO要快得多，且很快找到最优值，而GSO在第30～第175代很长一段时间陷入局部最优才寻找到最优值。从图2～图5可以看出，ASGSO的收敛速度明显高于GSO，GSO在一定的迭代次数中陷入局部最优很难跳出，而ASGSO由于动态调整了步长能够更快地跳出局部最优更快收敛。从图6可以看出，ASGSO求解精度比GSO提高了很多。图7和图8,ASGSO的收敛曲线下降得比GSO要快，能很快地收敛到全局最优。动态调整步长，可以使算法在收敛初期更快寻优，在陷入局部最优时能很快跳出局部最优，使ASGSO能比GSO更快地收敛到全局最优并提高解的精度。

图5 函数F5（x）函数值随迭代次数变化

图6 函数F6（x）函数值随迭代次数变化

图7 函数F7（x）函数值随迭代次数变化

4 结语

针对基本GSO优化多峰函数时早熟停滞的问题，提出了自适应步长的萤火虫算法。算法中引入了萤光因子概念，通过萤光因子来动态调整步长，使算法避免陷入局部最优，提高寻优速度和精度。通过函数优化实验可以看出，算法是可行的，而且优于基本的萤火虫算法。不仅进行迭代的次数减少了，提高了进化速度，而且获得了更精确的函数值。关于算法的收敛性证明，算法参数的优化及算法的其他应用需要深入研究，也是下一步将要做的工作。

图8 函数F8（x）函数值随迭代次数变化

参考文献:

［1］ KRISHNAND K N，GHOSE D. Glowworm swarm optimisation for simultaneous capture of mutiple local optima of multimodal functions［J］. Swarm Intelligence，2009，3（2）:87-124.

［2］ KRISHNAND K N，GHOSE D. Glowworm swarm optimisation: A new method for optimising multi-modal functions［J］. The International Journal of Computational Intelligence Studies，2009，1（1）:93-119.

［3］ CASTROL，ZUBEN L. Learning and optimization the clonal selection principle evolution computation［J］. IEEE Transactions on Evolutionary Computation,2002,6（3）:34-50.

［4］ 赵吉,孙俊,须文波.一种求解多峰函数优化问题的量子行为粒子群算法［J］.计算机应用,2006,26（12）: 2956-2960.

［5］ 曾国泰.萤火虫最佳化分群演算法［D］. 台北：大同大学资讯经营所,2008.

［6］ 刘彦君,江铭炎.自适应视野和步长的改进人工鱼群算法［J］.计算机工程与应用,2009,45（25）:35-37.

［7］ 王联国,洪敏,赵付青，等.一种改进的人工鱼群算法［J］.计算机工程,2008,34（19）:192-194.

［8］ 王航,薛晓中,孙瑞胜.基于人工鱼群算法的制导炸弹控制系统设计与仿真［J］.弹道学报,2009,28（4）:98-102.

［9］ 王晔,吴小俊,王士同.基于改进人工鱼群算法的RBF网络及其在人脸表情识别中的应用［J］.计算机应用研究,2008,25（9）:2643-2646.

［10］ DEEP K，BANSAL J C. Mean particle swarm optimization for function optimization［J］. The International Journal of Computational Intelligence Studies,2009,1（1）:72-92.