基于反向?qū)W習(xí)機(jī)制的蝙蝠算法

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

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

?

基于反向?qū)W習(xí)機(jī)制的蝙蝠算法

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

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

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

蝙蝠算法;反向?qū)W習(xí);多樣性;魯棒性

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

1 相關(guān)知識(shí)

1.1 原始蝙蝠算法

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

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

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

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

搜索脈沖頻率方程為：

(1)

其中：a為[0,1]范圍內(nèi)的隨機(jī)數(shù)，fi，fmax，fmin分別指當(dāng)前脈沖頻率，頻率最大值和最小值.

飛行速度方程為：

(2)

位置更新方程為：

(3)

隨機(jī)游走方程為：

(4)

脈沖響應(yīng)強(qiáng)度方程為：

(5)

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

(6)

1.2 反向?qū)W習(xí)機(jī)制

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

(7)

2 改進(jìn)的蝙蝠算法

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

本文在蝙蝠算法的基礎(chǔ)上，引入了反向?qū)W習(xí)機(jī)制來調(diào)節(jié)粒子的運(yùn)動(dòng)軌跡，這樣不僅有助于增加螢火蟲群體的多樣性和跳出局部最優(yōu)，且當(dāng)粒子在全局最優(yōu)附近時(shí)具有較好的收斂性.其主要作用在于當(dāng)粒子在進(jìn)行搜索時(shí)，在本種群及其反向種群中尋找最優(yōu)個(gè)體作為當(dāng)前的全局最優(yōu)，這樣不僅有助于跳出局部最優(yōu)，且當(dāng)粒子在全局最優(yōu)附近時(shí)得到較好的收斂性.

具有反向?qū)W習(xí)機(jī)制的BA算法(OL-BA)的具體步驟如下：

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

2)根據(jù)適應(yīng)度函數(shù)去確定蝙蝠群體中的最優(yōu)個(gè)體；

3)根據(jù)式(7)對(duì)種群進(jìn)行反向?qū)W習(xí)并代入適應(yīng)度函數(shù)進(jìn)行計(jì)算；

4)反向?qū)W習(xí)前后計(jì)算出的適應(yīng)度值進(jìn)行比較，取值較好的個(gè)體代替并加入種群中；

5)根據(jù)式(1)去設(shè)定每個(gè)蝙蝠個(gè)體的頻率；

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

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

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

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

10)當(dāng)?shù)螖?shù)未達(dá)到最大迭代次數(shù)，則返回步驟(2)繼續(xù)往下執(zhí)行，直到迭代結(jié)束，輸出結(jié)果為止.

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

3 仿真實(shí)驗(yàn)及分析

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

為了驗(yàn)證OL-BA的算法的性能，分別將BA算法，LF-BA算法和OL-BA算法用于6個(gè)典型的測(cè)試函數(shù)，并在MATLAB軟件中對(duì)各個(gè)算法運(yùn)行的結(jié)果進(jìn)行了測(cè)試和比較，這6個(gè)測(cè)試函數(shù)為：

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

[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].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(12):182-190.

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

[7] 尹進(jìn)田,劉云連,劉麗,等.一種高效的混合蝙蝠算法[J].計(jì)算機(jī)工程與應(yīng)用,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] 汪慎文,丁立新,謝承旺,等.應(yīng)用精英反向?qū)W習(xí)策略的混合差分演化算法[J].武漢大學(xué)學(xué)報(bào)(理學(xué)版),2013,59(2):111-116.

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

責(zé)任編輯：時(shí) 凌

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.

國家自然科學(xué)基金項(xiàng)目(61374014)；河南省科技攻關(guān)項(xiàng)目(132102210056、142102210080).

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

1008-8423(2016)03-0251-05

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

TP391.9

A