蝙蝠算法

蝙蝠算法( BA) 是 Yang 教授於 2010 年基於群體智慧型提出的啟發式搜尋算法,是一種搜尋全局最優解的有效方法。該算法是一種基於疊代的最佳化技術,初始化為一組隨機解,然後 通過疊代搜尋最優解,且在最優解周圍通過隨機飛行產生局部新解,加強了局部搜尋。與其他算法相比,BA 在準確性和有效性方面遠優於其他算法,且沒有許多參數要進行調整。

基本介紹

• 中文名：蝙蝠算法
• 外文名：BatAlgorithm

基本信息

蝙蝠算法（Bat Algorithm，BA）算法是模擬自然界中蝙蝠利用一種聲吶來探測獵物、避免障礙物的隨機搜尋算法即模擬蝙蝠利用超音波對障礙物或獵物進行最基本的探測、定位能力並將其和最佳化目標功能相聯繫。BA算法的仿生原理將種群數量為的蝙蝠個體映射為D維問題空間中的NP個可行解,將最佳化過程和搜尋模擬成種群蝙蝠個體移動過程和搜尋獵物利用求解問題的適應度函式值來衡量蝙蝠所處位置的優劣，將個體的優勝劣汰過程類比為最佳化和搜尋過程中用好的可行解替代較差可行解的疊代過程。在蝙蝠搜尋算法中,為了模擬蝙蝠探測獵物、避免障礙物,需假設如下三個近似的或理想化的規則：

1）所有蝙蝠利用回聲定位的方法感知距離,並且它們採用一種巧妙的方式來區別獵物和背景障礙物之間的不同。

2）蝙蝠在位置xi以速度vi隨機飛行,以固定的頻率fmin、可變的波長λ和音量A0來搜尋獵物。蝙蝠根據自身與目標的鄰近程度來自動調整發射的脈衝波長（或頻率）和調整脈衝發射率r屬於[0,1]

3）雖然音量的變化方式有多種但在蝙蝠算法中, 假定音量A是從一個最大值A0(整數)變化到固定最小值Amin

生物學機理

蝙蝠是唯一長著翅膀的哺乳動物,而且它們有先進的回音定位能力。大多數微型蝙蝠是食蟲類的動物。微型蝙蝠使用聲波回聲定位,檢測到獵物,躲避障礙,並在黑暗中找到自己位於裂縫的棲息地。這些蝙蝠發出很響亮的聲音,然後聽到從周圍物體反射回來的回音。對於不同的蝙蝠,它們的脈衝是與狩獵的策略有關的。大多數蝙蝠通過一種濾波器用短且高頻的信號掃描周圍,而其他蝙蝠則經常使用固定頻率的信號進行回聲定位。其信號頻寬的變化取決於蝙蝠的種類,且常常通過使用更多的諧波而增加。

對於不同的蝙蝠,它們的脈衝是與狩獵的策略有關的。大多數蝙蝠通過一種濾波器用短且高頻的信號掃描周圍,而其他蝙蝠則經常使用固定頻率的信號進行回聲定位。其信號頻寬的變化取決於蝙蝠的種類,且常常通過使用更多的諧波而增加。

依靠回聲定位進行捕食的蝙蝠,在搜尋獵物時通常每秒發出大約10 ~ 20 個、音強可達110 dB 的超音波脈衝,脈衝音強在搜尋獵物時通常為最大,在飛向獵物時逐漸減小,同時脈衝頻度逐漸增加,達到每秒發射約200 個脈衝。脈衝音強大有助於超音波傳播更遠的距離,脈衝頻度高有助於精確掌握獵物不斷變化的空間位置。蝙蝠發出的回聲定位聲波一般由單諧波或多諧波寬頻帶的調頻信號組成,頻率通常在25 ~ 100 kHz。每個諧波頻率由高到低,下降較快,多諧波、寬頻帶的調頻聲有利於確定複雜環境和獵物的精細結構。

算法描述

對於目標函式為minf(x),目標變數為X=(x1,x2,……,xd)T的最佳化問題，BA算法的實施過程描述如下：

Step1: 種群初始化，即蝙蝠以隨機方式在D維空間中擴散分布一組初始解。最大脈衝音量A0,最大脈衝率R0, 搜尋脈衝頻率範圍[fmin,fmax],音量的衰減係數α，搜尋頻率的增強係數γ，搜尋精度ε或最大疊代次數iter_max。

Step2: 隨機初始化蝙蝠的位置xi,並根據適應度值得優劣尋找當前的最優解x*。

Step3: 蝙蝠的搜尋脈衝頻率、速度和位置更新。種群在進化過程中每一下公式進行變化:

fi=fmin+(fmax-fmin)xβ (1)

vi^t=vi^(t-1)+(xi^t-x*)xfi (2)

xi^t=xi^(t-1)+vi^(t) (3)

式中:β屬於[0,1]是均勻分部的隨機數；fi是蝙蝠i的搜尋脈衝頻率，fi屬於[fmin,fmax]；vi^t、vi^(t-1)分別表示蝙蝠i在t和t-1時刻的速度；xi^t、xi^(t-1)分別表示蝙蝠i在t和t-1時刻的位置; x*表示當前所有蝙蝠的最優解。

Step4:生成均勻分布隨機數rand,如果rand>r,則對當前最優解進行隨機擾動，產生一個新的解，並對新的解進行越界處理。

Step5:生成均勻分布隨機數rand,如果rand<Ai且f(xi)<f(x*),則接受步驟4產生的新解,然後按如下公式對和進行更新:

Ai^(t+1)=αAi^(t) (4)

ri^(t+1)=R0[1-exp(-γt)] (5)

Step6:對所有蝙蝠的適應度值進行排序,找出當前的最優解和最優值。

Step7:重複步Step2~Step5直至滿足設定的最優解條件或者達到最大疊代次數。

Step8:輸出全局最優值和最優解。

從上述蝙蝠算法實現過程的式(3)~(5)可知,蝙蝠算法中的兩個參數:音量的衰減係數α和搜尋頻率的增強係數,對算法性能的影響非常大。如何有效平衡算法的尋優精度和收斂速度,關鍵是合理設定參數α、γ的值。仿真過程通過反覆調整參數α、γ的值,才能得到合適的參數α、γ值。

局限性

從最佳化原理可以看出,蝙蝠算法的尋優能力主要依靠蝙蝠個體之間的相互作用和影響,但個體本身缺乏變異機制,一旦受到某個局部極值約束後自身很難擺脫;而且在進化過程中,種群中的超級蝙蝠可能會吸引其它個體迅速向其周圍聚集,使得種群多樣性大幅下降,同時由於蝙蝠個體越來越接近種群最優個體,收斂速度大大降低甚至出現進化停滯,種群喪失了進一步進化的能力。而在許多情況下,尤其是對於具有高維、多峰、地形複雜等特點的最佳化空間,算法並沒有收斂到全局極值,因而很難發現分布在局部最優鄰域內的全局最優點。所以,對基本蝙蝠最佳化算法的改進應放在提高種群的多樣性上,使得種群在疊代過程中能保持持續最佳化的能力。

算法拓展

蝙蝠算法存在著後期收斂速度慢、收斂精度不高、易陷入局部極小點等不足,嚴重地限制了BA的套用領域。針對上述存在的缺陷,有如下幾種改進方法的研究。

基於模擬退火高斯擾動的蝙蝠最佳化算法

賀興時,丁文靜,楊新社等將模擬退火思想引入蝙蝠最佳化算法中,提出一種基於模擬退火的高斯擾動蝙蝠最佳化算法( SAGBA) ,採用高斯擾動的變異運算進一步調整所最佳化的集群。其基本執行過程是: 先隨機產生初始種群,開始隨機搜尋,設定初始溫度,利用模退火算法得到全局最優的替代值,再根據位置和速度更新式產生一組新解,然後在個體較優位置進行高斯擾動,進行進一步的搜尋。

基於DE算法改進的蝙蝠算法

肖輝輝,段艷明等人根據基本BA算法存在的不足，提出了一種改進BA算法的策略，把差分算法融入到基本BA算法中,使種群蝙蝠個體之間具有變異、交叉、選擇機制，從而達到增加蝙蝠個體的多樣性，提高算法的全局尋優能力和局部搜尋能力。蝙蝠算法與基於差分進化算法的改進蝙蝠算法（DEBA算法）的相比，兩者的不同之處在於DEBA算法在每一次進化過程中，經過進化後的蝙蝠位置xi(t)不是直接進入下一次進化過程中，經過進化後的蝙蝠位置xi(t)不是直接進入下一次疊代，而是進行種群中個體之間進行變異、交叉、選擇操作得到新的蝙蝠位置後, 再進入(t+1)次疊代。在算法疊代的初期因為種群中個體的差異較大,從而這樣的變異操作會使算法具有更強的全局搜尋能力,而到疊代的後期,當趨於收斂的時候,種群中個體的差異較小了，這也使得算法具有更強的局部搜尋能力。綜上所述，DEBA算法將差分進化算法和蝙蝠算法各自的優點融合在一起，使DEBA算法不僅具有強大全局尋優能力，而且也具有強大的局部搜尋能力，從而克服了BA算法收斂精度不高、容易陷入局部最優、後期收斂速度慢等缺點。

混合蝙蝠算法

尹進田,劉雲連,劉麗等針對基本蝙蝠算法存在收斂速度慢,易陷入局部最優,求解精度低等缺陷,提出一種融合局部搜尋的混合蝙蝠算法用於求解無約束最佳化問題。該算法利用混沌序列對蝙蝠的位置和速度進行初始化,為全局搜尋的多樣性奠定基礎;融合Powell搜尋以增強算法的局部搜尋能力,加快收斂速度;使用變異策略在一定程度上避免算法陷入局部最優。

自適應變異蝙蝠算法

針對蝙蝠算法在解決高維複雜問題時容易陷入局部最優解和精確度不高的問題,盛孟龍,賀興時,王慧敏提出了一種改進的蝙蝠算法。在原算法的基礎上,引入一種交叉變換的方式更新蝙蝠群體的位置,一方面是為了提高蝙蝠算法的遍歷性,另外還可以減小蝙蝠算法陷入局部最優解的可能性。模擬蝙蝠發聲的音量變化,採用自適應的變換的方式改進蝙蝠算法最優解的選擇模式,達到提高算法的精度和收斂速度的目的。

變步長自適應蝙蝠算法

2013年張宇楠等人提出了變步長自適應蝙蝠算法(CBA),該算法在收斂速度和計算精度方面有所提髙。基本蝙蝠算法執行到後期時,個體在峰值附近出現振盪現象.通過多次實驗分析,認為出現振盪現象的主要原因是蝙蝠移動步長使用了較小的固定步長:step = 0 .001 ,算法初期為了不跳過函式峰值需要使用較小步長,而算法後期要提高收斂速度需要使用較大步長.所以使用固定步長,就無法解決此類問題,導致算法收斂速度慢和求解精度低.

BA算法在求解全局最佳化問題,具有求解速度快、效率高、通用性強等優點.但由於在蝙蝠飛行中, 每一隻蝙蝠採用固定步長進行移動,如果固定步長取值較大,則可能導致蝙蝠飛離最優解,出現收斂速度慢、後期易出現震盪現象等問題.如果固定步長取值較小,可能導致算法過早的陷入局部最優解,同樣得不到較高精度的解.因此,採用式(8)使蝙蝠的移動步長隨著疊代次數的增加而自適應改變,在算法的運行初期保持一個最大值,避免算法過早的陷入局部最優隨著疊代次數的增加步長自適應的減小最後保持一個最小值,從而使算法在後期快速收斂,得到更精確的解.

step=step×a +step_min

a = exp(-30×(t/T_max)^p) (8)

其中, t為當前疊代次數; T_max為最大的疊代次數,step_min為步長的最小閾值,取值為0.0001;p為大於1的整數,可據具體情況在取值範圍[1,30]之間選取.

上述這些改進都在一定程度上解決了基本蝙蝠最佳化算法收斂速度慢、算法早熟等問題，但在穩定性、收斂速度等方面仍存在不足。同時，目前國內外對蝙蝠算法在非線性方程組求解方面的研究較少。

套用

目前BA 算法己被用於工程設計、分類、模糊聚類、預測和神經網路等領域。