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

劉暢，劉利強，張麗娜，YANG Xinshe

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

?

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

劉暢1，2，劉利強3，張麗娜3，YANG Xinshe4

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

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

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

自然科學、社會科學和工程應(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)化問題研究的不斷深入，其理論和方法得到了進一步的發(fā)展，一些優(yōu)秀的優(yōu)化算法也不斷被提出[6-8]。目前，主要的優(yōu)化算法可分為確定性算法和隨機性算法兩大類。確定性算法主要包括爬山法(Hill-Climbing)[9]、牛頓迭代法(Newton-Raphson)[10]和單純型法(simplex method)[11]等。對于確定性算法如果迭代開始于同樣的初始化猜想，算法將得到相同的系列解。其優(yōu)點主要集中于對于特定的問題擁有很高的收斂效率，往往僅需要很少的迭代次數(shù)。但是由于確定性算法屬于局部搜索算法，不可避免的容易陷入局部最優(yōu)。

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

大部分隨機搜索算法可以被認為是元啟發(fā)式算法(metaheuristic algorithm)。很多新型的元啟發(fā)式算法大部分是受到自然界中物理過程或生物智能的啟發(fā)而提出的。比較有代表性的算法主要包括：模擬退火算法(simulated annealing， SA)[13]、差分進化算法(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)點主要包括兩部分：算法自身所具有的良好的信息共享機制可以使算法在一定條件下快速收斂；隨機搜索算法不容易陷入局部最優(yōu)。

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

1 螢火蟲算法

1.1 螢火蟲算法的生物學原理

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

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

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

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

2)螢火蟲之間的吸引力和亮度成正比，亮度越大，吸引力越強。因此亮度小的螢火蟲會向亮度大的螢火蟲移動。

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

1.2 標準螢火蟲算法的數(shù)學描述及實現(xiàn)

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

(4)

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

2 基于隨機機制的改進螢火蟲算法

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

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

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

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

(5)

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

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

(6)

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

綜上所述，改進后的算法位置移動公式為

(7)

改進螢火蟲算法的偽代碼可表示為：

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

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

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

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

5)while(t

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

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

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

9)if(Ij>Ii)

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

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

12)endif

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

14)endforj

15)endfori

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

17)endwhile

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

3 仿真實驗與分析

3.1 基本測試函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

球函數(shù)f1是最為常用的單模測試函數(shù)，在原點處取全局最優(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)處在一個平坦的拋物線形的峽谷地帶，相對較難優(yōu)化。對于此函數(shù)，WFA和SA都能得到比較理想的解，但SA得到的解的穩(wěn)定性相對較差。對于函數(shù)f6和f7來說，本文提到的幾種算法都可以得到較好的解，但EFA和WFA可以得到相對更優(yōu)秀的解。

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

如圖1所示，對于Sphere函數(shù)，EFA、WFA和FA算法在收斂速度和精度上都優(yōu)于SA、PSO和DE算法。其中，EFA、WFA和FA算法僅需200次迭代就能達到PSO和DE算法2000次迭代的精度；同樣，EFA、WFA和FA算法僅需800次迭代就能超越SA算法2 000次迭代的精度。從局部放大圖上可見，在整個迭代過程中，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ù)，在迭代初期，所有的算法都具有較快的收斂速率。但是當算法運行到200代左右時，PSO算法和DE算法迅速陷入局部最優(yōu)。而EFA、WFA和FA則能跳出局部最優(yōu)，并向全局最優(yōu)進行進一步的搜索。

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

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

同樣，對30維的多模測試函數(shù)進行30次獨立測試，并對測試結(jié)果進行統(tǒng)計學分析。對于多模測試函數(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)出較強的全局優(yōu)化能力。尤其是WFA算法，幾乎對所有的多模測試函數(shù)都能找到比較優(yōu)秀的全局最優(yōu)解。由此可以說明韋布分布可以為FA算法提供比較適宜的隨機擾動步長，使算法能夠高效的跳出局部最優(yōu)，并向全局最優(yōu)解靠近。 FA、PSO和DE算法則比較容易陷入局部最優(yōu)，使最終得到的優(yōu)化結(jié)果并不理想。

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

如圖4所示，對于Rastrigin函數(shù)，WFA可以得到比較理想的優(yōu)化效果。在初始化迭代過程中，WFA、FA、EFA和SA算法都擁有較快收斂速度。隨著迭代的進行，F(xiàn)A、EFA和SA算法迅速陷入局部最優(yōu)。有趣的是對于Rastrigin函數(shù)，F(xiàn)A和EFA幾乎擁有同樣的收斂曲線。PSO算法一直嘗試跳出局部最優(yōu)并向全局最優(yōu)點移動，但整個迭代過程中，由于其收斂速率較慢，導致最終的收斂精度并不理想。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具有相當快的收斂速度，在算法迭代400次左右時即能達到全局最優(yōu)并跳出迭代。FA和SA在算法迭代初期擁有較快的收斂速度，但是在400次迭代左右陷入局部最優(yōu)，且沒能成功跳出局部最優(yōu)，導致算法尋優(yōu)失敗。PSO算法在算法迭代初期，收斂速度較慢，但是當算法迭代到第1 600代左右時，迅速向全局最優(yōu)點收斂。DE算法則一直以較慢的速度進行尋優(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則在整個迭代過程中以較慢的速率進行收斂，最終得到優(yōu)于FA和SA算法的優(yōu)化解。

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

4 結(jié)論

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

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

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

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

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

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

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

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

[3]李鑫， 張利劍， 何銀銅. 改進PSO的金屬橡膠卡箍隔振仿真分析與參數(shù)優(yōu)化[J]. 智能系統(tǒng)學報， 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]趙娜， 張伏生， 魏平，等. 基于改進多粒子群算法的電力系統(tǒng)無功優(yōu)化[J]. 西安交通大學學報， 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]常遠， 謝紅， 解武. 改進智能算法的認知無線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的六自由度機械臂時間最優(yōu)軌跡規(guī)劃[J]. 智能系統(tǒng)學報， 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.

國家自然科學基金項目(51109041， 51009036).

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

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

10.11990/jheu.201605106

TP18

A

1006-7043(2017)04-0569-09

劉暢，劉利強，張麗娜，等.改進螢火蟲算法及其在全局優(yōu)化問題中的應(yīng)用[J]. 哈爾濱工程大學學報， 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