胡 飛, 孫自強

(華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237)

一種基于椋鳥群行為的改進型蝙蝠算法

胡 飛, 孫自強

(華東理工大學化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237)

蝙蝠算法是一種新興的元啟發(fā)式算法,基本蝙蝠算法(BA)存在尋優(yōu)精度低、易陷入局部最優(yōu)等缺點。將椋鳥群的集體性行為引入到基本蝙蝠算法中,有效地提高了算法的搜索范圍;引入線性遞減權(quán)重,用于平衡全局搜索和局部搜索。通過一些測試函數(shù)對該算法進行仿真研究,結(jié)果表明改進的蝙蝠算法有效地避免了種群個體陷入局部最優(yōu),提高了算法的尋優(yōu)精度,優(yōu)化效果得到改善。

蝙蝠算法(BA); 椋鳥群行為; 權(quán)重; 局部最優(yōu)

蝙蝠算法是一種新興的元啟發(fā)優(yōu)化算法,該算法可以看作是和聲搜索算法和粒子群算法的混合[1]。目前,已有許多經(jīng)典的優(yōu)化算法應(yīng)用于諸多方面。文獻[2]將一種改進的混沌蜂群算法應(yīng)用于流水車間調(diào)度,優(yōu)化調(diào)度過程中的最大完成時間,優(yōu)化效果較好。文獻[3]針對化工過程的動態(tài)多目標問題,利用一種改進型粒子群算法對其進行優(yōu)化,測試結(jié)果表明該算法能較好地解決工程問題。蝙蝠算法作為新興的優(yōu)化算法,同樣具有較好的應(yīng)用前景,已經(jīng)廣泛應(yīng)用于工程和自然科學領(lǐng)域,如函數(shù)優(yōu)化問題、生產(chǎn)調(diào)度問題以及多目標優(yōu)化問題等。文獻[4]將蝙蝠算法應(yīng)用于一些工程函數(shù)尋優(yōu),結(jié)果表明該算法尋優(yōu)精度較高。文獻[5]將蝙蝠算法應(yīng)用于混合流水車間調(diào)度問題,能夠最小化車間調(diào)度的完工時間。文獻[6]針對多目標優(yōu)化問題提出了一種多目標蝙蝠算法,應(yīng)用于一些多目標函數(shù)優(yōu)化,尋優(yōu)效果較佳。然而蝙蝠算法亦具有粒子群等優(yōu)化算法的通病,即收斂速度慢、容易陷入局部最優(yōu)、搜索精度較低。為了提高蝙蝠算法的控制效果,許多研究者對蝙蝠算法開展研究,并對其進行改進。劉長平等[7]提出基于Lévy飛行特征的蝙蝠算法,從算法仿生原理入手,采用Lévy飛行搜索策略,更真實地模擬蝙蝠的捕食行為。Topal 等[8]提出一種動態(tài)虛擬蝙蝠算法,將蝙蝠種群分成探索類和開拓類子種群,當探索類蝙蝠進行對外搜索最優(yōu)值時,開拓類蝙蝠進行局部搜索,尋找最優(yōu)值。李枝勇等[9]將量子計算引入到蝙蝠算法中,利用量子位對蝙蝠的位置進行編碼,利用量子旋轉(zhuǎn)門進行蝙蝠最優(yōu)位置的搜索。Gandomi 等[10]提出具有混沌搜索策略的蝙蝠算法,并利用不同的混沌函數(shù)產(chǎn)生的混沌序列對精英個體進行混沌優(yōu)化,驗證了混沌策略的有效性。Niknam 等[11]提出了一種自適應(yīng)蝙蝠算法,將自適應(yīng)方法與蝙蝠算法結(jié)合,提高算法的種群多樣性及搜索能力,并應(yīng)用于電力系統(tǒng)中UC問題,能夠快速解決UC問題。Wang等[12]提出將差分進化算法與蝙蝠算法相結(jié)合,并用于解決UCVA三維路徑規(guī)劃問題,結(jié)果表明控制效果較好。

當前針對蝙蝠算法的改進主要有兩個方面:(1)針對蝙蝠算法自身機理存在的變量進行改進,包括參數(shù)自適應(yīng)、輔助參數(shù)的引入以及搜索策略等;(2)將其他的優(yōu)化算法與蝙蝠算法相結(jié)合,提高基本蝙蝠算法的控制效果[13]。本文提出的改進策略屬于第1種,將椋鳥群行為引入到蝙蝠算法中,當全局最優(yōu)值陷入局部最優(yōu)時,根據(jù)椋鳥群的集體性行為對蝙蝠的位置和速度進行更新。

1 基本蝙蝠算法

1.1基本蝙蝠算法的位置和速度更新

將蝙蝠類比為在當前可行域內(nèi)分布的搜索點,用目標函數(shù)值(適應(yīng)度函數(shù)值)的大小來判斷當前蝙蝠所處位置的優(yōu)劣;將蝙蝠飛行移動探測目標的過程類比為搜索目標函數(shù)位置最優(yōu)解的過程,則可用以下流程和公式來模擬蝙蝠回聲定位的行為[14]。初始時刻,需對蝙蝠的頻率進行初始化,同時,蝙蝠在飛行過程中也需對其速度和位置進行更新,兩者的更新公式如式(1)～ 式(3)所示。

(1)

(2)

(3)

在搜索過程中還需進行局部搜索,公式如下:

(4)

其中:xnew為蝙蝠更新后的位置;xold為蝙蝠更新前的位置;ε∈[-1,1]為隨機數(shù);At為整個蝙蝠種群在t時刻的平均響度。

1.2響度和脈沖發(fā)射率

在蝙蝠搜尋目標獵物時,需對響度Ai和脈沖發(fā)射率ri進行更新。初始階段,Ai較大,ri較小,搜尋到目標獵物后,Ai減小,ri增大[15]。Ai和ri更新公式如下:

(5)

(6)

2 改進的蝙蝠算法

2.1椋鳥群行為

椋鳥是一種群體性種群,在日常生活中會產(chǎn)生一些壯觀的景象。當遇到天敵時,其中一些個體會改變飛行方向,并影響周圍個體,如此使得整個種群方向迅速改變,從而躲避天敵的捕食。

由于每個個體都會與周圍的個體交流信息,因此由該個體發(fā)出的信息會很快傳播至整個種群,這種行為稱為椋鳥群行為。在椋鳥群中,椋鳥個體一般與其附近的7個個體進行信息交流,這7個個體再分別與其附近的7個個體進行信息交流,進而遍布整個種群,達到整個種群的信息共享。一項分析表明,6個或7個個體組成一個群體交流網(wǎng)絡(luò)將有效平衡整個種群凝聚性及個體交流,因此個體與其附近的7個個體進行信息交流足以影響整個種群的行為[16]。

2.2引入椋鳥群行為的蝙蝠算法[17](SFBA)

基本蝙蝠算法在搜索過程中易陷入局部最優(yōu),缺乏種群多樣性。將椋鳥群行為引入基本蝙蝠算法中,有助于增加種群多樣性,避免陷入局部最優(yōu)。當種群迭代結(jié)果發(fā)生停滯或更差超過上限值(count_limit)時,挑選出一定數(shù)目(max_num)適應(yīng)度值較差的個體,對這些個體的位置和速度進行變換,挑選出全局最優(yōu)值,替換原先的種群全局最優(yōu)值。

針對位置變換,依據(jù)式(7)對粒子i的位置進行更新。

(7)

針對速度變換,依據(jù)式(8)對粒子i的速度進行更新。

(8)

2.3針對位置和速度引入權(quán)重

由于固定的慣性權(quán)重控制精度不高,控制效果較差,本文針對蝙蝠算法速度和位置更新公式,分別引入權(quán)重w1和w2,見式(9)和式(10)。將權(quán)重w1由固定權(quán)重變?yōu)榫€性遞減權(quán)重。起初權(quán)重較大,加強全局搜索,隨著迭代次數(shù)的增加,迭代后期,權(quán)重減小,有利于提高局部搜索能力。線性遞減的權(quán)重公式如下:

(9)

(10)

(11)

其中:wmax為w1的上限值;wmin為w1的下限值;Iter為當前迭代次數(shù);Iter_max為最大迭代次數(shù)。

2.4SFBA算法流程

(2) 對所有蝙蝠個體計算適應(yīng)度函數(shù)值f(x),找出當前位置最優(yōu)解x*。

(3) 按照式(1)隨機產(chǎn)生頻率的新解。

(4) 根據(jù)式(9)和式(10)對蝙蝠的速度和位置進行更新,針對速度設(shè)置的權(quán)重w1使用線性遞減權(quán)重,見式(11)。

(5) 產(chǎn)生一個隨機值rand,若rand大于脈沖發(fā)射率ri,則根據(jù)式(4),從處在最佳位置的蝙蝠i個體中選取一個解,對該位置最優(yōu)解進行隨機擾動,產(chǎn)生一個局部解xnew替代蝙蝠i的當前位置。

(6) 計算適應(yīng)度函數(shù)值(目標函數(shù)值);

(7) 若隨機值rand小于響度Ai且更新位置后的目標函數(shù)值小于當前目標函數(shù)最優(yōu)值,則接受這個位置新解,并增大脈沖發(fā)射率ri和響度Ai,見式(5)、式(6)。

(8) 對位置變動后的蝙蝠重新排列,找出當前位置最優(yōu)解和適應(yīng)度函數(shù)最優(yōu)值。

(9) 判斷當前適應(yīng)度最優(yōu)值是否大于或等于上一代適應(yīng)度最優(yōu)值,若是,則計數(shù)器count+1(count初始值設(shè)為0)。

(10) 判斷count是否大于上限值count_limit,若是,則挑選出適應(yīng)度較差的max_num個個體,利用式(7)與式(8)更新該部分個體位置和速度值,替換原先個體最優(yōu)值,并從中找出全局最優(yōu)值,作為當前種群全局最優(yōu)值,并置count=0。

(11) 當?shù)螖?shù)小于最大迭代次數(shù)時,回到步驟(2)繼續(xù)迭代搜索最優(yōu)解。

(12) 算法迭代結(jié)束,輸出位置全局最優(yōu)解。

3 算法的參數(shù)選擇

SFBA算法參數(shù)主要包含w1,w2,count_limit,max_num,其中w1主要由wmax和wmin決定,因此需要選擇的參數(shù)主要為wmax,wmin,w2,count_limit,max_num,這5個參數(shù)可以通過實驗確定。以Sphere函數(shù)為基準進行實驗,種群規(guī)模設(shè)為100,迭代次數(shù)Iter_max為500次,分別運行20次,取20次優(yōu)化結(jié)果的平均值作為參考值,確定權(quán)值wmax,wmin以及w2的最優(yōu)值。

表1示出了wmax為0.45、0.46、0.47、0.48、0.49、0.50、0.51、0.52、0.53、0.54、0.55,wmin=0.1,w2=0.50時的運行結(jié)果,可以看出,wmax=0.50時算法控制效果較好。

表2示出了wmin為0.05、0.06、0.07、0.08、0.09、0.10、0.11、0.12、0.13、0.14、0.15,wmax=0.50,w2=0.50時的運行結(jié)果,可以看出,wmin=0.10時算法控制效果較好。

表3示出了w2為0.45、0.46、0.47、0.48、0.49、0.50、0.51、0.52、0.53、0.54、0.55,wmax=0.50,wmin=0.10時的運行結(jié)果,可以看出,w2=0.50時算法控制效果較好。

表1 wmax參數(shù)取值表Table 1 Parameter value table of wmax

表2 wmin參數(shù)取值表Table 2 Parameter value table of wmin

表3 w2參數(shù)取值表Table 3 Parameter value table of w2

表4示出了count_limit為1、2、3、4、5時的運行結(jié)果,可以看出,count_limit=3時算法控制效果較好。

表5示出了max_num為13、17、19、22、23時的運行結(jié)果,可以看出,max_num=19時算法控制效果較好。

表4 count_limit參數(shù)取值表Table 4 Parameter value table of count_limit

表5 max_num參數(shù)取值表Table 5 Parameter value table of max_num

綜上所述,對于改進型蝙蝠算法,取wmax=0.50,wmin=0.10,w2=0.50,count_limit=3,max_num=19,采用這組參數(shù)進行算法測試,可以進一步驗證改進型蝙蝠算法的可行性。

4 測試結(jié)果

為了評估本文提出的改進型蝙蝠算法的尋優(yōu)效果,選擇5個標準測試函數(shù)(如表6所示)進行測試。

表6 標準測試函數(shù)Table 6 Benchmark functions

表7 標準測試函數(shù)尋優(yōu)結(jié)果對比Table 7 Comparison of Benchmark functions optimization results

測試函數(shù)f1,f2,f3均為多峰值測試函數(shù),BA尋優(yōu)精度較低,控制效果較差,而SFBA均能取得較高的尋優(yōu)精度,控制效果較好。測試函數(shù)f4是一種典型的病態(tài)非凸單模函數(shù),難以極小化,從表7中數(shù)據(jù)可以看出BA和SFBA尋優(yōu)效果均不理想。測試函數(shù)f5為簡單的單峰值函數(shù),在自變量取值范圍內(nèi)僅有一個全局極小值點,因而BA的尋優(yōu)效果還可以,但是相比之下,SFBA的尋優(yōu)精度更高,控制效果更好。限于篇幅,本文僅給出部分維度的尋優(yōu)效果,測試函數(shù)迭代曲線對比如圖1～圖5所示。

圖1 測試函數(shù)f1迭代曲線對比(d=20)Fig.1 Comparison of Benchmark functionf1′s iterative curves (d=20)

圖2 測試函數(shù)f2迭代曲線對比(d=20)Fig.2 Comparison of Benchmark functionf2′s iterative curves (d=20)

為了進一步驗證本文算法的可行性,將SFBA與文獻[18]基于微分算子與Lévy飛行策略的蝙蝠算法(DLBA)及文獻[19]基于遺傳交叉因子的蝙蝠算法(GHBA)進行對比,結(jié)果如表8所示。從表8中數(shù)據(jù)可知,SFBA的尋優(yōu)效果優(yōu)于GHBA、DLBA。

圖3 測試函數(shù)f3迭代曲線對比(d=10)Fig.3 Comparison of Benchmark functionf3′s iterative curves (d=10)

圖4 測試函數(shù)f4迭代曲線對比(d=10)Fig.4 Comparison of Benchmark functionf4′s iterative curves (d=10)

圖5 測試函數(shù)f5迭代曲線對比(d=10)Fig.5 Comparison of Benchmark functionf5′s iterative curves (d=10)表8 改進的BA算法在5個測試函數(shù)尋優(yōu)結(jié)果對比Table 8 Comparison of improved BA algorithms in 5 Benchmark function optimization results

函數(shù)SFBAGHBADLBA最優(yōu)值平均值最優(yōu)值平均值最優(yōu)值平均值f12.8040×10-121.1585×10-91.31×10-73.41×10-24.7174×10-76.4097×10-6f2003.65×10-71.41×10-51.3818×10-75.0103×10-6f300005.9998×10-84.4705×10-6f41.8935×101.8991×107.64×10-51.515.66727.3903f54.2686×10-222.7087×10-188.08×10-195.65×10-184.3057×10-84.8036×10-6

5 改進型蝙蝠算法在PID參數(shù)整定中的應(yīng)用

為了進一步驗證本文算法的有效性,將改進型蝙蝠算法應(yīng)用于PID控制器參數(shù)優(yōu)化中[20]。選取二階被控對象,傳遞函數(shù)如下:

(12)

采樣時間為2 ms,輸入一個階躍信號,采用誤差絕對值時間積分性能指標作為參數(shù)選擇的最小目標函數(shù),為防止能量過大,在目標函數(shù)中加入控制輸入平方項,最優(yōu)指標如式(13)所示。

(13)

式中:J表示目標函數(shù);e(t)表示系統(tǒng)誤差;u(t)為控制器輸出;tu為上升時間;w1,w2,w3為權(quán)重值。

為避免超調(diào),采取懲罰功能,一旦出現(xiàn)超調(diào),就將超調(diào)量作為最優(yōu)指標中的一項,此時最優(yōu)指標如式(14)所示。

ifey(t)<0

(14)

其中:w4為權(quán)重值,且w4>>w1;ey(t)=y(t)-y(t-1),y(t)為被控對象輸出。

SFBA算法中,種群數(shù)為100,wmax=0.50,wmin=0.10,w2=0.5,count_limit=3,max_num=19,PID參數(shù)Kp,Ki,Kd取值范圍分別為[0,40],[0,4],[0,4],取w1=0.999,w2=0.001,w3=100,w4=2.0。迭代100次后,用BA算法優(yōu)化PID三參數(shù)優(yōu)化后Kp=31.711 6,Ki=3.354 7,Kd=0.147 2,性能指標J=79.189 6,適應(yīng)度函數(shù)J、Kp、Ki、Kd的優(yōu)化過程如圖6所示。用SFBA算法優(yōu)化PID三參數(shù)優(yōu)化后Kp=35.053 4,Ki=3.527 6,Kd=0.003 1,性能指標J=78.352 7,適應(yīng)度函數(shù)J,Kp,Ki,Kd的優(yōu)化過程如圖7所示。BA和SFBA算法優(yōu)化后,PID控制階躍響應(yīng)如圖8所示。

由圖8可知,SFBA算法優(yōu)化效果優(yōu)于BA算法,SFBA基本無超調(diào),調(diào)節(jié)時間較短,響應(yīng)速度較快。

圖6 BA算法迭代曲線Fig.6 Iterative curves of BA algorithm

圖7 SFBA算法的迭代曲線Fig.7 Iterative curves of SFBA algorithm

圖8 BA算法與SFBA算法的階躍響應(yīng)曲線Fig.8 Unit-step response of BA algorithm and SFBA algorithm

6 結(jié) 論

本文針對BA算法收斂速度慢、容易陷入局部最優(yōu)、搜索精度不高等缺點,提出了一種基于椋鳥群行為的蝙蝠算法(SFBA),同時引入線性遞減權(quán)重平衡全局搜索與局部搜索。通過5個不同的單峰值和多峰值測試函數(shù)進行驗證,與BA算法相比,SFBA算法優(yōu)化效果較佳。此外,將SFBA算法應(yīng)用于PID參數(shù)優(yōu)化,結(jié)果表明SFBA算法優(yōu)化效果優(yōu)于BA算法。

[1] YANG X S.A new metaheuristic bat-inspired algorithm[J].Physics,2010,284:65-74.

[2] 劉華,顧幸生.改進的混沌蜂群算法在流水線調(diào)度中的應(yīng)用[J].華東理工大學學報(自然科學版),2013,39(3):345-350.

[3] 王珊珊,杜文莉,陳旭,等.基于約束骨干粒子群算法的化工過程動態(tài)多目標優(yōu)化[J].華東理工大學學報(自然科學版),2014,40(4):449-457.

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

[5] MARICHELVAM M K,PRABAHARAN T,YANG X S,etal.Solving hybrid flow shop scheduling problems using bat algorithm[J].International Journal of Logistics Economics & Globalisation,2013,5(1):15-29.

[6] YANG X S.Bat algorithm for multi-objective optimization[J].International Journal of Bio-Inspired Computation,2011,3(5):267-274.

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

[8] TOPAL A O,ALTUN O.A novel meta-heuristic algorithm:Dynamic virtual bats algorithm[J].Information Sciences,2016,354:222-235.

[9] 李枝勇,馬良,張惠珍.函數(shù)優(yōu)化的量子蝙蝠算法[J].系統(tǒng)管理學報,2014(5):717-722.

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

[11] NIKNAM T,BAVAFA F,AZIZIPANAH-ABARGHOOEE R.New self-adaptive bat-inspired algorithm for unit comi--tment problem[J].IET Science Measurement Technology,2014,8(6):505-517.

[12] WANG G G,CHU H C E,MIRJALILI S.Three-dimensional path planning for UCAV using an improved bat algorithm[J].Aerospace Science & Technology,2016,49:231-238.

[13] AFRABANDPEY H,GHAFFARI M,MIRZAEI A,etal.A novel bat algorithm based on chaos for optimization tasks[C]//Iranian Conference on Intelligent Systems.USA:IEEE,2014:1-6.

[14] RAGHAVAN S,MARIMUTHU C,SARWESH P,etal.Bat algorithm for scheduling workflow applications in cloud[C]//International Conference on Electronic Design,Computer Networks & Automated Verification.USA:IEEE,2015:139-144.

[16] YOUNG G F,SCARDOVI L,CAVAGNA A,etal.Starling flock networks manage uncertainty in consensus at low cost[J].PloS Computational Biology,2013,9(1):e1002894.

[17] NETJINDA N,ACHALAKUL T,SIRINAOVAKUL B.Particle swarm optimization inspired by starling flock behavior[J].Applied Soft Computing,2015,35(C):411-422.

[18] XIE J,ZHOU Y,CHEN H.A novel bat algorithm based on differential operator and Lévy flights trajectory[J].Computational Intelligence & Neuroscience,2013(2013):453-812.

[19] 彭泓,丁玉成.基于遺傳交叉因子的蝙蝠算法的改進[J].激光雜志,2015(2):23-26.

[20] 劉金琨.先進PID控制MATLAB仿真[M].北京:電子工業(yè)出版社,2004.

AnImprovedBatAlgorithmBasedonStarlingFlockBehavior

HUFei,SUNZi-qiang

(KeyLaboratoryofAdvancedChemicalProcessControlandOptimizationTechnology,MinistryofEducation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

Bat algorithm (BA) is a new metaheuristic algorithm.However,the standard BA has some shortcomings,e.g.,low convergence precision and easily relapsing into the local optima.In this work,by introducing the collective behavior of the starling group into BA algorithm,the searching range of the standard BA algorithm can be effectively improved.Besides,a linear decreasing weight is introduced to balance the global search and the local search.Simulation results from Benchmark functions show that the improved algorithm can effectively avoid the local optimum and attain higher convergence precision.

bat algorithm (BA); starling group behavior; weight; local optima

1006-3080(2017)04-0525-08

10.14135/j.cnki.1006-3080.2017.04.011

2016-11-01

胡 飛(1992-),男,安徽人,碩士生,研究方向為智能優(yōu)化算法。 E-mail:xueshanfeihu1992@163.com

孫自強,E-mail:sunziqiang@ecust.edu.cn

TP301.6

A