螢火蟲算法收斂分析*

陸克中，孫　俊

1.池州學(xué)院 計(jì)算機(jī)科學(xué)系，安徽 池州 247100

2.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230026

3.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214021

螢火蟲算法收斂分析*

陸克中1,2+，孫俊3

1.池州學(xué)院 計(jì)算機(jī)科學(xué)系，安徽 池州 247100

2.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230026

3.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214021

LU Kezhong,SUN Jun.Convergence analysis of firefly algorithm.Journal of Frontiers of Computer Science and Technology,2016,10(2)：293-300.

為了系統(tǒng)地分析螢火蟲算法（firefly algorithm,FA），首先對(duì)FA算法的收斂過程進(jìn)行了分析，得出FA算法收斂的兩個(gè)一般條件：隨機(jī)擾動(dòng)項(xiàng)的數(shù)學(xué)期望等于0；最大吸引度β0∈(0,2)，通常取β0∈(0,1]，并且β0越大，算法收斂速度越快。接著根據(jù)隨機(jī)算法的收斂準(zhǔn)則，證明了FA算法不具有全局收斂特性。然后應(yīng)用數(shù)學(xué)歸納法，結(jié)合夾逼定理及反證法，從理論上證明了FA算法收斂于群體最優(yōu)解，是一個(gè)局部收斂算法。最后對(duì)不同條件下的FA算法收斂性進(jìn)行了仿真，實(shí)驗(yàn)結(jié)果與理論結(jié)果一致，佐證了理論分析的正確性。

螢火蟲算法；收斂分析；局部收斂

1　引言

2008年，劍橋大學(xué)的Yang[1]受螢火蟲利用自身熒光傳遞信息這種群體行為的啟發(fā)，提出了一種新穎的群智能優(yōu)化算法——螢火蟲算法（firefly algorithm，F(xiàn)A）。相比較而言，F(xiàn)A算法具有結(jié)構(gòu)簡(jiǎn)單，調(diào)節(jié)參數(shù)少，收斂速度快，易于操作實(shí)現(xiàn)等特點(diǎn)[2]，自提出以來，已經(jīng)在圖形圖像處理[3]、聚類分析[4]、機(jī)械設(shè)計(jì)[5]、任務(wù)調(diào)度[6]、證券投資[7]、軟件測(cè)試[8]等領(lǐng)域得到了應(yīng)用，并取得了較好的效果。

當(dāng)前，國(guó)內(nèi)外學(xué)者對(duì)FA算法的研究越來越多，但主要集中在算法自身的改進(jìn)，以及算法在不同領(lǐng)域的應(yīng)用上，還缺乏對(duì)算法進(jìn)行系統(tǒng)的理論分析，特別是算法的收斂條件與收斂特性方面。現(xiàn)有的一些對(duì)FA算法的分析均是基于實(shí)驗(yàn)方法進(jìn)行的，如文獻(xiàn)[9]通過對(duì)FA算法的參數(shù)進(jìn)行分析，提出了基于距離的光吸系數(shù)等多種參數(shù)調(diào)節(jié)方法，以提高算法的自適應(yīng)能力；文獻(xiàn)[10]基于5個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，分析了算法的參數(shù)選擇、群體規(guī)模以及目標(biāo)函數(shù)對(duì)算法性能的影響，并指出難以找到對(duì)所有問題均有效的統(tǒng)一參數(shù)調(diào)節(jié)方法；文獻(xiàn)[11]通過實(shí)驗(yàn)指出，F(xiàn)A算法的收斂效果與螢火蟲群體規(guī)模以及算法的迭代次數(shù)直接成正比。文獻(xiàn)[12]通過對(duì)一些標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真，指出FA算法存有早熟收斂，后期收斂速度慢，求解精度較低等缺點(diǎn)；文獻(xiàn)[13]在對(duì)算法參數(shù)進(jìn)行分析的基礎(chǔ)上，引入混沌策略，調(diào)節(jié)算法的參數(shù)，增強(qiáng)算法的全局搜索能力；還有一些在分析FA算法性能基礎(chǔ)上，引入其他算法，取長(zhǎng)補(bǔ)短，構(gòu)成混合優(yōu)化算法[14-15]。

由于FA算法還缺乏系統(tǒng)性分析，特別是收斂性方面的理論證明還未見報(bào)道，這在一定程度上制約了算法的研究與發(fā)展。為此，本文在對(duì)FA算法進(jìn)行系統(tǒng)分析的基礎(chǔ)上，給出了算法收斂性分析的理論證明，并應(yīng)用實(shí)驗(yàn)方法對(duì)算法的不同收斂情況進(jìn)行了仿真分析。

2　基本FA算法

Yang模擬自然界螢火蟲發(fā)光模式與信息交換行為，提出了FA算法。其中熒光亮度和吸引度是FA算法中兩個(gè)關(guān)鍵因素。假設(shè)螢火蟲的群體規(guī)模為m，問題空間為d維，第i只螢火蟲在d維空間中的位置表示為xi=()

xi1,xi2,…,xid。

定義1熒光亮度：

式中，I0為螢火蟲的最大熒光亮度，即為r=0處的自身熒光亮度，取決于需要尋優(yōu)的目標(biāo)函數(shù)值，一般用式（2）表示，f(x)越好則I0就越高；γ為光強(qiáng)吸收因子，表示熒光亮度受傳播距離與傳播媒介的影響而變化的特性，理論上γ∝[0,∞]，但在實(shí)際應(yīng)用中，γ=O(1)，常取[0.01,100]之間的某一常數(shù)；r表示兩只螢火蟲之間的空間距離，一般用式（3）的歐式距離表示。

其中，f為待優(yōu)化函數(shù)；x為某一螢火蟲的空間位置。

定義2吸引度：

式中，β0為最大吸引度，即光源（r=0處）的吸引度，通常設(shè)定為1；γ和r的意義同定義1。

定義3位置更新公式：

上式表示的是螢火蟲i受螢火蟲j的吸引，而發(fā)生位置改變。其中，t為迭代次數(shù)；xi與xj分別表示螢火蟲i與j的空間位置；β表示螢火蟲j對(duì)螢火蟲i的相對(duì)吸引度；α為步長(zhǎng)因子，α∝[0,1]；εi是一個(gè)服從高斯分布或均勻分布的隨機(jī)向量，其簡(jiǎn)化形式為rand()-1/2，rand()為[0,1]內(nèi)服從均勻分布的隨機(jī)數(shù)。

FA算法流程描述如下：

步驟1設(shè)置參數(shù)γ，β0和最大迭代次數(shù)MaxGen；

步驟2初始化螢火蟲群體xi(i=1,2,…,n) ，并計(jì)算xi的目標(biāo)函數(shù) f(xi) ，將其定義為熒光亮度Ii；

步驟3由式（3）計(jì)算螢火蟲xi、xj之間的距離rij；

步驟4由式（4）計(jì)算螢火蟲xj對(duì)xi的吸引度β；

步驟5由式（5）更新螢火蟲xi位置；

步驟6若達(dá)到最大迭代次數(shù)，則停止，否則搜索循環(huán)次數(shù)加1，轉(zhuǎn)步驟3。

3　FA算法收斂分析

對(duì)于式（5），可分為用于算法收斂的Part1部分和用于個(gè)體局部擾動(dòng)的Part2部分：

3.1FA算法收斂條件分析

對(duì)于Part2部分，個(gè)體在不斷迭代過程中，αεi將不斷地進(jìn)行累加操作，即∑Part2=αε1+αε2+…+αεt。

Fig.1　Two kinds of distance between fireflies圖1　螢火蟲個(gè)體兩種距離關(guān)系

從圖1可明顯看出，因螢火蟲個(gè)體在xi與xj之間移動(dòng)，所以取左邊部分xi′為xi的更新位置，即要求0＜β≤1，也即要求：

由上可得：若FA收斂，則0＜β0＜2，一般取0＜β0≤1。□

Fig.2　Trajectories of fireflies圖2　螢火蟲個(gè)體運(yùn)動(dòng)軌跡

3.2FA算法全局收斂性分析

文獻(xiàn)[16]在對(duì)隨機(jī)優(yōu)化算法進(jìn)行深入研究的基礎(chǔ)上，給出了隨機(jī)算法的求最小問題的收斂準(zhǔn)則。對(duì)于優(yōu)化問題＜S,f＞，隨機(jī)優(yōu)化算法A在第k次迭代的結(jié)果為xk，下一次迭代的結(jié)果為xk+1=A() xk,ξ，其中S是可行解空間，f為目標(biāo)函數(shù)，ξ為算法A迭代過程中得到的解。

3.3FA算法局部收斂性分析

由定理4，F(xiàn)A算法不具有全局收斂特性，下面考察FA算法的局部收斂情況。FA算法的局部收斂性分析是在滿足定理1與定理2的條件下進(jìn)行的。

定理5次優(yōu)解收斂于群體最優(yōu)解。

推論2 FA算法是一個(gè)局部收斂算法。

證明 由定理7，F(xiàn)A算法收斂于群體最優(yōu)解，由于群體最優(yōu)解不一定是全局最優(yōu)解，其解與群體的位置有關(guān)。若群體散落在全局最優(yōu)解附近，其群體最優(yōu)解往往就是全局最優(yōu)解，若群體散落在局部極值點(diǎn)附近，其群體最優(yōu)解往往就是局部最優(yōu)解，所以FA算法是一個(gè)局部收斂算法?！?/p>

4　實(shí)驗(yàn)分析

為了直觀地考察FA算法的收斂情況，這里使用實(shí)驗(yàn)的方法對(duì)不同條件下的算法進(jìn)行了仿真，仿真所使用的函數(shù)為式（48）的四峰函數(shù)，此函數(shù)存在4個(gè)極大值，坐標(biāo)分別是(0,-4)、(0,0)、(-4,4)、(4,4)，對(duì)應(yīng)的極值分別為2、2、1、1。

依據(jù)前面的理論分析，設(shè)定如下7個(gè)仿真條件，用以考察FA算法在不同參數(shù)設(shè)置下的收斂情況。其中共同的參數(shù)有α=0.2，γ=0.1，群體規(guī)模m=12，最大迭代次數(shù)MaxGen=50。

（1）β0=0.1，ε=rand()-1/2，range=[-5,5]；

（2）β0=1，ε=rand()-1/2，range=[-5,5]；

（3）β0=1.1，ε=rand()-1/2，range=[-5,5]；

（4）β0=1.9，ε=rand()-1/2，range=[-5,5]；

（5）β0=10，ε=rand()-1/2，range=[-5,5]；

（6）β0=1，ε=rand()-1/2，range=[0,5]；

（7）β0=1，ε=rand()，range=[-5,5]。

（1）～（5）這5種參數(shù)設(shè)置，用于考察β0在不同范圍內(nèi)對(duì)算法收斂情況的影響；情況（6）用于考察算法的全局收斂能力；情況（7）用于考察E(ε)≠0時(shí)，算法的收斂情況。情況（7）的實(shí)驗(yàn)結(jié)果見圖3。

Fig.3　Convergence curves under different parameters圖3　不同參數(shù)下的收斂曲線

參數(shù)設(shè)置的（1）～（4）情況中0＜β0＜2，從圖3中可明顯看出，F(xiàn)A算法收斂到全局最優(yōu)解2，與定理2一致。其中，β0=1時(shí)明顯比 β0=0.1時(shí)收斂速率要快，這是由于當(dāng)0＜β0≤1時(shí)，由式（11）可知，β0越大，1-β0就越小，則新的螢火蟲個(gè)體就更靠近較優(yōu)個(gè)體，故而收斂越快，反之，收斂越慢。情況（3）與（4）滿足1≤β0＜2，是螢火蟲個(gè)體在背離較優(yōu)個(gè)體一側(cè)運(yùn)動(dòng)的情況，β0越大，則||1-β0就越小，由式（12）知，算法收斂越快，反之，收斂越慢，圖3也印證了這個(gè)結(jié)論。當(dāng) β0=5時(shí)，對(duì)應(yīng)情況（5），此時(shí) β0不滿足定理2中的0＜β0＜2條件，從而螢火蟲個(gè)體不能向較優(yōu)個(gè)體靠近，而是遠(yuǎn)離較優(yōu)個(gè)體，缺失了群體啟發(fā)信息，導(dǎo)致算法發(fā)散。從圖3中可以看出，情況（5）的曲線出現(xiàn)了震蕩，特別是在迭代后期，算法還偏離了極值點(diǎn)而呈發(fā)散態(tài)。當(dāng)算法的初始解在局部極值點(diǎn)附近時(shí)，如情況（6），初始解范圍是[0,5]，這樣初始解已不在全局最優(yōu)解附近，而是在局部極值點(diǎn)（4,4）附近，算法經(jīng)多次運(yùn)行測(cè)試，即使MaxGen=10 000，其結(jié)果均呈現(xiàn)如圖3所示情況，收斂于局部極值點(diǎn)1，反映了FA算法的局部收斂特性，這與定理4關(guān)于FA算法不具有全局收斂性一致，也印證了推論2：FA算法是一個(gè)局部收斂算法。情況（7）考察的是E(ε)≠0時(shí)算法的收斂情況，從圖3中可以看出，由于ε=rand()，致使E(ε)≠0，這樣在迭代過程中，因累積效應(yīng)，使得最終的螢火蟲群體沒有像情況（2）那樣，聚集在全局最優(yōu)解2上，而是隨著迭代的進(jìn)行，逐漸偏離最優(yōu)解，呈現(xiàn)明顯發(fā)散狀態(tài)，其情況與定理1的結(jié)論一致。

5　結(jié)束語(yǔ)

本文從FA算法收斂過程入手，對(duì)FA算法的收斂條件與收斂性進(jìn)行了分析與論證，得出算法收斂的兩個(gè)條件：（1）隨機(jī)擾動(dòng)項(xiàng)的數(shù)學(xué)期望E(ε)=0；（2）最大吸引度 β0限制在0＜β0＜2，且一般取0＜β0≤1，并推論出螢火蟲個(gè)體以折線形式向最優(yōu)個(gè)體靠近的結(jié)論。接著利用隨機(jī)算法的收斂準(zhǔn)則，證明了FA算法不具有全局收斂特性。然后在以上基礎(chǔ)上，結(jié)合夾逼定理，應(yīng)用數(shù)學(xué)歸納法，從理論上證明了FA算法收斂于群體最優(yōu)解，以及局部收斂的結(jié)論。最后應(yīng)用實(shí)驗(yàn)方法，對(duì)不同條件下的FA算法收斂性進(jìn)行了仿真，仿真結(jié)果與理論結(jié)果保持一致，進(jìn)一步佐證了理論分析結(jié)論的正確性。今后，將進(jìn)一步改進(jìn)FA算法，特別是對(duì)于FA算法的全局收斂能力方面，以提升FA算法的優(yōu)化效果。

References:

[1]Yang Xinshe.Nature-inspired metaheuristic algorithms[M]. Beckington:Luniver Press,2008:81-96.

[2]Yang Xinshe.Firefly algorithms for multimodal optimization[C]//LNCS 5792:Proceedings of the 5th International Conference on Stochastic Algorithms:Foundation and Applications,Sapporo,Japan,Oct 26-28,2009.Berlin,Heidelberg:Springer,2009:169-178.

[3]Horng M H,Liou R J.Multilevel minimum cross entropy threshold selection based on the firefly algorithm[J].Expert Systems withApplications,2011,38(12):14805-14811.

[4]Senthilnath J,Omkar S N,Mani V.Clustering using firefly algorithm:performance study[J].Swarm and Evolutionary Computation,2011,1(3):164-171.

[5]Gandomi A H,Yang Xinshe,Alavi A H.Mixed variable structural optimization using firefly algorithm[J].Computers and Structures,2011,89(23/24):2325-2336.

[6]Yang Xinshe,Hosseini S S S,Gandomi A H.Firefly algorithm for solving non-convex economic dispatch problems with valve loading effect[J].Applied Soft Computing,2012, 12(3):1180-1186.

[7]Kazema A,Sharifia E,Hussain F K,et al.Support vector regression with chaos-based firefly algorithm for stock market price forecasting[J].Applied Soft Computing,2013, 13(2):947-958.

[8]Srivatsava P R,Mallikarjun B,Yang Xinshe.Optimal test sequence generation using firefly algorithm[J].Swarm and Evolutionary Computation,2013,8:44-53.

[9]Cheung N J,Ding Xueming,Shen Hongbin.Adaptive firefly algorithm:parameter analysis and its application[J]. PLoS ONE,2014,9(11):1-12.

[10]Arora S,Singh S.The firefly optimization algorithm:convergence analysis and parameter selection[J].International Journal of ComputerApplications,2013,69(3):48-52.

[11]Yang Xinshe.Firefly algorithm stochastic test functions and design optimization[J].International Journal of Bio-Inspired Computation,2010,2(2):78-84.

[12]?ukasik S,?ak S.Firefly algorithm for continuous constrained optimization tasks[C]//LNCS 5796:Proceedings of the 1st International Conference on Computational Collective Intelligence,Wroclaw,Poland,Oct 5-7,2009.Berlin, Heidelberg:Springer,2009:97-106.

[13]Gandomi A H,Yang Xinshe,Talatahari S,et al.Firefly algorithm with chaos[J].Communications in Nonlinear Science and Numerical Simulation,2013,18(1):89-98.

[14]Yang Xinshe.Firefly algorithm,Levy flights and global optimization[M]//Research and Development in Intelligent Systems XXVI.London,UK:Springer,2010:209-218.

[15]Yu Shuhao,Su Shoubao.Research and application of chaotic glowworm swarm optimization algorithm[J].Journal of Frontiers of Computer Science and Technology,2014,8(3): 352-358.

[16]Solis F,Wets R.Minimization by random search techniques[J]. Mathematics of Operations Research,1981,6(1):19-30.

附中文參考文獻(xiàn)：

[15]郁書好,蘇守寶.混沌螢火蟲優(yōu)化算法的研究及應(yīng)用[J].計(jì)算機(jī)科學(xué)與探索,2014,8(3):352-358.

陸克中（1976—），男，安徽樅陽(yáng)人，2005年于江南大學(xué)獲得碩士學(xué)位，現(xiàn)為池州學(xué)院副教授，中國(guó)科學(xué)技術(shù)大學(xué)訪問學(xué)者，主要研究領(lǐng)域?yàn)橹悄苡?jì)算，生物信息學(xué)等。發(fā)表學(xué)術(shù)論文16篇，主持安徽省自然科學(xué)研究項(xiàng)目2項(xiàng)。

孫?。?971—），男，江蘇無錫人，2009年于江南大學(xué)獲得博士學(xué)位，現(xiàn)為江南大學(xué)副教授、碩士生導(dǎo)師，主要研究領(lǐng)域?yàn)檫M(jìn)化計(jì)算，人工智能等。發(fā)表學(xué)術(shù)論文30余篇，主持國(guó)家自然科學(xué)基金項(xiàng)目1項(xiàng)。

ConvergenceAnalysis of FireflyAlgorithm*

LU Kezhong1,2+,SUN Jun3
1.Department of Computer Science,Chizhou University,Chizhou,Anhui 247100,China
2.School of Computer Science and Technology,University of Science and Technology of China,Hefei 230026,China
3.School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214021,China
+Corresponding author:E-mail:luke76@163.com

The purpose of this paper is to analyze the firefly algorithm(FA)systematically.Firstly,two general convergence conditions are obtained by analyzing the convergence process of FA.One is that mathematical expectation of random disturbance term is equal to 0,the other is that maximum attractiveness valueβ0belongs to(0,2),and usually belongs to(0,1],and the moreβ0value,the faster convergence speed.Nextly,according to the criterion of convergence of random algorithm,this paper proves that the FA is not a globally convergent algorithm.Then,this paper theoretically proves that the FA converges to the local optimal solution by using mathematical induction,sandwich theorem and apagoge.Finally,the convergence processes of FA under different conditions are simulated.The experimental results agree well with the theoretical results and prove the correctness of the theory analysis.

firefly algorithm;convergence analysis;local convergence

2015-04,Accepted 2015-06.

LU Kezhong was born in 1976.He the M.S.degree in computer application from Jiangnan University in 2005.Now he is an associate professor at Chizhou University.His research interests include intelligent computing and bioinformatics,etc.

SUN Jun was born in 1971.He the Ph.D.degree in control theory and control engineering from Jiangnan University in 2009.Now he is an associate professor and M.S.supervisor at Jiangnan University.His research interests include evolutionary computing and artificial intelligence,etc.

10.3778/j.issn.1673-9418.1504051

*The National Natural Science Foundation of China under Grant No.61170119(國(guó)家自然科學(xué)基金);the Natural Science Foundation ofAnhui Province under Grant No.KJ2016Z264(安徽省自然科學(xué)研究項(xiàng)目).

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-06-29,http://www.cnki.net/kcms/detail/11.5602.TP.20150629.1544.001.html

A

TP301.6