螢火蟲算法收斂分析*

陸克中，孫　俊

1.池州學院 計算機科學系，安徽 池州 247100

2.中國科學技術大學 計算機科學與技術學院，合肥 230026

3.江南大學 物聯網工程學院，江蘇 無錫 214021

螢火蟲算法收斂分析*

陸克中1,2+，孫俊3

1.池州學院 計算機科學系，安徽 池州 247100

2.中國科學技術大學 計算機科學與技術學院，合肥 230026

3.江南大學 物聯網工程學院，江蘇 無錫 214021

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

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

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

1　引言

2008年，劍橋大學的Yang[1]受螢火蟲利用自身熒光傳遞信息這種群體行為的啟發，提出了一種新穎的群智能優化算法——螢火蟲算法（firefly algorithm，FA）。相比較而言，FA算法具有結構簡單，調節參數少，收斂速度快，易于操作實現等特點[2]，自提出以來，已經在圖形圖像處理[3]、聚類分析[4]、機械設計[5]、任務調度[6]、證券投資[7]、軟件測試[8]等領域得到了應用，并取得了較好的效果。

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

由于FA算法還缺乏系統性分析，特別是收斂性方面的理論證明還未見報道，這在一定程度上制約了算法的研究與發展。為此，本文在對FA算法進行系統分析的基礎上，給出了算法收斂性分析的理論證明，并應用實驗方法對算法的不同收斂情況進行了仿真分析。

2　基本FA算法

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

xi1,xi2,…,xid。

定義1熒光亮度：

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

其中，f為待優化函數；x為某一螢火蟲的空間位置。

定義2吸引度：

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

定義3位置更新公式：

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

FA算法流程描述如下：

步驟1設置參數γ，β0和最大迭代次數MaxGen；

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

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

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

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

步驟6若達到最大迭代次數，則停止，否則搜索循環次數加1，轉步驟3。

3　FA算法收斂分析

對于式（5），可分為用于算法收斂的Part1部分和用于個體局部擾動的Part2部分：

3.1FA算法收斂條件分析

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

Fig.1　Two kinds of distance between fireflies圖1　螢火蟲個體兩種距離關系

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

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

Fig.2　Trajectories of fireflies圖2　螢火蟲個體運動軌跡

3.2FA算法全局收斂性分析

文獻[16]在對隨機優化算法進行深入研究的基礎上，給出了隨機算法的求最小問題的收斂準則。對于優化問題＜S,f＞，隨機優化算法A在第k次迭代的結果為xk，下一次迭代的結果為xk+1=A() xk,ξ，其中S是可行解空間，f為目標函數，ξ為算法A迭代過程中得到的解。

3.3FA算法局部收斂性分析

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

定理5次優解收斂于群體最優解。

推論2 FA算法是一個局部收斂算法。

證明 由定理7，FA算法收斂于群體最優解，由于群體最優解不一定是全局最優解，其解與群體的位置有關。若群體散落在全局最優解附近，其群體最優解往往就是全局最優解，若群體散落在局部極值點附近，其群體最優解往往就是局部最優解，所以FA算法是一個局部收斂算法。□

4　實驗分析

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

依據前面的理論分析，設定如下7個仿真條件，用以考察FA算法在不同參數設置下的收斂情況。其中共同的參數有α=0.2，γ=0.1，群體規模m=12，最大迭代次數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種參數設置，用于考察β0在不同范圍內對算法收斂情況的影響；情況（6）用于考察算法的全局收斂能力；情況（7）用于考察E(ε)≠0時，算法的收斂情況。情況（7）的實驗結果見圖3。

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

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

5　結束語

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

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.

附中文參考文獻：

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

陸克中（1976—），男，安徽樅陽人，2005年于江南大學獲得碩士學位，現為池州學院副教授，中國科學技術大學訪問學者，主要研究領域為智能計算，生物信息學等。發表學術論文16篇，主持安徽省自然科學研究項目2項。

孫俊（1971—），男，江蘇無錫人，2009年于江南大學獲得博士學位，現為江南大學副教授、碩士生導師，主要研究領域為進化計算，人工智能等。發表學術論文30余篇，主持國家自然科學基金項目1項。

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(國家自然科學基金);the Natural Science Foundation ofAnhui Province under Grant No.KJ2016Z264(安徽省自然科學研究項目).

CNKI網絡優先出版：2015-06-29,http://www.cnki.net/kcms/detail/11.5602.TP.20150629.1544.001.html

A

TP301.6