幾類元啟發(fā)式優(yōu)化算法性能的比較研究*

孫文嬌 高颯 王瑞慶 李澤卿 譚悅 臧睿

（東北林業(yè)大學理學院，哈爾濱，150040）

幾類元啟發(fā)式優(yōu)化算法性能的比較研究*

孫文嬌 高颯 王瑞慶 李澤卿 譚悅 臧睿

（東北林業(yè)大學理學院，哈爾濱，150040）

元啟發(fā)式優(yōu)化算法包括螢火蟲算法、布谷鳥算法、蝙蝠算法及和聲搜索算法等.選取20個標準測試函數(shù)，統(tǒng)計4種元啟發(fā)式優(yōu)化算法的運行結果.以算法運行的精確度、穩(wěn)定性作為比較指標分析算法的求解性能，提出了3種比較算法優(yōu)劣性的方法，總結了3種比較方法的優(yōu)缺點.

優(yōu)化 螢火蟲算法 布谷鳥算法 蝙蝠算法 和聲搜索算法

1　引言

元啟發(fā)式優(yōu)化算法［1］，又被稱作現(xiàn)代優(yōu)化算法或智能優(yōu)化算法，是一類通用啟發(fā)式策略［2］，用來指導傳統(tǒng)啟發(fā)式算法朝著可能含有高質量解的搜索空間進行搜索，是人類通過對自然界現(xiàn)象的模擬和生物智能的學習，提出的一類新型的搜索技術.這類算法能夠彌補傳統(tǒng)算法只生成數(shù)量非常有限的解或者算法易陷入質量不高的局部最優(yōu)的缺陷［3］.螢火蟲算法由劍橋學者Yang提出，稱為FA（firefly algorithm），是模擬自然界中螢火蟲成蟲通過熒光進行信息交流的生物學特性發(fā)展而來，也是基于群體搜索的隨機優(yōu)化算法［4］，目前該算法在組合優(yōu)化問題的求解中已獲得成功應用，在解決NP難度問題上有著巨大潛力［5］.布谷鳥搜索算法由劍橋大學的Yang和拉曼工程大學的DEB，利用布谷鳥尋窩放置鳥蛋的行為，并結合一些鳥類的飛行行為提出的新型智能優(yōu)化算法［6］，該算法模型簡單、可調參數(shù)少、收斂速度快，在工程優(yōu)化等領域得到了應用［7］.和聲搜索算法是2001年韓國學者Geem等人提出的一種新穎的智能優(yōu)化算法.算法模擬了音樂創(chuàng)作中樂師們憑借自己的記憶，通過反復調整樂隊中各樂器的音調，最終達到一個美妙的和聲狀態(tài)的過程［8］，該算法較遺傳算法、模擬退火算法等有更好的優(yōu)化性能［9］，在函數(shù)優(yōu)化、組合優(yōu)化、生產調度等領域中得到了應用［10］.另外，蝙蝠算法是由劍橋大學的Yang于2010年提出的一種模擬蝙蝠捕食過程中所采用的回聲定位原理的啟發(fā)式智能算法［11］.蝙蝠算法模型簡單、收斂速度快、具有潛在并行性和分布式等特點，且沒有許多參數(shù)要進行調整［12］.目前，蝙蝠算法已在工程設計、分類、模糊聚類、預測和神經(jīng)網(wǎng)絡等領域中得到了應用［13］.

目前已有的研究結果表明不同的智能優(yōu)化算法對各類優(yōu)化問題求解性能表現(xiàn)多樣.對算法性能的比較通常從兩個角度進行，一類是對同一實際優(yōu)化問題進行求解比較，另一類是對若干已知最優(yōu)解的標準測試函數(shù)進行求解比較.第二類方法主要衡量算法的綜合性能，已有文獻對性能比較采用的主要方法是通過圖表形式直觀描述.本文選取螢火蟲算法、布谷鳥搜索算法、和聲搜索算法及蝙蝠算法對20個標準測試函數(shù)進行求解，對算法的可行性和有效性進行了驗證.選取若干典型的測試結果從三個方面比較了算法性能，并對這些方法進行了評價.

2　標準測試函數(shù)的選取

為了探究螢火蟲算法、布谷鳥算法、蝙蝠算法以及和聲搜索算法的在計算函數(shù)最優(yōu)值方面的差異，將四類智能優(yōu)化算法分別應用于20個標準測試函數(shù)，選取其中9個運算結果差異較為顯著的標準測試函數(shù)進行比較.

表1　選取的部分測試函數(shù)表

3　測試結果的不同比較方法

本節(jié)根據(jù)相關技術規(guī)范要求在MATLAB 2010a平臺上對每個標準測試函數(shù)用4類智能優(yōu)化算法分別獨立計算30次.通過對執(zhí)行結果進行不同角度的分析具體比較這4類智能算法對標準測試函數(shù)的作用結果精確度以及算法的穩(wěn)定性的差異.

3.1統(tǒng)計數(shù)據(jù)的排序對比法

將實驗所得30次執(zhí)行結果的數(shù)據(jù)進行統(tǒng)計，利用執(zhí)行結果的中位數(shù)和平均值衡量算法對標準測試函數(shù)的作用效果，對四種不同的算法進行分析.

表2　實驗數(shù)據(jù)的平均值與中位數(shù)統(tǒng)計結果

通過上表可以看出：

對于f*1X（），可以明顯看出四個算法優(yōu)劣性依次為：布谷鳥算法、螢火蟲算法、蝙蝠算法、和聲搜索算法.

對于f*7X（），可以明顯看出螢火蟲算法和布谷鳥算法同等程度地近似于理論最優(yōu)值其次為和聲搜索算法，最后是蝙蝠算法.

對于f*9X（），可以明顯看出四個算法的優(yōu)劣排序依次為：螢火蟲算法、蝙蝠算法、布谷鳥算法、和聲搜索算法.

用該方法評價算法準確性時，對于所得的統(tǒng)計數(shù)據(jù)差異較大的情況可以直接明顯的判斷出優(yōu)劣排序，但用中位數(shù)和平均值作為參考值未能反映30次運行結果的波動幅度.

3.2執(zhí)行結果的圖像對比法

將執(zhí)行得到的30次結果繪制成二維圖像，通過圖像偏離理論值的情況以及圖像自身的波動情況比較不同算法對標準測試函數(shù)的作用效果.

關于f*2（X）的執(zhí)行結果，比較圖像可以看出，螢火蟲算法與最優(yōu)解最為接近；蝙蝠算法在最優(yōu)解附近浮動；布谷鳥算法稍大，和聲算法結果遠大于最優(yōu)解.

關于f*5（X）的執(zhí)行結果，比較圖像可以看出，布谷鳥算法最接近最優(yōu)解；螢火蟲算法較為接近，其他算法比較穩(wěn)定.

圖1　測試函數(shù)f（X　）運算結果比較

圖2　測試函數(shù)（X?。┻\算結果比較

圖3　測試函數(shù)f（X?。┻\算結果比較

關于f*5（X）的執(zhí)行結果，比較圖像可以看出，螢火蟲與布谷鳥算法能夠精確地和最優(yōu)解擬合.蝙蝠算法有較小偏差，和聲算法最不穩(wěn)定.

圖4　測試函數(shù)f（X　）運算結果比較

圖5　測試函數(shù)f（X?。┻\算結果比較

由圖1、圖2、圖3得該方法可以簡潔直觀地反映出每個算法對不同的標準測試函數(shù)的作用情況，但對圖4和圖5數(shù)據(jù)有交叉的測試函數(shù)，如f*6X（），f*8X（）結果無法通過圖像的分布來判斷算法的優(yōu)劣.

3.3平均距離與方差對比法

計算結果如下表：

表3　實驗數(shù)據(jù)的平均距離和均方差

通過上表可以看出：

對于f*3（X）布谷鳥算法的測試結果的精確度較其他算法最高，算法的穩(wěn)定性好，其次是和聲搜索算法精確度較高，算法也比較穩(wěn)定性；然后是蝙蝠算法，螢火蟲算法對它的精確程度最差，并且在解決這一問題時較其它算法具有不穩(wěn)定性.

對于f*6（X）可以分析得知蝙蝠算法的測試結果跟其它算法相比具有較高的精確度和穩(wěn)定性，其次布谷鳥算法和螢火蟲算法搜索算法二者在精確度上相差不大，但相比之下，布谷鳥算法的穩(wěn)定性較高，最后是和聲搜索算法在該函數(shù)的測試上的精確度較其他算法低.

對于f*8X（）可以看出蝙蝠算法的精確程度最高，布谷鳥算法、和聲搜索算法次之，螢火蟲算法在該問題的精確度上最差.

該方法將數(shù)據(jù)量化，既能準確的分析差異較大的實驗數(shù)據(jù)又可分析實驗數(shù)據(jù)有交叉的情況，彌補了前兩種方法的缺點.適用于對任何一種標準測試函數(shù)的算法的分析和比較.

4　總結與展望

隨著智能算法的發(fā)展和其應用領域的推廣，算法的優(yōu)劣差異也需要進一步的研究和比較，以便解決不同方面的問題.一般來說，算法的評價有多個指標，多種方法，本文主要從算法的精確度和穩(wěn)定性兩個方面來研究算法的差異，并提出了3種比較算法優(yōu)劣差異的方法，總結了3種比較方法的優(yōu)缺點.螢火蟲算法、布谷鳥算法、蝙蝠算法以及和聲搜索算法是以20個標準測試函數(shù)作為實驗的背景問題.為了更合理的評價算法效果，可采用更大數(shù)量的測試函數(shù)，或嘗試構造新的測試函數(shù)以得出更為準確的評價結果.

［1］趙玉新Xin-She Yang劉立強.新興元啟發(fā)式優(yōu)化方法，［M］科學出版社.

［2］徐俊杰.元啟發(fā)式優(yōu)化算法理論［D］.北京：北京郵電大學.

［3］陳萍.啟發(fā)式算法及其在車輛路徑問題中的應用.［D］.北京：北京交通大學.

［4］劉長平，葉春明.一種新穎的放生群智能優(yōu)化算法：螢火蟲算法.［J］計算機應用研究，2011，（28）.

［5］曾冰，李明富，張翼，馬建華.基于螢火蟲算法的裝配序列規(guī)劃研究.［J］機械工程學報，2013（11）.

［6］李煜，馬良.新型元啟發(fā)式布谷鳥搜索算法.［J］.系統(tǒng)工程，2012，（30）.

［7］劉長平，葉春明.求解置換流水車間調度問題的布谷鳥算法.［J］上海理工大學學報，2013（1）.

［8］雍龍泉，和聲搜索算法研究進展.［J］.計算機系統(tǒng)應用，2011，（20）.

［9］Mahdavi M，F(xiàn)esanghary M，Damangir E.An improved harmony search algorithm for solving optimization problems［J］.Applied Mathematics and Computation，2007，188（2）：1567-1579.

［10］韓紅燕，潘全科，梁靜.改進的和聲搜索算法在函數(shù)優(yōu)化中的應用.［J］計算機工程，2010（13）.

［11］劉長平，葉春明.具有Levy飛行特征的蝙蝠算法.［J］智能系統(tǒng)學報，2013（8）.

［12］劉長平，葉春明.具有混沌搜索策略的蝙蝠優(yōu)化算法及性能仿真.［J］系統(tǒng)仿真學報，2013（6）.

［13］賀新時，丁文靜，楊新社.基于模擬退火高斯擾動的蝙蝠優(yōu)化算法.［J］計算機應用研究，2014（2）.

［14］王柱.最小平方距離法和隱式線性函數(shù)關系的參數(shù)估計.［J］數(shù)理統(tǒng)計與管理，2013（5）.

［15］高慧旋.應用多元統(tǒng)計分析.［D］北京大學252-255.

A Comparison on the Performance of Some Novel Meta-heuristic Optimization Algorithms

Sun Wenjiao Gao Sa Wang Ruiqing Li Zeqing Tan Yue Zang Rui
（College of Science，Northeast Forestry University，Harbin 150040，China）

Firefly algorithm，cuckoo search algorithm，bat algorithm and harmony search algorithm are four novel meta-heuristic optimization algorithms.By analyzing the performace，the accuracy and the stability of these algorithms on 20 standard test functions，the superior and interior of these algorithms are compared in three ways.

Optimization Firefly algorithm Cuckoo search algorithm Bat algorithm Harmony search algorithm

東北林業(yè)大學大學生創(chuàng)新訓練計劃項目（201510225160）資助

2016年03月09日