基于同步扰动随机逼近的混合萤火虫算法

李维刚，冯 宁，刘 超，刘 翱

（1.武汉科技大学信息科学与工程学院，湖北武汉，430081；2.武汉科技大学冶金工业过程系统科学湖北省重点实验室，湖北武汉，430065；3.武汉科技大学管理学院，湖北武汉，430081；4.武汉科技大学智能信息处理与实时工业系统湖北省重点实验室，湖北武汉，430065）

基于同步扰动随机逼近的混合萤火虫算法

李维刚1，2，冯 宁1，刘 超1，刘 翱2，3，4

（1.武汉科技大学信息科学与工程学院，湖北武汉，430081；2.武汉科技大学冶金工业过程系统科学湖北省重点实验室，湖北武汉，430065；3.武汉科技大学管理学院，湖北武汉，430081；4.武汉科技大学智能信息处理与实时工业系统湖北省重点实验室，湖北武汉，430065）

针对标准萤火虫算法（FA）中存在的种群过早收敛、容易陷入局部最优等不足，提出一种以memetic算法为框架、将同步扰动随机逼近和萤火虫算法相结合的混合算法（FA-SPSA），即首先使用萤火虫算法对种群进行全局寻优，然后使用同步扰动随机逼近算法对选出的部分最优个体进行局部搜索，从而增强萤火虫算法跳出局部最优解的能力。通过6个标准测试函数对FA-SPSA算法的性能进行检验，并与标准萤火虫算法、果蝇算法、改进的果蝇算法等其他4种算法进行比较，结果表明，FA-SPSA算法在寻优精度、收敛速度、鲁棒性等方面的性能总体上优于对比算法。

萤火虫算法；同步扰动随机逼近（SPSA）；memetic算法；全局搜索；局部搜索

萤火虫算法（firefly algorithm，FA）［1］是一种新型智能优化算法，受萤火虫发光相互吸引的现象启发而设计。经过近几年的发展，萤火虫算法在理论和应用研究方面取得了较为丰富的成果，目前已在云计算调度［2］、路径规划［3］、PID控制器参数优化［4］、流水线调度［5］、钢结构优化［6］等领域得到广泛应用。

尽管萤火虫算法及其改进算法可以解决一些复杂的优化问题，但是它仍然存在收敛过早、容易陷入局部最优、精度不够高等问题，因此不少研究人员从改进位置更新公式和相对吸引度计算方法、自适应步长以及算法混合等诸多方面来弥补标准萤火虫算法的不足。例如:针对大范围搜索中寻优精度低、收敛速度慢等问题，白永珍［3］提出一种参数方差调节萤火虫算法，通过计算种群亮度的方差评估种群的敛散性，根据优化的需要调节参数，从而解决了随机搜索算法的收敛反弹问题，该算法在三维路径规划的实际应用中可以得到较好的优化解；针对PID控制器对复杂系统进行调节时会产生超调、震荡等问题，李远梅等［4］利用萤火虫算法求出目标系统函数的最优值，对比用传统Z-N算法计算得到的PID控制器参数值，该算法可以得到更好的解；张明等［7］在萤火虫进化模式和搜索步长两方面对算法进行改进，并与BP神经网络相结合以平衡算法的收敛速度和精度，改进算法应用于5个标准测试函数，均得到了最优解。杨单等［8］提出在萤火虫算法中加入混沌优化结果以改善个体之间的差异丧失，该混合算法可以解决云计算资源调度问题，并且具有较高的收敛速度。

本文提出一种以文化基因算法（memetic algorithm）为框架、将同步扰动随机逼近和萤火虫算法相结合的混合算法，该算法的主要思路为:采用萤火虫算法对种群进行全局寻优，然后采用同步扰动随机逼近算法对全局算法获得的部分较优个体进行局部搜索，以增强萤火虫算法跳出局部最优解的能力。本文最后通过6个标准测试函数对混合算法的寻优性能进行检验，并与其他几种优化算法进行比较。

1　标准萤火虫算法

考虑以下优化问题:

其中:f（X）为目标函数；X为决策变量；n为决策变量的个数；Lbi和Ubi分别为决策变量的下界和上界。

萤火虫算法相关符号与定义如下:

（1）对于最大值优化问题，萤火虫的发光亮度I与目标函数值f（X）之间的关系为［1］

即二者成正比，萤火虫的发光亮度越大，目标函数值就越好，而对于本文中的最小值问题，则恰好相反。

（2）萤火虫的发光亮度I与距离r之间的关系为

式中:I0为r=0时萤火虫自身的亮度；γ为光强吸收系数。

（3）吸引度β与距离r之间的关系为

式中:β0为r=0时的吸引度初始值。

（4）设萤火虫i、j的位置为Xi、Xj，两者之间的距离公式为

式中:d为空间维度；xi，d为萤火虫i的空间坐标向量中的元素。

（5）位置更新函数为

标准萤火虫算法流程如下:

（1）输入种群规模Popsize、最大进化次数Maxiter、参数β0和γ。

（2）随机初始化萤火虫种群Xi（i=1，2，…，n），计算发光亮度I（Xi），令进化次数iter=0。

（3）种群进化，其程序伪代码为:

2　改进的混合萤火虫算法

根据式（2）和式（3）可知，萤火虫算法是根据萤火虫的亮度来寻找函数最优值，而萤火虫的亮度I（r）和吸引度β（r）都随距离的增大而呈指数级减小，故距离较近的萤火虫个体由于相对吸引度大而靠近，但距离较远的个体相对吸引度就变得很小，同时由式（5）可知，标准萤火虫算法的位置更新函数中只有一个随机扰动项，所以该算法存在种群早熟、容易陷入局部最优等不足。

memetic算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体，其实质是一种进化算法设计框架，通过组合不同的全局搜索算子和局部搜索算子可以构成不同的memetic算法。因此，针对标准萤火虫算法的不足之处，本文根据memetic算法框架提出一种基于同步扰动随机逼近（SPSA）的混合萤火虫算法FASPSA，即采用萤火虫算法进行全局搜索，得到m个最优个体，然后用同步扰动随机逼近算法对这些个体进行局部搜索，以增强算法跳出局部最优解的能力。

2.1同步扰动随机逼近

同步扰动随机逼近是一种求解损失函数最优值问题的有效算法，通过同时扰动所有的待优化参数、再测量两次损失函数的值就可以得到迭代过程中的逼近梯度。

在SPSA算法中，定义待优化的目标函数（即损失函数）为L（θ），梯度函数的逼近公式为

估计值θ的更新公式为

式中:ak=a/（A+k+1）α，其中，a、A、α均为系数。

2.2FA-SPSA算法流程

（1）确定算法参数:种群规模Popsize、最大进化次数Maxiter、运行的次数Runtime、亮度I0、吸引度β0、增益系数a和c，并初始化种群。

（2）利用标准萤火虫算法对种群执行全局搜索，取出m个最优的萤火虫个体。

（3）利用同步扰动随机逼近算法对m个最优萤火虫个体进行局部搜索:

a）生成同时扰动向量Δk；

b）产生两个损失函数测量值L（θk-1+ckΔk）和L（θk-1-ckΔk）；

c）按式（6）进行梯度逼近；

d）按式（7）更新估计值。

3　算法验证

3.1标准测试函数

为验证FA-SPSA算法的寻优性能和收敛速度，本文选取6个标准测试函数（见表1）进行计算，并与标准萤火虫算法（FA）和3种果蝇优化算法（FFO、FFO_LGMS、IFFO）［9］进行性能比较。

表1　标准测试函数［9］Table 1 Benchmark functions

3.2实验环境

Window 7操作系统，CPU Inter（R）Core（TM）i5-2430M，主频2.40 GHz，内存4 GB，编程语言为MATLAB 2012a。

3.3参数设置

为保证结果的公平性及客观性，在测试中，FA和FA-SPSA算法中全局搜索部分采取相同参数:Popsize均分别取30和50，Maxiter=300，β0=1，γ=1。SPSA算法中的参数为:α=0.602，γ′=0.101［10］，最优萤火虫个体数m=1，局部搜索允许的最大迭代次数为40；为了产生更小的扰动量，使函数在寻优过程中保持合适的搜索范围，计算函数f3的增益系数取值为a=0.01、c=1，而计算其他5个函数的增益系数取值为a=0.1、c=1。

3.4结果分析

表2为5种不同算法用于6个标准测试函数（函数维度n=30）得到的平均值和标准差的寻优统计结果，其中:①FA和FA-SPSA算法分别独立运行20次，种群规模为30，函数评价次数达到9000次终止进化；②FFO、FFO_LGMS、IFFO等3种算法的统计结果来源于文献［9］，其最大函数评价次数为50 000。

从表2中可以看出，对于f1、f2、f4、f5、f6这5个函数，与其他4种算法相比，FA-SPSA算法具有更好的寻优性能:在标准测试函数的维度n为30时，FA-SPSA算法不仅优于标准萤火虫算法，而且通过较少的函数评价次数获得的结果要优于3种果蝇算法的结果，表现出更好的鲁棒性和适应性。

对于测试函数f3，FA-SPSA算法比IFFO算法的优化精度低，比其他3种算法的优化精度高。但FA-SPSA算法以较少的计算代价找到了排名第二的较优解，其平均值和标准差与IFFO算法得到的最优结果相差不是很大，可推测在加大计算资源的条件下FA-SPSA算法将会找到更优解。

表2　5种算法的优化结果比较Table 2 Comparison of optimization results by five algorithms

表3为种群规模分别取30和50的情况下，FA和FA-SPSA算法在6个标准测试函数上的平均值和标准差的寻优统计结果，其中:每种算法分别独立运行20次，种群规模为30时，函数评价次数达到9000次终止进化，种群规模为50时，函数评价次数达到15 000次终止进化。种群规模为30时，FA和FA-SPSA算法对于6个标准测试函数的优化收敛曲线如图1所示，种群规模为50的优化收敛曲线与此类似。

结合表3和图1可以看出:①种群规模增大时，FA和FA-SPSA的寻优精度和鲁棒性都有一定提升；②与FA相比，FA-SPSA由于综合了全局搜索和局部搜索的优点而具有更高的寻优精度；③FA-SPSA算法在经过2000～3000次函数评价后基本能找到最优解，收敛速度远快于FA；④FA算法在进化一段时间后的收敛曲线变化缓慢，即在搜索过程中陷入了局部最优，而FASPSA因引入了梯度随机变量扰动使算法能够很快跳出局部最优而继续寻找更优解。

图1　FA和FA-SPSA对于标准测试函数的优化收敛曲线（Popsize=30）Fig.1 Convergence curves of FA and FA-SPSA on benchmark functions（Popsize=30）

综上所述，相比其他几种优化算法，特别是标准萤火虫算法，FA-SPSA在寻优精度、收敛速度和鲁棒性方面都占有优势，因此利用memetic框架将萤火虫算法和同步扰动随机逼近算法结合在一起，十分有效地增强了混合算法的寻优能力。

4　结语

针对萤火虫算法存在过早收敛、容易陷入局部最优、全局探索能力较弱、精度不够高等问题，本文提出基于同步扰动随机逼近的混合萤火虫算法（FA-SPSA）。该算法采用萤火虫算法执行全局搜索，采用同步扰动随机逼近算法对部分已优化个体执行局部搜索，有效提高了算法跳出局部最优并进行全局探索的能力。从6个标准测试函数的对比实验中可以看出，FA-SPSA算法在5个标准测试函数中找到最优解，在另外1个测试函数中找到了与最优解相差不大的次优解，总之，其在寻优精度、收敛速度、鲁棒性方面表现出较优的性能。进一步的研究工作包括:①深入研究种群规模、吸引系数等参数对FA-SPSA寻优性能的影响；②考察FA-SPSA在多峰测试函数中的应用情况；③研究FA-SPSA在云计算调度、工程优化、车间调度等实际问题中的应用。

［1］Yang X S.Firefly algorithms for multimodal optimization［C］//Stochastic Algorithms:Foundations and Applications，SAGA 2009，Lecture Notes in Computer Science.Sapporo，Japan，October 26-28，2009，5792:169-178.

［2］李逦，姚晔，李铁.基于改进型人工萤火虫算法的云计算资源研究［J］.计算机应用研究，2013，30（8）:2298-2300.

［3］白永珍.基于参数方差调节萤火虫算法的三维路径规划［J］.计算机系统应用，2015，24（5）:92-99.

［4］李远梅，张宏立.基于改进萤火虫算法PID控制器参数优化研究［J］.计算机仿真，2015，32（9）:356-359.

［5］李永林，叶春明.基于萤火虫算法的零等待流水线调度优化［J］.机械设计与研究，2013，29（6）:50-54.

［7］张明，张树群，雷兆宜.改进的萤火虫算法在神经网络中的应用［J/OL］.计算机工程与应用.（2015-12-03）［2016-01-05］.http://www.cnki.net/kcms/detail/11.2127.TP.20151202.0931.012.html.DOI: 10.3778/j.issn.1002-8331.1508-0134.

［8］杨单，李超锋，杨健.基于改进混沌萤火虫算法的云计算资源调度［J］.计算机工程，2015，41（2）: 17-20，25.

［9］Pan Q K，Sang H Y，Duan J H，et al.An improved fruit fly optimization algorithm for continuous function optimization problems［J］.Knowledge-Based Systems，2014，62（5）:69-83.

［10］Spall J C.Multivariate stochastic approximation using a simultaneous perturbation gradient approximation［J］.IEEE Transactions on Automatic Control，1992，37（3）:332-341.

［责任编辑 尚 晶］

Hybrid firefly algorithm based on simultaneous perturbation stochastic approximation

Li Weigang1，2，Feng Ning1，Liu Chao1，Liu Ao2，3，4
（1.College of Information Science and Engineering，Wuhan University of Science and Technology，Wuhan 430081，China；2.Hubei Province Key Laboratory of Systems Science in Metallurgical Process，Wuhan University of Science and Technology，Wuhan 430065，China；3.College of Management，Wuhan University of Science and Technology，Wuhan 430081，China；4.Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System，Wuhan University of Science and Technology，Wuhan 430065，China）

To overcome such disadvantages as premature convergence and falling into local optimum easily in the basic firefly algorithm（FA），a hybrid algorithm named as FA-SPSA is presented，which introduces simultaneous perturbation stochastic approximation（SPSA）into FA under the frame of memetic algorithm.Firstly，FA is employed to search for global optimal solutions.Then SPSA is used in the local search aiming at the selected part of the best individuals，which enhances the ability of firefly algorithm to jump out of local optimum.The performances of FA-SPSA are testified by six benchmark functions and the calculation results are compared with those of basic firefly algorithm，fruit fly optimization and two improved fruit fly optimization algorithms，which indicates that FASPSA is generally superior to the other four algorithms in optimization accuracy，convergence speed and robustness.

firefly algorithm；SPSA；memetic algorithm；global search；local search

TP301.6

A

1674-3644（2016）05-0376-06

2016-03-30

湖北省教育厅科学技术研究计划重点项目（D20161103）；武汉科技大学冶金工业过程系统科学湖北省重点实验室开放基金资助项目（Z201501）；武汉科技大学智能信息处理与实时工业系统湖北省重点实验室开放基金面上项目（2016znss18B）；武汉科技大学青年科技晨光计划资助项目（2016070204010099）.

李维刚（1977-），男，武汉科技大学教授，博士.E-mail:liweigang.luck@foxmail.com

刘 翱（1987-），男，武汉科技大学讲师，博士.E-mail:liuao@wust.edu.cn