岳偉娜，馬吉明，蘇日建，郭盛楠

(鄭州輕工業(yè)學院 計算機與通信工程學院，河南 鄭州 450002)

?

基于反向學習機制的蝙蝠算法

岳偉娜，馬吉明，蘇日建，郭盛楠

(鄭州輕工業(yè)學院 計算機與通信工程學院，河南 鄭州 450002)

針對蝙蝠算法存在收斂速度慢，尋優(yōu)精度低問題，提出一種基于反向學習的蝙蝠算法，該算法具有易跳出局部最優(yōu)，尋優(yōu)精度高，種群多樣性且魯棒性好等特點.通過對6個典型的測試函數進行仿真實驗，結果表明該算法是行之有效的，且在求解多峰函數時運算的效果更好.

蝙蝠算法;反向學習;多樣性;魯棒性

蝙蝠算法(BA) 是Yang教授[1]于2010年基于群體智能提出的啟發(fā)式搜索算法,是一種搜索全局最優(yōu)解的有效方法.蝙蝠算法模擬的是微型蝙蝠的回聲定位原理，該算法利用頻率調諧技術來提高種群中解的多樣性,通過自動縮放技術來改變脈沖發(fā)射速率和脈沖響度的大小來平衡算法搜索過程中全局尋優(yōu)和局部尋優(yōu)的平衡性.與遺傳算法相比，蝙蝠算法簡單、容易實現同時又有深刻的智能背景，既適合科學研究，又特別適合工程應用.如多目標優(yōu)化、工程優(yōu)化、大規(guī)模優(yōu)化等問題.但蝙蝠算法的缺點有易陷入局部極值點，進化后期收斂慢，精度較差等.嚴重的制約了蝙蝠算法的應用領域.為了克服蝙蝠優(yōu)化算法的缺點，目前出現了大量的改進蝙蝠算法，本文引入反向學習機制，該算法在收斂速度和計算精度方面相比蝙蝠算法有所提高，可以選出部分優(yōu)秀的反向個體加入到全局搜索，這樣既增加了種群多樣性，又讓粒子更容易使算法跳出局部極值的限制.這種改進在一定程度上解決了基本BA算法的收斂速度、算法等缺點.并通過對6個典型的測試函數進行仿真實驗，結果表明該算法是行之有效的，且在求解多峰函數時運算的效果更好.

1 相關知識

1.1 原始蝙蝠算法

蝙蝠擁有回聲定位能力，它們能產生短促而頻率高的聲波脈沖，這些聲波在碰到附近物體便反射回來[2-4].然后這些反射回來的聲波被蝙蝠大耳廓所接收，聲波反饋的信息被它們微細的大腦所分析，為飛行提供導向.所以蝙蝠利用回聲定位的方法感知距離,并且它們采用一種巧妙的方式來區(qū)別獵物和背景障礙物之間的不同.

在理想狀態(tài)下，蝙蝠算法[5-7]是利用蝙蝠在覓食時所發(fā)出的脈沖的頻率、響度、脈沖發(fā)射率的變化而模擬設計出的群智能算法.基本蝙蝠算法是模擬蝙蝠的覓食行為，通過頻率f的調整引起波長λ的變化(λf=v).其中，v是聲波在空氣中的傳播速度，頻率f在[fmin,fmax]范圍內變化．蝙蝠按脈沖發(fā)射率ri在[0，1]的范圍內和響度Ai發(fā)出聲波脈沖來近似無聲無息[8]的搜索獵物.

BA算法和其他進化算法相比有很多相似之處，都能用來求解方程的優(yōu)化問題.比如多元函數的優(yōu)化問題[9-10].而大量的理論和實驗研究結果表明，BA算法在解決一些典型實際的優(yōu)化問題時，相比較其他算法能夠取得較好的優(yōu)化結果.BA算法被成功地應用于多目標優(yōu)化，自動目標檢測和決策調度等領域并且取得了良好的效果.

如上所述，蝙蝠算法包含搜索脈沖頻率、速度和位置更新、脈沖音強及脈沖發(fā)射頻度四個要素.

搜索脈沖頻率方程為：

(1)

其中：a為[0,1]范圍內的隨機數，fi，fmax，fmin分別指當前脈沖頻率，頻率最大值和最小值.

飛行速度方程為：

(2)

位置更新方程為：

(3)

隨機游走方程為：

(4)

脈沖響應強度方程為：

(5)

其中：β，γ為常數，脈沖發(fā)射頻度方程為：

(6)

1.2 反向學習機制

近年來，反向學習是多種優(yōu)化算法應用中的一種新技術，首先需要對所有粒子的位置求出其適應值，得到適應最大值xmax和適應最小值xmin，然后，對所有粒子進行式(7)的運算得出新的粒子位置并求出所有粒子的適應值，對新得到的適應最小值與之前的適應最小值進行比較，若前者小于后者，則對前者的位置信息進行更新.反向學習[11-15]機制的方程為：

(7)

2 改進的蝙蝠算法

從蝙蝠算法的步驟可以看出，在迭代過程中，整個群體只向最優(yōu)的個體學習，一旦發(fā)現最優(yōu)個體，則所有粒子都往該處尋找，這種位置更新方式不僅大幅降低了粒子種群的多樣性，并且如果該位置并不是全局最優(yōu)，則也有可能導致算法陷入局部最優(yōu)，進而對收斂精度和收斂速度有一定影響.事實上，蝙蝠種群在整個搜索空間中，全局最優(yōu)往往存在于局部最優(yōu)的附近，并且種群的進化速度更大程度取決于較差個體而不是較優(yōu)個體.

本文在蝙蝠算法的基礎上，引入了反向學習機制來調節(jié)粒子的運動軌跡，這樣不僅有助于增加螢火蟲群體的多樣性和跳出局部最優(yōu)，且當粒子在全局最優(yōu)附近時具有較好的收斂性.其主要作用在于當粒子在進行搜索時，在本種群及其反向種群中尋找最優(yōu)個體作為當前的全局最優(yōu)，這樣不僅有助于跳出局部最優(yōu)，且當粒子在全局最優(yōu)附近時得到較好的收斂性.

具有反向學習機制的BA算法(OL-BA)的具體步驟如下：

1)初始化種群，在定義域內隨機生成蝙蝠種群大小為n，設定收索空間維數為m，設定每個蝙蝠個體的初識位置，速度，響應和脈沖發(fā)射率.

2)根據適應度函數去確定蝙蝠群體中的最優(yōu)個體；

3)根據式(7)對種群進行反向學習并代入適應度函數進行計算；

4)反向學習前后計算出的適應度值進行比較，取值較好的個體代替并加入種群中；

5)根據式(1)去設定每個蝙蝠個體的頻率；

6)根據式(2)和式(3)去更新每個蝙蝠的速度和位置；

7)計算適應度值，從而更新每個蝙蝠的歷史最優(yōu)和全局最優(yōu)；

8)對每個蝙蝠進行rand>ri;滿足條件按式(4)計算，若新解較好，取代舊解并更新蝙蝠的歷史最優(yōu)和全局最優(yōu)；

9)根據式(5)和(6)對蝙蝠個體的響度和脈沖發(fā)射率進行更新；

10)當迭代次數未達到最大迭代次數，則返回步驟(2)繼續(xù)往下執(zhí)行，直到迭代結束，輸出結果為止.

表1 標準測試函數

3 仿真實驗及分析

實驗平臺：處理器CPU I5-3470，主頻3.20 GHz，內存4 GB，操作系統(tǒng)：Windows XP，集成開發(fā)環(huán)境MATLAB R2012a.

為了驗證OL-BA的算法的性能，分別將BA算法，LF-BA算法和OL-BA算法用于6個典型的測試函數，并在MATLAB軟件中對各個算法運行的結果進行了測試和比較，這6個測試函數為：

蝙蝠算法中的參數無確切的理論依據，而具反向學習的蝙蝠算法中：個體個體i最大脈沖頻度r0=0.75，最大脈沖響度Ai=0.25，脈沖響度衰減系數β =0.9，脈沖頻度增加系數 γ=0.05，Lévy飛行尺度參數λ=1.5.對6個不同的測試函數的最大迭代次數和種群數分別設置不同的數值，如表1所示.

在進行最優(yōu)值和平均最優(yōu)值分析時，具體參數設定如下：迭代次數為200次，種群規(guī)模為40個.為了避免算法的偶然性帶來的誤差，對6個函數在不同的維度上都獨立運行30次，取其中的最差值和最優(yōu)值及平均值帶入到表2中.

表2 測試函數的最優(yōu)值、最差值和平均最優(yōu)值

從表2中可以看出，文中提出的算法與BA算法和LF-BA算法相比，在求解低維函數f1時，OL-BA算法的綜合優(yōu)化性能較好；在對多峰值且求解域內有大量的局部最優(yōu)值的f3到f6時，BA算法得到的最優(yōu)值和理論的最優(yōu)值的偏差較大.而OL-BA算法在得到的最優(yōu)值和理論值較為接近且算法的魯棒性能較好.特別是在求解f2，BA算法得到的最優(yōu)值和最差值之間的差值較大得到的平均值離理論值較遠，而OL-BA算法在這方面就體現出優(yōu)勢，進一步說明了OL-BA算法具有很好的適應性和魯棒性.

為了測試OL-BA算法的收斂速度，搜索能力和尋優(yōu)精度等，一般情況都采用如下方法：在相同的測試函數相同維度下，評估各個算法的搜索能力，尋優(yōu)能力和魯棒性.

如圖1所示，可以看出在求解低維度的函數時，三個算法在運行到20次左右都可以達到3位數的精度，只是改進算法的收斂速度比原始算法更快些.如圖2所示， OL-BA的收斂速度上明顯好于BA和LF-BA算法且在25次左右收斂于5位數的精度，如圖3至圖5所示，在求解多峰函數時，OL-BA和LF-BA兩種算法要明顯優(yōu)于原始的BA算法，但OL-BA算法的收斂速度明顯好于后者.從圖6可以看出，當迭代到100次時，BA算法陷入局部最優(yōu)值，當迭代到145次左右時，兩個改進算法都收斂到3位數精度，由于步長因子的限制，LF-BA算法停止了尋優(yōu)，OL-BA算法還繼續(xù)尋優(yōu)到200次達到4位數精度.

圖1 Schaffer函數(維數D=2) 圖2 Sphere函數(維數D=10)Fig.1 Schaffer function (dimension D=2) Fig.2 Sphere funilion(dimension D=10)

圖3 Rastrigin函數(維數D=10) 圖4 Ackley函數(維數D=10)Fig.3 Rastrigin function (dimension D=10) Fig.4 Ackley function (dimension D=10)

圖5 Griewank函數(維數D=10) 圖6 Salomon函數(維數D=20)Fig.5 Griewank function (dimension D=10) Fig.6 Salomon function (dimension D=20)

5 結論

本文針對BA算法的缺點，容易陷入局部極小的缺陷，且精度差.提出了一種基于反向學習的改進BA算法.此算法在尋優(yōu)的過程中，根據最優(yōu)粒子和最差粒子之間的信息，得出一個反向種群，根據其最優(yōu)粒子和先前的最優(yōu)粒子作比較，取其中較好的粒子并更新當前粒子的坐標信息，這樣即增加了粒子種群的多樣性也提高了尋優(yōu)的收斂速度.仿真結果表明，本算法不僅彌補了BA算法的缺陷，還對多峰函數的求解有更好的尋優(yōu)效果.從而驗證了反向學習機制的蝙蝠算法的有效性和可行性，進而擴展了他的應用領域.但是對于算法參數的優(yōu)化及其應用仍需深入的研究，如何設置自適應參數，提高蝙蝠算法的自適應性，這也是接下來將要進一步的工作.

[1] BISWAS A,BISWAS B.Swarm Intelligence Techniques and Their Adaptive Nature with Applications[M]// Complex System Modelling and Control Through Intelligent Soft Computations. Springer International Publishing,2015:253-273.

[2] Bahmani-Firouzi B, Azizipanah-Abarghooee R. Optimal sizing of battery energy storage for micro-grid operation management using a new improved bat algorithm[J]. International Journal of Electrical Power & Energy Systems, 2014, 56(3):42-54.

[3] MIRJALILI S,MIRJALILI S M,YANG X S.Binary bat algorithm[J].Neural Computing & Applications,2014,25(3/4):663-681.

[4] GANDOMI A H,YANG X S.Chaotic bat algorithm[J].Journal of Computational Science,2014,5(2):224-232.

[5] 李枝勇,馬良,張惠珍.蝙蝠算法收斂性分析[J].數學的實踐與認識,2013,43(12):182-190.

[6] 張宇楠,劉付永.一種改進的變步長自適應蝙蝠算法及其應用[J].廣西民族大學學報(自然科學版),2013,19(2):51-54，81.

[7] 尹進田,劉云連,劉麗,等.一種高效的混合蝙蝠算法[J].計算機工程與應用,2014,50(7):62-66.

[8] YANG X S,GANDOMI A H.Bat algorithm:a novel approach for global engineering optimization[J].Engineering Computations,2012,29(5):464-483.

[9] TSAI P W,PAN J S,LIAO B Y,et al.Bat Algorithm Inspired Algorithm for Solving Numerical Optimization Problems[J].Applied Mechanics & Materials,2011,148-149(148):134-137.

[10] NAKAMURA R Y M,PEREIRA A M,COSTA K A,et al.BBA:A Binary Bat Algorithm for Feature Selection[C]//Graphics,Patterns and Images (SIBGRAPI),2012 25th SIBGRAPI Conference on,IEEE,2012:291-297.

[11] AHANDANI M A,Alavi-Rad H. Opposition-based learning in the shuffled differential evolution algorithm[J].Soft Computing,2012,16(8):1303-1337.

[12] XU Q,WANG L,WANG N,et al.A review of opposition-based learning from 2005 to 2012[J].Engineering Applications of Artificial Intelligence,2014,29(3):1-12.

[13] WANG H,RAHNAMAYAN S,WU Z.Parallel differential evolution with self-adapting control parameters and generalized opposition-based learning for solving high-dimensional optimization problems[J].Journal of Parallel & Distributed Computing,2013,73(1):62-73.

[14] 汪慎文,丁立新,謝承旺,等.應用精英反向學習策略的混合差分演化算法[J].武漢大學學報(理學版),2013,59(2):111-116.

[15] 周新宇,吳志健,王暉,等.一種精英反向學習的粒子群優(yōu)化算法[J].電子學報,2013,41(8):1647-1652.

責任編輯：時 凌

Bat Algorithm Based on Opposition Learning Mechanism

YUE Weina，MA Jiming，SU Rijian，GUO Shengnan

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China)

Aiming at the problem that the firefly algorithm has slow convergence and low precision,an improved Bat algorithm based on opposition learning mechanism is proposed.The proposed algorithm is characterized by high precision and good robustness,and it can effectively jump out the local optimum.6 typical test functions are simulated and the results show that the algorithm is effective and feasible.What′s more,the algorithm also has excellent arithmetic performance in solving an optimization problem with multi-modal function.

bat algorithm；opposition learning；diversity；robustnes

2016-08-11.

國家自然科學基金項目(61374014)；河南省科技攻關項目(132102210056、142102210080).

岳偉娜(1989- )，女，碩士生,主要從事數據庫與信息集成、智能信息處理的研究.

1008-8423(2016)03-0251-05

10.13501/j.cnki.42-1569/n.2016.09.003

TP391.9

A