陳 思,賀興時,楊新社,2

(1.西安工程大學 理學院,陜西 西安 710048;2.密德薩斯大學 科學與技術學院,英國 倫敦 NW4 4BT)

基于時變慣性權重學習機制的蝙蝠優(yōu)化算法

陳 思1,賀興時1,楊新社1,2

(1.西安工程大學 理學院,陜西 西安 710048;2.密德薩斯大學 科學與技術學院,英國 倫敦 NW4 4BT)

為解決蝙蝠算法容易陷入局部最優(yōu)，過早進入停滯狀態(tài)等缺點,在蝙蝠算法更新模式中引入時變的慣性權重,給出3種不同的慣性權重學習機制,將蝙蝠算法進行改進,提高算法的開發(fā)和探索能力.通過數(shù)值仿真實驗,將3種不同學習機制下的改進蝙蝠算法與基本算法進行對比分析.結果表明,改進的蝙蝠算法具有較高的收斂精度和較強的全局搜索能力.

蝙蝠算法;時變慣性權重;收斂對比;學習機制

0 引 言

蝙蝠算法(bat algorithm,簡稱BA)是英國學者YANG Xinshe于2010年提出的一種基于蝙蝠回聲定位行為的新型啟發(fā)式算法[1].自提出以來,蝙蝠算法被廣泛應用于各類優(yōu)化問題.盛孟龍等提出一種改進的自適應變異蝙蝠算法[2],引入交叉變換的方式更新蝙蝠群體的位置;劉長平等提出基于Levy飛行特征的蝙蝠算法[3],采用Levy飛行搜索策略，更為真實地模擬蝙蝠的捕食行為,充分利用不均勻隨機游走的特性,有效避免了局部極值的吸引;賀興時等將模擬退火的思想引入BA算法中,同時對某些個體進行高斯擾動,提出了一種基于模擬退火的高斯擾動蝙蝠優(yōu)化算法[4];SELIM Yilmaz等人對算法更新模式進行改進,并將其應用于連續(xù)優(yōu)化問題[5]中.

在蝙蝠算法的應用方面,YANG將BA運用于多目標優(yōu)化[6]的工程設計;李枝勇等將遺傳變異蝙蝠算法應用0-1背包問題[7];GANDOMI等將BA運用于分類問題[8];MISHRA S等將BA運用于模糊聚類[9];KHAN K等將BA運用于預測問題[10]和神經(jīng)網(wǎng)絡[11].蝙蝠算法的收斂性證明方面,也少有文獻涉及.黃光球等構造了可全局收斂的蝙蝠算法[12],用于求解大規(guī)模優(yōu)化問題;李枝勇等定義了兩種新的蝙蝠算法的更新模式[13],分別對這兩種模式進行收斂性分析.丁文靜等在模擬退火的高斯擾動蝙蝠優(yōu)化算法的基礎上,探討了基于動態(tài)加權和向量估計的改進方法,并將改進后的蝙蝠算法應用于多目標優(yōu)化[14];肖輝輝等提出一種基于差分進化算法的改進蝙蝠算法[15],并將其應用于求解數(shù)值積分問題;盛曉華等利用對蝙蝠算法重新編碼以及初始化的方式來求解離散型生產(chǎn)調(diào)度問題[16];張勇凱等對蝙蝠算法進行混沌序列初始化和自適應變步長的改進[17],運用于云制造平臺中,效果較好;于泉等提出蝙蝠-擬牛頓混合算法[18],將其成功應用于無線傳感器網(wǎng)絡節(jié)點定位.然而,基本的蝙蝠算法存在容易陷入局部最優(yōu)，過早進入停滯狀態(tài)等問題.為了更好地控制蝙蝠算法的開發(fā)和探索能力,解決基本蝙蝠算法的缺點,文中在蝙蝠算法更新模式中引入時變的慣性權重,給出3種不同的慣性權重學習機制,將蝙蝠算法進行改進.通過數(shù)值仿真實驗,將3種不同學習機制下的改進蝙蝠算法與基本算法進行對比分析.

1 基本蝙蝠算法

蝙蝠在捕獵時,利用聲吶探測獵物、避免障礙物,這些行為都依賴于回聲定位的聲學原理.BA便是受啟于蝙蝠的生物行為,從而得出的一種基于種群的隨機全局優(yōu)化技術.蝙蝠通過發(fā)出聲音脈沖,然后根據(jù)其回聲定位器接收到的回聲來探測獵物的位置,繞開障礙物,在黑暗中棲息.蝙蝠發(fā)出聲音的響度范圍從搜索獵物時的最高響度到靠近獵物時的靜音.蝙蝠個體通過發(fā)出和接收回聲的時間差,判斷目標的距離、方位.

fi=fmin+(fmax-fmin)β ,

(1)

(2)

(3)

式中，fi,fmax,fmin分別表示第i只蝙蝠當前時刻發(fā)出的聲波頻率以及聲波頻率的最大值和最小值；w表示速度更新中的慣性權重；β∈[0,1]為一個隨機向量；p表示當前最優(yōu)位置.開始時每只蝙蝠隨機分配頻率,頻率從[fmin,fmax]隨機得出.

2 改進學習機制的蝙蝠算法

2.1 時變慣性權重

慣性權重w作為蝙蝠算法中為數(shù)不多的參數(shù)之一,有著很重要的作用,慣性權重的大小決定了對前一個蝙蝠個體速度繼承的多少.一般地,慣性權重主要有固定權重和時變權重兩種選擇.固定權重是在算法迭代過程中,固定地選擇某一個常數(shù)作為權重值,在整個優(yōu)化過程中不做變動.時變權重是隨著迭代次數(shù)的增加,慣性權重取值也不斷變化.在整個迭代過程中按照某種遞減率減小,從而呈現(xiàn)出不同的取值情況.較大的慣性權重將使蝙蝠個體具有較大的速度,從而增強了蝙蝠的探索能力;較小的慣性權重將使蝙蝠個體具有較強的開發(fā)能力.因此,算法的優(yōu)化效果很大程度上取決于慣性權重的選取,并且時變的慣性權重更有利于增加算法多樣性,提高搜索能力和探索能力．文中提出3種不同方案的遞減性時變慣性權重學習機制,即

(4)

式中，w1,w2,w3分別表示方案1,2,3的時變慣性權重表達式;wmax,wmin分別表示慣性權重的最大、最小值,根據(jù)已有的數(shù)值實驗發(fā)現(xiàn),當其分別取值為0.9，0.4時,算法收斂效果較好;Tmax為最大迭代次數(shù),k為當前迭代次數(shù).易知,這3種學習機制中的慣性權重均是隨著迭代次數(shù)的增加按照某種遞減率逐次減小的,衰減曲線如圖1所示.其中,方案1中時變權重w1的衰減性態(tài)為簡單的一次函數(shù),方案2中時變權重w2的衰減性態(tài)為二次函數(shù),方案3中時變權重w3的衰減性態(tài)為指數(shù)函數(shù).

2.2 改進學習機制的蝙蝠算法

根據(jù)提出的3種不同的遞減性慣性權重學習機制,基本蝙蝠算法的速度更新公式得到改進,即

方案1:

(5)

從式(5)可以看出,時變慣性權重w1是以當前迭代次數(shù)k為變量,呈現(xiàn)出簡單一次線性的衰減性態(tài).

方案2:

(6)

從式(6)中可以看出,時變慣性權重w2的衰減性態(tài)是以迭代次數(shù)為變量的二次函數(shù)形式,衰減后的最小值比w1大得多,也就是方案2的慣性權重取值對速度有著更大的繼承.

方案3:

(7)

從式(7)可以看出,時變慣性權重w3的衰減性態(tài)是以迭代次數(shù)為變量的指數(shù)函數(shù)形式,其衰減速率比w1緩慢得多,迭代1 000次后的取值與w2相近.

3 仿真實驗

為驗證本文提出的3種具有不同衰減性態(tài)的時變慣性權重學習機制的蝙蝠算法性能,選取4個標準測試函數(shù)進行仿真測試,并與基本進行對比.

3.1 參數(shù)設置

蝙蝠算法中涉及的參數(shù)較少,參數(shù)的選取目前尚無確切的理論依據(jù),本文所選擇的參數(shù)值是由反復實驗獲得的經(jīng)驗值確定.其中,基本的慣性權重w=0.5,改進算法wmax=0.9,wmin=0.4,算法最大搜索次數(shù)均為Tmax=1000,群體數(shù)D=30.

3.2 測試函數(shù)

4種測試函數(shù)如表1所示.測試函數(shù)均是非線性函數(shù),可以有效地檢驗算法的探索、開發(fā)性能.其中,g1函數(shù)是典型的單模態(tài)函數(shù);g2函數(shù)是多峰的,它的局部最優(yōu)值隨著維數(shù)的升高而增加,能夠獨立地優(yōu)化各變量,有眾多局部極值且多個極小值呈規(guī)律分布;g3函數(shù)由于自身特性，致使算法極易陷于局部極值，是測試算法收斂性能的經(jīng)典函數(shù)；g4函數(shù)具有非常粗糙的適應度表面,很容易誘導進入非真的全局最優(yōu)解,從而陷入局部極值中,是測試算法全局收斂性能的極佳函數(shù).

表 1 標準測試函數(shù)

3.3 結果及分析

仿真實驗規(guī)定,當測試中實際的尋優(yōu)值與理論最優(yōu)值的相對誤差小于1%時,視為找到最優(yōu)解,規(guī)定每種算法獨立運行10次.圖2為3種時變慣性權重改進后的蝙蝠算法與基本蝙蝠算法的收斂曲線對比圖,形象地展示了改進前后的蝙蝠算法適應度值的迭代下降過程.

從圖2(a),(b)可以看出,在測試函數(shù)g1的仿真實驗中,方案1,2改進后的蝙蝠算法相對于基本算法的性能均有所提升,收斂的迭代次數(shù)基本持平于150次,并且在前100次的迭代過程中收斂精度和收斂速度都優(yōu)于基本蝙蝠算法.從圖2(c)中可以看出,在對測試函數(shù)g1的仿真實驗中,方案3改進蝙蝠算法的收斂性能比基本算法提升很多,收斂速度明顯加快,基本蝙蝠算法在200次迭代后才收斂,引入時變慣性權重的改進算法達到最優(yōu)值所需的迭代次數(shù)明顯減少.

從圖3(a),(b)中可以看出,在測試函數(shù)g2的仿真實驗中,前兩種衰減性態(tài)的時變慣性權重改進的蝙蝠算法在收斂速度方面,作用類似,但均比基本算法表現(xiàn)更優(yōu);同時,對測試函數(shù)g2來說,方案2改進的算法達到收斂所需的迭代次數(shù)較方案1有所減少；從圖3(c)中可以看出，方案3改進的算法收斂性略差于方案1和方案2，迭代次數(shù)較方案2有所增加.

從圖4(a)～(c)可以看出,在測試函數(shù)g3的仿真實驗中,方案1和方案3改進后的蝙蝠算法性能得到有效的改善.基本蝙蝠算法收斂需要的迭代次數(shù)幾乎均達到實驗允許的最大值1 000次,而改進后的算法則明顯尋優(yōu)能力更強,算法收斂到最優(yōu)值所需要的迭代次數(shù)明顯減少,收斂速度提高.從圖4(b)可以看出,方案2改進后的蝙蝠算法性能和方案1,方案3比較并不突出,但是,算法性能得到提升,在迭代進行到400次時就達到最優(yōu)解,而基本蝙蝠算法則是在進行到800次時才取到最優(yōu)解.

從圖5(a),(b)可以看出,在測試函數(shù)g4的仿真實驗中,對方案1,雖然當?shù)螖?shù)小于100次時,基本蝙蝠算法表現(xiàn)更優(yōu),但是基本蝙蝠算法陷入了局部極值,且最終沒有跳出,方案1改進的蝙蝠算法收斂速度和收斂精度均高于基本算法.對方案2,在200次迭代之前基本蝙蝠算法的收斂速度快于改進后的算法,但是同樣地在后來的測試過程中基本蝙蝠算法不可避免地陷入了局部極值,沒有收斂到最優(yōu)解.而方案2改進后的算法在很大程度上提升了算法性能,收斂精度較高.從圖5(c)可以看出,在對測試函數(shù)g4的仿真實驗中,方案3改進的蝙蝠算法雖然在收斂速度方面優(yōu)勢并不明顯,但它在收斂精度和避免進入局部極值方面均有所改善,比基本蝙蝠算法表現(xiàn)更優(yōu).

縱觀所有的收斂曲線對比圖,可以發(fā)現(xiàn),引入時變慣性權重的改進蝙蝠算法均比基本算法的性能好,在一定程度上提高了算法的收斂速度和收斂精度,在避免進入局部極值方面也比基本算法表現(xiàn)更優(yōu).而且對于不同的測試函數(shù),3種不同衰減性態(tài)的時變慣性權重方案對算法收斂性態(tài)有著不同的影響,方案1和方案2的改進效果較為相似.在各個測試函數(shù)仿真實驗后的收斂速度和收斂精度方面,方案3的改進效果都優(yōu)于方案1，2,并且在慣性權重衰減的過程中,當權重值遞減到0.4～0.5時,算法的改進效果最優(yōu);如果繼續(xù)遞減,改進效果則下降,而方案3中慣性權重最終在這個范圍內(nèi),因此可以認定這3種不同的衰減性態(tài)中,方案3的效果最好.

為了進一步測試方案3改進后的BA性能,將其與另外2種時變慣性權重方案進行對比性的仿真實驗.實驗結果表明,本文提出的改進方案效果更優(yōu).其中,進行仿真實驗對比的2種改進方案如下.

方案4:

(8)

方案4的改進方法來自于文獻[19],分別通過4個測試函數(shù)將其進行對比仿真,即將方案3和方案4分別用于4種測試函數(shù),得到的對比結果如圖6所示.

從圖6可以看出,在選用的4個不同的測試函數(shù)下,方案3改進后的BA算法在收斂速度和收斂精度上均比文獻[19]中提出的改進方案要好.

方案5:

(9)

方案5的改進方法來自于文獻[20],同樣地,分別通過4個測試函數(shù)將兩種方案進行對比仿真實驗,得到的對比結果如圖7所示.

從圖7可以看出,方案3改進的BA算法比文獻[20]中提出的改進方案效果要好,在算法的收斂速度和收斂精度方面,方案3均表現(xiàn)更優(yōu).文中提出的改進方案是切實有效的.

4 結束語

本文在基本蝙蝠優(yōu)化算法的理論基礎上,引入了時變的慣性權重,用3種不同衰減性態(tài)的權重模式將蝙蝠算法進行改進,并通過標準測試函數(shù)進行仿真實驗.結果表明,3種方案改進后的蝙蝠算法均有效改善了算法性能,增強了收斂速度和精度,蝙蝠個體的尋優(yōu)能力得到了提升.

蝙蝠算法自提出以來,被廣泛應用到各類優(yōu)化問題,為了提升基本蝙蝠算法性能,使其能夠更好地解決各類問題,學者們對蝙蝠算法的研究不斷深入.算法收斂性方面的解析則是改進算法很重要的突破口,然而這方面的研究卻并不詳盡.在未來的研究中,會在蝙蝠算法的收斂性、魯棒性等方向做更深入的探索.

[1] YANG Xinshe.A new met heuristic bat-inspired algorithm[C]//Nature Inspired Cooperative Strategies for Optimization,Berlin:Springer-Verlay,2010:65-74.

[2] 盛孟龍,賀興時,丁文靜.蝙蝠算法的全局收斂性分析[J].紡織高校基礎科學學報,2013,26(4):543-547.

SHENG Menglong,HE Xingshi,DING Wenjing.Analysis of bat algorithm′s global convergence[J].Basic Sciences Journal of Textile Universities,2013,26(4):543-547.

[3] 劉長平,葉春明.具有Levy飛行特征的蝙蝠算法[J].智能系統(tǒng)學報,2013,8(3):240-246.

LIU Changping,YE Chunming.Bat algorithm with the characteristics of Levy flights[J].CAAI Transactions on Intelligent Systems,2013,8(3):240-246.

[4] HE Xingshi,DING Wenjing,YANG Xinshe.Bat algorithm based on simulated annealing and gaussion perturbations[J].Neural Computing and Applications,2014,25(2):459-468.

[5] YILMAZ Selim,KUCUKSILLE Ecir.Improved bat algorithm (IBA) on continuous optimization problems[J].Lecture Notes on Software Engineering,2013,1(3):279-283.

[6] YANG Xinshe.Bat algorithm for multiobjective optimization[J].International Journal Bio-Inspired Computation,2011,3(5):267-274.

[7] 李枝勇,馬良,張惠珍.蝙蝠算法在多目標多選擇背包問題中的應用[J].計算機仿真,2013,30(10):350-353.

LI Zhiyong,MA Liang,ZHANG Huizhen.Application of bat algorithm in multi-objective and multi-choice knapsack problem[J].Computer Simulation,2013,30(10):350-353.

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

[9] MISHRA S,SHAW K,MISHRA D.A new metaheuristic classification approach for microarray data[J].Procedia Technology,2012,4(1):802-806.

[10] KHAN K,NIKOV A,SAHAI A.A fuzzy bat clusterig method for ergonomic screening of office workplaces,S3T 2011[C]//Advances in Intelligent and Soft Computing,Berlin:Springer,2011:59-66.

[11] KHAN K,SAHAI A.A comparison of BA,GA,PSO,BP and LM for training feed forward neural networks in e-learning context [J].International Journal of Intelligent Systems and Applications,2012,4(7):23-29.

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

HUANG Guangqiu,ZHAO Weijuan,LU Qiuqin.Bat algorithm with global convergence for solving large-scale optimization problem[J].Application Research of Computers,2013,30(5):1323-1328.

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

LI Zhiyong,MA Liang, ZHANG Huizhen.Convergence analysis of bat algorithm[J].Mathematics in Practice and Theory,2013,43(12):182-190.

[14] 丁文靜,賀興時,楊新社,等.改進蝙蝠算法在多目標優(yōu)化中的應用[J].紡織高?；A科學學報,2013,26(4):538-542.

DING Wenjing,HE Xingshi,YANG Xinshe,et al.The application of the improved bats algorithm in multi-objective optimization[J].Basic Sciences Journal of Textile Universities,2013,26(4):538-542.

[15] 肖輝輝,段艷明.改進的蝙蝠算法在數(shù)值積分中的應用研究[J].智能系統(tǒng)學報,2014,9(3):364-371.

XIAO Huihui,DUAN Yanming.Application of the improved bat algorithm in numerical integration[J].CAAL Transactions on Intelligence Systems,2014,9(3):364-371.

[16] 盛曉華,葉春明.蝙蝠算法在PFSP調(diào)度問題中的應用研究[J].工業(yè)工程,2013,16(1):119-124.

SHENG Xiaohua,YE Chunming.Application of bat algorithm to permutation flow-shop scheduling problem[J].Industrial Engineering Journal,2013,16(1):119-124.

[17] 張勇凱,李芳,包曉曉.改進蝙蝠算法在云制造供應鏈中的應用[J].數(shù)學理論與應用,2015,35(2):83-94.

ZHANG Yongkai,LI Fang,BAO Xiaoxiao.Application of an improved bat algorithm in cloud manufacturing supply chains[J].Mathmatical Theory and Applications,2015,35(2):83-94.

[18] 于泉,孫順遠,徐保國,等.基于蝙蝠-擬牛頓混合算法的無線傳感器網(wǎng)絡節(jié)點定位[J].計算機應用,2015,35(5):1238-1241.

YU Quan,SUN Shunyuan,XU Baoguo,et al.Node localization of wireless sensor networks based on hybrid bat-quasi-Newton algorithm[J].Journal of Computer Applications,2015,35(5):1238-1241.

[19] 周宗渠,田大鋼.改進蝙蝠算法求解置換流水線車間調(diào)度問題[J].信息技術,2015,37(5):140-143.

ZHOU Zongqu,TIAN Dagang.Improved bat algorithm for permutation flow-shop scheduling problem[J].Information Tecnology,2015,37(5):140-143.

[20] 范彬,周力行,黃頔,等.基于改進蝙蝠算法的配電網(wǎng)分布式電源規(guī)劃[J].電力建設,2015,36(3):123-128.

FAN Bin,ZHOU Lixing,HUANG di,et al.Distributed generation planning for distribution network based on modified bat algorithm[J].Electric Power Construction,2015,36(3):123-128.

編輯:武 暉；校對：趙 放

Optimized bat algorithm based on learning mechanism of variable inertia weight

CHENSi1,HEXingshi1,YANGXinshe1,2

(1.School of Science, Xi′an Polytechnic University, Xi′an 710048, China;2.School of Science & Technology, Middlesex University, London NW4 4BT, UK)

In order to solve shortcoming of being easy to fall into local optimum and premature, the time-varying inertia weights is introduced to the update mode of bat algorithm, and three different learning mechanisms of the inertia weight are given. The bat algorithm is improved in aspects of capabilities of development and exploration. By numerical simulation, the improved bat algorithm in three different learning mechanisms were comparative analyzed with basic algorithm. The results show that the improved bat algorithm has higher convergence and stronger global search capability.

bat algorithm; time-varying inertia weight; convergence contrast; learning mechanism

1006-8341(2016)04-0555-08

10.13338/j.issn.1006-8341.2016.04.024

2016-08-11

陜西省教育廳自然科學基金資助項目(2014JM1006);西安市基礎教育研究重大招標項目(2015ZB-ZY04)

賀興時(1960—),男,陜西省富平縣人,西安工程大學教授,研究方向為智能優(yōu)化算法、數(shù)理統(tǒng)計、數(shù)據(jù)挖掘等.E-mail:chen1991si@126.com

陳思,賀興時,楊新社.基于時變慣性權重學習機制的蝙蝠優(yōu)化算法[J].紡織高校基礎科學學報,2016,29(4)：555-562.

CHEN Si,HE Xingshi,YANG Xinshe.Optimized bat algorithm based on learning mechanism of variable inertia weight[J].Basic Sciences Journal of Textile Universities,2016,29(4):555-562.

TP 301.6

A