基于同步擾動隨機(jī)逼近的混合螢火蟲算法

李維剛，馮 寧，劉 超，劉 翱

（1.武漢科技大學(xué)信息科學(xué)與工程學(xué)院，湖北武漢，430081；2.武漢科技大學(xué)冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點實驗室，湖北武漢，430065；3.武漢科技大學(xué)管理學(xué)院，湖北武漢，430081；4.武漢科技大學(xué)智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室，湖北武漢，430065）

基于同步擾動隨機(jī)逼近的混合螢火蟲算法

李維剛1，2，馮 寧1，劉 超1，劉 翱2，3，4

（1.武漢科技大學(xué)信息科學(xué)與工程學(xué)院，湖北武漢，430081；2.武漢科技大學(xué)冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點實驗室，湖北武漢，430065；3.武漢科技大學(xué)管理學(xué)院，湖北武漢，430081；4.武漢科技大學(xué)智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室，湖北武漢，430065）

針對標(biāo)準(zhǔn)螢火蟲算法（FA）中存在的種群過早收斂、容易陷入局部最優(yōu)等不足，提出一種以memetic算法為框架、將同步擾動隨機(jī)逼近和螢火蟲算法相結(jié)合的混合算法（FA-SPSA），即首先使用螢火蟲算法對種群進(jìn)行全局尋優(yōu)，然后使用同步擾動隨機(jī)逼近算法對選出的部分最優(yōu)個體進(jìn)行局部搜索，從而增強螢火蟲算法跳出局部最優(yōu)解的能力。通過6個標(biāo)準(zhǔn)測試函數(shù)對FA-SPSA算法的性能進(jìn)行檢驗，并與標(biāo)準(zhǔn)螢火蟲算法、果蠅算法、改進(jìn)的果蠅算法等其他4種算法進(jìn)行比較，結(jié)果表明，F(xiàn)A-SPSA算法在尋優(yōu)精度、收斂速度、魯棒性等方面的性能總體上優(yōu)于對比算法。

螢火蟲算法；同步擾動隨機(jī)逼近（SPSA）；memetic算法；全局搜索；局部搜索

螢火蟲算法（firefly algorithm，F(xiàn)A）［1］是一種新型智能優(yōu)化算法，受螢火蟲發(fā)光相互吸引的現(xiàn)象啟發(fā)而設(shè)計。經(jīng)過近幾年的發(fā)展，螢火蟲算法在理論和應(yīng)用研究方面取得了較為豐富的成果，目前已在云計算調(diào)度［2］、路徑規(guī)劃［3］、PID控制器參數(shù)優(yōu)化［4］、流水線調(diào)度［5］、鋼結(jié)構(gòu)優(yōu)化［6］等領(lǐng)域得到廣泛應(yīng)用。

盡管螢火蟲算法及其改進(jìn)算法可以解決一些復(fù)雜的優(yōu)化問題，但是它仍然存在收斂過早、容易陷入局部最優(yōu)、精度不夠高等問題，因此不少研究人員從改進(jìn)位置更新公式和相對吸引度計算方法、自適應(yīng)步長以及算法混合等諸多方面來彌補標(biāo)準(zhǔn)螢火蟲算法的不足。例如:針對大范圍搜索中尋優(yōu)精度低、收斂速度慢等問題，白永珍［3］提出一種參數(shù)方差調(diào)節(jié)螢火蟲算法，通過計算種群亮度的方差評估種群的斂散性，根據(jù)優(yōu)化的需要調(diào)節(jié)參數(shù)，從而解決了隨機(jī)搜索算法的收斂反彈問題，該算法在三維路徑規(guī)劃的實際應(yīng)用中可以得到較好的優(yōu)化解；針對PID控制器對復(fù)雜系統(tǒng)進(jìn)行調(diào)節(jié)時會產(chǎn)生超調(diào)、震蕩等問題，李遠(yuǎn)梅等［4］利用螢火蟲算法求出目標(biāo)系統(tǒng)函數(shù)的最優(yōu)值，對比用傳統(tǒng)Z-N算法計算得到的PID控制器參數(shù)值，該算法可以得到更好的解；張明等［7］在螢火蟲進(jìn)化模式和搜索步長兩方面對算法進(jìn)行改進(jìn)，并與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合以平衡算法的收斂速度和精度，改進(jìn)算法應(yīng)用于5個標(biāo)準(zhǔn)測試函數(shù)，均得到了最優(yōu)解。楊單等［8］提出在螢火蟲算法中加入混沌優(yōu)化結(jié)果以改善個體之間的差異喪失，該混合算法可以解決云計算資源調(diào)度問題，并且具有較高的收斂速度。

本文提出一種以文化基因算法（memetic algorithm）為框架、將同步擾動隨機(jī)逼近和螢火蟲算法相結(jié)合的混合算法，該算法的主要思路為:采用螢火蟲算法對種群進(jìn)行全局尋優(yōu)，然后采用同步擾動隨機(jī)逼近算法對全局算法獲得的部分較優(yōu)個體進(jìn)行局部搜索，以增強螢火蟲算法跳出局部最優(yōu)解的能力。本文最后通過6個標(biāo)準(zhǔn)測試函數(shù)對混合算法的尋優(yōu)性能進(jìn)行檢驗，并與其他幾種優(yōu)化算法進(jìn)行比較。

1　標(biāo)準(zhǔn)螢火蟲算法

考慮以下優(yōu)化問題:

其中:f（X）為目標(biāo)函數(shù)；X為決策變量；n為決策變量的個數(shù)；Lbi和Ubi分別為決策變量的下界和上界。

螢火蟲算法相關(guān)符號與定義如下:

（1）對于最大值優(yōu)化問題，螢火蟲的發(fā)光亮度I與目標(biāo)函數(shù)值f（X）之間的關(guān)系為［1］

即二者成正比，螢火蟲的發(fā)光亮度越大，目標(biāo)函數(shù)值就越好，而對于本文中的最小值問題，則恰好相反。

（2）螢火蟲的發(fā)光亮度I與距離r之間的關(guān)系為

式中:I0為r=0時螢火蟲自身的亮度；γ為光強吸收系數(shù)。

（3）吸引度β與距離r之間的關(guān)系為

式中:β0為r=0時的吸引度初始值。

（4）設(shè)螢火蟲i、j的位置為Xi、Xj，兩者之間的距離公式為

式中:d為空間維度；xi，d為螢火蟲i的空間坐標(biāo)向量中的元素。

（5）位置更新函數(shù)為

標(biāo)準(zhǔn)螢火蟲算法流程如下:

（1）輸入種群規(guī)模Popsize、最大進(jìn)化次數(shù)Maxiter、參數(shù)β0和γ。

（2）隨機(jī)初始化螢火蟲種群Xi（i=1，2，…，n），計算發(fā)光亮度I（Xi），令進(jìn)化次數(shù)iter=0。

（3）種群進(jìn)化，其程序偽代碼為:

2　改進(jìn)的混合螢火蟲算法

根據(jù)式（2）和式（3）可知，螢火蟲算法是根據(jù)螢火蟲的亮度來尋找函數(shù)最優(yōu)值，而螢火蟲的亮度I（r）和吸引度β（r）都隨距離的增大而呈指數(shù)級減小，故距離較近的螢火蟲個體由于相對吸引度大而靠近，但距離較遠(yuǎn)的個體相對吸引度就變得很小，同時由式（5）可知，標(biāo)準(zhǔn)螢火蟲算法的位置更新函數(shù)中只有一個隨機(jī)擾動項，所以該算法存在種群早熟、容易陷入局部最優(yōu)等不足。

memetic算法是一種基于種群的全局搜索和基于個體的局部啟發(fā)式搜索的結(jié)合體，其實質(zhì)是一種進(jìn)化算法設(shè)計框架，通過組合不同的全局搜索算子和局部搜索算子可以構(gòu)成不同的memetic算法。因此，針對標(biāo)準(zhǔn)螢火蟲算法的不足之處，本文根據(jù)memetic算法框架提出一種基于同步擾動隨機(jī)逼近（SPSA）的混合螢火蟲算法FASPSA，即采用螢火蟲算法進(jìn)行全局搜索，得到m個最優(yōu)個體，然后用同步擾動隨機(jī)逼近算法對這些個體進(jìn)行局部搜索，以增強算法跳出局部最優(yōu)解的能力。

2.1同步擾動隨機(jī)逼近

同步擾動隨機(jī)逼近是一種求解損失函數(shù)最優(yōu)值問題的有效算法，通過同時擾動所有的待優(yōu)化參數(shù)、再測量兩次損失函數(shù)的值就可以得到迭代過程中的逼近梯度。

在SPSA算法中，定義待優(yōu)化的目標(biāo)函數(shù)（即損失函數(shù)）為L（θ），梯度函數(shù)的逼近公式為

估計值θ的更新公式為

式中:ak=a/（A+k+1）α，其中，a、A、α均為系數(shù)。

2.2FA-SPSA算法流程

（1）確定算法參數(shù):種群規(guī)模Popsize、最大進(jìn)化次數(shù)Maxiter、運行的次數(shù)Runtime、亮度I0、吸引度β0、增益系數(shù)a和c，并初始化種群。

（2）利用標(biāo)準(zhǔn)螢火蟲算法對種群執(zhí)行全局搜索，取出m個最優(yōu)的螢火蟲個體。

（3）利用同步擾動隨機(jī)逼近算法對m個最優(yōu)螢火蟲個體進(jìn)行局部搜索:

a）生成同時擾動向量Δk；

b）產(chǎn)生兩個損失函數(shù)測量值L（θk-1+ckΔk）和L（θk-1-ckΔk）；

c）按式（6）進(jìn)行梯度逼近；

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

3　算法驗證

3.1標(biāo)準(zhǔn)測試函數(shù)

為驗證FA-SPSA算法的尋優(yōu)性能和收斂速度，本文選取6個標(biāo)準(zhǔn)測試函數(shù)（見表1）進(jìn)行計算，并與標(biāo)準(zhǔn)螢火蟲算法（FA）和3種果蠅優(yōu)化算法（FFO、FFO_LGMS、IFFO）［9］進(jìn)行性能比較。

表1　標(biāo)準(zhǔn)測試函數(shù)［9］Table 1 Benchmark functions

3.2實驗環(huán)境

Window 7操作系統(tǒng)，CPU Inter（R）Core（TM）i5-2430M，主頻2.40 GHz，內(nèi)存4 GB，編程語言為MATLAB 2012a。

3.3參數(shù)設(shè)置

為保證結(jié)果的公平性及客觀性，在測試中，F(xiàn)A和FA-SPSA算法中全局搜索部分采取相同參數(shù):Popsize均分別取30和50，Maxiter=300，β0=1，γ=1。SPSA算法中的參數(shù)為:α=0.602，γ′=0.101［10］，最優(yōu)螢火蟲個體數(shù)m=1，局部搜索允許的最大迭代次數(shù)為40；為了產(chǎn)生更小的擾動量，使函數(shù)在尋優(yōu)過程中保持合適的搜索范圍，計算函數(shù)f3的增益系數(shù)取值為a=0.01、c=1，而計算其他5個函數(shù)的增益系數(shù)取值為a=0.1、c=1。

3.4結(jié)果分析

表2為5種不同算法用于6個標(biāo)準(zhǔn)測試函數(shù)（函數(shù)維度n=30）得到的平均值和標(biāo)準(zhǔn)差的尋優(yōu)統(tǒng)計結(jié)果，其中:①FA和FA-SPSA算法分別獨立運行20次，種群規(guī)模為30，函數(shù)評價次數(shù)達(dá)到9000次終止進(jìn)化；②FFO、FFO_LGMS、IFFO等3種算法的統(tǒng)計結(jié)果來源于文獻(xiàn)［9］，其最大函數(shù)評價次數(shù)為50 000。

從表2中可以看出，對于f1、f2、f4、f5、f6這5個函數(shù)，與其他4種算法相比，F(xiàn)A-SPSA算法具有更好的尋優(yōu)性能:在標(biāo)準(zhǔn)測試函數(shù)的維度n為30時，F(xiàn)A-SPSA算法不僅優(yōu)于標(biāo)準(zhǔn)螢火蟲算法，而且通過較少的函數(shù)評價次數(shù)獲得的結(jié)果要優(yōu)于3種果蠅算法的結(jié)果，表現(xiàn)出更好的魯棒性和適應(yīng)性。

對于測試函數(shù)f3，F(xiàn)A-SPSA算法比IFFO算法的優(yōu)化精度低，比其他3種算法的優(yōu)化精度高。但FA-SPSA算法以較少的計算代價找到了排名第二的較優(yōu)解，其平均值和標(biāo)準(zhǔn)差與IFFO算法得到的最優(yōu)結(jié)果相差不是很大，可推測在加大計算資源的條件下FA-SPSA算法將會找到更優(yōu)解。

表2　5種算法的優(yōu)化結(jié)果比較Table 2 Comparison of optimization results by five algorithms

表3為種群規(guī)模分別取30和50的情況下，F(xiàn)A和FA-SPSA算法在6個標(biāo)準(zhǔn)測試函數(shù)上的平均值和標(biāo)準(zhǔn)差的尋優(yōu)統(tǒng)計結(jié)果，其中:每種算法分別獨立運行20次，種群規(guī)模為30時，函數(shù)評價次數(shù)達(dá)到9000次終止進(jìn)化，種群規(guī)模為50時，函數(shù)評價次數(shù)達(dá)到15 000次終止進(jìn)化。種群規(guī)模為30時，F(xiàn)A和FA-SPSA算法對于6個標(biāo)準(zhǔn)測試函數(shù)的優(yōu)化收斂曲線如圖1所示，種群規(guī)模為50的優(yōu)化收斂曲線與此類似。

結(jié)合表3和圖1可以看出:①種群規(guī)模增大時，F(xiàn)A和FA-SPSA的尋優(yōu)精度和魯棒性都有一定提升；②與FA相比，F(xiàn)A-SPSA由于綜合了全局搜索和局部搜索的優(yōu)點而具有更高的尋優(yōu)精度；③FA-SPSA算法在經(jīng)過2000～3000次函數(shù)評價后基本能找到最優(yōu)解，收斂速度遠(yuǎn)快于FA；④FA算法在進(jìn)化一段時間后的收斂曲線變化緩慢，即在搜索過程中陷入了局部最優(yōu)，而FASPSA因引入了梯度隨機(jī)變量擾動使算法能夠很快跳出局部最優(yōu)而繼續(xù)尋找更優(yōu)解。

圖1　FA和FA-SPSA對于標(biāo)準(zhǔn)測試函數(shù)的優(yōu)化收斂曲線（Popsize=30）Fig.1 Convergence curves of FA and FA-SPSA on benchmark functions（Popsize=30）

綜上所述，相比其他幾種優(yōu)化算法，特別是標(biāo)準(zhǔn)螢火蟲算法，F(xiàn)A-SPSA在尋優(yōu)精度、收斂速度和魯棒性方面都占有優(yōu)勢，因此利用memetic框架將螢火蟲算法和同步擾動隨機(jī)逼近算法結(jié)合在一起，十分有效地增強了混合算法的尋優(yōu)能力。

4　結(jié)語

針對螢火蟲算法存在過早收斂、容易陷入局部最優(yōu)、全局探索能力較弱、精度不夠高等問題，本文提出基于同步擾動隨機(jī)逼近的混合螢火蟲算法（FA-SPSA）。該算法采用螢火蟲算法執(zhí)行全局搜索，采用同步擾動隨機(jī)逼近算法對部分已優(yōu)化個體執(zhí)行局部搜索，有效提高了算法跳出局部最優(yōu)并進(jìn)行全局探索的能力。從6個標(biāo)準(zhǔn)測試函數(shù)的對比實驗中可以看出，F(xiàn)A-SPSA算法在5個標(biāo)準(zhǔn)測試函數(shù)中找到最優(yōu)解，在另外1個測試函數(shù)中找到了與最優(yōu)解相差不大的次優(yōu)解，總之，其在尋優(yōu)精度、收斂速度、魯棒性方面表現(xiàn)出較優(yōu)的性能。進(jìn)一步的研究工作包括:①深入研究種群規(guī)模、吸引系數(shù)等參數(shù)對FA-SPSA尋優(yōu)性能的影響；②考察FA-SPSA在多峰測試函數(shù)中的應(yīng)用情況；③研究FA-SPSA在云計算調(diào)度、工程優(yōu)化、車間調(diào)度等實際問題中的應(yīng)用。

［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ìn)型人工螢火蟲算法的云計算資源研究［J］.計算機(jī)應(yīng)用研究，2013，30（8）:2298-2300.

［3］白永珍.基于參數(shù)方差調(diào)節(jié)螢火蟲算法的三維路徑規(guī)劃［J］.計算機(jī)系統(tǒng)應(yīng)用，2015，24（5）:92-99.

［4］李遠(yuǎn)梅，張宏立.基于改進(jìn)螢火蟲算法PID控制器參數(shù)優(yōu)化研究［J］.計算機(jī)仿真，2015，32（9）:356-359.

［5］李永林，葉春明.基于螢火蟲算法的零等待流水線調(diào)度優(yōu)化［J］.機(jī)械設(shè)計與研究，2013，29（6）:50-54.

［7］張明，張樹群，雷兆宜.改進(jìn)的螢火蟲算法在神經(jīng)網(wǎng)絡(luò)中的應(yīng)用［J/OL］.計算機(jī)工程與應(yīng)用.（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ìn)混沌螢火蟲算法的云計算資源調(diào)度［J］.計算機(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.

［責(zé)任編輯 尚 晶］

Hybrid firefly algorithm based on simultaneous perturbation stochastic approximation

Li Weigang1，2，F(xiàn)eng 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，F(xiàn)A 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

湖北省教育廳科學(xué)技術(shù)研究計劃重點項目（D20161103）；武漢科技大學(xué)冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點實驗室開放基金資助項目（Z201501）；武漢科技大學(xué)智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室開放基金面上項目（2016znss18B）；武漢科技大學(xué)青年科技晨光計劃資助項目（2016070204010099）.

李維剛（1977-），男，武漢科技大學(xué)教授，博士.E-mail:liweigang.luck@foxmail.com

劉 翱（1987-），男，武漢科技大學(xué)講師，博士.E-mail:liuao@wust.edu.cn