蝙蝠算法的一種改進(jìn)

薛威力，賀興時(shí)，楊新社,2

(1.西安工程大學(xué) 理學(xué)院，西安 710048；2. 密德薩斯大學(xué) 科學(xué)與技術(shù)學(xué)院，英國倫敦NW4 4BT)

?

蝙蝠算法的一種改進(jìn)

薛威力1，賀興時(shí)1，楊新社1,2

(1.西安工程大學(xué) 理學(xué)院，西安 710048；2. 密德薩斯大學(xué) 科學(xué)與技術(shù)學(xué)院，英國倫敦NW4 4BT)

為了保持蝙蝠算法快速搜索能力，并提高算法尋優(yōu)精度和搜索能力，分析蝙蝠算法適應(yīng)度值方差與搜索過程中影響蝙蝠音量和脈沖發(fā)生率變化的參數(shù)的關(guān)系，為了維持解的多樣性，動(dòng)態(tài)調(diào)整蝙蝠算法搜索過程中影響蝙蝠音量和脈沖發(fā)生率變化的參數(shù)，并對適應(yīng)度值進(jìn)行擾動(dòng)，提出了一種基于方差改進(jìn)的蝙蝠算法(The improved Bat Algorithm based on the Variance，VBA)，并通過7個(gè)標(biāo)準(zhǔn)測試函數(shù)分別對BA和VBA進(jìn)行測試，結(jié)果表明，VBA的尋優(yōu)性能優(yōu)于BA.

蝙蝠算法；調(diào)整參數(shù)；自適應(yīng)蝙蝠算法；適應(yīng)度值方差

蝙蝠算法是Xin-she Yang在2010年基于回聲定位特性提出的一種算法[1].在適當(dāng)簡化下的特殊情況.為了提高蝙蝠算法性能，已研究出各種進(jìn)化的、有效的變種蝙蝠算法.如楊新社[2]提出了多目標(biāo)蝙蝠算法(MOBA)，且已證明其在解決工程中一些設(shè)計(jì)基準(zhǔn)問題上的有效性，Lin等人[3]提出了一種利用Levy飛行和混沌映射實(shí)現(xiàn)動(dòng)態(tài)生物系統(tǒng)參數(shù)估計(jì)的CBA算法，WANG G 等人[4]將和聲搜索算法與蝙蝠算法相結(jié)合, 得到了用于優(yōu)化函數(shù)基準(zhǔn)數(shù)值的混合蝙蝠算法. 賀興時(shí)等人[5]提出了基于模擬退火高斯擾動(dòng)的蝙蝠優(yōu)化算法.由于蝙蝠算法的具有快速收斂、效率高等特點(diǎn)，使該算法在多個(gè)學(xué)科和工程領(lǐng)域得到了廣泛的應(yīng)用[6-8].然而，如果我們允許通過快速改變和使算法快速切換到開發(fā)階段，將導(dǎo)致算法在一些初始階段之后出現(xiàn)停滯.本文提出通過維持解的多樣性來提高算法的尋優(yōu)精度.

1 蝙蝠算法

蝙蝠算法的思想首先設(shè)定以下理想的規(guī)則：

1) 所有的蝙蝠利用超聲波回音的感覺差異來判斷食物/獵物和障礙物之間的差異；

2) 蝙蝠是以速度vi，位置xi和固定頻率fmin(或波長λ)隨機(jī)飛行的，并用不同的波長λ(或頻率f)和音量A0來搜索獵物.它們會根據(jù)獵物的接近程度自動(dòng)調(diào)整他們發(fā)出脈沖的波長(或頻率)；

3) 雖然音量在不同形式下變化不同，這里我們假設(shè)音量是隨著從一個(gè)很大的(正數(shù))A0到最小值A(chǔ)min的變化.

另一個(gè)明顯的簡化是用無限追蹤來估計(jì)時(shí)間的延遲和三維地形的.雖然它在幾何計(jì)算中的應(yīng)用非常好，但是我們還是用不到它，因?yàn)槲覀兠媾R的大多是多維問題.

fi=fmin+(fmax-fmin)β

(1)

(2)

(3)

其中:β∈[0,1]是一個(gè)服從均勻分布的隨機(jī)向量.此處的x*表示當(dāng)前全局最優(yōu)位置(解)，它是在所有n只蝙蝠搜索到的解中進(jìn)行比較而得到的位置.

對于局部搜索，一旦在當(dāng)前最優(yōu)解中選中了一個(gè)解，那么每只蝙蝠是按照隨機(jī)游走產(chǎn)生的局部新解

xnew=xold+εAt

(4)

在一定程度上，BA可以看作是標(biāo)準(zhǔn)粒子群優(yōu)化和強(qiáng)化的局部搜索的平衡結(jié)合，其平衡是受音量和脈沖發(fā)生率的控制.當(dāng)蝙蝠找到獵物時(shí)，音量就會降低，同時(shí)脈沖發(fā)生率就會增加，音量會以任意簡便的值改變. 音量Ai和脈沖發(fā)生率ri按照以下迭代過程更新.

(5)

(6)

其中:α和γ為常量.實(shí)際上，α類似于本文中前面討論過的模擬退火中一個(gè)冷卻過程的冷卻因素.對任意的0<α<1,γ>0，有

(7)

最簡單的情況是令α=γ，在我們的實(shí)現(xiàn)中，使用的是α=γ=0.9.

2 改進(jìn)的蝙蝠算法(VBA)

為使蝙蝠算法保持高效，結(jié)合適應(yīng)度值方差提出使參數(shù)α和γ隨算法進(jìn)程動(dòng)態(tài)變化的策略：在算法前期α相對小的值，被更新音量的變化量相對大，使算法保持很強(qiáng)的全局搜索能力；在算法后期此時(shí)適應(yīng)度值多樣性減小，α相對大的值，提高算法的局部搜索能力.提出用式(9)實(shí)現(xiàn)參數(shù)α的自適應(yīng)策略：

(8)

α=αmax-αmin*ec*NI

(9)

其中:NI為當(dāng)前迭代次數(shù),maxgen為最大迭代次數(shù).實(shí)現(xiàn)了在算法前期以全局搜索為主、局部搜索為輔，以期能在全局范圍內(nèi)快速鎖定最優(yōu)值可能存在的若干區(qū)域；而后對算法保持一定全局搜索能力的同時(shí)，局部搜索逐漸加強(qiáng)，以期能提高收斂的速度和精度，又不至于陷入局部最優(yōu)，從而從整體上提升算法的性能.

γ的取值將影響脈沖發(fā)生率的變化快慢，間接影響種群多樣性，自適應(yīng)調(diào)整γ的值：γ增大時(shí)意味著脈沖發(fā)生率ri變化速度減慢，使搜索更加精細(xì)，則

(10)

在算法后期，種群多樣性減小，計(jì)算適應(yīng)度值的方差，當(dāng)方差變化較小時(shí)，在調(diào)整參數(shù)的基礎(chǔ)上對下一次迭代產(chǎn)生的新解分別施行Levy飛行擾動(dòng)[9]和高斯擾動(dòng)，干擾種群多樣性，使算法有效跳出局部最優(yōu)，以達(dá)到精確搜索的目的.

(11)

(12)

當(dāng)對算法的解施行Levy飛行擾動(dòng)和高斯擾動(dòng)時(shí)，分別產(chǎn)生一組新的解，進(jìn)行比較后將每個(gè)位置對應(yīng)的最好解保留，作為下一次搜索的最優(yōu)解使用.利用Levy飛行和高斯擾動(dòng)的特點(diǎn)能使算法搜索有效跳出早熟.

改進(jìn)的蝙蝠算法(VBA)的基本步驟概括如下[4]：

step1：初始化蝙蝠種群的規(guī)模n、第i只蝙蝠的位置x(i),(i=1,2,…,n)和速度v(i),i=1,2,…,n、脈沖發(fā)射率r、脈沖響度A(i)、脈沖頻率F(i)、適應(yīng)度值fitness(i),(i=1,2,…,n)、當(dāng)前最優(yōu)位置fbest、當(dāng)前最優(yōu)位置xbest；

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

step3：判斷新解的值是否滿足Znew≤fitness(i)，滿足則將執(zhí)行step4，否則轉(zhuǎn)入step2；

step4：比較新解和當(dāng)前最優(yōu)解適應(yīng)度值是否滿足fbest≥Znew，如果滿足則更新當(dāng)前最優(yōu)適應(yīng)度值及最優(yōu)位置；

step5：計(jì)算每次迭代所得適應(yīng)度值的方差，當(dāng)前適應(yīng)度值的方差與上一次適應(yīng)度值方差的差值小于ε時(shí),通過公式(9)(10)更新參數(shù)，并通過(1)(2)(11)，(1)(2)(12)分別產(chǎn)生新的解，比較原始解與擾動(dòng)后得到的兩組新解，保留最優(yōu)的適應(yīng)度值，并更新對應(yīng)的解；

step6：若算法滿足停止準(zhǔn)則，則停止；否則更新參數(shù)并轉(zhuǎn)至step3；

Step7：輸出全局最優(yōu)值gbest，算法結(jié)束.

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

本文選取7個(gè)測試函數(shù)分別對BA和VBA對進(jìn)行了仿真試驗(yàn)，7個(gè)測試函數(shù)均來自全局優(yōu)化測試函數(shù)庫[11]，如表1所示.各參數(shù)設(shè)置為n=50，A=0.25，r=0.5.實(shí)驗(yàn)硬件環(huán)境為Intel(R) Core(TM)2 Duo CPU T5900 @ 2.20 GHz 2.00GB，操作系統(tǒng)Window 7，利用Matlab編程實(shí)現(xiàn).

表1 測試函數(shù)

在同等實(shí)驗(yàn)條件下，設(shè)定10維時(shí)最大迭代次數(shù)為100，15，30維時(shí)最大迭代次數(shù)為200，(Zakharov函數(shù)在最大迭代次數(shù)為200)獨(dú)立運(yùn)行50次，計(jì)算最優(yōu)值、平均最優(yōu)值、均方誤差及達(dá)優(yōu)率(說明f1～f5的達(dá)優(yōu)率是參考各自最優(yōu)值相差5倍的數(shù)量級得到的結(jié)果，f6～f7是與測試函數(shù)最優(yōu)值進(jìn)行比較得到的結(jié)果)，見表2.

表2 測試結(jié)果

從表2的結(jié)果可以看出，基于方差改進(jìn)的蝙蝠算法提高了f1,f2～f5函數(shù)最優(yōu)值的精度，使蝙蝠算法的尋優(yōu)能力得到了提高并且能保持較高的達(dá)優(yōu)率；函數(shù)f2的達(dá)優(yōu)率雖然略低于蝙蝠算法，但VBA可以搜索到精確度更高的最優(yōu)值，對于該測試函數(shù)VBA一定程度上提高了蝙蝠算法的尋優(yōu)能力；對f6測試函數(shù)維數(shù)較低時(shí)，VBA的達(dá)優(yōu)率高于蝙蝠算法，而高維時(shí)雖然達(dá)優(yōu)率略有降低，但是算法尋優(yōu)精度得到了提高；對函數(shù)f7在一定程度上提高了算法的達(dá)優(yōu)率.總體上說明了在搜索過程中改進(jìn)后的算法可以有效地跳出局部最優(yōu)尋找到全局最優(yōu)值.

測試VBA的性能，對表2所示測試函數(shù)f1～f5進(jìn)行仿真模擬，得到算法的進(jìn)化曲線對比圖(作圖過程中由于數(shù)量級比較小對函數(shù)f3～f5迭代過程對應(yīng)的函數(shù)值取對數(shù)).進(jìn)化曲線的橫軸表示進(jìn)化的迭代次數(shù)，縱軸表示目標(biāo)函數(shù)的適應(yīng)度值(作圖過程中由于數(shù)量級比較小對函數(shù)f3～f5迭代過程對應(yīng)的函數(shù)值取對數(shù)).BA和VBA進(jìn)化曲線對比的圖像如圖1.

圖1 Ackely函數(shù)

Ackley函數(shù)是多模態(tài)函數(shù)，有少數(shù)的局部最小值.從圖1可以看出，對于Ackely函數(shù)來說，在整個(gè)進(jìn)化過程中VBA對個(gè)體優(yōu)化質(zhì)量優(yōu)于BA，在算法中期BA陷入局部最優(yōu)點(diǎn)無法跳出，表現(xiàn)出了早熟的特點(diǎn)，而VBA在低維和高維兩種情況都出現(xiàn)拐點(diǎn)，跳出局部最優(yōu)，最終收斂到了更加精確的全局最優(yōu)值. 從圖2可以看出，BA對于Ronsebrock函數(shù)高維時(shí)尋優(yōu)能力比較差，在整個(gè)進(jìn)化過程中VBA對個(gè)體優(yōu)化質(zhì)量優(yōu)于BA，在算法中期BA陷入局部最優(yōu)點(diǎn)無法跳出，表現(xiàn)出了早熟的特點(diǎn)，VBA在低維出現(xiàn)拐點(diǎn)，跳出局部最優(yōu)，最終收斂到了更加精確的全局最優(yōu)值，但在高維時(shí)VBA雖然在拐點(diǎn)處跳出局部最優(yōu)但再一次出現(xiàn)早熟的現(xiàn)象，優(yōu)化表現(xiàn)不明顯僅在尋優(yōu)速度上有所提高.

圖2 Ronsebrock函數(shù)

從圖3～5可以看出，對Sphere函數(shù)、Griewank函數(shù)、Zakharov函數(shù)，BA尋優(yōu)都會陷入局部最優(yōu)，雖然在迭代中出現(xiàn)拐點(diǎn)但仍然無法跳出局部最優(yōu)，而VBA可以在拐點(diǎn)處跳出局部最優(yōu)，尋找到精度更大的全局最優(yōu)值.

圖3 Sphere函數(shù)

圖4 Griewank函數(shù)

圖5 Zakharov函數(shù)

由以上所有函數(shù)的測試結(jié)果及進(jìn)化曲線對比可以得到以下結(jié)論: 本文提出的改進(jìn)算法的特點(diǎn)主要體現(xiàn)在搜索過程中算法能有效地跳出局部最優(yōu)，搜索精度有明顯的提高，并且尋優(yōu)速度也有所提高，所以基于方差改進(jìn)的蝙蝠優(yōu)化算法是合理并且有效地一種進(jìn)化算法.

4 結(jié) 語

本文在蝙蝠算法的基礎(chǔ)上提出了一種自適應(yīng)參數(shù)調(diào)整的蝙蝠優(yōu)化算法.分析表明適應(yīng)度值方差反映種群多樣性，通過適應(yīng)度值方差變化動(dòng)態(tài)的調(diào)整算法參數(shù)，并提出對適應(yīng)度值進(jìn)行擾動(dòng)增加解的多樣性的思想，從而尋求最優(yōu)位置.測試表明，改進(jìn)算法提高了尋優(yōu)精度及尋優(yōu)速度，并使算法后期能有效地跳出局部最優(yōu)，提高了蝙蝠群體的搜索能力.本算法也適合一般的函數(shù)優(yōu)化.如何進(jìn)一步使用方差的其他特征調(diào)整算法，并高效處理普通問題及多目標(biāo)問題，將是下一步的研究工作.

[1] YANG X S. Nature inspired cooperative strategies for optimization (NICSO 2010) [M]. Berlin: Springer Berlin Heidelberg, 2010. 65-74.

[2] YANG X S. Bat algorithm for multi-objective optimization [J]. International Journal of Bio-Inspired Computation, 2011, 3(5):267-274.

[3] LIN J H, CHOU C W, YANG C H. A chaotic Levy flight bat algorithm for parameter estimation in nonlinear dynamic biological systems [J]. Computer and Information Technology.2012, 2(2): 56-63.

[4] WANG G, GUO L. A Novel Hybrid Bat Algorithm With Harmony Search for Global Numerical Optimization [J]. Journal of Applied Mathematics, 2013, 21(1): 233-256.

[5] 賀興時(shí), 丁文靜, 楊新社. 基于模擬退火高斯擾動(dòng)的蝙蝠優(yōu)化算法 [J]. 計(jì)算機(jī)應(yīng)用研究, 2014, 31(2): 392-397.

[6] 肖輝輝, 段艷明. 基于DE算法改進(jìn)的蝙蝠算法的研究及應(yīng)用[J].工業(yè)工程, 2014, 31(1): 272-277.

[7] 劉長平, 葉春明. 具有Levy飛行特征的蝙蝠算法[J].智能系統(tǒng)學(xué)報(bào), 2013, 8(3): 240-246.

[8] 謝 健, 周永權(quán), 陳 歡. 一種基于Levy飛行軌跡的蝙蝠算法[J].模式識別與人工智能, 2013, 19(2): 51-54, 81.

[9] YANG X S. Nature-inspired metaheuristic algorithms [M].[S.l.], Luniver Press, 2010. 14-16.

[10] VALIAN E, MOHANNA S, TAVAKOLI S. Improved cuckoo search algorithm for global optimization [J]. International Journal of Communications and Information Technology, 2011, 1(1): 31-44.

[11] JAMIL M, YANG X S. A literature survey of benchmark functions for global optimization problems [J]. International Journal of Mathematical Modelling and Numerical Optimization, 2013, 4(2): 1-47.

Study on improved bat algorithm

XUE Wei-li1, HE Xing-shi1, YANG Xin-she1,2

(1. School of Science Xi’an Polytechnic University, Xi’an 710048, China;2. School of Science and Technology, Middlesex University, London NW4 4BT, UK)

In order to make the Bat Algorithm maintaining the strong search ability, and to improve the local search ability and the accuracy of the search for the optimal solution. An improved bat algorithm was proposed—the improved bat algorithm based on the variance (VBC). In this paper, the relationship between the parameters and the fitness variance of bat algorithm was analyzed. In order to maintain the diversity of solution it is to adjust parameters that affect the bat's volume and pulse generating at the search process of bat algorithm and to disturb the values. And it used BA and VBA to carry out numerical experiments for 7 test benchmarks. The results showed that VBA was superior to the BA.

bat algorithm; adjusted parameters; adaptive of bat algorithm; fitness variance

2015-10-14.

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(2014JM1006)；陜西省教育廳專項(xiàng)科研計(jì)劃項(xiàng)目(14JK1282).

薛威力(1989-)，男，碩士，研究方向：智能優(yōu)化算法.

TP18

A

1672-0946(2016)06-0706-07