1. 蝙蝠算法簡介

（以下描述，均不是學(xué)術(shù)用語膀懈，僅供大家快樂的閱讀）
　　蝙蝠算法（Bat Algorithm）是受蝙蝠回聲定位的特性啟發(fā)而提出的新興算法谨垃，提出時間是2010年刘陶，雖然距今（2020）有近10年，但與其它的經(jīng)典算法相比仍算一個新算法匙隔。算法也已有一定規(guī)模的研究和應(yīng)用纷责，但仍有改進(jìn)點、創(chuàng)新點及應(yīng)用點挺勿。
　　蝙蝠算法主要模擬了蝙蝠通過回聲定位系統(tǒng)來尋找小型昆蟲進(jìn)行覓食的行為不瓶。蝙蝠算法對解空間的搜索方式與粒子群算法（PSO）有一定的類似灾杰，與粒子群相比吭露，蝙蝠算法的每只蝙蝠多了頻率屬性和響度，頻率與相對距離決定蝙蝠的速度泥兰，而速度與當(dāng)前位置決定了蝙蝠下一刻的位置题禀÷踵冢可以看出，算法很符合我們想象中的蝙蝠的回聲定位覓食行為：當(dāng)蝙蝠發(fā)出的超聲波返回的頻率和自己與目標(biāo)之間的相對距離均較為合適時（目標(biāo)個頭不太大融痛，自己離得也不太遠(yuǎn)）雁刷，蝙蝠會加速（或減速）向目標(biāo)飛去保礼。
　　當(dāng)然發(fā)送超聲波的動物還有海豚什么的炮障，大家可以發(fā)揮想象力，創(chuàng)造一個什么海豚算法企蹭。

2. 算法流程

這次我們的主角顯而易見谅摄，就是蝙蝠了吹害。

　　每一個蝙蝠有四個屬性它呀，當(dāng)前位置X,當(dāng)前速度V,回聲頻率f,回聲響度A纵穿。蝙蝠算法每只蝙蝠的有兩種行為（1）更新頻率，更新位置淆院，（2）隨機(jī)飛行

2.1更新速度句惯，更新位置

每只蝙蝠在更新速度之前會先隨機(jī)自己的超聲波頻率f:
$f^{t+1}=rand(f_{min},f_{min})(1)$
　　其中 $f_{min}$ 和 $f_{max}$ 表示其頻率的最大值和最小值。
　　然后每只蝙蝠會根據(jù)自身當(dāng)前速度和當(dāng)前位置與最優(yōu)位置間的距離來更新其速度：
$v^{t+1}=v^{t}+f^{t+1}(x^{t}-x_{best}^{t})(2)$
　　可以看出各墨，本次飛行的隨度是上次的速度與自身位置到最優(yōu)位置的反方向的合速度贬堵。（想不通為什么是 $(x^{t}-x_{best}^{t})$ 而不是 $(x_{best}^{t}-x^{t})$ 结洼，為什么不向著最優(yōu)個體飛行松忍，不過做了實驗,好像區(qū)別不大）
　　更新位置的公式也很簡單挽铁，和粒子群一樣
$x^{t+1}=x^{t}+v^{t+1}(3)$

2.2隨機(jī)飛行

蝙蝠隨機(jī)取一個數(shù)，如果該數(shù)大于蝙蝠的脈沖頻率時進(jìn)行隨機(jī)飛行楣铁。文章中對隨機(jī)飛行的描述過于抽象盖腕，我完全無法明確理解其實現(xiàn)方式浓镜。
　　進(jìn)行隨機(jī)飛行的公式如下：
$x_{new}=x_{old}+\varepsilon A^t(4)$
　　其中膛薛， $\varepsilon$ 是[-1,1]內(nèi)的均勻隨機(jī)數(shù)，A為該代的所有蝙蝠的響度的平均值雅任。
　　每只蝙蝠每一代會產(chǎn)生一個(0,1)內(nèi)的隨機(jī)數(shù)rand,如果rand> $r^t$ 則進(jìn)行隨機(jī)飛行沪么。
　　理解的難處在于 $x_{old}$ 的選取禽车。
　　文章中的偽代碼描述見下圖：

偽代碼

　　根據(jù)上述描述，我大致有3種理解：
　≈莞臁（1）如果蝙蝠的隨機(jī)數(shù)大于自己的脈沖頻率陋葡，則選取最優(yōu)蝙蝠彻采，即該蝙蝠在最優(yōu)蝙蝠附近進(jìn)行隨機(jī)飛行肛响，否則選取自己當(dāng)前位置特笋。
　〗碚住（2）如果蝙蝠的隨機(jī)數(shù)大于自己的脈沖頻率角塑，則在當(dāng)前較優(yōu)的數(shù)個蝙蝠中隨機(jī)選取一個蝙蝠。
　〉倘纭（3）如果蝙蝠的隨機(jī)數(shù)大于自己的脈沖頻率窒朋，則選取最優(yōu)蝙蝠侥猩，但是隨機(jī)飛行時只隨機(jī)選擇最優(yōu)蝙蝠的一維欺劳，其他維保持不變。

反正我不知道是哪一種兵怯，亦或是以上都不是腔剂。后面我們實驗說話。
　　位置更新完后绪爸，蝙蝠會比較新位置與之前的位置中哪個更好宙攻，如果新位置更好座掘，則飛行到新的位置溢陪，否則留在原處。飛到新位置的同時杉编，蝙蝠會更新自己的響度A和自己的脈沖頻率r:
$A^t=\alpha^t A^0(5)$
$r^{t+1}=r^{t}(1-e^{-\gamma t})(6)$
其中 $\alpha,\gamma$ 為常數(shù)邓馒。

理解1流程圖

理解2流程圖

理解3流程圖

　　我的三個理解的流程圖如上，看上去三個都差不太多挂疆，但是實現(xiàn)方式和效果的差別還挺大的下翎。

3. 實驗

適應(yīng)度函數(shù) $f(x_1,x_2)=(x_1-a)^2+(x_2-b)^2$ 视事。
實驗一：按照理解（1）實現(xiàn)

參數(shù)	值
問題維度(維度)	2
總?cè)簲?shù)量(種群數(shù))	20
搜索次數(shù)(最大迭代次數(shù))	100
最小頻率-最大頻率	0-1
最小響度-最大響度	1-2
$\alpha$	0.85
$\gamma$	0.9
初始脈沖頻率r	0.7
取值范圍	（-100俐东，100）
實驗次數(shù)	10

實驗一圖像

	值
最優(yōu)值	9.200577911544411E-5
最差值	98.94310340856839
平均值	9.894879535644769

可以看出按照理解（1）實現(xiàn)的算法有點不穩(wěn)定虏辫，我選取了得到最差值的那次實驗的圖像砌庄，可以看出奕枢，算法在一開始收斂很快缝彬，在第二代就聚集于一個較小的范圍谷浅，之后在不停的蠕動著奶卓。這說明按照這種方式理解寝杖，算法的收斂速度極快，且局部搜索能力較強(qiáng)，但是其全局搜索能力不足只盹，且易陷入局部最優(yōu)殖卑，并且在算法后期坊萝，其收斂速度隨著蝙蝠越來越集中，變得越來越慢菩鲜。

實驗二：按照理解（2）實現(xiàn)接校，選取種群中較優(yōu)的20%個體為最優(yōu)群體蛛勉，每次從最有群體中隨機(jī)選取一個最為隨機(jī)飛行的目標(biāo)位置

參數(shù)	值
問題維度(維度)	2
總?cè)簲?shù)量(種群數(shù))	20
搜索次數(shù)(最大迭代次數(shù))	100
最小頻率-最大頻率	0-1
最小響度-最大響度	1-2
$\alpha$	0.85
$\gamma$	0.9
初始脈沖頻率r	0.7
取值范圍	（-100诽凌，100）
實驗次數(shù)	10

實驗二圖像

	值
最優(yōu)值	2.7533362235525127E-5
最差值	372.7498404620516
平均值	139.51154472392443

按照理解（2）實現(xiàn)的結(jié)果好像比理解(1)差不少侣诵。從圖像中可以看出窝趣，雖然在開始沒有像實驗一一樣收斂的那么快，但是在中期聚集的范圍更加集中哑舒，導(dǎo)致陷入局部最優(yōu)難以尋得更優(yōu)的位置妇拯。從理解上看似乎隨機(jī)飛行的隨機(jī)性增大了，但只是減緩了收斂速度洗鸵，并沒有增強(qiáng)跳去局部最優(yōu)的能力越锈。

實驗三：按照理解（3），隨機(jī)選擇最優(yōu)個體的一維進(jìn)行隨機(jī)飛行

實驗三圖像

	值
最優(yōu)值	1.5094277647207394E-9
最差值	8.377006798211614E-5
平均值	1.9714038461326115E-5

實驗三的結(jié)果優(yōu)于實驗一和實驗二膘滨，但是從圖像中可以看出甘凭，其實和實驗一并沒有太大的差別，可以認(rèn)為這次實驗只是運氣比較好火邓，每次都在100代內(nèi)找到較好的解，而實驗一也只是在十次實驗中有一次沒有在100代以內(nèi)找到最優(yōu)的個體铲咨。
　　綜上躲胳，個人認(rèn)為選擇理解（1）和理解（3）差別不大，這兩種理解方式都行纤勒，理解（2）還有待商榷坯苹。

為什么蝙蝠群前期收斂的這么快呢？看一看公式（6）的曲線：

公式6曲線

可以看出r的值隨著迭代次數(shù)iter的增加上升的非常的快摇天，在第6代時就接近1了粹湃。R的大小又決定該蝙蝠是否進(jìn)行隨機(jī)飛行過程∪看了隨機(jī)飛行的實現(xiàn)方式为鳄，可以明確蝙蝠的隨機(jī)飛行就是一個向著全局最優(yōu)位置迅速靠近的過程。進(jìn)行隨機(jī)飛行的條件決定了算法在最初期蝙蝠會大概率飛向全局最優(yōu)位置坚冀，而在約6代后則大概率按照自己的行為飛行（頻率->速度->位置）济赎。因此算法在初期會急速收斂，而后進(jìn)行局部搜索记某，這與實驗中的表現(xiàn)一致司训。

實驗四：在實驗一的基礎(chǔ)上，將隨機(jī)飛行的條件由rand(0,1)>r,修改為rand(0,1)>0.9,即每只蝙蝠每代有10%的概率進(jìn)行隨機(jī)飛行液南，實驗圖像如下：

實驗四圖像

	值
最優(yōu)值	9.663711890794937E-5
最差值	0.002455606291026529
平均值	0.0014838545478091704

可以看出蝙蝠群的收斂速度減慢了不少壳猜，這次的結(jié)果相對較為穩(wěn)定，但仍然容易陷入局部最優(yōu)滑凉，不過由于收斂的速度沒有那么快统扳，陷入局部最優(yōu)的概率相對較低喘帚。
　　對于蝙蝠收斂過快導(dǎo)致陷入局部最優(yōu)的情況，我們也可以學(xué)習(xí)粒子群算法咒钟，對其飛行速度增加上限吹由，保證每只蝙蝠每代的飛行距離存在上限，也能防止其收斂過速朱嘴。但是這樣一來倾鲫，蝙蝠算法就成了粒子群算法的一個改進(jìn)。（弱化版“改進(jìn)”萍嬉，蝙蝠算法本就是參照了粒子群算法）乌昔。

4. 總結(jié)

蝙蝠算法提出距今10年，也算法是一個新算法壤追。算法根據(jù)蝙蝠覓食的行為對粒子群算法進(jìn)行了改造磕道。就結(jié)果而言，蝙蝠算法可以看做是一個弱化的粒子群行冰，拋棄了粒子群的部分優(yōu)點（速度最大限制和向著兩個目標(biāo)飛行）溺蕉，引入了頻率來控制飛行速度，導(dǎo)致飛行的速度沒有粒子群的隨機(jī)性好资柔，更加容易陷入局部最優(yōu)焙贷，但收斂速度更快。
　　原始論文的描述不清晰贿堰，關(guān)鍵的部分描述的模棱兩可，而其他的改進(jìn)蝙蝠算法的論文中的描述與原始論文如出一轍啡彬，感覺并未對算法流程有明確的了解羹与。蝙蝠算法的文章我這幾年間反反復(fù)復(fù)看了很多遍，也參考了前人大神們的代碼庶灿，感覺這個論文就像《哈姆雷特》一樣纵搁。

看了數(shù)年后還是在此記錄一下，可能我的理解能力確實有待提高往踢，但還是希望發(fā)布論文時要將細(xì)節(jié)描述清楚腾誉，不然文中的實驗將無法由其他讀者重現(xiàn)。
參考文獻(xiàn)
Yang X S . A New Metaheuristic Bat-Inspired Algorithm[J]. computer knowledge & technology, 2010, 284:65-74.提取碼：vu7l
以下指標(biāo)純屬個人yy,僅供參考

指標(biāo)	星數(shù)
復(fù)雜度	★★★★★☆☆☆☆☆
收斂速度	★★★★★★★★☆☆
全局搜索	★★☆☆☆☆☆☆☆☆
局部搜索	★★★★☆☆☆☆☆☆
優(yōu)化性能	★★★☆☆☆☆☆☆☆
跳出局部最優(yōu)	☆☆☆☆☆☆☆☆☆☆
改進(jìn)點	★★★★★★★★☆☆

目錄
 上一篇優(yōu)化算法筆記（十四）水波算法
 下一篇優(yōu)化算法筆記（十六）混合蛙跳算法

優(yōu)化算法matlab實現(xiàn)（十五）蝙蝠算法matlab實現(xiàn)

優(yōu)化算法筆記（十五）蝙蝠算法