一種排序變異的改進(jìn)蝙蝠算法

陳梅雯

(福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院，福建 福州 350002)

一種排序變異的改進(jìn)蝙蝠算法

陳梅雯

(福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院，福建 福州 350002)

摘要：針對(duì)蝙蝠算法易陷入局部最小值等不足，提出一種改進(jìn)的蝙蝠算法，局部搜索采用指數(shù)交叉變異，提高局部搜索能力的同時(shí)又保持種群多樣性；受自然界啟發(fā)，優(yōu)良的品種總是包含有好的信息，采用排序策略選擇較優(yōu)質(zhì)的個(gè)體進(jìn)行變異來產(chǎn)生優(yōu)質(zhì)的候選解。在典型測(cè)試函數(shù)上對(duì)新算法進(jìn)行了仿真，結(jié)果表明改進(jìn)的蝙蝠算法能夠有效提高算法的收斂速度并改善解的質(zhì)量，與其它改進(jìn)蝙蝠算法和改進(jìn)群智能算法的比較表明，改進(jìn)算法在求解多維函數(shù)優(yōu)化問題上是具有競(jìng)爭(zhēng)力的。

關(guān)鍵詞：蝙蝠算法；變異；多樣性；排序

近年來，受自然規(guī)律和生物群體智能行為的啟發(fā)，陸續(xù)提出了一些新穎的仿生群智能算法，如魚群算法、蜂群算法、螢火蟲算法、布谷鳥算法(Cuckoo Search,簡(jiǎn)稱CS)等[1]，在科學(xué)計(jì)算和工程技術(shù)領(lǐng)域內(nèi)顯示出獨(dú)特的特點(diǎn)和應(yīng)用效果。例如布谷鳥算法模擬布谷鳥寄生育雛行為以及鳥類或果蠅的Lévy飛行行為。蝙蝠算法（Bat Algorithm，簡(jiǎn)稱BA）[2]是模擬自然界中蝙蝠通過超聲波搜索,回聲定位行為，捕食獵物的生物學(xué)特性發(fā)展而來的一種新穎的群智能優(yōu)化算法，最早由Yang X S提出。目前BA算法已經(jīng)廣泛應(yīng)用于自然科學(xué)與工程科學(xué)領(lǐng)域中，但也存在易陷入局部極小點(diǎn)、后期收斂速度較慢等問題，針對(duì)這些不足，目前國(guó)內(nèi)外學(xué)者對(duì)BA算法提出相關(guān)的改進(jìn)策略，如謝健等[3]提出的基于Lévy飛行軌跡的LBA算法，Wang等[4]把和聲搜索作為變異算子嵌入到BA算法中，Iztok等[5]把DE算法策略應(yīng)用于局部搜索中，以此加強(qiáng)算法的局部求精能力，He等[6]提出的基于模擬退火和高斯擾動(dòng)的SAGBA算法，這些改進(jìn)策略都有效提高了BA算法的求解精度和收斂速度。

BA算法中個(gè)體的飛行由最佳解引導(dǎo)，以及局部搜索隨機(jī)游走于最佳解附近，這些導(dǎo)致種群多樣性降低過快，易陷入局部極小值，影響了算法的尋優(yōu)性能；其次，響度參數(shù)影響候選解的接收概率，有可能會(huì)使好的解丟失。本文受自然界現(xiàn)象的啟發(fā)，即優(yōu)良的品種總是包含有好的信息，它們應(yīng)該有更多的機(jī)會(huì)被用于引導(dǎo)其它物種。因此，針對(duì)BA算法局部搜索的不足，本文提出基于排序變異的改進(jìn)BA算法（improved bat algorithm with ranking-based mutation,簡(jiǎn)稱RBA）。仿真實(shí)驗(yàn)結(jié)果說明RBA算法有效地提高了算法的局部求精能力，并改善收斂速度和解的質(zhì)量。

1　蝙蝠算法

假設(shè)在D維空間中，蝙蝠i在t時(shí)刻的位置xit、速度vit更新公式為：

其中，β∈[0,1]是來自均勻分布的隨機(jī)變量，x*是全局最優(yōu)解。

對(duì)于局部搜索部分，當(dāng)一個(gè)解被選為當(dāng)前最好解時(shí)，新解通過如下的隨機(jī)游走方式產(chǎn)生：

這里的ε∈[-1,1]是一個(gè)服從均勻分布的隨機(jī)數(shù)，At=

基于上述，基本的BA算法的基本流程如算法1表示。

算法1.Bat Algorithm

Begin

初始化各參數(shù)及種群位置xi.

計(jì)算適應(yīng)值，得出fitmin,x*.

Whi1e(不滿足停止條件)

For(i=1 to popsize)

通過公式(1-3)產(chǎn)生新解.{飛行}

If(rand＞ri)

通過公式(4)產(chǎn)生解.

EndIf{局部搜索}

檢查是否越界.

計(jì)算新的適應(yīng)值fitnew.

If(fitnew

接收新解.

利用公式(5-6)更新ri和Ai.

EndIf

EndFor

找出當(dāng)前最佳解fitmin,x*.

EndWhi1e

End

2　排序變異的蝙蝠算法

2.1指數(shù)交叉變異

本文的重點(diǎn)是提高局部搜索的求精能力，算法1中的局部搜索受差分算法的啟示，公式(4)改為其中r1,r2,r3∈[1,popsize],且r1≠r2≠r3，r∈[-1,1]為服從均勻分布隨機(jī)數(shù)，達(dá)到雙向搜索，擴(kuò)大搜索范圍。

差分算法中有二項(xiàng)式和指數(shù)兩種交叉方式，Lin[7]和Zhao[8]的研究表明，使用指數(shù)概率分布的交叉效果要好于二項(xiàng)式交叉，因此本文采用指數(shù)交叉操作進(jìn)行局部搜索。具體描述如算法2。

算法2.指數(shù)交叉操作

Begin

用公式(7)修改第j維

Whi1e(rand<=Cr&1en<=dimension)

j=mod(j,dimension)+1

用公式(7)修改第j維

1en=1en+1;

Endwhi1e

End

其中Cr為指數(shù)分布概率，j∈[1,dimension]中的隨機(jī)數(shù)，1en表示修改維數(shù)的長(zhǎng)度。

2.2排序選擇策略

一般來說，對(duì)于公式（7）中的r1,r2,r3是從父代隨機(jī)選取的。在自然界中，優(yōu)質(zhì)的品種總是包含有好的信息，它們應(yīng)該有更多的機(jī)會(huì)被用于引導(dǎo)其它物種。因此通過排序的方式，讓較優(yōu)質(zhì)的個(gè)體更有機(jī)會(huì)被選中，Gong[9]等人的實(shí)驗(yàn)表明，基于排序選擇的策略用于原始的差分算法和改進(jìn)的差分算法中，其搜索性能都有明顯提高。

（1）排名分配：種群中個(gè)體的適應(yīng)度值按從優(yōu)到差進(jìn)行排列，每個(gè)個(gè)體的排名分配按照如下公式（8）：

Ri=NP-i,i=1,2,…,NP(8)

其中NP表示種群的大小，Ri表示第i個(gè)個(gè)體的分配值，從公式（8）可以看出，當(dāng)前種群中，排名越前的個(gè)體獲得的分配值就越大。

（2）選擇概率：當(dāng)前種群中每個(gè)個(gè)體的選擇概率按照公式（9）：

其中pi表示第i個(gè)個(gè)體的選擇概率，很明顯排名越前的個(gè)體，其概率值越高。

基于排序策略的選取公式（7）中的r1,r2的具體實(shí)現(xiàn)如算法3描述。

算法3.排序策略

Begin

隨機(jī)選擇r1[1,popsize]

Whi1e(rand＞pr1or r1==i)

隨機(jī)選擇r1[1,popsize]

Endwhi1e

隨機(jī)選擇r2[1,popsize]

Whi1e(rand＞pr2or r2==r1or r2==i)

隨機(jī)選擇r2[1,popsize] Endwhi1e

隨機(jī)選擇r3[1,popsize] Whi1e(r3==r2or r3==r1or r3==i)

隨機(jī)選擇r3[1,popsize] Endwhi1e

End

其中rand∈[0,1]為服從均勻分布隨機(jī)數(shù)。

最后，借鑒閾值接收算法[9]的策略來使用響度，在接收優(yōu)質(zhì)解的同時(shí)，概率接收劣質(zhì)解，這樣可以減少算法陷入局部極小的可能性，增加種群的多樣性，提高算法的穩(wěn)定性。

2.3RBA算法

綜合2.1和2.2，本文提出了基于排序變異操作應(yīng)用于局部搜索中的改進(jìn)蝙蝠算法，具體算法描述如下：

算法3.RBA算法

Begin

初始化各參數(shù)及種群位置xi.

計(jì)算適應(yīng)值，得出fitmin,x*. Whi1e(不滿足停止條件)

For(i=1 to popsize)

通過公式(1)(2)(3)產(chǎn)生新解.

If(rand＞ri)

通過算法3選擇r1,r2,r3

通過算法2實(shí)現(xiàn)指數(shù)交叉變異EndIf{局部搜索}

If(fitnew-fit(i)

接受新解.

利用公式(5-6)更新ri和Ai.

EndIf

EndFor

找出當(dāng)前最佳解fitmin,x*. EndWhi1e

End

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

3.1實(shí)驗(yàn)函數(shù)及參數(shù)設(shè)置

為便與其它改進(jìn)的BA算法進(jìn)行性能比較，使用Iz1ok F J等[5]所用的10個(gè)測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)，見文后附表。實(shí)驗(yàn)中的參數(shù)設(shè)置見表1。

表1　實(shí)驗(yàn)參數(shù)表

注：BA算法中的參數(shù)依據(jù)源代碼給出，而RBA算法中的參數(shù)依據(jù)個(gè)人經(jīng)驗(yàn)給出。

表2　RBA算法與NRBA算法的實(shí)驗(yàn)比較結(jié)果

注：“+”表示兩種算法獲得的平均適應(yīng)值誤差在置信水平0.05下Wilcoxon Signed-rank檢驗(yàn)是顯著的，而且RBA優(yōu)于NRBA；“-”表示兩算法獲得的平均適應(yīng)值誤差在置信水平0.05下Wilcoxon Signed-rank檢驗(yàn)是顯著的，而且RBA劣于NRBA；“=”表示兩算法獲得的平均適應(yīng)值誤差在置信水平0.05下Wilcoxon Signed-rank檢驗(yàn)是不顯著的。

3.2排序選擇策略對(duì)算法性能影響的分析

受自然界的啟發(fā)，本文采用排序選擇策略對(duì)2.1節(jié)中的r1,r2兩個(gè)父?jìng)€(gè)體有概率的擇優(yōu)選取，表2列出了在D=30維空間上未排序和有排序的實(shí)驗(yàn)結(jié)果，以函數(shù)適應(yīng)值誤差“平均值±標(biāo)準(zhǔn)差”的呈現(xiàn)形式。其中用 “NRBA”表示未排序的算法，種群的規(guī)模popsize=D，迭代次數(shù)為2 000×D，每個(gè)算法獨(dú)立運(yùn)行50次，為了公平，兩種算法中所有的參數(shù)都一致。

從表2數(shù)據(jù)可知，排序選擇策略對(duì)于提高算法的尋優(yōu)性能是有影響的。對(duì)于f2，f3和f9函數(shù)，雖然函數(shù)適應(yīng)值誤差近似，但根據(jù)統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果，RBA算法的尋優(yōu)性能顯著優(yōu)于NRBA算法。由此說明排序策略是有效的。

3.3尋優(yōu)質(zhì)量和收斂速度分析

表3給出了BA算法和RBA算法在D=30維空間上的函數(shù)適應(yīng)度“平均值±標(biāo)準(zhǔn)差”的形式，其中，種群的規(guī)模popsize=D，迭代次數(shù)為2 000×D，每個(gè)算法獨(dú)立運(yùn)行50次，其它參數(shù)設(shè)置見附表，數(shù)據(jù)加粗表示得到較好的解。

表3　BA算法與RBA算法的實(shí)驗(yàn)比較結(jié)果

注：“+”表示兩種算法獲得的平均適應(yīng)值誤差在置信水平0.05下Wilcoxon Signed-rank檢驗(yàn)是顯著的，而且RBA優(yōu)于BA；“-”表示兩算法獲得的平均適應(yīng)值誤差在置信水平0.05下Wilcoxon Signed-rank檢驗(yàn)是顯著的，而且RBA劣于BA；“=”表示兩算法獲得的平均適應(yīng)值誤差在置信水平 0.05下Wilcoxon Signed-rank檢驗(yàn)是不顯著的。

從表3中的最后一行可知，對(duì)于10個(gè)測(cè)試函數(shù)，RBA算法的求解質(zhì)量都比BA算法有顯著的提高，特別對(duì)于f5和f7函數(shù)，改進(jìn)算法獲得全局最優(yōu)解。同時(shí)，為了觀察兩種算法的收斂速度，下圖給出部分函數(shù)的收斂曲線圖，圖1至圖3圖形化展示了某些函數(shù)在兩種算法中的收斂過程。從圖1、圖2可看出RBA算法在f1和f3函數(shù)上前期具有較快的收斂速度，后期有較好的求精能力。圖3可看出，雖然BA算法在f6函數(shù)上一開始求解精度高于RBA算法，但后期求精能力差，可能是陷入局部極小值;而RBA算法一開始求解精度不高，但有較好的尋優(yōu)性能。從圖中很明顯看出，BA算法在求解精度和收斂速度都差于RBA算法。以上圖形直觀地說明了提出的改進(jìn)算法在很大程度上提高了基本算法的搜索性能。

圖1　f1函數(shù)的收斂曲線

圖2　f3函數(shù)的收斂曲線

圖3 f6函數(shù)的收斂曲線

3.4與其它改進(jìn)的BA算法及其它改進(jìn)的群智能算法比較

為了觀察RBA算法性能的競(jìng)爭(zhēng)性，表4給出了RBA算法和其它改進(jìn)的BA算法HSABA[5]，以及其它改進(jìn)的群智能算法，即ICS[10]算法和CSPSO[11]算法，顯示“平均適應(yīng)度值±標(biāo)準(zhǔn)差”的形式。同時(shí)表4中采用Zhan Z H等[12]的排序比較方法將每個(gè)算法求解各函數(shù)的平均適應(yīng)值誤差按升序排序，排序結(jié)果為“R”。例如，各算法求解函數(shù)f1函數(shù)，HSABA算法和RBA算法分別獲得最大和最小平均適應(yīng)值誤差，故其“R”分別為4和1。此外，“Rave”表示每個(gè)算法在所有函數(shù)上的平均排序，而“RK”表示每個(gè)算法根據(jù)“Rave”得到的最終排序。其中，種群個(gè)數(shù)popsize=20,維數(shù)D=30，函數(shù)評(píng)價(jià)次數(shù)FES=1 000×D，每個(gè)算法獨(dú)立運(yùn)行25次，HSABA算法、ICS算法和CSPSO算法的參數(shù)根據(jù)其各自文獻(xiàn)設(shè)置。

從表4中可知，各種改進(jìn)算法針對(duì)不同的函數(shù)，其尋優(yōu)性能有所不同。如針對(duì)函數(shù)f7函數(shù)，ICS算法的求解精度高于其它三個(gè)算法；對(duì)f10函數(shù)，CSPSO算法的求解質(zhì)量?jī)?yōu)于其它三個(gè)算法；根據(jù)統(tǒng)計(jì)結(jié)果，RBA算法的尋優(yōu)性能明顯優(yōu)于CSPSO算法、ICS算法和HSABA算法，表現(xiàn)出較強(qiáng)的競(jìng)爭(zhēng)力。

表4　RBA算法與HSABA算法、ICS算法、CSPSO算法實(shí)驗(yàn)比較結(jié)果

4　結(jié)論

BA算法是一種新元啟發(fā)式的優(yōu)化算法，該算法通過模擬蝙蝠回聲定位行為，改變頻率、響度和脈沖發(fā)射率，進(jìn)行最佳解的選擇，目前已經(jīng)廣泛應(yīng)用于自然科學(xué)與工程科學(xué)領(lǐng)域中。為進(jìn)一步提高BA算法的性能，本文提出了基于排序選擇的指數(shù)交叉變異的改進(jìn)蝙蝠算法。實(shí)驗(yàn)仿真結(jié)果說明改進(jìn)的策略能有效地提高BA算法的尋優(yōu)能力，并改善收斂速度和解的質(zhì)量，且與其它改進(jìn)的BA算法和改進(jìn)的群智能優(yōu)化算法做比較，表現(xiàn)出較好的競(jìng)爭(zhēng)力。此外，還需要在更多的實(shí)際優(yōu)化問題中對(duì)改進(jìn)算法進(jìn)行分析與驗(yàn)證。

參考文獻(xiàn):

[1]Yang X S,Deb S.Cuckoo search via Lévy f1ight[M]. Piscataway,NJ:IEEE Inc,2009:210-214.

[2]Yang X S.A new metaheuristic bat-inspired a1gorithm[M]. Ber1in:Springer,2010:65-74.

[3]Xie J,Zhou Y Q,Chen Huan.A bat a1gorithm based on Lévy f1ighttrajectory[J].PatternRecognitionandArtificia1 Inte11igence,2013,26(9):830-837.

[4]Wang G,Guo L H.A nove1 hybrid bat a1gorithm with Harmony search for g1oba1 numerica1 optimization.Hindawi pub1ishing corporation journa1 of app1ied[Z].Mathematics Vo1ume 2013,http://dx.doi.org/10.1155/2013/696491.

[5]Iztok F J,Simon F,Janez B,et a1.A nove1 hybrid se1fadaptive bat a1gorithm[Z].Hindawi Pub1ishing Corporation Scientific Wor1d Journa1 Vo1ume 2014，http://dx.doi.org/ 10.1155/2014/709738.

[6]He X S,Ding W J,Yang X S.Bat a1gorithm based on simu-1ated annea1ing and gaussian perturbations[J].Neura1 Computation&App1ication.2014,25(2):459-468.

[7]Dueck G,Scheuer T.Thresho1d accepting:a genera1 purpose a1gorithm appearing superior to simu1ate annea1ing[J].Journa1 of Computationa1 Physics,1990(12):161-175.

[8]Gong W Y,Cai Z H.Differentia1 evo1ution with rankingbased mutation operators[J].IEEE Trans Cybernetics,2013,43 (6):2066-2081.

[9]Va1ian E,Mohanna S,Tavako1i S.Improved cuckoo search a1gorithm for g1oba1 optimization[J].Int'1 Journa1 of Communications and Information Techno1ogy,2011,1(1):31-44.

[10]Wang F,He X S,Luo L G,et a1.Hybrid optimization a1gorithm of PSO and cuckoo search[A].In:proc.of the 2nd int'1 conf.on artificia1 inte11igence,management science and e1ectronic commerce(AIMSEC).Piscataway:IEEE Inc., 2011:1172-1175.

[11]Zhan Z H,Zhang J,Li Y,et a1.Orthogona1 1earning partic1e swarm optimization[J].IEEE Transaction on Evo1utionary Computation,2011,16(5):832-847.

（責(zé)任編輯：葉麗娜）

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1674-2109(2015)12-0050-06

收稿日期：2015-09-10

作者簡(jiǎn)介：陳梅雯(1978-),女，漢族，講師，主要從事計(jì)算智能及應(yīng)用研究。

Improved Bat Algorithm with Ranking-based Mutation

CHEN Meiwen

(Schoo1 of Computer and Information Science,Fujian Agricu1ture and Forestry University,Fuzhou 350002)

Abstract:Aiming at the shortages that bat a1gorithm is easy fa11ing into 1oca1 minimum,an improved bat a1gorithm is proposed.Exponentia1 crossover mutation is emp1oyed in the 1oca1 search,which improve searching capabi1ities whi1e maintaining the diversity of popu1ation on the process of iterations.Inspired by nature,good species a1ways contain good information,and hence,they have more chance to be uti1ized.So some of the parents in the mutation operators are proportiona11y se1ected according their rankings in the current popu1ation. The higher ranking a parent obtains,the more opportunity it wi11 be se1ected.The simu1ation experiments on typica1 test functions show the proposed method can improve the convergence speed and the qua1ity of the so1ution effective1y.Meanwhi1e,the resu1ts a1so revea1 the proposed a1gorithm is competitive for so1ving mu1ti-dimensiona1 function optimization compared with other improved bat a1gorithm and swarm inte11igence a1gorithms.

Key words:bat a1gorithm;mutation;diversity;ranking