基于連續(xù)空間的螢火蟲算法改進

劉晨旻，王亞剛

(上海理工大學 光電信息與計算機工程學院,上海 200093)

啟發(fā)式算法是當代全局優(yōu)化算法、智能計算以及軟計算的重要組成部分。這類算法的靈感大多來源于科學家們對自然界多種機構(gòu)之間交互方式的觀察，其中又以基于種群的啟發(fā)式搜索算法[1]為主。這些算法在使用測試函數(shù)進行全局優(yōu)化問題試驗時，表現(xiàn)出不同的特性[2]，這是由其基本原理決定的。粒子群算法是基于鳥類和魚類的群居行為提出的[3]。蟻群算法于1992年提出，源于螞蟻覓食過程中的搜索行為[4]。布谷鳥算法模擬部分布谷鳥的寄生育雛行為[5]，常用于在性能與全局尋優(yōu)方面與其它啟發(fā)式算法進行比較[6]。在這類算法中，螢火蟲算法(Firefly Algorithm，F(xiàn)A)在處理多模態(tài)全局優(yōu)化問題上較為有效。

螢火蟲算法是一種源于熱帶螢火蟲發(fā)光行為的啟發(fā)式算法[7]。該算法的原理為螢火蟲尋找伙伴時的趨光性。螢火蟲在空間中會向附近最亮的螢火蟲移動，相互吸引，以此對其位置進行更新[8]。目前國內(nèi)外都對螢火蟲算法進行了一定的研究。文獻[9]提出了基于螢火蟲算法的新穎圖像檢索方法，用以提高檢索反饋樣本的性能。文獻[10]引入多種群技術(shù)及權(quán)重系數(shù)因子來細分螢火蟲種群。這些研究使得螢火蟲算法在圖像處理、控制優(yōu)化、生產(chǎn)管理、電力系統(tǒng)、神經(jīng)網(wǎng)絡訓練等領域得到了應用。

但是，螢火蟲算法存在著收斂精度低以及容易陷入局部最優(yōu)等缺點。針對上述缺陷，研究人員從多個角度對螢火蟲算法進行了改進和應用，包括參數(shù)、移動方式、新的吸引策略、算法混合以及算法的學科應用。

為了增加算法的全局搜索能力，文獻[11]通過將交叉熵(Cross Entropy，CE)嵌入螢火蟲算法，提出了一種新型的混合元啟發(fā)式算法。文獻[9]在螢火蟲算法中引入相對亮度差異來動態(tài)調(diào)整其步長，并將改進的螢火蟲算法與用戶反饋結(jié)果相結(jié)合，優(yōu)化特征選擇并對支持向量機(Support Vector Machine，SVM)進行參數(shù)尋優(yōu)，以提高圖像檢索精度。文獻[12]先采用新的吸引度模型來確定被吸引的螢火蟲數(shù)量，再設計新的搜索運算符進行優(yōu)化，用以增強其全局尋優(yōu)能力。文獻[13]采用部分吸引力模型和快速吸引力計算策略，用以保留群體多樣性并充分利用個人信息，確保了個人之間的信息共享，提高了收斂精度。文獻[14]融合了粒子群(Particle Swarm Optimization，PSO)算法與螢火蟲算法，提出了3種新穎的算子，將混合算法的種群分為兩個子種群，分別選擇FA和PSO作為其基本算法來進行優(yōu)化過程。該算法通過兩個子群體交換信息，以便充分利用PSO和FA的優(yōu)點，但整個算法的停滯程度超過了預定義的閾值。

文獻[15]將螢火蟲算法引入人工智能領域，提出一種具有高斯干擾和局部搜索能力的FA算法。然后，使用隨機吸引模型更新群體，將粒子的當前位置與粒子的歷史最佳位置進行比較。該方法增強了種群多樣性，且提高了優(yōu)化精度。文獻[16]將潮汐力公式用于修改螢火蟲算法，在新的算法中不再使用吸光系數(shù)，提高了算法性能和效率。文獻[17]對螢火蟲種群進行分組，每個螢火蟲都會根據(jù)與之相距最近的組的亮度進行尋優(yōu)，而每個組之間又可以進行信息交換。各組別中，適應度最高的螢火蟲之間相互吸引，從而尋找全局最優(yōu)。

上述改進方法表明，傳統(tǒng)螢火蟲算法存在著缺陷。在迭代過程中，螢火蟲算法在全局尋優(yōu)方面的表現(xiàn)不佳。現(xiàn)有研究多致力于將螢火蟲算法與其它魯棒性優(yōu)異的算法相結(jié)合，構(gòu)建新的混合算法[18]，并以此嵌入到FA的薄弱環(huán)節(jié)中，提高FA的性能。混合算法著重于強調(diào)多組的概念[19]，以FA以及PSO為基礎算法對種群進行優(yōu)化?；旌纤惴ㄒ部赏ㄟ^使用新穎的吸引度計算式或改變其移動策略來降低算法復雜度[20]。除此以外，使用精英策略加速算法收斂也是一種研究方向，但是該改進對傳統(tǒng)算法結(jié)構(gòu)簡單、可操作性強的優(yōu)點會造成負面影響，且對算法性能的改善也不夠完備[21]。

終上所述，本文將從理論上對傳統(tǒng)算法的缺陷進行改進，采用多種經(jīng)典測試函數(shù)驗證改進后的算法，并將新方法與傳統(tǒng)算法進行對比。

1 螢火蟲算法原理

在螢火蟲算法中，每個螢火蟲都對應著一個解空間中的可行解。螢火蟲在此位置的亮度表示螢火蟲在該位置的適應度，螢火蟲亮度越高則表明越接近最優(yōu)解[22]。螢火蟲之間也會互相吸引，越亮的螢火蟲吸引力越大。解空間存在傳播介質(zhì)吸收光，所以距離越近的螢火蟲吸引力越大[23]。在實現(xiàn)算法前需要完成幾個假設[24]：

假設1螢火蟲雌雄同體，所以一只螢火蟲會被其他螢火蟲吸引這種屬性與性別無關(guān)[25]；

假設2吸引力與亮度成正比，并且隨著距離的增加而減小。因此，對于任何兩只閃爍的螢火蟲，較暗的那只會向較亮的那只移動。如果沒有比那只螢火蟲更亮的螢火蟲，則這只螢火蟲將隨機移動；

假設3螢火蟲的亮度是由設計的目標函數(shù)決定的。

螢火蟲之間的相對吸引度計算式為

β(r)=β0e-γr2

(1)

式中，β0為螢火蟲之間的初始吸引度；γ為解空間介質(zhì)的吸光系數(shù)；r為螢火蟲之間的距離。螢火蟲i會被另外一個更亮的個體所吸引，其移動方式由式(2)決定

(2)

種群中適應度最高(亮度最大)的個體移動方式由式(3)決定。其中，αt會隨螢火蟲代數(shù)增加而減小[27]。

(3)

傳統(tǒng)螢火蟲算法的基本步驟如下：

步驟1初始化種群；

步驟2計算螢火蟲個體適應度值，適應度越高的螢火蟲亮度越高；

步驟3每個螢火蟲向比自己亮度更高的螢火蟲飛行；

步驟4最亮的螢火蟲更新自身位置；

步驟5到達最大迭代次數(shù)時輸出結(jié)果，否則返回步驟2。

傳統(tǒng)螢火蟲算法存在著許多問題：(1)算法過早收斂，導致陷入局部最優(yōu)；(2)控制參數(shù)選取不合適，導致無法收斂；(3)難以解決多目標優(yōu)化或含有多個約束條件的問題[28]。

2 算法優(yōu)化

當?shù)枰嬎阄灮鹣x種群吸引度時，不再僅僅對離散的個體計算其吸引度或是吸引度分量。實際應用中，螢火蟲個體之間產(chǎn)生吸引時，其對周圍空間也產(chǎn)生一定的影響，那么螢火蟲的移動方式就不僅受到當前適應度最高個體的影響。

螢火蟲在尋優(yōu)過程中不應僅以限定步長向更優(yōu)解跳動。為了保證其快速性與收斂性，步長應當隨著迭代次數(shù)的增加而下降，漸漸形變?yōu)槲⒄{(diào)的方式前進。

由于最亮點僅以隨機方式運動，為了避免在迭代后期由于僅跟隨有限個較優(yōu)個體而陷入局部最優(yōu)，個體在選取前進方向時應當將多個優(yōu)于自身的解納入考慮范疇之內(nèi)。

2.1 問題維度分解

本文將適應度函數(shù)中的變量個數(shù)作為螢火蟲算法解空間的維度。以適應度函數(shù)為f(x1,x2)=(x1-a)2+(x2-b)2的問題為例，建立一個以X和Y為軸的二維參數(shù)空間。將N×N個螢火蟲個體均勻分布在二維空間內(nèi)，此時螢火蟲種群的初始坐標(Xi0,Yi0)為

(4)

式中，XL為X軸定義域的左邊界；YL為Y軸定義域的左邊界；Int(·)為取整函數(shù)；lX和lY為X和Y軸經(jīng)過N等分后的單個區(qū)間長度。

2.2 吸引度計算

根據(jù)螢火蟲當前所處位置計算此時解空間內(nèi)的吸引度分布情況。定義螢火蟲個體所處位(X,Y)的吸引度為

βi(Xs,Ys)=β0e-γ[(Xs-Xi)2+(Ys-Yi)2]

(5)

式中，β0為螢火蟲之間的初始吸引度；γ為解空間介質(zhì)的吸光系數(shù)。

根據(jù)當前個體所處區(qū)域的位置，計算空間內(nèi)所有螢火蟲對應的適應度，并按照適應度的大小對螢火蟲群重新排序編號，從1至N2。此時適應度比個體i高的所有螢火蟲對i在X軸區(qū)域內(nèi)的總吸引度可以用式(6)來表示。

(6)

同理，適應度高于個體i的所有螢火蟲對i在Y軸區(qū)域內(nèi)的總吸引度可以表示為

(7)

式中，XL和XR為X軸定義域的左右邊界；YL和YR為Y軸定義域的左右邊界；lX、lY分別為X、Y軸N等分后的單區(qū)間長度。使用所有適應度高于個體i的點，計算它們對個體的總吸引度的方式，利用其替代僅使用適應度最高點計算吸引度的方式。這樣操作可以降低尋優(yōu)時的隨機性，避免陷入局部最優(yōu)。

2.3 個體移動方法

螢火蟲個體i的移動受到其它所有比它亮的螢火蟲的影響，個體i在X和Y軸上的運動為

(8)

αt=α0δt,0<δ<1

(9)

式中，α0是初始隨機因子；δ為冷卻因子；t為種群迭代次數(shù)。對于大多是情況下，δ取0.95～0.97。

基本流程如圖1所示。

圖1 算法流程圖

3 實例研究及仿真結(jié)果

為了演示優(yōu)化后算法的工作情況，并將其與原始算法做比較，本文在MATLAB中進行仿真，并使用多種測試函數(shù)驗證優(yōu)化后的算法。仿真實驗中適應度函數(shù)為f(x1,x2)=(x1-a)2+(x2-b)2，a=-3，b=3。其它相關(guān)參數(shù)設置如下：螢火蟲數(shù)量(種群數(shù))n為100，最大迭代次數(shù)為60，初始吸引度β0=1，介質(zhì)吸光系數(shù)γ=1，冷卻因子δ=0.97，擾動方式采用[0,1]之間的正態(tài)分布。實驗中優(yōu)化算法的仿真如圖2所示，其與傳統(tǒng)算法的結(jié)果對比如表1所示。

(a) (b)

表1 螢火蟲算法的參數(shù)及辨識結(jié)果

使用傳統(tǒng)螢火蟲算法以及本文算法尋優(yōu)后的結(jié)果分布區(qū)間如表1所示。實驗結(jié)果表明本文算法的結(jié)果分布區(qū)間均優(yōu)于傳統(tǒng)算法，證明了本文優(yōu)化算法的有效性。仿真結(jié)果得到傳統(tǒng)螢火蟲算法的平均值為(-3.000 3,2.995 6)，而優(yōu)化后的算法平均值為(-2.999 9,2.999 8)，算法精確度得到了提高。

為了對新算法的全局尋優(yōu)能力進行演示并與傳統(tǒng)螢火蟲算法比較，本文選取Michalewicz函數(shù)為測試函數(shù)。Michalewicz函數(shù)是一個多模態(tài)的函數(shù)，具體為

(10)

式中，d為問題的維度，本文取值為2；xi為輸入域；參數(shù)m定義了函數(shù)谷和脊的陡度，其值越大，搜索的難度就越大，本文采用其推薦值m=10。考慮到某些實際情況下，函數(shù)的最優(yōu)值與其周圍值差異不明顯，因此需要在難以收斂到最優(yōu)值的情況下求解。本文分別使用兩種算法搜索函數(shù)的最小值以及最大值，以判斷其是否易陷入局部最優(yōu)。圖3和圖4分別為傳統(tǒng)算法和優(yōu)化后螢火蟲算法的仿真結(jié)果。

(a) (b)

仿真中的相關(guān)參數(shù)設置如下：螢火蟲數(shù)量(種群數(shù))n為36，最大迭代次數(shù)為60，初始吸引度β0=1，介質(zhì)吸光系數(shù)β=1，冷卻因子δ=0.97。對比圖3(a)以及圖4(a)可知，在尋找Michalewicz函數(shù)最小值時，傳統(tǒng)算法與本文算法都能找到全局最優(yōu)解，無個體陷入局部最優(yōu)。對比圖3(b)以及圖4(b)發(fā)現(xiàn)，在尋找函數(shù)最大值時，傳統(tǒng)螢火蟲算法有部分個體陷入局部最優(yōu)，未能找到全局最優(yōu)解，而本文算法沒有陷入局部最優(yōu)，成功找到最優(yōu)解。該結(jié)果說明，相較于傳統(tǒng)方法，本文算法尋找全局最優(yōu)的能力得到了較大改善。

上述兩項仿真說明了本文算法在全局尋優(yōu)以及精確度上的改善。本文還使用了其他測試函數(shù)進行仿真，用于對比傳統(tǒng)螢火蟲算法與本文算法的性能。仿真過程中，每種測試函數(shù)均進行了多次運行。本文取運行次數(shù)的平均值進行統(tǒng)計分析。

表2中，1.781 4±0.015 0表示函數(shù)輸出的平均值為1.781 4，標準值為0.015 0。從表中可以看出，優(yōu)化螢火蟲算法在全局尋優(yōu)時的總體性能優(yōu)于傳統(tǒng)算法，且傳統(tǒng)算法在仿真時易陷于局部最優(yōu)。

表2 實驗數(shù)據(jù)對比

近年來對螢火蟲算法的優(yōu)化方向大致可以分為以下幾種方式：(1)對參數(shù)的改善；(2)對個體移動方式的改善；(3)優(yōu)化吸引策略；(4)算法混合。為了進一步驗證本文算法的性能，本文研究了近年來不同改進方法，包括一種基于混合種群的全局優(yōu)化算法、基于概率吸引模型的改進FA、基于光強差的修正FA以及一種帶有混沌閃爍機制的雙種群協(xié)同進化的改進算法[29-33]，并在同一測試函數(shù)下加以實現(xiàn)。各改進算法結(jié)果的平均值如表2所示。結(jié)果表明，對比其它改進算法，本文算法在全局尋優(yōu)的能力上表現(xiàn)出一定的優(yōu)越性。

4 結(jié)束語

為了提高螢火蟲算法在尋優(yōu)過程中的性能，本文在計算螢火蟲吸引度時，將離散問題連續(xù)化，以所有適應度更高的螢火蟲對當前個體所在區(qū)間的總吸引度來代替單個螢火蟲對當前個體的吸引度。螢火蟲種群的運動總體效果是在連續(xù)的解空間內(nèi)逐漸收斂至最優(yōu)解附近，個體的吸引度函數(shù)對所有解空間的區(qū)域均存在作用，且作用強度隨距離增加而減小。通過這種方法實現(xiàn)的算法改進不僅提高了種群的全局尋優(yōu)能力，還降低了傳統(tǒng)算法運行過程中，因參數(shù)設置或者步長過長等問題導致出現(xiàn)的提前收斂或錯過最優(yōu)解的情況。然而，相較于傳統(tǒng)算法，本文算法運行過程消耗時間較長，下一步將針對該問題進行重點研究。