劉暢，劉利強(qiáng)，張麗娜，YANG Xinshe

(1.哈爾濱工程大學(xué) 動(dòng)力與能源工程學(xué)院，黑龍江 哈爾濱 150001； 2.海軍駐哈爾濱汽輪機(jī)廠有限責(zé)任公司軍事代表室， 黑龍江 哈爾濱 150046; 3.哈爾濱工程大學(xué) 自動(dòng)化學(xué)院，黑龍江 哈爾濱 150001； 4.Design Engineering and Mathematics， Middlesex University， Hendon NW4 4BT， UK)

?

改進(jìn)螢火蟲算法及其在全局優(yōu)化問題中的應(yīng)用

劉暢1，2，劉利強(qiáng)3，張麗娜3，YANG Xinshe4

(1.哈爾濱工程大學(xué) 動(dòng)力與能源工程學(xué)院，黑龍江 哈爾濱 150001； 2.海軍駐哈爾濱汽輪機(jī)廠有限責(zé)任公司軍事代表室， 黑龍江 哈爾濱 150046; 3.哈爾濱工程大學(xué) 自動(dòng)化學(xué)院，黑龍江 哈爾濱 150001； 4.Design Engineering and Mathematics， Middlesex University， Hendon NW4 4BT， UK)

針對標(biāo)準(zhǔn)螢火蟲算法容易陷入局部最優(yōu)的問題，本文提出一種改進(jìn)的螢火蟲算法。在標(biāo)準(zhǔn)螢火蟲算法的位置移動(dòng)公式中，利用指數(shù)分布和韋伯分布對吸引力項(xiàng)進(jìn)行改進(jìn)，以增強(qiáng)算法的全局探測能力；同時(shí)利用步長單調(diào)遞減模式對隨機(jī)項(xiàng)進(jìn)行改進(jìn)，以增強(qiáng)算法后期的局部挖掘能力。 通過13個(gè)測試函數(shù)對本文提出的改進(jìn)算法、模擬退火算法、粒子群算法和差分進(jìn)化算法進(jìn)行算法性能的比較。實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)算法能較好地平衡算法的全局探測能力和局部挖掘能力，使算法跳出局部最優(yōu)，從而提高算法的收斂速度和精度。

螢火蟲算法；隨機(jī)分布；元啟發(fā)式算法；隨機(jī)性算法；全局優(yōu)化；模擬退火算法；粒子群算法；差分進(jìn)化算法

自然科學(xué)、社會(huì)科學(xué)和工程應(yīng)用中的大部分問題都可以歸結(jié)為全局優(yōu)化問題。全局優(yōu)化問題廣泛應(yīng)用于圖像處理[1]、路徑規(guī)劃[2]、金屬橡膠卡箍隔振[3]、電力系統(tǒng)[4]、無線網(wǎng)絡(luò)規(guī)劃[5]等領(lǐng)域。近年，隨著對全局優(yōu)化問題研究的不斷深入，其理論和方法得到了進(jìn)一步的發(fā)展，一些優(yōu)秀的優(yōu)化算法也不斷被提出[6-8]。目前，主要的優(yōu)化算法可分為確定性算法和隨機(jī)性算法兩大類。確定性算法主要包括爬山法(Hill-Climbing)[9]、牛頓迭代法(Newton-Raphson)[10]和單純型法(simplex method)[11]等。對于確定性算法如果迭代開始于同樣的初始化猜想，算法將得到相同的系列解。其優(yōu)點(diǎn)主要集中于對于特定的問題擁有很高的收斂效率，往往僅需要很少的迭代次數(shù)。但是由于確定性算法屬于局部搜索算法，不可避免的容易陷入局部最優(yōu)。

而隨機(jī)搜索算法因其所特有的隨機(jī)機(jī)制可以使算法很容易跳出局部最優(yōu)從而找到全局最優(yōu)解。即使在相同的初始化條件下，算法也將會(huì)產(chǎn)生不同的解集。所以對于不同的個(gè)體其尋優(yōu)路線一般是不可重復(fù)的[12]。

大部分隨機(jī)搜索算法可以被認(rèn)為是元啟發(fā)式算法(metaheuristic algorithm)。很多新型的元啟發(fā)式算法大部分是受到自然界中物理過程或生物智能的啟發(fā)而提出的。比較有代表性的算法主要包括：模擬退火算法(simulated annealing， SA)[13]、差分進(jìn)化算法(differential evolution， DE)[14]、粒子群算法(particle swarm optimization， PSO)[15]、遺傳算法(genetic algorithm， GA)[16]、蟻群算法(ant colony optimization， ACO)[17]、人工蜂群算法(artificial bee colony， ABC)[18]、蝙蝠算法(bat algorithm， BA)[19]和螢火蟲算法(firefly algorithm， FA)[20]等。其優(yōu)點(diǎn)主要包括兩部分：算法自身所具有的良好的信息共享機(jī)制可以使算法在一定條件下快速收斂；隨機(jī)搜索算法不容易陷入局部最優(yōu)。

本文在深入分析螢火蟲算法基本原理的基礎(chǔ)上，提出基于隨機(jī)機(jī)制的改進(jìn)螢火蟲算法，以平衡算法間的全局探測與局部搜索能力。然后使用13個(gè)基本測試函數(shù)驗(yàn)證改進(jìn)算法的有效性。并對本文提出的算法與粒子群算法、差分算法和模擬退火算法進(jìn)行性能間的橫向比較。

1 螢火蟲算法

1.1 螢火蟲算法的生物學(xué)原理

螢火蟲算法(firefly algorithm， FA)是由劍橋大學(xué)學(xué)者Xinshe Yang于2008年提出的一種新型的自然啟發(fā)式優(yōu)化算法，該算法模擬自然界中熱帶螢火蟲的發(fā)光機(jī)制和行為方式，是一種基于群體智能的隨機(jī)搜索算法[21]。

自然界中的絕大多數(shù)螢火蟲都會(huì)閃光，螢火蟲利用這種閃光機(jī)制進(jìn)行求偶、溝通或者防御潛在的捕食者。這種閃光僅在一定范圍內(nèi)可以被其他螢火蟲感知，主要有以下兩方面原因：光強(qiáng)度和距離光源的距離成平方反比關(guān)系；光會(huì)被空氣所吸收。

為了構(gòu)建螢火蟲算法的數(shù)學(xué)模型，使用以下三個(gè)理想化準(zhǔn)則：

1) 算法中的所有螢火蟲都不分雌雄，即螢火蟲之間的吸引只基于亮度，不考慮性別。

2)螢火蟲之間的吸引力和亮度成正比，亮度越大，吸引力越強(qiáng)。因此亮度小的螢火蟲會(huì)向亮度大的螢火蟲移動(dòng)。

3)螢火蟲的光亮度與待優(yōu)化目標(biāo)函數(shù)的值有關(guān)。

1.2 標(biāo)準(zhǔn)螢火蟲算法的數(shù)學(xué)描述及實(shí)現(xiàn)

由于距離的增加和空氣對光的吸收，螢火蟲i的亮度會(huì)隨著距離r的增加而逐漸減小。為了對螢火蟲之間相互吸引力進(jìn)行建模，本文首先給出螢火蟲絕對亮度和相對亮度的定義。

定義1：絕對亮度。對于螢火蟲i，初始光強(qiáng)度(r=0處的光強(qiáng)度)為螢火蟲i的絕對亮度，記作Ii。

定義2：相對亮度。螢火蟲i在螢火蟲j所在位置處的光強(qiáng)度為螢火蟲i對螢火蟲j的相對亮度，記作Iij。

螢火蟲算法的核心思想是螢火蟲被種群中所有絕對亮度比它大的螢火蟲所吸引，并根據(jù)算法中的位置更新公式進(jìn)行位置更新，不斷迭代直至達(dá)到算法的停止準(zhǔn)則(達(dá)到既定的迭代次數(shù)或?qū)?yōu)精度)。下面，將分別對相對亮度、吸引力和位置更新機(jī)制進(jìn)行數(shù)學(xué)建模[22]。

一般情況下，我們用待優(yōu)化函數(shù)的目標(biāo)函數(shù)值表征算法的絕對亮度。假設(shè)在點(diǎn)x=(x1，x2，…，xd)處螢火蟲i的絕對亮度Ii與x處的目標(biāo)函數(shù)值成正比，即Ii∝f(x)。

考慮到螢火蟲i的亮度隨著距離的增加以及空氣的吸收而減弱，可以定義螢火蟲i對螢火蟲j的相對亮度為

(1)

式中：Ii為螢火蟲i的絕對亮度。γ為光吸收系數(shù)，可設(shè)為常數(shù)；rij為到螢火蟲i到螢火蟲j的笛卡爾距離:

(2)

假設(shè)螢火蟲j的絕對亮度比螢火蟲i的絕對亮度大，則螢火蟲i被螢火蟲j吸引而向j移動(dòng)。這種吸引力的大小是由螢火蟲j對螢火蟲i的相對亮度決定的，相對亮度越大，吸引力越大。則由螢火蟲j相對亮度的定義，可得螢火蟲j對螢火蟲i的吸引力βij(rij)為

(3)

式中：β0為最大吸引力，即在光源處(r=0處)螢火蟲的吸引力。此吸引力模型可以使種群中的個(gè)體自動(dòng)分成幾個(gè)小的種群，同時(shí)進(jìn)行尋優(yōu)，大大增加了算法的求解速度，尤其適合解決多模態(tài)問題。

由于被螢火蟲j吸引，螢火蟲i向其移動(dòng)而更新自己的位置，i位置更新公式為

(4)

式中：t為算法的迭代次數(shù)；εi是由高斯分布、均勻分布或者其他分布得到的隨機(jī)數(shù)；α為隨機(jī)項(xiàng)系數(shù)。此位置更新公式由三部分組成：第一部分為螢火蟲當(dāng)前時(shí)刻的位置信息，第二項(xiàng)為吸引力項(xiàng)，第三項(xiàng)是帶有特定系數(shù)的隨機(jī)項(xiàng)。

2 基于隨機(jī)機(jī)制的改進(jìn)螢火蟲算法

探測能力和搜索能力的平衡是大多數(shù)元啟發(fā)式式算法的核心問題[23-25]。探測能力體現(xiàn)出算法探測到新的解空間的能力，而搜索能力指的是算法在局部鄰域內(nèi)搜索到更高精度的解的能力。根據(jù)不同的分類方法，探測能力和搜索能力的平衡也可以理解為算法的多樣性和一致性之間的平衡[26]。

在元啟發(fā)式算法中，探測能力的提高一般可以通過引入隨機(jī)機(jī)制來實(shí)現(xiàn)[27-28]。隨機(jī)機(jī)制的引入可以使算法以更大的幾率跳出局部最優(yōu)從而實(shí)現(xiàn)全局搜索，以保證算法收斂到全局最優(yōu)。而搜索能力的提升更多是依賴于豐富的局部信息，如梯度、模態(tài)和算法運(yùn)行過程中的歷史信息。

事實(shí)上，隨機(jī)機(jī)制是元啟發(fā)式算法中非常重要的一種搜索機(jī)制。一方面，當(dāng)隨機(jī)步長較長時(shí)，算法可在全局范圍內(nèi)進(jìn)行搜索，從而可以在一定層度上增強(qiáng)算法的探測能力。另一方面，當(dāng)隨機(jī)步長大小減小到局部范圍內(nèi)的時(shí)候，算法可以在當(dāng)前最優(yōu)解附近進(jìn)行深度搜索，以增強(qiáng)算法的搜索能力。

綜合以上分析，在本文中，我們從兩個(gè)方面對螢火蟲算法的位置移動(dòng)公式進(jìn)行改進(jìn)。首先對式(4)中第二項(xiàng)吸引力項(xiàng)進(jìn)行改進(jìn)。在吸引力算子中加入隨機(jī)因素以對吸引力系數(shù)進(jìn)行擾動(dòng)，增加算法跳出局部最優(yōu)的能力。

(5)

本文中，分別取Ri為指數(shù)分布(exponentialdistribution)和韋伯布(weibulldistribution)，并分別記為EFA和WFA。

其次，對第3項(xiàng)帶有特定系數(shù)的隨機(jī)項(xiàng)進(jìn)行改進(jìn)。若隨機(jī)項(xiàng)系數(shù)α取固定值時(shí)，第3項(xiàng)則可以被認(rèn)為是完全隨機(jī)項(xiàng)。此時(shí)隨機(jī)項(xiàng)在整個(gè)算法運(yùn)行的過程中并不能特別有效的調(diào)節(jié)算法的探測能力和搜索能力。所以在本文中對隨機(jī)項(xiàng)系數(shù)α進(jìn)行遞減操作。以便隨機(jī)項(xiàng)在迭代初期擁有較大的隨機(jī)步長，使算法更好的在全局范圍內(nèi)進(jìn)行搜索；迭代后期步長逐漸減小，以便算法在局部范圍內(nèi)精細(xì)化搜索。α遞減公式為

(6)

式中：α0為初始隨機(jī)步長，δ為冷卻系數(shù)，S為待優(yōu)化問題的問題域。

綜上所述，改進(jìn)后的算法位置移動(dòng)公式為

(7)

改進(jìn)螢火蟲算法的偽代碼可表示為：

1)定義目標(biāo)函數(shù)f(x)，x=(x1，x2，…，xd)T

2)設(shè)置算法參數(shù)β0，γ，α0，Ri，δ以及最大迭代次數(shù)MaxGeneration

3)初始化螢火蟲種群xi(i=1，2，…n)，n為螢火蟲的個(gè)數(shù)

4)根據(jù)xi處的目標(biāo)函數(shù)值確定各個(gè)螢火蟲的絕對亮度

5)while(t

6)fori=1:n全部螢火蟲

7)forj=1:n全部螢火蟲

8)計(jì)算xi和xj之間的笛卡爾距離rij

9)if(Ij>Ii)

10)計(jì)算螢火蟲j對螢火蟲i的吸引力βij(rij)

11)由位置更新式(7)更新螢火蟲i的位置

12)endif

13)更新目標(biāo)函數(shù)值及螢火蟲的亮度

14)endforj

15)endfori

16)重新排列所有螢火蟲，找到當(dāng)前最優(yōu)解

17)endwhile

18)輸出最優(yōu)解及其對應(yīng)的位置信息

3 仿真實(shí)驗(yàn)與分析

3.1 基本測試函數(shù)

測試函數(shù)在評估算法性能方面起到了至關(guān)重要的作用，例如算法的收斂速度、求解精度、魯棒性以及性能表現(xiàn)的通用性。為了測試改進(jìn)的螢火蟲算法與其他已知算法的性能，本文從CEC2005推薦的基本測試函數(shù)中選取了13個(gè)測試函數(shù)進(jìn)行算法性能測試，所有函數(shù)都以求取極小值為例[29-30]。并根據(jù)其局部最優(yōu)解的個(gè)數(shù)，將13個(gè)測試函數(shù)分為：單模測試函數(shù)和多模測試函數(shù)。分別如表1和表2所示。

單模測試函數(shù)在問題域內(nèi)只含有一個(gè)全局最優(yōu)，因此適合測試函數(shù)的局部搜索能力。相對于算法最終的收斂精度，我們更關(guān)心此類測試函數(shù)的收斂速度的快慢。對于多模測試函數(shù)，隨著問題維數(shù)的增加其局部最優(yōu)值的數(shù)量呈指數(shù)級增加。所以此類測試函數(shù)適合測試算法的探測能力。由于關(guān)系到算法是否具有跳出局部最優(yōu)并尋找到近全局最優(yōu)的點(diǎn)的能力，因此我們更關(guān)注優(yōu)化算法求解此類問題時(shí)的求解精度問題。

表1 單模測試函數(shù)

表2 多模測試函數(shù)

3.2 算法參數(shù)設(shè)置

為了測試改進(jìn)的算法的性能，我們將其得到的結(jié)果與標(biāo)準(zhǔn)FA， SA， PSO以及DE進(jìn)行比較。

在所有算法中，種群大小設(shè)置為40，基本測試函數(shù)中問題的維數(shù)設(shè)置為30，最大迭代次數(shù)(即算法的停止準(zhǔn)則)為2 000，并在測試函數(shù)的問題域內(nèi)對種群進(jìn)行隨機(jī)初始化。另外，為了對算法性能進(jìn)行統(tǒng)計(jì)學(xué)分析，設(shè)置算法在不同的初始化條件下獨(dú)立運(yùn)行30次，并利用適應(yīng)度函數(shù)的最小值、最大值、均值和標(biāo)準(zhǔn)差進(jìn)行統(tǒng)計(jì)結(jié)果分析。

對于標(biāo)準(zhǔn)FA，設(shè)其初始化吸引力系數(shù)β0=1，光吸收系數(shù)γ=1，隨機(jī)系數(shù)α在整個(gè)迭代過程中單調(diào)遞減(α=0.25×0.95iter，其中0.25為初始化隨機(jī)因子，iter為當(dāng)前迭代代數(shù))。最后，由于Lévy飛行可以提供一些較長的跳躍使算法跳出局部最優(yōu)，選擇萊維飛行來產(chǎn)生隨機(jī)數(shù)εi。對于SA算法，其初始

溫度t0=0.1，溫度下降率α=0.99，并以p=e-δ/iter，δ=(fnew-f)/f的概率接受非最優(yōu)解。對于PSO算法，設(shè)置其學(xué)習(xí)因子c1=c2=2，慣性權(quán)重由ωmax=0.9到ωmin=0.4進(jìn)行線性遞減。在DE算法中設(shè)置縮放因子F=0.5，交叉系數(shù)Cr=0.9。表3為算法參數(shù)選取總結(jié)。

表3 算法參數(shù)選取

3.3 單模測試函數(shù)結(jié)果及分析

如上文所討論的，對于單模測試函數(shù)f1～f7，主要用來測試算法的局部搜索能力和收斂速度。對于30維的單模測試函數(shù)，其30次獨(dú)立實(shí)驗(yàn)的統(tǒng)計(jì)學(xué)結(jié)果如表4所示，其中最優(yōu)的均值結(jié)果已加粗顯示。

通過表4的統(tǒng)計(jì)分析結(jié)果可以看出，除了f3之外，對于單模測試函數(shù)EFA和WFA得到的測試結(jié)果要遠(yuǎn)遠(yuǎn)優(yōu)于其他的對比算法。通過分析30次獨(dú)立運(yùn)算得到的結(jié)果的均值，可以看出EFA和WFA具有較高的求解精度；同樣，通過分析表4中的方差結(jié)果可以看出，EFA和WFA具有較高的魯棒性。事實(shí)上，以上結(jié)論的得出符合無免費(fèi)午餐定理(no-freelunchtheorem)[31-32]，即沒有一個(gè)普適的算法其求解所有問題的能力都優(yōu)于其他算法。

表4 單模測試函數(shù)結(jié)果分析

球函數(shù)f1是最為常用的單模測試函數(shù)，在原點(diǎn)處取全局最優(yōu)。EFA、WFA和FA算法都能以較高的精度找到全局最優(yōu)，但相比較而言，PSO和DE算法最終解的精度并不高。對于f3而言，WFA和FA等陷入局部最優(yōu)，并不能得到理想的優(yōu)化解，但EFA和SA可以擺脫局部最優(yōu)從而尋找到全局最優(yōu)解。函數(shù)f5又可稱為bananafunction，其全局最優(yōu)處在一個(gè)平坦的拋物線形的峽谷地帶，相對較難優(yōu)化。對于此函數(shù)，WFA和SA都能得到比較理想的解，但SA得到的解的穩(wěn)定性相對較差。對于函數(shù)f6和f7來說，本文提到的幾種算法都可以得到較好的解，但EFA和WFA可以得到相對更優(yōu)秀的解。

下面，通過函數(shù)的收斂曲線進(jìn)一步分析本文涉及到的算法的性能。

如圖1所示，對于Sphere函數(shù)，EFA、WFA和FA算法在收斂速度和精度上都優(yōu)于SA、PSO和DE算法。其中，EFA、WFA和FA算法僅需200次迭代就能達(dá)到PSO和DE算法2000次迭代的精度；同樣，EFA、WFA和FA算法僅需800次迭代就能超越SA算法2 000次迭代的精度。從局部放大圖上可見，在整個(gè)迭代過程中，EFA、WFA和FA幾乎擁有相同的收斂性能。PSO算法在迭代初期收斂速度較慢，后期收斂速度加快，在1 700次迭代左右其收斂性能超越DE算法。

圖1 基于Sphere函數(shù)的算法性能比較Fig.1 Comparison between the mentioned algorithms on Sphere function

從圖2可以看出，對于Schwefel′s2.22函數(shù)，在迭代初期，所有的算法都具有較快的收斂速率。但是當(dāng)算法運(yùn)行到200代左右時(shí)，PSO算法和DE算法迅速陷入局部最優(yōu)。而EFA、WFA和FA則能跳出局部最優(yōu)，并向全局最優(yōu)進(jìn)行進(jìn)一步的搜索。

對于Schwefel′s2.21函數(shù)，通過圖3可知，EFA和WFA依然具有比較優(yōu)秀的表現(xiàn)，但是FA、PSO和DE卻在算法迭代初期就陷入局部最優(yōu)且在整個(gè)迭代過程中并沒有有效的機(jī)制使其跳出局部最優(yōu)。

3.4 多模測試函數(shù)結(jié)果及分析

同樣，對30維的多模測試函數(shù)進(jìn)行30次獨(dú)立測試，并對測試結(jié)果進(jìn)行統(tǒng)計(jì)學(xué)分析。對于多模測試函數(shù)，主要測試算法跳出局部最優(yōu)以尋求全局最優(yōu)的能力，即算法的全局探測能力。相對于算法的收斂速度，我們更看重其最終的收斂精度。

圖2 基于Schwefel′s 2.22函數(shù)的算法性能比較Fig.2 Comparison between the mentioned algorithms onSchwefel′s 2.22 function

圖3 基于Schwefel′s 2.21函數(shù)的算法性能比較Fig.3 Comparison between the mentioned algorithms onSchwefel′s 2.21 function

從表5中可以看出，對于多模測試函數(shù)，EFA、WFA和SA算法表現(xiàn)出較強(qiáng)的全局優(yōu)化能力。尤其是WFA算法，幾乎對所有的多模測試函數(shù)都能找到比較優(yōu)秀的全局最優(yōu)解。由此可以說明韋布分布可以為FA算法提供比較適宜的隨機(jī)擾動(dòng)步長，使算法能夠高效的跳出局部最優(yōu)，并向全局最優(yōu)解靠近。 FA、PSO和DE算法則比較容易陷入局部最優(yōu)，使最終得到的優(yōu)化結(jié)果并不理想。

下面，通過函數(shù)的收斂曲線進(jìn)一步分析本文涉及到的算法的性能。

如圖4所示，對于Rastrigin函數(shù)，WFA可以得到比較理想的優(yōu)化效果。在初始化迭代過程中，WFA、FA、EFA和SA算法都擁有較快收斂速度。隨著迭代的進(jìn)行，F(xiàn)A、EFA和SA算法迅速陷入局部最優(yōu)。有趣的是對于Rastrigin函數(shù)，F(xiàn)A和EFA幾乎擁有同樣的收斂曲線。PSO算法一直嘗試跳出局部最優(yōu)并向全局最優(yōu)點(diǎn)移動(dòng)，但整個(gè)迭代過程中，由于其收斂速率較慢，導(dǎo)致最終的收斂精度并不理想。DE算法在算法迭代初期就陷入局部最優(yōu)，并一直在局部最優(yōu)附近游蕩，直到算法迭代結(jié)束。

表5 多模測試函數(shù)結(jié)果分析

圖4 基于Rastrigin函數(shù)的算法性能比較Fig.4 Comparison between the mentioned algorithms onRastrigin function

從圖5可知，對于Griewank函數(shù)，WFA和EFA具有相當(dāng)快的收斂速度，在算法迭代400次左右時(shí)即能達(dá)到全局最優(yōu)并跳出迭代。FA和SA在算法迭代初期擁有較快的收斂速度，但是在400次迭代左右陷入局部最優(yōu)，且沒能成功跳出局部最優(yōu)，導(dǎo)致算法尋優(yōu)失敗。PSO算法在算法迭代初期，收斂速度較慢，但是當(dāng)算法迭代到第1 600代左右時(shí)，迅速向全局最優(yōu)點(diǎn)收斂。DE算法則一直以較慢的速度進(jìn)行尋優(yōu)。

圖5 基于Griewank函數(shù)的算法性能比較Fig.5 Comparison between the mentioned algorithms onGriewank function

對于Pendlized函數(shù)，通過圖6可以看出，EFA和WFA依然擁有較快的收斂速率和較高的收斂精度。FA和SA在算法迭代初期擁有較快的收斂速度，但很快就陷入局部最優(yōu)，直至算法迭代結(jié)束。PSO和DE則在整個(gè)迭代過程中以較慢的速率進(jìn)行收斂，最終得到優(yōu)于FA和SA算法的優(yōu)化解。

圖6 基于Pendlized函數(shù)的算法性能比較Fig.6 Comparison between the mentioned algorithms onPendlized function

4 結(jié)論

本文提出的改進(jìn)螢火蟲算法具有以下優(yōu)勢：

1)改進(jìn)算法中的隨機(jī)機(jī)制可以增加算法的全局探測能力，從而增加算法的求解速度；

2)隨機(jī)步長單調(diào)遞減機(jī)制可以使算法在迭代初期擁有較強(qiáng)的全局探測能力，后期擁有較強(qiáng)的局部探測能力，提高算法的收斂精度；

3)以上兩種機(jī)制的混合，可以使算法更好的平衡算法的全局探測能力和局部搜索能力，從而提升算法跳出局部最優(yōu)的能力和魯棒性。

4)由數(shù)值結(jié)果和算法的收斂曲線可以明顯看出改進(jìn)的螢火蟲算法的收斂速度和精度要遠(yuǎn)遠(yuǎn)高于粒子群算法和差分進(jìn)化算法。

[1]HORNG M H. Vector quantization using the firefly algorithm for image compression [J]. Expert systems with applications， 2012， 39(1): 1078-1091.

[2]劉利強(qiáng). 蟻群優(yōu)化方法研究及其在潛艇導(dǎo)航規(guī)劃中的應(yīng)用[D]. 哈爾濱：哈爾濱工程大學(xué)， 2007.

LIU Liqiang. Ant colony optimization methods and its applications in navigation planning for submarine [D]. Harbin: Harbin Engineering University， 2007.

[3]李鑫， 張利劍， 何銀銅. 改進(jìn)PSO的金屬橡膠卡箍隔振仿真分析與參數(shù)優(yōu)化[J]. 智能系統(tǒng)學(xué)報(bào)， 2015(4): 599-606.

LI Xin， ZHANG Lijian， HE Yintong. Simulation analysis and parameter optimization of vibration isolation of metal rubber clamps based on the modified PSO[J]. CAAI transactions on intelligent systems， 2015(4): 599-606.

[4]趙娜， 張伏生， 魏平，等. 基于改進(jìn)多粒子群算法的電力系統(tǒng)無功優(yōu)化[J]. 西安交通大學(xué)學(xué)報(bào)， 2006， 40(4): 463-467.

ZHAO Na， ZHANG Fusheng， WEI Ping， et al. Reactive power optimization based on improved poly-particle swarm optimization algorithm [J]. Journal of Xi′an Jiaotong University，2006， 40(4): 463-467.

[5]常遠(yuǎn)， 謝紅， 解武. 改進(jìn)智能算法的認(rèn)知無線Mesh網(wǎng)絡(luò)優(yōu)化頻譜分配算法[J]. 應(yīng)用科技， 2015(2): 24-28.

CHANG Yuan， XIE Hong， XIE Wu. Spectrum allocation optimization algorithm based on improved intelligence algorithm in cognitive wireless Mesh networks[J]. Applied science and technology， 2015(2): 24-28.

[6]PARDALOS P M， ROMEIJN H E. Handbook of global optimization:Vol.2. [M]. [S.l.]: Springer Science & Business Media， 2013.

[7]KAVOUSI-FARD A， SAMET H， MARZBANI F. A new hybrid modified firefly algorithm and support vector regression model for accurate short term load forecasting [J]. Expert systems with applications， 2014， 41(13): 6047-6056.

[8]SU C T， LEE C S. Network reconfiguration of distribution systems using improved mixed-integer hybrid differential evolution [J]. Power delivery， 2003， 18(3): 1022-1027

[9]GOLDFELD S M， QUANDT R E， TROTTER H F. Maximization by quadratic hill-climbing [J]. Econometrica: journal of the econometric society， 1966: 541-551.

[10]ABBASBANDY S. Improving Newton-Raphson method for nonlinear equations by modified Adomian decomposition method [J]. Applied mathematics and computation， 2003， 145(2): 887-893.

[11]NELDER J A， MEAD R. A simplex method for function minimization [J]. The computer journal， 1965， 7(4): 308-313.

[12]YANG X S. Nature-inspired metaheuristic algorithms， 2edEdition [M]. [S.l.]: Luniver Press, 2010.

[13]HWANG C R. Simulated annealing: theory and applications [J]. Acta applicandae mathematicae， 1988， 12(1): 108-111.

[14]STORN R， PRICE K. Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces [J]. Journal of global optimization， 1997， 11(4): 341-359.

[15]李小為， 胡立坤， 王琥. 速度約束下PSO的六自由度機(jī)械臂時(shí)間最優(yōu)軌跡規(guī)劃[J]. 智能系統(tǒng)學(xué)報(bào)， 2015(3): 393-398. LI Xiaowei， HU Likun， WANG Hu. PSO-based time optimal trajectory planning for six degrees of freedom robot manipulators with speed constraints[J]. CAAI transactions on intelligent systems， 2015(3): 393-398.

[16]DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm: NSGA-II [J]. Evolutionary computation， 2002， 6(2): 182-197.

[17]DORIGO M， BIRATTARI M， STüTZLE T. Ant colony optimization [J]. Computational intelligence magazine， 2006， 1(4): 28-39.

[18]KARABOGA D， BASTURK B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm [J]. Journal of global optimization， 2007， 39(3): 459-471.

[19]YANG X S. A new metaheuristic bat-inspired algorithm [M]. Nature inspired cooperative strategies for optimization (NICSO 2010). Springer Berlin Heidelberg， 2010: 65-74.

[20]YANG X S. Firefly algorithm， stochastic test functions and design optimization [J]. International journal of bio-inspired computation， 2010， 2(2): 78-84.

[21]YANG X S. Firefly algorithm， Levy flights and global optimization [M]. Research and development in intelligent systems XXVI. Springer London， 2010: 209-218.

[22]YANG X S. Firefly algorithm [J]. Nature-inspired metaheuristic algorithms， 2008， 20: 79-90.

[23]EIBEN A E， SCHIPPERS C A. On evolutionary exploration and exploitation [J]. Fundamenta informaticae， 1998， 35(1-4): 35-50.

[25]HARIK G R， LOBO F G， GOLDBERG D E. The compact genetic algorithm [J]. Evolutionary computation， 1999， 3(4): 287-297.

[26]LENSTRA J K. Local search in combinatorial optimization [M]. Princeton: Princeton University Press， 2003.

[27]YANG X S. Efficiency analysis of swarm intelligence and randomization techniques [J]. Journal of computational and theoretical nanoscience， 2012， 9(2): 189-198.

[28]TALBI E G. Metaheuristics: from design to implementation [M]. [S.l.]: John Wiley & Sons， 2009.

[29]BREST J， GREINER S， BOB， et al. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems [J]. Evolutionary computation 2006， 10(6): 646-657.

[30]YAO X， LIU Y， LIN G. Evolutionary programming made faster [J]. Evolutionary computation 1999， 3(2): 82-102.

[31]YANG X S. Free lunch or no free lunch: that is not just a question? [J]. International journal on artificial intelligence tools， 2012， 21(3): 1240010.

[32]WOLPERT D H， Macready W G. No free lunch theorems for optimization [J]. Evolutionary computation 1997， 1(1): 67-82.

An improved firefly algorithm and its application in global optimization

LIU Chang1，2， LIU Liqiang3， ZHANG Lina3， YANG Xinshe4

(1. College of Power and Energy Engineering， Harbin Engineering University， Harbin 150001， China; 2. Department of Navy Equipment Military Representative Office Shenyang Region， Harbin 150046， China; 3. College of Automation， Harbin Engineering University， Harbin 150001， China; 4. Design Engineering and Mathematics， Middlesex University， Hendon NW4 4BT， UK)

Escape from the local minimum of the standard firefly algorithm exhibits low probability， and hence an improved firefly algorithm was proposed in this article. In this paper， exponential distribution and weibull distribution were used for randomizing the firefly algorithm′s attractive mechanism to enhance the exploration ability of the algorithm. At the same time， randomized move terms can be changed by monotonous decreasing stratagem to improve the exploitation ability of the later iteration. In our experiments， extensive experiments were conducted between the modified firefly algorithm and the simulated annealing algorithm， particle swarm optimization， differential evolution algorithm on 13 benchmark functions. The results of these experiments indicate that the modified firefly algorithm can fairly balance the exploration and exploitation ability in the sense of avoiding the local optimum. Moreover， the convergence rate and the precision of the firefly algorithm can be improved significantly.

firefly algorithm; random distribution; metaheuristic algorithm; stochastic algorithm; global optimization; simulated annealing algorithm; particle swarm optimization; differential evolution algorithm

2016-05-31.

日期：2017-03-18.

國家自然科學(xué)基金項(xiàng)目(51109041， 51009036).

劉暢(1986-)， 男， 碩士研究生; 劉利強(qiáng)(1980-)， 男， 副教授， 副博士生導(dǎo)師.

劉暢， E-mail: nenga@163.com.

10.11990/jheu.201605106

TP18

A

1006-7043(2017)04-0569-09

劉暢，劉利強(qiáng)，張麗娜，等.改進(jìn)螢火蟲算法及其在全局優(yōu)化問題中的應(yīng)用[J]. 哈爾濱工程大學(xué)學(xué)報(bào)， 2017， 38(4): 569-577.

LIU Chang， LIU Liqiang， ZHANG Li′na， et al.An improved firefly algorithm and its application in global optimization[J]. Journal of Harbin Engineering University， 2017， 38(4): 569-577.

網(wǎng)絡(luò)出版地址：http://kns.cnki.net/kcms/detail/23.1390.u.20170318.0715.002.html