螢火蟲算法參數(shù)分析與優(yōu)化*

卓宏明，陳倩清

(浙江國際海運(yùn)職業(yè)技術(shù)學(xué)院 船舶工程學(xué)院，浙江 舟山 316021)

0 引言

螢火蟲算法Firefly Algorithm(FA)是2008年YANG X S[1-2]提出的一種新型群智能優(yōu)化算法，其操作簡單、參數(shù)少、易實(shí)現(xiàn)，成為眾多學(xué)者研究的熱點(diǎn)，在諸多領(lǐng)域得到了較好的應(yīng)用[3-6]。然而決定算法性能的參數(shù)選擇還缺少相關(guān)的深入研究，算法的參數(shù)設(shè)定對求解性能影響很大，因此，螢火蟲算法的參數(shù)優(yōu)化已成為急需解決的問題。

1 螢火蟲算法及數(shù)學(xué)模型

螢火蟲算法基本思想是模擬螢火蟲的發(fā)光特性在一定區(qū)域內(nèi)尋找伙伴，向位置較優(yōu)的螢火蟲移動，以達(dá)到尋優(yōu)的目的。將問題的目標(biāo)函數(shù)定義為螢火蟲所處位置的適應(yīng)度值，將優(yōu)化過程模擬成螢火蟲個體的相互吸引而引發(fā)的位置更新的過程，將個體的優(yōu)勝劣汰過程類比為搜索和優(yōu)化過程中用好的可行解取代較差可行解的迭代過程。

螢火蟲算法的尋優(yōu)主要由熒光亮度和吸引度兩個關(guān)鍵要素實(shí)現(xiàn)。主要公式包括相對相對螢光亮度公式、相對吸引度公式和位置更新公式[1-2]，如下所示：

螢火蟲的相對螢光亮度為：

I=I0×e-γrij

(1)

其中，I0為初始光強(qiáng)度，即在光源(r=0)處的光強(qiáng)度，與目標(biāo)函數(shù)值相關(guān)，目標(biāo)函數(shù)值越優(yōu)自身亮度越高；γ為光強(qiáng)吸收系數(shù)即吸收因子，以體現(xiàn)光強(qiáng)的減弱特性，一般情況下γ∈[0.01，100]；r通常為螢火蟲i與j間的歐氏距離。

螢火蟲的吸引度為：

(2)

其中，β0為最大吸引力，即光源(r=0)處的吸引力。

螢火蟲i被螢火蟲j吸引而向其移動的位置更新公式如下：

xj(t+1)=xj(t)+βij(rij)[xi(t)-xj(t)]+αεj

(3)

其中，t為算法迭代次數(shù)；α為隨機(jī)步長，一般取值范圍為[0，1]；εj通常是由高斯分布、均勻分布或其他分布生成的隨機(jī)數(shù)向量。

2 算法參數(shù)分析及數(shù)值試驗(yàn)

根據(jù)螢火蟲算的數(shù)學(xué)模型可知螢火蟲算法的需要設(shè)定的參數(shù)有：螢火蟲數(shù)量n,步長因子α,光吸收因子γ，最大吸引度β0,最大迭代次數(shù)T，共5個參數(shù)。而對于大多數(shù)的應(yīng)用問題，β0可取為1，通過單因素數(shù)值試驗(yàn)測試經(jīng)典測試函數(shù)[7-8](見表1)分析螢火蟲算法其他4個參數(shù)對算法性能的影響。

表1 測試函數(shù)[7-8]

算法參數(shù)的經(jīng)驗(yàn)設(shè)置見表2，在進(jìn)行單因素試驗(yàn)時固定三個參數(shù)，改變一個參數(shù)進(jìn)行仿真試驗(yàn)。試驗(yàn)環(huán)境為Windows 7，64位操作系統(tǒng)，Core i5-4210U處理器，8 GB內(nèi)存，MATLAB 7.11版本。為降低隨機(jī)誤差，每個測試函數(shù)每組參數(shù)組合分別獨(dú)立運(yùn)行20次。

表2 算法參數(shù)經(jīng)驗(yàn)設(shè)置

2.1 螢火蟲數(shù)量(n)對算法的影響

根據(jù)經(jīng)驗(yàn)值，設(shè)置螢火蟲數(shù)量n=10、20、30、…、90、100。對3個測試函數(shù)進(jìn)行獨(dú)立運(yùn)行20次的數(shù)值試驗(yàn)。試驗(yàn)結(jié)果見表3，對應(yīng)各測試函數(shù)的平均最優(yōu)解曲線如圖1所示。

圖1螢火蟲數(shù)n對算法性能的影響

從理論定性地來看，螢火蟲數(shù)越多找到最優(yōu)解的可能性越大，算法的求解精度也越高，但也會產(chǎn)生大量重復(fù)解。從表3及圖1分析可以發(fā)現(xiàn)共性的規(guī)律：隨著螢火蟲數(shù)n的增多，對應(yīng)的平均最優(yōu)解也越精確，越趨于平緩，這與理論定性分析相吻合。但各測試函數(shù)又有其各自的特點(diǎn)。

Sphere函數(shù)的求解精度很高，并且最優(yōu)解與最差解差距也較小，具有較好的魯棒性。但當(dāng)螢火蟲數(shù)n超過50時，求解精度已經(jīng)基本穩(wěn)定，過多的螢火蟲數(shù)反而會增加計算開銷，浪費(fèi)資源。根據(jù)圖表綜合考慮求解精度及計算開銷，對于Sphere函數(shù)，螢火蟲數(shù)n取50時較為合理。

表3 螢火蟲數(shù)n對算法性能的影響

Rosenbrock函數(shù)由于其復(fù)雜性，螢火蟲算法對其求解精度不是非常高，并且最優(yōu)解與最差解差距也較大。根據(jù)圖表綜合考慮求解精度及計算開銷對于Rosenbrock函數(shù)，螢火蟲數(shù)n取70時較為合理。

Rastrigin函數(shù)由于其易陷入局部最優(yōu)，螢火蟲算法對其求解精度也不是非常高，最優(yōu)解與最差解差距一般。根據(jù)圖表綜合考慮求解精度及計算開銷對于Rastrigin函數(shù)，螢火蟲數(shù)n取60時較為合理。

2.2 步長因子(α)對算法的影響

根據(jù)常用步長因子取值區(qū)間α= [0,1],設(shè)置步長因子α=0.1、0.2、0.3、…、0.9、1。對3個測試函數(shù)進(jìn)行獨(dú)立運(yùn)行20次的數(shù)值試驗(yàn)。試驗(yàn)結(jié)果見表4，對應(yīng)各測試函數(shù)的平均最優(yōu)解曲線如圖2所示。

表4 步長因子α對算法性能的影響

圖2 步長因子α對算法性能的影響

從理論角度定性地來看，步長因子α直接影響螢火蟲尋優(yōu)移動的步長，步長越小求解越精確，但容易陷入局部最優(yōu)，步長越大收斂的速度越快，但會降低求解精度。從表4及圖2分析可見步長因子的大小直接影響了算法的求解精度。各測試函數(shù)又有其各自的特點(diǎn)。

Sphere函數(shù)隨著步長因子α的增加，算法的求解精度越差。但從整體來看平均求解精度在10-6和10-7，求解精度已經(jīng)很高，并且最優(yōu)解與最差解差距也較小，具有較好的魯棒性。步長因子α越小精度越高，也越趨于平緩。根據(jù)圖表所示，對于Sphere函數(shù)，步長因子α取0.1時較為合理。

Rosenbrock函數(shù)隨著步長因子α的增加，算法的求解精度越高，也越趨于平緩。根據(jù)圖表所示，對于Rosenbrock函數(shù)，步長因子α取1時較為合理。

Rastrigin函數(shù)隨著步長因子α的增加，算法的求解精度越高，但有微小振蕩。根據(jù)圖表所示，對于Rastrigin函數(shù)，步長因子α取1時較為合理。

2.3 吸收因子(γ)對算法的影響

根據(jù)常用經(jīng)驗(yàn)值γ=1及取值區(qū)間γ= [0.01,100],設(shè)置光強(qiáng)吸收因子γ=0.01、0.05、0.1、0.5、1、5、10、50、100。對3個測試函數(shù)進(jìn)行獨(dú)立運(yùn)行20次的數(shù)值試驗(yàn)。試驗(yàn)結(jié)果見表5，對應(yīng)各測試函數(shù)的平均最優(yōu)解曲線如圖3所示。

從算法數(shù)學(xué)模型理論定性地來看，吸收因子γ越小體現(xiàn)光強(qiáng)的減弱越小，從而使得螢火蟲相對螢光亮度以及吸引度越大，越容易被位置優(yōu)的螢火蟲吸引，從而加速收斂。但也可能會降低隨機(jī)擾動新解的開拓，反而降低求解精度。因此，需要合理設(shè)定吸收因子γ，以獲得較高的求解精度及求解速度。從表5及圖3分析可見其大小直接影響了算法的求解精度。各測試函數(shù)又有其各自的特點(diǎn)。

Sphere函數(shù)隨著吸收因子γ的增加，算法的求解精度越差，但有微小振蕩。從整體來看吸收因子在10及以下時，平均求解精度在10-6和10-7，求解精度已經(jīng)很高，并且最優(yōu)解與最差解差距也較小，具有較好的魯棒性。根據(jù)圖表所示，對于Sphere函數(shù)，吸收因子γ取0.5時較為合理。

Rosenbrock函數(shù)隨著吸收因子γ的增加，算法的求解精度越差。根據(jù)圖表所示，對于Rosenbrock函數(shù)，吸收因子γ取0.01時較為合理。

Rastrigin函數(shù)隨著吸收因子γ的增加，算法的求解精度越高，但有微小振蕩。根據(jù)圖表所示，對于Rastrigin函數(shù)，吸收因子γ取50時較為合理。

表5 吸收因子γ對算法性能的影響

圖3 吸收因子γ對算法性能的影響

2.4 最大迭代次數(shù)(T)對算法的影響

根據(jù)經(jīng)驗(yàn)值，最大迭代次數(shù)T=100、200、300、…、900、1 000。對3個測試函數(shù)進(jìn)行獨(dú)立運(yùn)行20次的數(shù)值試驗(yàn)。試驗(yàn)結(jié)果見表6，對應(yīng)各測試函數(shù)的平均最優(yōu)解曲線如圖4所示。

從理論定性地來看，最大迭代次數(shù)T越大找到最優(yōu)解的可能性越大，算法的求解精度也越高，但會越趨于平緩，也會大量增加計算開銷。從表6及圖4分析可以發(fā)現(xiàn)：Sphere函數(shù)和Rosenbrock函數(shù)，隨著最大迭代次數(shù)T的增多，對應(yīng)的平均最優(yōu)解也越精確，越趨于平緩，這與理論定性分析相吻合。但Rastrigin函數(shù)卻處于小幅振蕩中，各測試函數(shù)有其各自的特點(diǎn)。

Sphere函數(shù)的求解精度很高，并且最優(yōu)解與最差解差距也較小，具有較好的魯棒性。但當(dāng)最大迭代次數(shù)T超過700時，求解精度已經(jīng)基本穩(wěn)定，過多的迭代反而會增加計算開銷，浪費(fèi)資源，根據(jù)圖表綜合考慮求解精度及計算開銷，對于Sphere函數(shù)最大迭代次數(shù)T為700時較為合理。

Rosenbrock函數(shù)由于其復(fù)雜性，螢火蟲算法對其求解精度比Sphere函數(shù)低的多，并且最優(yōu)解與最差解差距也較大。根據(jù)圖表綜合考慮求解精度及計算開銷，對于Rosenbrock函數(shù)最大迭代次數(shù)T為700時較為合理。

Rastrigin函數(shù)由于其易陷入局部最優(yōu)，螢火蟲算法對其求解精度也不是非常高，最優(yōu)解與最差解差距也較大。并且從圖表中發(fā)現(xiàn)其處于小幅振蕩，說明只增大最大迭代次數(shù)無法提高其求解精度，需要綜合考慮其他各參數(shù)。綜合考慮求解精度及計算開銷，對于Rastrigin函數(shù)最大迭代次數(shù)T為700時較為合理。

表6 最大迭代次數(shù)T對算法性能的影響

圖4 最大迭代次數(shù)(T)對算法性能的影響

3 算法參數(shù)優(yōu)化

根據(jù)前面的算法參數(shù)分析及對各測試函數(shù)的仿真試驗(yàn)結(jié)果整理各對應(yīng)優(yōu)化參數(shù)見表7。

表7 算法參數(shù)優(yōu)化設(shè)置

再根據(jù)優(yōu)化前的經(jīng)驗(yàn)參數(shù)與優(yōu)化后的算法參數(shù)對各測試函數(shù)在相同測試環(huán)境下進(jìn)行對比數(shù)值實(shí)驗(yàn)，各測試函數(shù)分別獨(dú)立運(yùn)行20次。試驗(yàn)結(jié)果對應(yīng)各測試函數(shù)的平均最優(yōu)解收斂曲線如圖5、圖6所示，對比結(jié)果見表8。

圖5 參數(shù)優(yōu)化前測試函數(shù)收斂曲線

圖6 參數(shù)優(yōu)化后測試函數(shù)收斂曲線

表8 算法參數(shù)優(yōu)化前后對比效果

從圖表中可見參數(shù)優(yōu)化后的3個測試函數(shù)隨著迭代次數(shù)的增加都明顯收斂，求解精度提高了1～2個數(shù)量級，并且收斂代數(shù)也明顯減少，提高了算法的求解精度和速度。

4 結(jié)論

(1)螢火蟲數(shù)n越大，螢火蟲算法的求解精度也越高，但越趨于平緩，也會產(chǎn)生大量重復(fù)解，增加計算開銷。步長因子α越小求解越精確，但容易陷入局部最優(yōu)，步長因子越大收斂的速度越快，但會降低求解精度。吸收因子γ越小越可加速收斂，但也可能會降低隨機(jī)擾動新解的開拓，降低求解精度。最大迭代次數(shù)T越大找到最優(yōu)解的可能性越大，算法的求解精度也越高，但會越趨于平緩，也會大量增加計算開銷。

(2)合理設(shè)置參數(shù)可以充分發(fā)揮算法的尋優(yōu)性能。螢火蟲算法參數(shù)優(yōu)化后比優(yōu)化前對各測試函數(shù)的求解精度和速度都有了明顯提高。求解精度提高了1～2個數(shù)量級，并且收斂代數(shù)也明顯減少。

下一步將研究考慮各參數(shù)之間的相互影響及算法參數(shù)的動態(tài)調(diào)整，并應(yīng)用于具體工程問題。