蝙蝠算法的研究進展

程春英　劉娜仁

摘要：蝙蝠算法（BA）是通過用搜索空間中的點模擬自然界中的蝙蝠個體，將搜索和優(yōu)化過程模擬成蝙蝠個體搜索獵物和移動過程，將求解問題的目標函數度量成個體所處位置的優(yōu)劣，在搜索和優(yōu)化過程中用好的可行解取代較差的可行解的迭代過程的一種優(yōu)化算法。蝙蝠算法因具有較強的魯棒性、高效性和應用性，已成功地應用于函數優(yōu)化、工程設計、分類等多個方面。本文首先給出了蝙蝠算法的原理及模型，然后列出了蝙蝠算法近幾年來的改進研究，最后展望了蝙蝠算法的發(fā)展方向。

關鍵詞：蝙蝠算法；回聲定位；脈沖；改進

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2016）24-0187-02

Abstract： Bat algorithm （BA） is by using the search space of some model bats in the nature， search and optimization of process simulation into bats individual search prey and moving process， measures to solve the problem of objective function into individual strengths and weaknesses of the location， in the search and optimization process with good poor feasible solution to replace the feasible solution of an optimization algorithm of iterative process.The bat algorithm for has stronger robustness， efficiency and applicability， has been successfully applied to functionoptimization， engineering design， classification， and many other aspects.This article first elaborated the bat algorithm basic principle and mathematical model， and then bat algorithm existing various kinds of improved algorithm is given， and the development direction of the bat algorithm are discussed.

Key words： Bat Algorithm； Echolocation ；Impulse ；Improvement

1 引言

蝙蝠算法（Bat Algorithm，BA）是2012年楊教授提出的一種群智能優(yōu)化算法[1]。該算法具有實現(xiàn)簡單、參數少等特點，已經成為近幾年啟發(fā)式算法的研究熱點。蝙蝠算法也像其他群智能優(yōu)化算法一樣是一種基于迭代的優(yōu)化算法。算法初始化時隨機生成一組隨機解，再通過反復的迭代過程查找最優(yōu)解，并且在尋優(yōu)過程中會在最優(yōu)解周圍通過隨機飛行產生部分的新解，這不僅加快了局部搜索過程，還保證了種群的多樣性。

蝙蝠算法在解決函數優(yōu)化問題方面表現(xiàn)出了良好的性能，通過對多個標準測試函數的測試，展現(xiàn)了在連續(xù)性優(yōu)化問題中的較好應用。

2 BA的基本原理

（1）蝙蝠的行為

蝙蝠是一種具有回聲定位能力的哺乳動物。蝙蝠在覓食時，通過發(fā)出聲音脈沖和聆聽從周圍反彈回來的回聲，可準確的躲避障礙物和發(fā)現(xiàn)獵物。

（2）蝙蝠的回聲定位功能

在蝙蝠算法中提出了一些基本假設條件：

1）所有蝙蝠粒子利用自身回聲定位感知與目標之間的距離，同時以一種神秘的方式辨別目標和障礙物的不同。

2）蝙蝠的位置為[xi]，以速度[ui]任意地飛行，以固定的頻率[fmin]、可變波長[λ]和響應度[Ao]搜索目標。它們可以判斷自己與獵物之間的距離并自動地調整脈沖的波長，同時在接近目標時調整脈沖的頻度[r∈[0，1]]。

3）響應度的變化從為[[+Ao，-Ao]]。

3 BA算法的數學描述

4 BA算法研究

根據文獻資料的研究來看，蝙蝠算法的研究目標主要集中在如何改善蝙蝠算法的性能方面。具體改進的算法有：

劉長平等人[2]針對基本蝙蝠算法收斂精度低和易早熟的不足，采用levy飛行搜索策略來模擬蝙蝠的捕食行為，取代了原有算法的速度和位置更新公式，使得該算法有效地避免了局部極值的吸引。

賀興時等人[3] 提出了一種基于模擬退火的高斯擾動蝙蝠優(yōu)化算法。該算法將模擬退火的思想引入到蝙蝠優(yōu)化算法中，并對蝙蝠算法的某些個體進行高斯擾動，提高了蝙蝠算法的搜索效果。

李枝勇等人[4]在基本蝙蝠算法的基礎上結合遺傳變異的思想，引入主動進化算子、無效蝙蝠和當前最優(yōu)蝙蝠集聚的處理規(guī)則，提出了遺傳變異蝙蝠算法，并將該算法用于求解0/1背包問題，仿真結果表明該算法在精度和收斂速度上都要要優(yōu)于基本蝙蝠算法。

李枝勇等人[5]針對傳統(tǒng)的多目標多選擇優(yōu)化算法由于計算復雜度非常高，難以獲得滿意的解的缺點，在基本蝙蝠算法的基礎上，提出了一種改進的蝙蝠算法用于求解多目標多選擇背包問題，并與粒子群算法相比較。仿真結果表明，該算法能夠以更快的速度找到相同的Pareto，拓展了蝙蝠算法的應用領域。

盛曉華等人[6]將蝙蝠算法用于解決PFSP調度干擾研究問題，并與粒子群算法進行比較，結果表明蝙蝠算法性能不僅適用于生產調度問題的求解且優(yōu)于粒子群算法。

肖輝輝等人[7]提出了一種基于差分進化算法的改進蝙蝠算法，該算法把差分進化算法中的變異、交叉、選擇機制應用于蝙蝠算法，使缺乏變異機制的蝙蝠算法具有變異機制，從而提高蝙蝠算法的多樣性，避免種群個體陷入局部最優(yōu)，增強了算法全局尋優(yōu)能力。

黃光球等人[8]采用正交拉丁方原理生成蝙蝠的初始位置，將蝙蝠的追隨、自主、避險和從眾行為用于構造每個蝙蝠的空間位置轉移策略，根據蝙蝠捕獲獵物時的響度和脈沖速率來保證整個蝙蝠群體保持原態(tài)或向好的空間轉移，但絕不會向差的空間轉移，提高了算法的適應性和收斂速度。

張宇楠等人[9]提出一種變步長自適應的蝙蝠算法。該算法中，步長可隨迭代次數的增加而自適應地調整，從而使算法在后期獲得更高精度的解。因此算法的收斂速度及精度均有明顯提高，且算法在一定程度上避免了過早陷入局部最優(yōu)解的問題。

冷令[10]針對入侵檢測的特征和分類器參數選擇問題，采用極限學習機ELM進行構建分類器，提出一種蝙蝠算法聯(lián)合選擇特征和分類器參數的網絡入侵檢測模型。算法將特征子集和極限學習機參數編碼成蝙蝠個體，以入侵檢測準確率和特征數加權組成個體適應度函數，通過個體和群體更新的規(guī)則引導蝙蝠向最優(yōu)解飛行，從而找到最優(yōu)的子特征集和極限學習機參數。

李枝勇等人[11] 對于元胞自動機原理進行研究，提出了一種元胞蝙蝠算法。該算法通過元胞及其鄰居來提高算法的全局尋優(yōu)能力和搜索過程的多樣性。并利用該算法求解多個0/1規(guī)劃問題，實驗結果表明該算法具有較好的全局尋優(yōu)能力和較快的收斂速度。

孫文捷等人[12]利用Fuch映射對基本蝙蝠算法的局部最優(yōu)解的鄰域和蝙蝠的頻率變化區(qū)間進行混沌遍歷搜索，提出了一種新型混合蝙蝠算法——Fuch混沌蝙蝠算法。通過仿真計算與基本蝙蝠算法相比，該算法具有較好的收斂性能，能夠較快地收斂于測試算例的全局最優(yōu)解，并很好地避免了搜索過程陷入局部最優(yōu)的問題。

李枝勇等人[13]針對傳統(tǒng)的蝙蝠算法在解決整數規(guī)劃問題時容易陷入局部最優(yōu)并出現(xiàn)早熟收斂現(xiàn)象，提出了一種基于勢阱的具有量子行為的蝙蝠算法。并將具有量子行為的蝙蝠算法與粒子群算法和量子行為粒子群算法進行性能對比研究，實驗結果表明，該算法不僅能夠有效地解決整數規(guī)劃問題，而且比其他算法具有更好的性能。

韓福霞等人[14] 為了優(yōu)化信息工程監(jiān)理過程中的多目標問題，通過對各目標權重分配方法的改進，構建針對各監(jiān)理階段的多目標控制優(yōu)化模型，采用蝙蝠算法對其進行求解，并與粒子群算法進行比較，仿真結果表明，該算法能夠適用于對信息工程監(jiān)理多目標優(yōu)化問題的最優(yōu)解的搜索且優(yōu)于基本粒子群算法。

陳紹煒等人[15]將蝙蝠算法引入到極限學習機輸人權值和閾值的優(yōu)化中，有機結合兩種算法的優(yōu)點，建立了基于蝙蝠算法優(yōu)化極限學習機的故障模型，以帶通濾波器作為測試電路，并和ELM、DE-ELM、SAE-ELM進行對比，仿真和實驗結果表明蝙蝠算法有效地改善了ELM網絡的診斷精度和泛化能力。

蝙蝠算法在函數優(yōu)化問題的應用上取得了一定的成績，但在離散優(yōu)化問題上的應用卻少之又少。因此，對蝙蝠算法的改進還是有很大的空間的。

1）BA算法的收斂性研究

對于蝙蝠算法的研究，還只是停留在實驗研究階段，其數學基礎還很薄弱，沒有其收斂性證明給予支持，因此對蝙蝠算法的收斂性研究是一個很重要的研究方向。

2）BA算法的拓展研究和混合研究

從文獻資料來看，已出現(xiàn)了蝙蝠算法與一些常用群智能算法（遺傳算法、粒子群算法等）的混合算法，但是與近幾年來出現(xiàn)的新型群智能算法（蛙群算法、布谷鳥算法等）的混合算法的相關研究還是很少，因此，將BA算法和這一類新型群智能算法的混合研究也是一個非常重要的研究方向。

3）BA算法應用研究

從文獻資料來看，目前蝙蝠算法的應用研究有：在PFSP調度和干擾管理上的應用、0/1及多目標背包問題上的應用、在分類器參數的入侵檢測問題的應用、在ELM模擬電路故障診斷中的應用、在信息工程管理優(yōu)化問題中的應用等等，其他應用還是集中解決函數優(yōu)化問題。因此今后如何拓展蝙蝠算法的應用領域也是一個非常重要的研究方向。

參考文獻：

[1] YANG X S. A new met heuristic Bat-Inspired Algorithm[J]. Nature Inspried Cooperative Strategies for Optimization，Spinger，2010：65-74.

[2]劉長平，葉春明.具有l(wèi)evy飛行特征的蝙蝠算法[J].智能系統(tǒng)學報，2013，8（3）：240-245.

[3] 賀興時，丁文靜，楊新社.基于模擬退火高斯擾動的蝙蝠優(yōu)化算法[J].計算機應用研究.

[4] 李枝勇，馬良，張惠珍.遺傳變異蝙蝠算法在0-1背包問題上的應用[J].計算機工程與應用.2012

[5] 李枝勇，馬良，張惠珍.蝙蝠算法在多目標多選擇背包問題中的應用[J].計算機仿真.2013，（10）：350-353.

[6] 盛曉華，葉春明. 基于蝙蝠算法的PFSP調度干擾管理研究[J].工業(yè)工程，2013，16（1）：119-124.

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

[8] 黃光球，趙魏娟，陸秋琴.求解大規(guī)模優(yōu)化問題的可全局收斂蝙蝠算法[J].計算機應用研究，2013，30（5）：1323-1328.

[9] 張宇楠，劉付永.一種改進的變異步長自適應蝙蝠算法及其應用[J].廣西民族大學學報，20113，19（2）：51-54.

[10] 冷令.蝙蝠算法聯(lián)合選擇特征和分類器參數的入侵檢測[J].計算機應用與軟件，2014.

[11] 李枝勇，馬良，張惠珍.0-1規(guī)劃問題的元胞蝙蝠算法[J].計算機應用研究.2013.

[12] 孫文捷，張惠珍，張建，趙坤.基于Fuch映射的混沌蝙蝠算法[J].上海理工大學學報，2014.

[13] 李枝勇，馬良，張惠珍.整數規(guī)劃的量子行為蝙蝠算法[J].計算機工程與科學，2014.

[14] 韓福霞，劉宏志.基于蝙蝠算法的信息工程監(jiān)理多目標優(yōu)化研究[J].現(xiàn)代計算機，2013.

[15] 陳紹煒，柳光峰，冶帥，等. 基于蝙蝠算法優(yōu)化ELM的模擬電路故障診斷研究[J].電子測量技術，2015，38（2）.