當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

群体智能优化算法之蝙蝠算法(Bat Algorithm，BA)

發布時間：2023/12/9 编程问答 30 豆豆

生活随笔收集整理的這篇文章主要介紹了群体智能优化算法之蝙蝠算法(Bat Algorithm，BA) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

獲取更多資訊，趕快關注上面的公眾號吧！

文章目錄

第十章蝙蝠算法
- 10.1 介紹
- 10.2 蝙蝠的自然行為概述
- 10.3 蝙蝠算法的數學表達
- 10.4 蝙蝠算法變種
- - 10.4.1 混沌蝙蝠算法
  - 10.4.2 二進制蝙蝠算法
  - 10.4.3 并行蝙蝠算法
  - 10.4.4 定向蝙蝠算法
  - 10.4.5 自適應蝙蝠算法
- 參考文獻

第十章蝙蝠算法

10.1 介紹

蝙蝠算法（Bat Algorithm，BA）是一種基于群體智能的算法，是受微型蝙蝠的回聲定位的啟發，由Xin-She Yang(Yang, 2010a)[1]于2010年提出的。大多數微型蝙蝠將聲音輻射到周圍環境，并聆聽這些聲音來自不同物體的的回聲，從而可以識別獵物，躲避障礙物，并追蹤黑暗的巢穴。聲音脈沖因蝙蝠的種類而異，基本上，頻率調諧是一種突變，因為它在解中引起波動，主要是在較好的解附近，盡管較大的突變導致全局搜索。特定的選擇是通過對相對恒定的選擇施加壓力來實現的，這是由于在目前已經建立的種群中使用了最優解。與遺傳算法相比，沒有明顯的交叉;然而，響度和脈沖發射的偏差會導致變異的不同。另外，還有一種自動縮放的功能，即隨著搜索在響度和脈沖發射率的變化上接近全局最優，利用就會變得集中起來，這導致從探索階段自動切換到利用階段。

10.2 蝙蝠的自然行為概述

蝙蝠是唯一有翅膀的哺乳動物，它們具有非凡的回聲定位能力。它們是世界上種類第二多的哺乳動物，有超過1200種。一般分為蝙蝠可以分為兩類：回聲定位微型蝙蝠和以水果為食的巨型蝙蝠。蝙蝠算法是由Yang Xin-She (2010a)[1]基于第一類蝙蝠的行為而開發的。大多數蝙蝠以倒掛的棲息姿勢休息。所有的微型蝙蝠和一些巨型蝙蝠都會發出超聲波來產生回聲。微型蝙蝠的大腦和聽覺神經系統可以通過比較出站脈沖和反復出現的回聲，對環境產生深入的圖像。微型蝙蝠發出這些超聲波(通過喉部產生)通常通過嘴巴，偶爾通過鼻子，它們會在回聲返回前就結束發出超聲波。回聲定位可以是低負荷循環，也開始是高負荷循環，第一種情況時，蝙蝠可以根據時間區分它們的叫聲和多次出現的回聲；第二種情況時，蝙蝠發出不間斷的叫聲，并在頻率上將脈沖和回聲分離。回聲定位也被稱為生物聲納，主要用于動物的導航和覓食。在這些回聲的幫助下，蝙蝠測量物體的大小和距離，有些種類的蝙蝠甚至能夠測量物體移動的速度。

10.3 蝙蝠算法的數學表達

蝙蝠在尋找目標、對象或獵物時，在位置xi以速度vi隨機飛行，其具有靜態的頻率f_min，變化的波長λ，響度A₀。頻率變化范圍為f_min到f_max，聲音的響度可以根據需要在A₀和A_min之間變化。Xin-She Yang (2010a)[1]建立了一系列規則來更新蝙蝠尋找獵物時的速度、位置和響度。蝙蝠算法的數學公式如下：
$fi=fmin?+(fmax??fmin?)×β(1){f_i} = {f_{\min }} + \left( {{f_{\max }} - {f_{\min }}} \right) \times \beta \tag 1$
$vit+1=vit+(xit?x?)×fi(2)v_i^{t + 1} = v_i^t + \left( {x_i^t - {x_*}} \right) \times {f_i}\tag 2$
$xit+1=xit+vit(3)x_i^{t + 1} = x_i^t + v_i^t\tag 3$
$Ait+1=αAit,rit+1=ri0[1?exp?(?γt)](4)A_i^{t + 1} = \alpha A_i^t,r_i^{t + 1} = r_i^0[1 - \exp ( - \gamma t)]\tag 4$
$Ait→0,rit→riU,ast→∞(5)A_i^t \to 0,r_i^t \to r_i^U,{\rm{ }}as{\rm{ }}t \to \infty \tag 5$

其中β為[0,1]內均勻分布的隨機數，x*表示當前種群中的全局最優解，r為脈沖發射率，α和γ為常數且0<α<1，γ>0。
選擇全局最優解后，當前種群中每一個局部解（x_old）使用式（6）更新其位置：
$xnew=xold+εAt(6){x_{new}} = {x_{old}} + \varepsilon {A^t}\tag 6$

其中ε為[-1,1]之間的任意數。

BA結合了粒子群優化、遺傳算法和和聲搜索的最佳特性，因此，與這些算法相比，它提供了良好的結果。參數α和γ的調整會影響收斂速度。BA的實現有點復雜，但它已經證明了它的性能，并稱為一種良好的受自然啟發的元啟發式。

10.4 蝙蝠算法變種

蝙蝠算法在優化問題上取得了很好的效果。最近，它經歷了多次改進，并通過將其與現有的元啟發式雜交或引入一些新的參數來開發一些變體，這里選取一些進行討論。

10.4.1 混沌蝙蝠算法

Gandomi和Yang(2014)[2]開發了混沌BA的四個變種，每個變種都在13個混沌映射的幫助下得到驗證。這些混沌映射代替了固定的參數，增強了靈活性和多樣性，因為不同的混沌映射會導致算法的不同行為。提出的改進主要是對參數β、γ（分別見式（7）和（8）），響度A和脈沖發射率r進行改變。
$fi=fmin?+(fmax??fmin?)×CMi(7){f_i} = {f_{\min }} + \left( {{f_{\max }} - {f_{\min }}} \right) \times C{M_i}\tag 7$
$vit+1=vit+(xit?x?)×CMi×fi(8)v_i^{t + 1} = v_i^t + \left( {x_i^t - {x_*}} \right) \times C{M_i} \times {f_i}\tag 8$

10.4.2 二進制蝙蝠算法

Mirjalili, Mirjalili和Yang(2014)[3]在修改了速度和位置的一些基本概念后，使程序現代化，產生了BA的二進制版本。在離散二進制搜索空間中，由于現有方法無法對位置進行更新，因此引入傳遞函數對位置進行更新，所使用的傳遞函數為：
$S(vik(t))=11+e?vik(t)(9)S\left( {v_i^k(t)} \right) = \frac{1}{{1 + {e^{ - v_i^k(t)}}}}\tag 9$

其中v_i^k(t)表示第i個個體在第k維上速度。使用傳遞函數的位置更新如下：

$xik(t+1)={0if?rand?<S(vik(t+1))1if?rand?≥S(vik(t+1))(10)x_{i}^{k}(t+1)=\left\{\begin{array}{ll}{0} & {\text { if } \quad \text { rand }<S\left(v_{i}^{k}(t+1)\right)} \\ {1} & {\text { if } \quad \text { rand } \geq S\left(v_{i}^{k}(t+1)\right)}\end{array}\right.\tag {10}$

在這個過程中，每個個體被分配0或1，因此，隨著速度的增加，個體的位置保持不變。為了克服這個問題，提出了一種新的v形傳遞函數，并利用該函數設計了新的位置更新過程，分別如式（11）和（12）所示：
$V(vik(t))=∣2πarctan?(π2vik(t))∣(11)V\left( {v_i^k(t)} \right) = \left| {\frac{2}{\pi }\arctan \left( {\frac{\pi }{2}v_i^k(t)} \right)} \right|\tag {11}$

$xik(t+1)={(xik(t))?1if?rand?<V(vik(t+1))xik(t)if?rand?≥V(vik(t+1))(12)x_{i}^{k}(t+1)=\left\{\begin{array}{ll}{\left(x_{i}^{k}(t)\right)^{-1}} & {\text { if } \operatorname{rand}<V\left(v_{i}^{k}(t+1)\right)} \\ {x_{i}^{k}(t)} & {\text { if } \operatorname{rand} \geq V\left(v_{i}^{k}(t+1)\right)}\end{array}\right.\tag {12}$

10.4.3 并行蝙蝠算法

BA的并行版本是由Tsai, Dao, Yang和Pan (2014)[4]提出的，在并行BA中，群體被分割成了一些子群體，然后這些子群體獨立地進行工作。在Tsai, Dao, Yang和Pan (2014)[4]中，群體被分成G組，總迭代包含R（R={R₁,2R₁,3R₁,…}）次通信。并行BA算法如下：

Step1：初始化：生成蝙蝠種群，分成G組。分別初始化每個組，并定義迭代集R來實現通信策略。
Step2：評估：獲取每個組中每只蝙蝠的適應度值。
Step3：更新：使用基本BA（式（2）和（3））更新蝙蝠的速度和位置。
Step4：通信策略：選擇當前群體中最優的蝙蝠（G^t），并將其遷移到每一個組中，每R₁次迭代，使用變異的G^t替換每組中最差的蝙蝠。
Step5：終止：重復Step2-Step5，直到滿足終止條件。存儲函數f(G^t)的最優值，以及所有蝙蝠G^t中最優蝙蝠的位置。

10.4.4 定向蝙蝠算法

Chakri、Khelif、Benouaret和Yang(2017)[5]提出了一種新的BA變體—定向BA(dBA)，在基本BA算法基礎做了四項新的修正，以求解高維問題。蝙蝠在兩個不同的方向產生聲音脈沖，一個方向是當前群體中最好的，另一個方向是隨機的，通過個體的適應性來決定最佳可行食物來源的位置。蝙蝠運動的數學公式由式（13）給出：
${xit+1=xit+(x??xit)f1+(xkt?xit)f2if?F(xkt)<F(xit)xit+1=xit+(x??xit)f1otherwise?(13)\left\{\begin{array}{ll}{x_{i}^{t+1}=x_{i}^{t}+\left(x^{*}-x_{i}^{t}\right) f_{1}+\left(x_{k}^{t}-x_{i}^{t}\right) f_{2}} & {\text { if } F\left(x_{k}^{t}\right)<F\left(x_{i}^{t}\right)} \\ {x_{i}^{t+1}=x_{i}^{t}+\left(x^{*}-x_{i}^{t}\right) f_{1}} & {\text { otherwise }}\end{array}\right.\tag {13}$
其中，x*代表當前種群中最優的蝙蝠，x_k^t表示在k個方向隨機選擇的蝙蝠，F(.)表示適應度函數。兩個脈沖的頻率根據式（14）計算得到：
${f1=fmin?+(fmax??fmin?)×rand?1f2=fmin?+(fmax??fmin?)×rand?2(14)\left\{\begin{array}{l}{f_{1}=f_{\min }+\left(f_{\max }-f_{\min }\right) \times \operatorname{rand}_{1}} \\ {f_{2}=f_{\min }+\left(f_{\max }-f_{\min }\right) \times \operatorname{rand}_{2}}\end{array}\right.\tag {14}$
提出的策略僅在前期的迭代中增強了探索能力，可以避免過早收斂。蝙蝠的位置更新使用式（15）進行更新，式中用到了響度A_t和單調遞減函數w_i^t。
$xit+1=xit+<At>εwit(15)x_i^{t + 1} = x_i^t + < {A^t} > \varepsilon w_i^t\tag {15}$
其中w_i是縮放參數，用于調節搜索過程，其計算工時如下：
$wit=(wi0?wi∞1?tmax?)×(t?tmax?)+wi∞(16)w_i^t = \left( {\frac{{{w_{i0}} - {w_{i\infty }}}}{{1 - {t_{\max }}}}} \right) \times \left( {t - {t_{\max }}} \right) + {w_{i\infty }}\tag {16}$

縮放參數的初值（w_i0）和終值（w_i∞）分別使用式（17）和（18）進行計算：
$wi0=(Ubi?Lbi)/4(17){w_{i0}} = \left( {U{b_i} - L{b_i}} \right)/4\tag {17}$
$wi∞=wi0/100(18){w_{i\infty }} = {w_{i0}}/100\tag {18}$
Chakri等(2017)[5]提出了脈率和響度的變化，如式（19）和（20）所示。
$rt=(r0?r∞1?tmax?)×(t?tmax?)+r∞(19){r^t} = \left( {\frac{{{r_0} - {r_\infty }}}{{1 - {t_{\max }}}}} \right) \times \left( {t - {t_{\max }}} \right) + {r_\infty }\tag {19}$
$At=(A0?A∞1?tmax?)×(t?tmax?)+A∞(20){A^t} = \left( {\frac{{{A_0} - {A_\infty }}}{{1 - {t_{\max }}}}} \right) \times \left( {t - {t_{\max }}} \right) + {A_\infty }\tag {20}$

所提出的兩組脈沖發射方向不同，探索和利用都得到了改善，因為它使得移動在最優蝙蝠的方向更加接近有利的搜索空間。此外，提出的脈沖發射速率和響度自適應控制了不同迭代階段的探索和利用。

10.4.5 自適應蝙蝠算法

Fister, Fong, and Brest(2014)[6]提出了一種自適應BA，期望控制參數在算法運行時能夠自動調整，其提出的響度和脈沖率自適應調整如下：
$At+1={Alb(t)+rand?0(Aub(t)?Alb(t))if?rand?1<τ1A(t)otherwise?(21)A^{t+1}=\left\{\begin{array}{ll}{A_{l b}^{(t)}+\operatorname{rand}_{0}\left(A_{u b}^{(t)}-A_{l b}^{(t)}\right)} & {\text { if } \operatorname{rand}_{1}<\tau_{1}} \\ {A^{(t)}} & {\text { otherwise }}\end{array}\right.\tag {21}$

其中τ_i（i={1,2}）表示學習率，取固定值τ_i=0.1。使用該自適應策略，每10個候選解就會被重新構造一次，而且Fister等人(2014)將這種自適應技術與一種流行的進化算法—差分進化(DE)雜交。受自然啟發的元啟發式的最佳特征是它們之間是合作的，而不是競爭的，因此它們可以彼此雜交。雜交BA使用DE策略更新試驗解，如下所示：
$yn={DE?Strategy,?if?rand?(0,1)≤CR∨n=Dxin(t)otherwise?(23)y_{n}=\left\{\begin{array}{ll}{D E_{-} S \text { trategy, }} & {\text { if } \operatorname{rand}(0,1) \leq C R \vee n=D} \\ {x_{i n}^{(t)}} & {\text { otherwise }}\end{array}\right.\tag {23}$
考慮四種DE策略：
DE/rand/1/bin：
$yj=xr1,j+F×(xr2,j?xr3,j)(24){y_j} = {x_{r1,j}} + F \times \left( {{x_{r2,j}} - {x_{r3,j}}} \right)\tag {24}$
DE/best/1/bin：
$yj=xbest,j+F×(xr1,j?xr2,j)(25){y_j} = {x_{best,j}} + F \times \left( {{x_{r1,j}} - {x_{r2,j}}} \right)\tag {25}$
DE/best/2/bin：
$yj=xbest,j+F×(xr1,j+xr2,j?xr3,j?xr4,j)(26){y_j} = {x_{best,j}} + F \times \left( {{x_{r1,j}} + {x_{r2,j}} - {x_{r3,j}} - {x_{r4,j}}} \right)\tag {26}$
DE/rand_to_best/1/bin：
$yj=xi,j+F×(bestj?xi,j)?F×(xr1,j?xr2,j)(27){y_j} = {x_{i,j}} + F \times \left( {bes{t_j} - {x_{i,j}}} \right) - F \times \left( {{x_{r1,j}} - {x_{r2,j}}} \right)\tag {27}$

所使用的DE策略是修改操作中的最佳解，即“rand_to_best/1/bin”、“best/2/bin”和“best/1/bin”，通常將模擬蝙蝠引導到當前最佳解的方向。

參考文獻

Yang, X.-S., A New Metaheuristic Bat-Inspired Algorithm, in Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), J.R. González, et al., Editors. 2010, Springer Berlin Heidelberg: Berlin, Heidelberg. p. 65-74.

Gandomi, A.H. and X.-S. Yang, Chaotic bat algorithm. Journal of Computational Science, 2014. 5(2): p. 224-232.

Mirjalili, S., S.M. Mirjalili, and X.-S. Yang, Binary bat algorithm. Neural Computing and Applications, 2014. 25(3): p. 663-681.

Tsai, C.-F., et al. Parallelized Bat Algorithm with a Communication Strategy. in Modern Advances in Applied Intelligence. 2014. Cham: Springer International Publishing.

Chakri, A., et al., New directional bat algorithm for continuous optimization problems. Expert Systems with Applications, 2017. 69: p. 159-175.

Fister jr, I., et al., A Novel Hybrid Self-Adaptive Bat Algorithm. TheScientificWorldJournal, 2014. 2014: p. 709738.

總結

以上是生活随笔為你收集整理的群体智能优化算法之蝙蝠算法(Bat Algorithm，BA)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： C++基础知识（四）—— 操作符/运算符
下一篇： MYSQL-skip-networkin