蝙蝠算法的一種改進方法

魏三強，張 超

(1.宿州職業技術學院計算機信息系，安徽 宿州 234101；2.中國礦業大學信息與控制工程學院，江蘇 徐州 221116)

蝙蝠算法的一種改進方法

魏三強1，2，張 超1

(1.宿州職業技術學院計算機信息系，安徽 宿州 234101；2.中國礦業大學信息與控制工程學院，江蘇 徐州 221116)

針對蝙蝠算法在進行局部搜索時，易使算法陷入局部極值的束縛，導致算法收斂精度不高的缺陷，提出了使用t-分布對局部搜索時的最優解進行變異操作.為最優解各維度增加t分布型隨機擾動項，選取7個經典測試函數做仿真實驗.實驗結果表明：改進的蝙蝠算法在收斂精度和速度上有顯著提升，說明通過對最優解實施t-分布擾動能夠使算法擺脫局部極值的束縛，顯著提高收斂精度.

蝙蝠算法；t分布；收斂精度；群體多樣性；智能算法

0 引言

X.S.Yang[1]根據自然界的蝙蝠能夠利用其發出聲波的回聲，從而準確定位獵物位置的特征，于2010年提出了一種群智能優化算法——蝙蝠算法(Bat Algorithm，BA).該算法能模擬蝙蝠在飛行或捕捉獵物時的回聲定位行為，每個蝙蝠通過改變聲波的頻率、音響強度、脈沖發射率來控制其飛行位置和速度，追隨最優蝙蝠在解空間搜索最優解.文獻[1-5]通過大量數值實驗得出蝙蝠算法在尋找最優解的成功率上優于粒子群算法、和聲算法及遺傳算法.鑒于此，近年來蝙蝠算法在神經網絡優化[6]、資源調配[7]等領域已被應用，但蝙蝠算法也存在收斂精度不高、易陷入局部極值點等缺陷[8]，為此，學者們對蝙蝠算法進行了相關的改進工作.改進的策略主要集中在蝙蝠算法的兩個主要過程：個體飛行和局部搜索.在個體飛行方面，劉長平等[9]提出使用Levy飛行取代原算法的速度和位置更新方式；謝健等[10]在原算法速度和位置更新方式上，對組成蝙蝠速度和位置的各維度添加Levy分布變異.在局部搜索方面，李雅梅等[11]引入Powell機制提高蝙蝠算法的局部搜索能力；劉萬軍等[12]對最優個體進行SQP局部搜索，提高蝙蝠算法的局部深度搜索能力；陳梅雯等[13]使用隨機蝙蝠來引導個體飛行和局部搜索，以提高種群多樣性；臧慧芳等[14]通過引入早熟判斷機制，將差分進化算法思想融入到蝙蝠算法中.這些改進策略在不同程度上提升了蝙蝠算法的收斂精度.

蝙蝠算法在局部搜索時采用隨機游走方式，通過對組成最優解的各維度增加隨機數進行擾動，在最優蝙蝠個體附近生成局部新解.當局部搜索條件成立，算法進行局部搜索時，容易被局部極值點吸引，導致算法不一定收斂到局部最優，并且，隨著迭代進程的推進，當到達中后期階段時，蝙蝠個體集中在局部最優解附近，致使種群多樣性消耗過快，易陷入局部最優，從而導致算法不能夠收斂到全局最優解，收斂精度不高.本文提出使用學生t-分布(簡稱t分布)變異代替原算法的局部新解生成方式，即在最優解best的基礎上增加t分布型隨機擾動項best?t(Iteration)，對最優解各維度進行基于迭代次數Iteration為t分布自由度的自適應變異.選用7個經典測試函數做仿真實驗，以驗證本文提出改進策略的有效性.

1 蝙蝠算法

1.1 蝙蝠算法基本原理

蝙蝠算法模擬蝙蝠的回聲定位行為，通過改變聲波的頻率、音響強度、脈沖發射率來控制其飛行位置和速度，追隨最優蝙蝠在解空間搜索最優解.蝙蝠算法可以歸納出如下7個步驟：

(1) 初始化參數.設置種群規模為sizepop、最大迭代次數為maxgen(或目標精度)、脈沖頻率范圍為[fminfmax]、最大脈沖頻度為r0、最大脈沖音強為A、音強衰減系數為α、頻度增加系數為γ、搜索變量的維度為d.

(2) 蝙蝠種群初始化.在搜索范圍內隨機初始化蝙蝠個體位置xi(i=1，…，d)，找出當前搜索中最佳蝙蝠位置x*.

(3) 種群迭代.蝙蝠個體飛行按照

(1)

對脈沖頻率fi，蝙蝠t時刻的速度vi，位置xi進行更新.其中x*是當前搜索全局最優解，rand∈[0，1]的隨機數.

(4) 生成隨機數rand.如果rand>ri，選擇最優蝙蝠個體，按照

xnew=xold+ε×At，

(2)

(5)再次生成隨機數rand.如果rand

(3)

增大ri和減小Ai的值.其中t為當前迭代次數，α和γ為常量.

(6) 對蝙蝠種群的適應度值進行排序.記錄當前最優蝙蝠位置及其適應度值.

(7) 重復執行步驟(3)—(6).進入迭代尋優，直至滿足最大迭代次數或設定精度停止算法，輸出全局最優值及對應蝙蝠位置.

1.2 改進的蝙蝠算法

蝙蝠算法在局部搜索時采用隨機游走方式，通過對組成最優解的各維度增加隨機數進行擾動，在最優蝙蝠個體附近生成局部新解，當算法進行局部搜索靠近極值點時，容易被極值點吸引，致使種群多樣性消耗過快，導致算法收斂精度不高.本文使用t分布變異策略對原算法的局部搜索方式進行改進.

1.2.1 t分布

t分布是英國統計學家Gosset于1908年以筆名“Student”提出的，因此稱學生氏t分布，簡稱t分布.t分布曲線是左右對稱的，圍繞平均數向兩側遞降.t分布受自由度參數df=n-1的制約，每個自由度都有一條t分布曲線.和正態分布相比，t分布的頂部偏低，尾部偏高.自由度df越小，t分布曲線越低平；自由度df越大，t分布曲線越接近正態分布.柯西分布和高斯分布是t分布的兩個邊界特例.當t分布自由度df=1時，t分布曲線和柯西分布曲線重合；當自由度df>30時，t分布曲線開始與正態分布曲線接近；當df∞時，t分布曲線和高斯分布曲線重合.

1.2.2 自適應t分布變異蝙蝠算法

由于t分布隨著自由度的增加能夠在柯西分布和高斯分布之間轉換，柯西分布變異具有良好的全局開發能力，而高斯變異具有穩定的局部搜索能力.因此，文獻[15]將t分布應用到人工魚群算法的改進中，提出將算法的迭代次數作為t分布的自由度參數，對除了最優魚之外的非最優魚進行t分布變異.文獻[16]將t分布引入到蝙蝠算法的改進中，對除了最優蝙蝠之外的非最優蝙蝠進行t分布變異.從文獻[15-16]的結果看出，經過對非最優解進行t分布變異后，提高了算法的收斂精度和速度.本文使用

xnew=xold+xold?t(Iteration)

(4)

代替公式(2)，即提出使用t分布對最優解進行變異，進行局部搜索生成新解的方式.其中?為點乘符號，t(Iteration)是以算法的迭代次數Iteration為自由度的t分布.

改進策略在蝙蝠算法迭代初期，Iteration值較小，通過對最優解進行近似柯西分布變異能夠產生遠離最優解的下一代點，提高種群多樣性，避免算法過早早熟，陷入局部最優.算法運行后期，Iteration的取值較大，對最優解進行t分布變異近似高斯分布，具有較好的局部搜索能力，能夠提高算法的收斂精度.

改進的算法記為TBA.改進的算法使用公式(4)進行局部搜索，其執行流程與原算法一致.

2 實驗與結果分析

2.1 實驗方案設計和部署

本文從兩方面對改進的算法性能進行仿真實驗：(1)對BA和TBA做對比實驗；(2)將TBA與其他改進BA的結果進行比較.

為了便于與其他改進BA的比較，本文選用7個測試函數，使用比較苛刻的參數設置，函數的表達式、變量范圍、理論極值和目標精度見表1.實驗在主頻2.50 GHz的CPU、2 GB內存、32位Win7操作系統的計算機上使用Matlab R2012a編程實現仿真程序.

算法參數設置：蝙蝠種群規模sizepop=20，迭代次數maxgen=1 000，脈沖頻率范圍為[0，2]，音強衰減系數α=0.95，頻度增加系數γ=0.05，每個蝙蝠的脈沖頻度ri∈[0，1]，脈沖音強Ai∈[1，2].

表1 測試函數的參數

2.2 實驗結果分析與比較

2.2.1 TBA與BA性能比較分析

對表1中的7個測試函數按照指定維度和變量范圍，使用BA和TBA仿真程序，分別隨機獨立連續運行20次.固定迭代次數下的實驗結果見表2.由表2可見，改進的蝙蝠算法TBA在衡量算法性能的4個指標上均明顯優于BA，收斂精度顯著提高.圖1為TBA和BA的適應度收斂進化曲線(為了便于觀察，對Michalewicz函數除外的其他6個函數的適應度值取10為底的對數處理).從圖1中可以看出，TBA較BA收斂速度有大幅提升.函數f1，f5，f6和f7理論極值為0， TBA在這4個函數上的適應度進化曲線出現間斷，表明已經找到該函數的理論極值0，因為對數的真數為0時不顯示.

表2 BA和TBA的實驗結果

圖1 BA和TBA的適應度值進化收斂趨勢比較

表3為固定精度下的BA算法和TBA算法的平均迭代次數和成功率.數值采用 “平均迭代次數/成功率”表示，1代表百分之百成功.從表3中可知，BA在預設精度下，均不能收斂到固定精度，而TBA在比較苛刻的精度設定下，均能百分百成功收斂到固定精度.從而說明TBA有效地提高了算法的收斂速度.

表3 固定精度下平均迭代次數與成功率

2.2.2 TBA與其他BA改進算法性能比較分析

為了將本文提出的改進算法與其他蝙蝠改進算法進行比較，選取近兩年改進效果較好的4個改進算法：IBA[13]、CDEBA[14]、TMBA[16]、VBA[17].文獻[13]中f1，f2，f3，f4，f5，f6，f7函數變量范圍分別為±600，±15，[-5，10]，[0，π]，±600，±32.768，±15，種群規模sizepop=20，maxgen=3 000；文獻[14]中f1，f5，f6，f7函數變量范圍分別為±100，±600，±32，±5.12，種群規模sizepop=50，maxgen=200；文獻[16]中f1，f3，f5，f6，f7函數變量范圍分別為±5.12，[-5，10]，±600，[-15，30]，±15，種群規模sizepop=50，maxgen=1 000；文獻[17]中f1，f4，f5，f6函數變量范圍分別為±5.12，[0，π]，±600，±32，種群規模sizepop=50，maxgen=200.

TBA是在種群規模、迭代次數、測試函數變量范圍等指標比較苛刻的約束設定下進行的仿真.對比結果及對比算法的搜索空間維度見表4.從表4可知，除了Rosenbrock 函數外，本文的TBA適應度平均值明顯優于其他算法，并在f1，f5，f6，f74個函數上均能收斂到理論極值0.文獻[13] 提出的IBA在Rosenbrock 函數上的收斂精度優于TBA，但在其他6個函數收斂精度上遠低于本文提出的TBA.文獻[14]提出的CDEBA在搜索維度為2的情況下，能夠收斂到Griewank函數的理論極值0，但隨著維度的增加收斂精度明顯下降.

表4 TBA(30維)與其他蝙蝠改進算法優化平均值比較

綜上所述，本文提出的對原算法局部搜索使用的隨機游走方式進行自適應t分布變異能夠有效擺脫局部極值的束縛，避免算法“早熟”，在迭代早期近似柯西分布的t分布變異拓展了種群的多樣性，從而提高了算法的收斂精度和速度.

3 結論

對蝙蝠算法進行局部搜索時的最優解進行t-分布變異操作后的改進算法，在Sphere、Griewank、Ackley、Rastrigin函數上均能收斂到函數的理論極值0，在Zakharov、Michalewicz函數上的收斂精度也明顯優于其他算法.結果表明，通過過對最優解進行t-分布擾動能夠使算法擺脫局部極值的束縛，顯著提高收斂精度.

[1] YANG X S.A new metaheuristic bat-inspired algorithm[J].Nature Inspired Cooperative Strategies for Optimization(NICSO 2010)，2010，284：65-74.

[2] YANG X S.Bat algorithm for multi-objective optimization[J].Int J Bio-Inspired Computation，2011，3(5)：267-274.

[3] YANG X S，GANDOMI A H.Bat algorithm：a novel approach for global engineering optimization[J].Engineering Computation，2012，29(5)：267-289.

[4] 李煜，馬良.新型全局優化蝙蝠算法[J].計算機科學，2013，40(9)：225-229.

[5] 劉長平，葉春明，劉滿成.來自大自然的尋優策略：像蝙蝠一樣感知[J].計算機應用研究，2013，30(5)：1320-1322，1356.

[6] 孔令春，孫瓊瓊，楊照峰.蝙蝠算法優化極限學習機的電力負荷預測模型[J].遼寧工程技術大學學報(自然科學版)，2016，35(1)：89-92.

[7] 劉長平，陳偉達.求解零等待流水車間調度問題的改進蝙蝠算法[J].數學的實踐與認識，2016，46(11)：38-46.

[8] 尚俊娜，劉春菊，岳克強，等.具有自學習能力的變異蝙蝠優化算法及性能仿真[J].系統仿真學報，2017，29(2)：301-308.

[9] 劉長平，葉春明.具有Lévy飛行特征的蝙蝠算法[J].智能系統學報，2013，8(3)：240-246.

[10] 謝健，周永權，陳歡.一種基于Lévy飛行軌跡的蝙蝠算法[J].模式識別與人工智能，2013，26(9)：829-837.

[11] 李雅梅，曹益華.基于Powell機制的改進蝙蝠算法[J].微電子學與計算機，2015，32(3)：73-76，80.

[12] 劉萬軍，楊笑，曲海成.基于SQP局部搜索的蝙蝠優化算法[J].計算機工程與應用，2016，52(15)：183-189.

[13] 陳梅雯，鐘一文，王李進，等.一種求解多維全局優化問題的改進蝙蝠算法[J].小型微型計算機系統，2015，36(12)：2749-2753.

[14] 臧慧芳，高岳林.基于混沌和差分進化的混合蝙蝠算法[J].蘭州理工大學學報，2016，42(5)：90-94.

[15] 王波.基于自適應t分布混合變異的人工魚群算法[J].計算機工程與科學，2013，35(4)：120-124.

[16] 常青，賀興時.基于t分布變異的蝙蝠算法[J].西安工程大學學報，2015，29(5)：647-653.

[17] 薛威力，賀興時，楊新社.蝙蝠算法的一種改進[J].哈爾濱商業大學學報(自然科學版)，2016，32(6)：706-712.

Animprovedmethodforbatalgorithm

WEI San-qiang1，2，ZHANG Chao1

(1.Department of Computer and Information，Suzhou Vocational and Technological College，Suzhou 234101，China；(2.School of Information and Control Engineering，China University of Mining and Technology，Xuzhou 221116，China)

When the bat algorithm performs local search，random numbers are added to the optimal solution of each dimension.This mechanism makes the bat algorithm fall into local extremum，which leads to the low precision of the algorithm.In view of the shortcomings of the bat algorithm.This paper proposes a modified algorithm，which employed a student’st-distribution mutation operator to disturb the optimal solution of each dimension.The experimental results of seven function show that the modified algorithm improves the convergence precision and speed.Therefore，the modified algorithm whicht-distribution mutation operator is added can improve the abilities of seeking the global excellent result and evolution speed.

bat algorithm；student’st-distribution；convergence precision；population diversity；intelligence algorithm

1000-1832(2017)04-0076-06

10.16163/j.cnki.22-1123/n.2017.04.015

2017-04-12

國家自然科學基金資助項目(61572036)；安徽省高校自然科學研究重點項目(KJ2016A781).

魏三強(1980—)，男，副教授，博士研究生，主要從事智能算法、云計算研究.

TP 301.6學科代碼520·10

A

(責任編輯：石紹慶)