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

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

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

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

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

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

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

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

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

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

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

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

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

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

螢火蟲(chóng)算法相關(guān)符號(hào)與定義如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

估計(jì)值θ的更新公式為

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

2.2FA-SPSA算法流程

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

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

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

a）生成同時(shí)擾動(dòng)向量Δk；

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

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

d）按式（7）更新估計(jì)值。

3　算法驗(yàn)證

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

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

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

3.2實(shí)驗(yàn)環(huán)境

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

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

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

3.4結(jié)果分析

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

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

對(duì)于測(cè)試函數(shù)f3，F(xiàn)A-SPSA算法比IFFO算法的優(yōu)化精度低，比其他3種算法的優(yōu)化精度高。但FA-SPSA算法以較少的計(jì)算代價(jià)找到了排名第二的較優(yōu)解，其平均值和標(biāo)準(zhǔn)差與IFFO算法得到的最優(yōu)結(jié)果相差不是很大，可推測(cè)在加大計(jì)算資源的條件下FA-SPSA算法將會(huì)找到更優(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個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上的平均值和標(biāo)準(zhǔn)差的尋優(yōu)統(tǒng)計(jì)結(jié)果，其中:每種算法分別獨(dú)立運(yùn)行20次，種群規(guī)模為30時(shí)，函數(shù)評(píng)價(jià)次數(shù)達(dá)到9000次終止進(jìn)化，種群規(guī)模為50時(shí)，函數(shù)評(píng)價(jià)次數(shù)達(dá)到15 000次終止進(jìn)化。種群規(guī)模為30時(shí)，F(xiàn)A和FA-SPSA算法對(duì)于6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的優(yōu)化收斂曲線(xiàn)如圖1所示，種群規(guī)模為50的優(yōu)化收斂曲線(xiàn)與此類(lèi)似。

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

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

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

4　結(jié)語(yǔ)

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

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

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

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

［7］張明，張樹(shù)群，雷兆宜.改進(jìn)的螢火蟲(chóng)算法在神經(jīng)網(wǎng)絡(luò)中的應(yīng)用［J/OL］.計(jì)算機(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)混沌螢火蟲(chóng)算法的云計(jì)算資源調(diào)度［J］.計(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ù)研究計(jì)劃重點(diǎn)項(xiàng)目（D20161103）；武漢科技大學(xué)冶金工業(yè)過(guò)程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目（Z201501）；武漢科技大學(xué)智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金面上項(xiàng)目（2016znss18B）；武漢科技大學(xué)青年科技晨光計(jì)劃資助項(xiàng)目（2016070204010099）.

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

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