蝙蝠算法

• 1. 簡(jiǎn)介
• 2. 數(shù)學(xué)原理以及算法步驟
• • 2.1 連續(xù)情況下的BA算法
  • 2.2 離散型BA算法
• 4. 具體應(yīng)用
• • 4.1 簡(jiǎn)單的例子
  • 4.2 TSP問(wèn)題中的求解
  • 4.3 背包問(wèn)題的求解
• 5. 參數(shù)選擇的原則
• 小結(jié)
• 參考文獻(xiàn)

1. 簡(jiǎn)介

蝙蝠算法(Bat Algorithm,BA)是Yang受自然界蝙蝠回聲定位的方式進(jìn)行搜索、捕食行為的啟發(fā)，于2010年提出的一種新型的群智能仿生優(yōu)化算法。BA算法具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)較少、搜索能力較強(qiáng)、穩(wěn)定性較強(qiáng)、便于實(shí)現(xiàn)等優(yōu)點(diǎn)，在函數(shù)優(yōu)化、調(diào)度問(wèn)題、模式識(shí)別、圖像處理、故障診斷等等方面表現(xiàn)出極大的優(yōu)勢(shì)。BA算法目前主要在連續(xù)域函數(shù)優(yōu)化問(wèn)題上進(jìn)行求解，較少的地方用來(lái)求解組合優(yōu)化問(wèn)題，例如背包問(wèn)題、TSP問(wèn)題求解、可靠性冗余分配問(wèn)題等等。蝙蝠回聲定位原理為：蝙蝠以脈沖的形式以一定的發(fā)射率進(jìn)行發(fā)射一定量的頻率和音量的超聲波，當(dāng)超聲波在傳播過(guò)程中遇到三維空間中的物體之后就會(huì)以回聲的形式返回，通過(guò)對(duì)自身回聲的接收和處理，蝙蝠不僅能夠探測(cè)到運(yùn)動(dòng)物體與自身的距離和飛行方向，還可以判斷其運(yùn)動(dòng)速率、大小、形態(tài)以及結(jié)構(gòu)，從而避開(kāi)障礙物。

2. 數(shù)學(xué)原理以及算法步驟

蝙蝠算法有兩種不同的形式，一種是用于連續(xù)型計(jì)算的算法，一種是基于連續(xù)型計(jì)算方法而提出的一種離散型的BA算法。這兩種算法具有很大的不同點(diǎn)，下面就這兩種不同的算法進(jìn)行學(xué)習(xí)。

2.1 連續(xù)情況下的BA算法

蝙蝠是通過(guò)其發(fā)出超聲波的頻率、速度來(lái)確定物體的位置信息。所以，為了便于模擬蝙蝠的回聲定位行為。Yang給出了兩個(gè)理想化的規(guī)則：

• 搜索規(guī)則：蝙蝠隨機(jī)飛行，同時(shí)以固定的頻率、可變的波長(zhǎng)和音量來(lái)搜索獵物；
• 參數(shù)變化規(guī)則：蝙蝠會(huì)根據(jù)自身與獵物的距離來(lái)自動(dòng)調(diào)整脈沖波長(zhǎng)和脈沖發(fā)射率，并限定音量在指定范圍內(nèi)依照給定方式由大到小而發(fā)生變化。

在以上的假設(shè)的基礎(chǔ)上，BA算法的步驟如下所示：
步驟一：初始化相關(guān)參數(shù)，包括蝙蝠的種群數(shù)量$n$、蝙蝠種群的位置和速度。
步驟二：根據(jù)目標(biāo)函數(shù)和初始位置計(jì)算適應(yīng)度值，從而得出初始解；
步驟三：對(duì)于每只蝙蝠$k$，根據(jù)下列公式更新脈沖頻率、速度和位置信息，從而產(chǎn)生后代個(gè)體：
$$?\begin{array}{l}{f}_k=f_{\min }+(f_{max}?f_{min})?\beta \\ v_k^{t+1}=v_k^t+(x_k^t?x^{?})?f_k\\ x_k^{t+1}=x_k^t+v_k^t\end{array}$$

其中，$f_k$表示第$k$只蝙蝠的脈沖頻率信息，$f_{\max }$和$f_{\min }$分別表示脈沖頻率的最大值和最小值，$\beta \in [0,1]$是均勻分布的隨機(jī)數(shù)，$x_k^t,v_k^t$表示第$t$個(gè)迭代過(guò)程中蝙蝠$k$所在的位置和速度，$x^{?}$表示當(dāng)前全局的最優(yōu)解。
步驟四：生成隨機(jī)數(shù)$\text{rand1}$，如若$\text{rand1}>r_k^t$，則在當(dāng)前最優(yōu)解附近進(jìn)行鄰域位置的搜索，搜索方式如下公式所確定：
$$x_{\text{new}}=x_{\text{old}}+??A^t$$

其中，$r_k^t$表示第$t$代蝙蝠$k$的脈沖發(fā)射率，$x_{\text{new}}$表示隨機(jī)擾動(dòng)得到的新解，$x_{\text{old}}$即$x^{?}$，$A^t$表示第$t$迭代中所有蝙蝠群體音量的平均值，$?$表示均勻分布的隨機(jī)數(shù)$?\in [?1,1]$。
步驟五：生成隨機(jī)數(shù)$\text{rand2}$，如若$\text{rand2}<A_k^t$并且$x_{\text{new}}$的適應(yīng)度優(yōu)于$x_{\text{old}}$，則接受$x_{new}$并且更新$r_k^t$和$A_k^t$，更新的公式如下所示：
$$\{\begin{array}{l}{A}_k^{t+1}=\alpha ?A_k^t\\ r_k^{t+1}=r_k^0(1?e^{?\gamma t})\end{array}$$

其中，$0<\alpha <1,\gamma >0$,$\alpha ,\gamma$均為常量；
步驟六：計(jì)算出當(dāng)前所有蝙蝠的適應(yīng)度并找出當(dāng)前最優(yōu)解；
步驟七：重復(fù)步驟三至步驟六，直到達(dá)到循環(huán)條件，退出算法。

2.2 離散型BA算法

BA算法在離散化的領(lǐng)域內(nèi)的應(yīng)用比較少，為拓寬BA算法的應(yīng)用領(lǐng)域，便將連續(xù)化的蝙蝠算法經(jīng)過(guò)改進(jìn)，應(yīng)用到了離散型的蝙蝠算法。下面來(lái)介紹TSP求解問(wèn)題中的蝙蝠算法。

4. 具體應(yīng)用

4.1 簡(jiǎn)單的例子

4.2 TSP問(wèn)題中的求解

4.3 背包問(wèn)題的求解

5. 參數(shù)選擇的原則

小結(jié)

參考文獻(xiàn)

[1] 一種求解TSP問(wèn)題的離散蝙蝠算法
[2] 蝙蝠算法及其在CVRPTW-SDP問(wèn)題中的應(yīng)用
[3] 旅行商問(wèn)題的混沌混合離散蝙蝠算法

總結(jié)

以上是生活随笔為你收集整理的群体智能算法之蝙蝠算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。