一種排序變異的改進蝙蝠算法

陳梅雯

(福建農林大學 計算機與信息學院，福建 福州 350002)

一種排序變異的改進蝙蝠算法

陳梅雯

(福建農林大學 計算機與信息學院，福建 福州 350002)

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

關鍵詞：蝙蝠算法；變異；多樣性；排序

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

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

1　蝙蝠算法

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

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

對于局部搜索部分，當一個解被選為當前最好解時，新解通過如下的隨機游走方式產生：

這里的ε∈[-1,1]是一個服從均勻分布的隨機數，At=

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

算法1.Bat Algorithm

Begin

初始化各參數及種群位置xi.

計算適應值，得出fitmin,x*.

Whi1e(不滿足停止條件)

For(i=1 to popsize)

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

If(rand＞ri)

通過公式(4)產生解.

EndIf{局部搜索}

檢查是否越界.

計算新的適應值fitnew.

If(fitnew

接收新解.

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

EndIf

EndFor

找出當前最佳解fitmin,x*.

EndWhi1e

End

2　排序變異的蝙蝠算法

2.1指數交叉變異

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

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

算法2.指數交叉操作

Begin

用公式(7)修改第j維

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

j=mod(j,dimension)+1

用公式(7)修改第j維

1en=1en+1;

Endwhi1e

End

其中Cr為指數分布概率，j∈[1,dimension]中的隨機數，1en表示修改維數的長度。

2.2排序選擇策略

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

（1）排名分配：種群中個體的適應度值按從優到差進行排列，每個個體的排名分配按照如下公式（8）：

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

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

（2）選擇概率：當前種群中每個個體的選擇概率按照公式（9）：

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

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

算法3.排序策略

Begin

隨機選擇r1[1,popsize]

Whi1e(rand＞pr1or r1==i)

隨機選擇r1[1,popsize]

Endwhi1e

隨機選擇r2[1,popsize]

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

隨機選擇r2[1,popsize] Endwhi1e

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

隨機選擇r3[1,popsize] Endwhi1e

End

其中rand∈[0,1]為服從均勻分布隨機數。

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

2.3RBA算法

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

算法3.RBA算法

Begin

初始化各參數及種群位置xi.

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

For(i=1 to popsize)

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

If(rand＞ri)

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

通過算法2實現指數交叉變異EndIf{局部搜索}

If(fitnew-fit(i)

接受新解.

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

EndIf

EndFor

找出當前最佳解fitmin,x*. EndWhi1e

End

3　仿真實驗與分析

3.1實驗函數及參數設置

為便與其它改進的BA算法進行性能比較，使用Iz1ok F J等[5]所用的10個測試函數進行實驗，見文后附表。實驗中的參數設置見表1。

表1　實驗參數表

注：BA算法中的參數依據源代碼給出，而RBA算法中的參數依據個人經驗給出。

表2　RBA算法與NRBA算法的實驗比較結果

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

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

受自然界的啟發，本文采用排序選擇策略對2.1節中的r1,r2兩個父個體有概率的擇優選取，表2列出了在D=30維空間上未排序和有排序的實驗結果，以函數適應值誤差“平均值±標準差”的呈現形式。其中用 “NRBA”表示未排序的算法，種群的規模popsize=D，迭代次數為2 000×D，每個算法獨立運行50次，為了公平，兩種算法中所有的參數都一致。

從表2數據可知，排序選擇策略對于提高算法的尋優性能是有影響的。對于f2，f3和f9函數，雖然函數適應值誤差近似，但根據統計實驗結果，RBA算法的尋優性能顯著優于NRBA算法。由此說明排序策略是有效的。

3.3尋優質量和收斂速度分析

表3給出了BA算法和RBA算法在D=30維空間上的函數適應度“平均值±標準差”的形式，其中，種群的規模popsize=D，迭代次數為2 000×D，每個算法獨立運行50次，其它參數設置見附表，數據加粗表示得到較好的解。

表3　BA算法與RBA算法的實驗比較結果

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

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

圖1　f1函數的收斂曲線

圖2　f3函數的收斂曲線

圖3 f6函數的收斂曲線

3.4與其它改進的BA算法及其它改進的群智能算法比較

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

從表4中可知，各種改進算法針對不同的函數，其尋優性能有所不同。如針對函數f7函數，ICS算法的求解精度高于其它三個算法；對f10函數，CSPSO算法的求解質量優于其它三個算法；根據統計結果，RBA算法的尋優性能明顯優于CSPSO算法、ICS算法和HSABA算法，表現出較強的競爭力。

表4　RBA算法與HSABA算法、ICS算法、CSPSO算法實驗比較結果

4　結論

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

參考文獻:

[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.

（責任編輯：葉麗娜）

中圖分類號：TP301.6

文獻標識碼：A

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

收稿日期：2015-09-10

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

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