改進的新型蝙蝠算法

呂趙明，張穎江

(湖北工業(yè)大學 計算機學院，湖北 武漢 430068)

0 引 言

在許多科學計算中都會遇到最優(yōu)化問題，最優(yōu)化問題是通過對無限可行的方案進行尋優(yōu)從而得到最優(yōu)的方案。傳統(tǒng)的優(yōu)化算法，如線搜索、非線性搜索、線性規(guī)劃和整數(shù)規(guī)劃等，對函數(shù)有一定要求，對高維、非線性的問題計算復雜度大，在實際工程中不適用。20世紀50年代中期一些研究者擺脫了經(jīng)典數(shù)學優(yōu)化方法，受生物群體行為特點、覓食方法等機理的啟發(fā)，提出了仿生智能優(yōu)化算法，如進化算法、粒子群算法、人工蜂群算法等，對傳統(tǒng)算法無法處理的問題可以求解到較好的結果。

Yang Xinshe教授受蝙蝠利用回聲定位的能力在黑暗中捕食獵物和躲避障礙物行為的啟發(fā)，在2010年提出了蝙蝠算法(BA)[1-2]。在對基本的蝙蝠算法進行試驗研究后，發(fā)現(xiàn)基本蝙蝠算法存在易陷入局部最優(yōu)、求解精度不高等缺陷。文獻[3]通過自適應改變蝙蝠的步長，提高了算法的求解精度。文獻[4]把差分進化算法應用到蝙蝠算法中，提高了算法的性能。文獻[5]提出每只蝙蝠動態(tài)自適應地調(diào)整自己的飛行速度和方向，不僅提高了全局搜索性能，而且有效避免了過早收斂。

在上述研究的基礎上，文中提出了基于細菌覓食算法算子改進的新型蝙蝠算法。為了避免陷入局部最優(yōu)，融合細菌覓食算法的趨化算子來提高算法的局部搜索能力；為了提高算法的求解精度，增加了試探擾動因子來充分搜索解空間，采用隨機慣性權重[6]來平衡算法的探索能力和挖掘能力。

1 蝙蝠算法

基本蝙蝠算法的仿生原理是模仿蝙蝠的回聲定位的機制設計的仿生智能優(yōu)化算法。該算法將空間中捕食的蝙蝠模擬為問題的解，將蝙蝠不斷變化的位置模擬為問題函數(shù)的適應度值，將蝙蝠捕食過程中不斷變化的頻率、脈沖速率、音強模擬為解的優(yōu)化搜索過程，整個群體的運動在問題求解空間中產(chǎn)生從無序到有序的演化過程[1-2]。

具體的仿真數(shù)學模型為蝙蝠在d維空間中位置和速度的更新，通過以下公式實現(xiàn)：

fi=fmin+(fmax-fmin)β

(1)

(2)

(3)

xnew=xold+εAt

(4)

在迭代過程中，一旦蝙蝠發(fā)現(xiàn)了獵物，其脈沖發(fā)射的響度Ai通常會減小，而脈沖速率ri會相應增加。其調(diào)整方式表示為：

(5)

(6)

其中，α為音強的衰減系數(shù)；γ為脈沖速率增加系數(shù)。對于任何0<α<1和γ>0的量都有：

(7)

通過多次試驗，發(fā)現(xiàn)α=γ=0.9效果較好。初始化時每只蝙蝠都應該有不同的音強和脈沖速率，如果新解被更新，它們的音強和脈沖速率將相應更新，也就意味著蝙蝠正在向最優(yōu)解移動。

基本蝙蝠算法的計算步驟如下：

步驟1：設置算法的基本參數(shù)，包括種群大小、空間維數(shù)、音強衰減系數(shù)α、脈沖頻率fi、脈沖速率增加系數(shù)γ、最大音強A、迭代次數(shù)；

步驟2：初始化蝙蝠種群的位置、速度、脈沖速率ri和音強Ai，計算每只蝙蝠的適應度值，找出當前蝙蝠的最佳位置和適應值；

步驟3：通過式1～3調(diào)整頻率來更新蝙蝠的位置和速度；

步驟4：根據(jù)產(chǎn)生的隨機數(shù)，如果(rand>ri)對當前最佳解的位置進行隨機擾動產(chǎn)生新位置，并計算新解；

步驟5：根據(jù)產(chǎn)生的隨機數(shù)和產(chǎn)生的新解，如果(rand

步驟6：判斷新解是否優(yōu)于全局最優(yōu)解，若優(yōu)于全局最優(yōu)解，則更新最優(yōu)解和最優(yōu)蝙蝠位置；

步驟7：判斷是否滿足最大迭代次數(shù)，不滿足轉步驟3；

步驟8：對結果進行分析輸出，算法結束。

2 細菌覓食算法

細菌覓食算法(bacterial foraging optimization,BFO)[7-9]是K.M.Passino在2002年模仿細菌在人體腸道內(nèi)尋找食物的行為提出的群體智能算法，該算法有三個算子，分別是趨化算子、繁殖算子、遷徙算子。算法在進行搜索時按照三個算子的執(zhí)行順序依次執(zhí)行，從而使得待求的解不斷更新，不斷逼近最優(yōu)解。

趨化算子是算法的核心部分，決定著細菌能否找到食物源，對算法的性能和收斂性有著極其重要的影響。其中包括翻轉和前進兩種算子，翻轉算子表示細菌向任意方向移動的模式；前進算子表示在細菌翻轉后，若適應值沒有得到改善而沿著同一方向移動若干步，直到達到最大移動次數(shù)或其適應度值穩(wěn)定的模式。相對應的公式如下：

Xi(j+1,k,l)=Xi(j,k,l)+rand()×step×Φ(i)

(8)

(9)

其中，Xi(j,k,l)表示細菌個體i當前的位置，j表示細菌的第j代趨化算子，k表示細菌的第k代繁殖算子，l表示細菌的第l代遷徙算子；step表示前進步長；Φ(i)表示細菌的隨機翻滾方向；Xrand(j,k,l)表示當前個體領域內(nèi)的一個隨機位置。

3 新型蝙蝠算法

基本蝙蝠算法在尋優(yōu)過程中，當搜索到近似解后會出現(xiàn)停滯現(xiàn)象，表明此時種群沒有進化能力，導致種群多樣性受到限制而最終陷入局部最優(yōu)解，對高維復雜函數(shù)問題就會明顯地出現(xiàn)尋優(yōu)精度不高的現(xiàn)象，可見種群的多樣性及種群的質量對蝙蝠算法的性能起著決定性作用?；掘鹚惴ㄍ请S機初始化一定數(shù)量的種群，這樣會出現(xiàn)種群的不均勻現(xiàn)象，導致算法陷入局部最優(yōu)?；掘鹚惴ㄔ谡{(diào)整自身速度時是通過隨機頻率、位置差和上一代的速度來更新當前速度的，缺乏對父代速度繼承的特性，這樣算法缺乏均衡搜索的能力。從算法的步驟4和步驟5可以看出，蝙蝠發(fā)現(xiàn)獵物后，若適應值和音強沒有同時減小，則當前蝙蝠的適應度值不改變，另外若適應值沒有當前最小適應值優(yōu)，則丟棄該位置，這樣可能跳過鄰近最優(yōu)解[10-15]。

基于以上分析，文中采用細菌覓食算法的趨化算子來改善種群的均勻度，提高種群的質量，從而改進蝙蝠算法的局部搜索能力；增加隨機慣性權重來提高蝙蝠對父代的繼承性，從而均衡搜索能力；增加試探擾動因子來提高算法搜索的充分性和求解精度。

為了改善種群的均勻度，提高種群的質量，融合細菌覓食算法的趨化算子。細菌覓食算法的趨化算子是細菌躲避有害區(qū)域向食物源區(qū)域聚集的行為。趨化算子又包括翻轉算子和前進算子，翻轉算子是通過先將每只細菌進行翻滾，使其向一個隨機方向前進一個步長后判斷適應值是否得到改善，若適應值得到改善，則細菌繼續(xù)在這個方向上前進指定的步數(shù)，若此時細菌的適應度值不再改善或達到了指定的步數(shù)，則算法結束[8]。由此可見，前進算子使細菌個體在自己的領域范圍進行了深度的尋優(yōu)搜索，這樣在領域內(nèi)能找到更加優(yōu)秀的解，從而增強了算法的局部搜索能力。在經(jīng)過趨化算子后，每個個體都靠近了食物豐富的區(qū)域，改善了最初的位置，就整個群體來看，整個種群得到了均勻化，提高了整個群體的質量。

趨化算子的搜索步驟如下：

步驟1：根據(jù)式8和式9計算翻轉算子；

步驟2：判斷群體的適應度值是否得到改善；

步驟3：若得到改善，群體執(zhí)行前進算子；

步驟4：判斷群體的適應度值是否得到改善；

步驟5：若得到改善，判斷是否達到指定的最大前進次數(shù)，若沒有達到跳轉到步驟3；

步驟6：判斷趨化算子的執(zhí)行次數(shù)，若達到，算法結束并輸出優(yōu)化后的群體，否則跳轉到步驟1繼續(xù)執(zhí)行。

為了提高蝙蝠對父代的繼承性，從而均衡搜索能力，使用下面的速度調(diào)整公式：

(10)

w=μ+σ*N(0,1)

(11)

μ=μmin+(μmax-μmin)*rand(0,1)

(12)

其中，μmax,μmin為隨機權重平均值的最大值和最小值；σ為隨機權重的方差；N(0,1)為標準正態(tài)分布的隨機數(shù)。

為了提高算法搜索的充分性和求解精度，在蝙蝠更新位置后若不滿足局部搜索或飛向獵物的條件，對當前的蝙蝠進行試探擾動，保持蝙蝠在鄰域內(nèi)的游動狀態(tài)，而不是根據(jù)速度公式飛到下一個位置，根據(jù)試探擾動的新位置的適應度值試圖更新當前最佳位置及最優(yōu)值。若適應值未得到改善，說明原蝙蝠(位置更新前的蝙蝠)尋優(yōu)能力差，因此再通過試探擾動因子更新原蝙蝠位置，在下次迭代過程中由更新后較優(yōu)的位置為起點繼續(xù)搜索。這樣不僅確保了蝙蝠的靈活性而且增加了搜索的全面性和求解的精度。其試探擾動因子公式如下：

(13)

(14)

其中，u×rand(1,d)為試探擾動因子，u為[0,1]之間的隨機數(shù)，d為維數(shù)。

綜上所述，新型蝙蝠算法的計算步驟如下：

步驟1：設置算法的基本參數(shù)，包括種群大小、空間維數(shù)、音強衰減系數(shù)α、脈沖速率增加系數(shù)γ、最大音強A、最大迭代次數(shù)等；

步驟2：初始化蝙蝠種群的位置和速度、脈沖速率；

步驟3：根據(jù)式8和式9對蝙蝠群體執(zhí)行趨化算子；

步驟4：計算每只蝙蝠的適應度值，找出當前蝙蝠的最佳位置和適應值；

步驟5：通過式1、式3和式10調(diào)整頻率來更新蝙蝠的位置和速度；

步驟6：根據(jù)產(chǎn)生的隨機數(shù)，如果(rand>ri)對當前最佳解的位置進行隨機擾動，產(chǎn)生新位置，并計算新解；

步驟7：根據(jù)產(chǎn)生的隨機數(shù)和新解，如果(rand

步驟8：若步驟7不成立，則根據(jù)式13對當前蝙蝠進行試探擾動并計算新解，若新解優(yōu)于當前最優(yōu)解，則更新蝙蝠當前位置和最優(yōu)解，否則根據(jù)式14進行試探擾動，更新原蝙蝠位置；

步驟9：判斷是否滿足最大迭代次數(shù)，不滿足轉步驟5；

步驟10：對結果進行分析輸出。

4 實 驗

4.1 實驗環(huán)境和測試函數(shù)

實驗采用Windows7 64位操作系統(tǒng)，處理器為Intel(R)Core(TM)i3-2120 3.30 GHz，內(nèi)存4 G，編程實驗環(huán)境為MatlabR2013a。

為了驗證改進的新型蝙蝠算法(WRBFBA)的尋優(yōu)性能，與基本的BA算法和基本的粒子群算法進行對比，從經(jīng)典的測試函數(shù)中選取5個不同維數(shù)的函數(shù)進行實驗，如表1所示。

表1 標準測試函數(shù)實驗參數(shù)

4.2 實驗參數(shù)設置

群智能優(yōu)化算法的初始參數(shù)設置對算法的優(yōu)化性能起著關鍵作用，因此為了驗證算法的可比性，分別對WRBFBA算法、基本BA算法和基本PSO算法的初始參數(shù)進行一致性設置：

每種算法的種群數(shù)都設置為s=40，迭代次數(shù)為300，趨化算子次數(shù)Nc=40，最大前進次數(shù)Ns=5，獨立運行20次。對基本的BA算法，蝙蝠的頻率范圍f∈[0,2]，初始脈沖速率r0=0.75，脈沖速率增加系數(shù)γ=0.9，最大脈沖音強A=0.7，脈沖音強衰減系數(shù)α=0.9。WRBFBA算法基本參數(shù)同BA算法一致，其中趨化算子中步長c=0.000 5，隨機權重平均值的最大值mean_max=0.9，隨機權重平均值的最小值mean_min=0.4。在PSO算法中學習因子c1=c2=2，慣性權重ω=0.5、σ=0.2。

4.3 實驗結果及分析

表2是分別使用算法WRBFBA、PSO和BA對5個測試函數(shù)進行實驗得到的結果?？梢钥闯觯琖RBFBA算法在函數(shù)的最優(yōu)值、最差值、平均值和標準差這四個指標中對四個高維復雜函數(shù)的尋優(yōu)精度比BA算法和PSO算法高；對于f2f4和f5這樣具有較多的局部最小值的函數(shù)，WRBFBA算法搜索到的最優(yōu)值比BA算法和PSO算法精度高并且f5搜索到最優(yōu)值-1。對于f3這樣很難辨別搜索最優(yōu)值方向和搜索到全局最優(yōu)值的函數(shù)，算法WRBFBA的尋優(yōu)結果比BA算法和PSO算法得到的尋優(yōu)結果誤差較小。

表2 三種算法實驗結果對比

從圖1～4每種算法的收斂情況可以看出， WRBFBA算法快速向下收斂，明顯比BA算法和PSO算法收斂速度快；BA和PSO算法收斂到一定值后基本保持不變的趨勢；由此可見改進的新型蝙蝠算法不僅避免了陷入局部最優(yōu)解，而且提高了算法的收斂速度和尋優(yōu)精度。

圖1 三種算法對函數(shù)f1的收斂曲線

圖2 三種算法對函數(shù)f2的收斂曲線

圖3 三種算法對函數(shù)f3的收斂曲線

圖4 三種算法對函數(shù)f4 的收斂曲線

5 結束語

針對基本蝙蝠算法存在的問題，提出采用細菌覓食算法趨化算子改進蝙蝠種群的多樣性和質量，從而改進蝙蝠算法的局部搜索能力，利用試探擾動因子來提高算法的求解精度和充分性，采用隨機慣性權重來均衡算法的探索能力和挖掘能力。實驗結果表明，提出的新型蝙蝠算法比基本的BA算法和PSO算法的尋優(yōu)性能有明顯的提高。下一步將對蝙蝠算法參數(shù)設置理論及實際的應用進行研究。

參考文獻：

[1] YANG Xinshe.A new metaheuristic bat-inspired algorithm[C]//Studies in computational intelligence.Berlin:Springer,2010:65-74.

[2] GANDOMI A H,YANG Xinshe,ALAVI A H,et al.Bat algorithm for constrained optimization tasks[J].Neural Computing & Applications，2013，22(6)：1239-1255.

[3] 張宇楠，劉付永.一種改進的變步長自適應蝙蝠算法及其應用[J].廣西民族大學學報:自然科學版，2013，19(2)：51-54.

[4] 肖輝輝，段艷明.基于DE算法改進的蝙蝠算法的研究及應用[J].計算機仿真，2014，31(1):272-277.

[5] WANG Xiaowei,WANG Wen,WANG Yong.An adaptive bat algorithm[C]//9th international conference on intelligent computing theories and technology.Nanning,China:[s.n.],2013:216-223.

[6] 龔 純，王正林.精通MATLAB最優(yōu)化計算[M].北京:電子工業(yè)出版社，2012:163-179.

[7] PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems,2002,22:52-67．

[8] 楊淑瑩，張 樺.群體智能與仿生計算:Matlab技術實現(xiàn)[M].北京:電子工業(yè)出版社，2012:196-200.

[9] DAS S，BISWAS A，DASGUPTA S,et al．Bacterial foraging

optimization algorithm:theoretical foundations,analysis,and applications[M]//Foundations of computational intelligence.[s.l.]:[s.n.],2009:23-55.

[10] PAN T S,KIEN D,NGUYEN T T,et al.Hybrid particle swarm optimization with bat algorithm[C]//Proceeding of the eighth international conference on genetic and evolutionary computing.Nanchang,China:[s.n.],2015:37-47.

[11] WANG Yong,CAI Zixing,ZHOU Yuren,et al.Constrained optimization based on hybrid evolutionary algorithm and adaptive constraint-handling technique[J].Structural and Multidisciplinary Optimization,2008,37(4):395-413.

[12] 伊進田,劉云連,劉 麗,等.一種高效的混合蝙蝠算法[J].計算機工程與應用,2014,50(7):62-66.

[13] 王 麗，王曉凱.一種非線性改變慣性權重的粒子群算法[J].計算機工程與應用,2007,43(4):47-48.

[14] 盛孟龍，賀興時,王慧敏.一種改進的自適應變異蝙蝠算法[J].計算機技術與發(fā)展,2014,24(10):131-134.

[15] LAAMARI M A,KAMEL N.A hybrid bat based feature selection approach for intrusion detection[M]//Bio-inspired computing:theories and applications.Berlin:Springer,2014:230-238.