程春英　劉娜仁

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

關(guān)鍵詞：蝙蝠算法；回聲定位；脈沖；改進(jìn)

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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]。該算法具有實(shí)現(xiàn)簡(jiǎn)單、參數(shù)少等特點(diǎn)，已經(jīng)成為近幾年啟發(fā)式算法的研究熱點(diǎn)。蝙蝠算法也像其他群智能優(yōu)化算法一樣是一種基于迭代的優(yōu)化算法。算法初始化時(shí)隨機(jī)生成一組隨機(jī)解，再通過(guò)反復(fù)的迭代過(guò)程查找最優(yōu)解，并且在尋優(yōu)過(guò)程中會(huì)在最優(yōu)解周圍通過(guò)隨機(jī)飛行產(chǎn)生部分的新解，這不僅加快了局部搜索過(guò)程，還保證了種群的多樣性。

蝙蝠算法在解決函數(shù)優(yōu)化問(wèn)題方面表現(xiàn)出了良好的性能，通過(guò)對(duì)多個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的測(cè)試，展現(xiàn)了在連續(xù)性優(yōu)化問(wèn)題中的較好應(yīng)用。

2 BA的基本原理

（1）蝙蝠的行為

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

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

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

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

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

3）響應(yīng)度的變化從為[[+Ao，-Ao]]。

3 BA算法的數(shù)學(xué)描述

4 BA算法研究

根據(jù)文獻(xiàn)資料的研究來(lái)看，蝙蝠算法的研究目標(biāo)主要集中在如何改善蝙蝠算法的性能方面。具體改進(jìn)的算法有：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）BA算法的收斂性研究

對(duì)于蝙蝠算法的研究，還只是停留在實(shí)驗(yàn)研究階段，其數(shù)學(xué)基礎(chǔ)還很薄弱，沒(méi)有其收斂性證明給予支持，因此對(duì)蝙蝠算法的收斂性研究是一個(gè)很重要的研究方向。

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

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

3）BA算法應(yīng)用研究

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

參考文獻(xiàn)：

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

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

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

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

[5] 李枝勇，馬良，張惠珍.蝙蝠算法在多目標(biāo)多選擇背包問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)仿真.2013，（10）：350-353.

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

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

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

[9] 張宇楠，劉付永.一種改進(jìn)的變異步長(zhǎng)自適應(yīng)蝙蝠算法及其應(yīng)用[J].廣西民族大學(xué)學(xué)報(bào)，20113，19（2）：51-54.

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

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

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

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

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

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