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

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

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

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

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

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

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

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

1　引言

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

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

2　標(biāo)準(zhǔn)測(cè)試函數(shù)的選取

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

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

3　測(cè)試結(jié)果的不同比較方法

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

3.1統(tǒng)計(jì)數(shù)據(jù)的排序?qū)Ρ确?/p>

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

表2　實(shí)驗(yàn)數(shù)據(jù)的平均值與中位數(shù)統(tǒng)計(jì)結(jié)果

通過上表可以看出：

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

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

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

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

3.2執(zhí)行結(jié)果的圖像對(duì)比法

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

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

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

圖1　測(cè)試函數(shù)f（X　）運(yùn)算結(jié)果比較

圖2　測(cè)試函數(shù)（X　）運(yùn)算結(jié)果比較

圖3　測(cè)試函數(shù)f（X　）運(yùn)算結(jié)果比較

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

圖4　測(cè)試函數(shù)f（X　）運(yùn)算結(jié)果比較

圖5　測(cè)試函數(shù)f（X　）運(yùn)算結(jié)果比較

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

3.3平均距離與方差對(duì)比法

計(jì)算結(jié)果如下表：

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

通過上表可以看出：

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

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

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

該方法將數(shù)據(jù)量化，既能準(zhǔn)確的分析差異較大的實(shí)驗(yàn)數(shù)據(jù)又可分析實(shí)驗(yàn)數(shù)據(jù)有交叉的情況，彌補(bǔ)了前兩種方法的缺點(diǎn).適用于對(duì)任何一種標(biāo)準(zhǔn)測(cè)試函數(shù)的算法的分析和比較.

4　總結(jié)與展望

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

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

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

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

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

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

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

［7］劉長(zhǎng)平，葉春明.求解置換流水車間調(diào)度問題的布谷鳥算法.［J］上海理工大學(xué)學(xué)報(bào)，2013（1）.

［8］雍龍泉，和聲搜索算法研究進(jìn)展.［J］.計(jì)算機(jī)系統(tǒng)應(yī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］韓紅燕，潘全科，梁靜.改進(jìn)的和聲搜索算法在函數(shù)優(yōu)化中的應(yīng)用.［J］計(jì)算機(jī)工程，2010（13）.

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

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

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

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

［15］高慧旋.應(yīng)用多元統(tǒng)計(jì)分析.［D］北京大學(xué)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è)大學(xué)大學(xué)生創(chuàng)新訓(xùn)練計(jì)劃項(xiàng)目（201510225160）資助

2016年03月09日