基于倒位變異的蜉蝣優(yōu)化算法①

陳偉超,符 強(qiáng)

(寧波大學(xué)科學(xué)技術(shù)學(xué)院,寧波 315300)

隨著社會(huì)的發(fā)展,出現(xiàn)了許多復(fù)雜的優(yōu)化問題亟待解決,傳統(tǒng)的數(shù)學(xué)工具已經(jīng)不在適用于求解這些問題.隨著計(jì)算智能的發(fā)展,出現(xiàn)了群智能算法[1].群智能算法是一種新興的演化計(jì)算技術(shù),相比于其它傳統(tǒng)優(yōu)化算法能更快的發(fā)現(xiàn)復(fù)雜優(yōu)化問題的最優(yōu)解,已成為越來越多研究者的關(guān)注焦點(diǎn).群智能算法原理簡(jiǎn)單,尋優(yōu)能力良好.通過對(duì)群智能算法的不斷改進(jìn)和優(yōu)化,使得群智能算法應(yīng)用面越來越廣,粒子群算法[2]等已經(jīng)廣泛應(yīng)用于非線性復(fù)雜約束規(guī)劃、作業(yè)調(diào)度優(yōu)化等實(shí)際工程中.

蜉蝣算法(Mayfly Algorithm,MA)[3]是2020年新提出的群智能優(yōu)化算法.MA 算法根據(jù)蜉蝣的活動(dòng)方式和習(xí)性而編寫.其中雄蜉蝣成群的聚集,每只雄蜉蝣的位置都是根據(jù)自己和鄰居的經(jīng)驗(yàn)來調(diào)整,雄蜉蝣通過婚禮舞蹈吸引雌蜉蝣進(jìn)行交配.

MA 算法把雄蜉蝣的位置移動(dòng)看作算法的尋優(yōu)過程,同時(shí)引入了婚禮舞蹈系數(shù)和隨機(jī)飛行系數(shù),有助于算法跳出局部最優(yōu).但在高維非線性復(fù)雜問題中,MA算法的全局收斂性能較差.本文將倒位變異和突變結(jié)合,提出了一種基于倒位變異的蜉蝣算法(Inversion Variation Mayfly Algorithm,IVMA),以提高算法在高維非線性復(fù)雜問題的收斂精度.并通過隨機(jī)抽取的10個(gè)50 維度benchmark 標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)算法性能進(jìn)行驗(yàn)證.

1 標(biāo)準(zhǔn)蜉蝣優(yōu)化算法簡(jiǎn)介

MA[3]算法是一種求解優(yōu)化問題的群智能優(yōu)化算法,該算法受蜉蝣飛行行為和交配過程的啟發(fā).其中MA 算法結(jié)合了粒子群算法(PSO)[4,5]、遺傳算法(GA)[6]和螢火蟲算法(FA)[7]的主要優(yōu)點(diǎn),提高了算法尋優(yōu)能力,使得MA 算法具有較好的尋優(yōu)能力,但在高維非線性復(fù)雜問題上,MA 算法跳出局部最優(yōu)的能力較差,容易出現(xiàn)早熟收斂的現(xiàn)象.使得算法在多峰函數(shù)中表現(xiàn)較差.具體的計(jì)算方法如下:

設(shè)有一個(gè)D維問題,MA 算法根據(jù)蜉蝣的位置來求出最優(yōu)解,第i個(gè)蜉蝣的位置xi={x1,x2,x3,…,xD}對(duì)應(yīng)速度為Vi={V1,V2,V3,…,VD}.

1.1 雌蜉蝣更新

雌蜉蝣的速度更新:雌蜉蝣不會(huì)像雄蜉蝣一樣成群結(jié)隊(duì),當(dāng)雌蜉蝣被雄蜉蝣吸引時(shí),會(huì)向雄蜉蝣靠近,否則雌蜉蝣會(huì)隨機(jī)飛行.它們的速度計(jì)算如下:

其中,Vijt+1是雌蜉蝣i在維度j中的位置,a2是固定的可見性系數(shù),rmf是雄蜉蝣和雌蜉蝣之間的笛卡爾距離為笛卡爾距離計(jì)算公式),fl是隨機(jī)飛行系數(shù),r是[-1,1]區(qū)間內(nèi)的一個(gè)隨機(jī)數(shù),iter是當(dāng)前迭代次數(shù),itermax為最大迭代次數(shù).g是動(dòng)態(tài)慣性系數(shù),更新公式如下:

雌蜉蝣的位置移動(dòng)通過蜉蝣所在位置加上蜉蝣獲得的速度Vit+1來改變.

其中,yit為雌性蜉蝣i在時(shí)間步長t時(shí)在搜索空間上的位置,蜉蝣在搜索空間中飛行,因此位置具有限制yij∈(ymin,ymax).

1.2 雄蜉蝣更新

雄蜉蝣的速度更新:在表演婚禮舞蹈時(shí),雄蜉蝣不能產(chǎn)生出很快的速度,但它們會(huì)不斷地移動(dòng).因此,雄性蜉蝣i的速度計(jì)算如下:

其中,Vijt+1是雄蜉蝣i在維度j上的速度,a1,a2分別是正吸引系數(shù),用于衡量認(rèn)知和社會(huì)貢獻(xiàn).d是舞蹈系數(shù),r是[-1,1]區(qū)間內(nèi)的一個(gè)隨機(jī)數(shù),g是動(dòng)態(tài)慣性系數(shù),GlobalBest是全局最優(yōu)個(gè)體.

此外pbest是蜉蝣i去過最好的位置,在下一個(gè)時(shí)間步長中,個(gè)體最優(yōu)位置為:

其中,全局最優(yōu)位置gbest的定義如下

雄蜉蝣的位置的移動(dòng)通過在蜉蝣所在位置加上蜉蝣獲得的速度來改變.

其中,xit+1為雄蜉蝣i在時(shí)間步長t時(shí)在搜索空間上的位置,雄蜉蝣在搜索空間中飛行,因此位置具有限制xij∈(xmin,xmax).

當(dāng)更新一個(gè)遠(yuǎn)離全局最佳位置或個(gè)人最佳位置的蜉蝣的速度時(shí)可能會(huì)出現(xiàn)蜉蝣飛出問題空間的情況.根據(jù)蜉蝣的生活習(xí)性,蜉蝣不會(huì)一直增加速度.假設(shè)每個(gè)蜉蝣能夠產(chǎn)生一個(gè)指定的最大速度Vmax.因此,速度調(diào)整為:

其中,Vmax=rand*(xmax-xmin),其中rand∈(0,1].

1.3 蜉蝣交配

在一個(gè)種群中,雄雌蜉蝣按照適應(yīng)值選擇配對(duì)個(gè)體進(jìn)行交配,適應(yīng)值最優(yōu)的雄蜉蝣和適應(yīng)值最優(yōu)的雌蜉蝣進(jìn)行交配,依此類推.交配結(jié)果是產(chǎn)生兩個(gè)子代,其產(chǎn)生公式如下:

其中,L是[-1,1]之間的一個(gè)隨機(jī)數(shù),子代的初始速度設(shè)定為0.

1.4 蜉蝣變異

為了處理可能導(dǎo)致出現(xiàn)的最優(yōu)值是局部最優(yōu)而不是全局最優(yōu)的早熟收斂情況,在,將正態(tài)分布的隨機(jī)數(shù)加到所選子代蜉蝣中進(jìn)行突變,子代蜉蝣突變公式如下:

其中,σ是正態(tài)分布的標(biāo)準(zhǔn)偏差.N(0,1)是平均值為0,方差為1的標(biāo)準(zhǔn)正態(tài)分布.變異個(gè)體的數(shù)量為round(0.05*雄蜉蝣數(shù)量).

婚禮舞蹈系數(shù)與隨機(jī)飛行系數(shù)也會(huì)隨迭代次數(shù)減少,公式如下:

其中,dt與flt為t時(shí)刻的婚禮舞蹈系數(shù)和隨機(jī)飛行系數(shù),ddamp與fldamp是婚禮舞蹈系數(shù)和隨機(jī)飛行的衰減參數(shù).

2 基于倒位變異的蜉蝣算法(Inversion Variation Mayfly Algorithm,IVMA)

面對(duì)高維非線性復(fù)雜問題時(shí),MA 算法容易陷入局部最優(yōu)區(qū)域,發(fā)生進(jìn)化停滯的情況.如圖1所示在函數(shù)Griewank中MA 算法較早的出現(xiàn)了陷入局部最優(yōu)的現(xiàn)象,使得種群進(jìn)化停滯.

圖1 Griewank 函數(shù)

對(duì)于MA 算法存在的缺陷,本文提出的IVMA 算法通過對(duì)最優(yōu)個(gè)體進(jìn)行倒位變異操作,使得IVMA 算法具有較好全局搜索能力.對(duì)倒位變異策略產(chǎn)生的新個(gè)體使用精英策略保留進(jìn)化成果.改變?cè)惴ㄔ谧儺惿系牟僮?提高IVMA 算法在高維復(fù)雜問題中的收斂精度.

2.1 倒位變異機(jī)制

由于MA 算法在算法收斂過程中容易出現(xiàn)早熟收斂的問題,IVMA 算法在為了避免在算法后期陷入局部最優(yōu),提高算法擺脫局部極值點(diǎn)的能力,引用了倒位變異機(jī)制[8].在進(jìn)行一輪種群進(jìn)化之后,當(dāng)種群的適應(yīng)值連續(xù)兩代的差值小于某個(gè)閾值時(shí)(閾值設(shè)于10-3),對(duì)蜉蝣的最優(yōu)個(gè)體進(jìn)行倒位變異,以增強(qiáng)種群的多樣性,提高算法的全局收斂性能.

倒位變異的具體操作如下,對(duì)最優(yōu)個(gè)體GlobalBest進(jìn)行倒位操作.首先在[1,D]之間隨機(jī)選取兩個(gè)整數(shù)p和q,設(shè)p＜q,p,q為最優(yōu)個(gè)體的不同維度,將p,q兩個(gè)維度之間的GlobalBest位置進(jìn)行倒序,如當(dāng)p為10,q為20 時(shí),GlobalBest的10 維的位置和20 維的位置進(jìn)行交換,GlobalBest的11 維的位置和19 維的位置進(jìn)行交換.以此進(jìn)行類推,則執(zhí)行倒序操作后得到了新個(gè)體,帶入目標(biāo)函數(shù),如果產(chǎn)生的新個(gè)體比當(dāng)前全局最優(yōu)個(gè)體更好,則進(jìn)行更新,以此保留種群進(jìn)化的成果.

利用倒位變異改變GlobalBest在隨機(jī)維度段p至q之間的位置,即對(duì)選定的維度段內(nèi)GlobalBest的位置進(jìn)行倒序操作,得到的新個(gè)體和GlobalBest比較,使用較優(yōu)個(gè)體對(duì)種群進(jìn)化進(jìn)行引導(dǎo).因?yàn)樾垓蒡龅奈恢檬峭ㄟ^自身到過的最好位置和當(dāng)前全局最優(yōu)個(gè)體GlobalBest的位置進(jìn)行移動(dòng)的,利用經(jīng)過倒位變異操作的GlobalBest的引導(dǎo),使得雄蜉蝣在靠近自身到過的最優(yōu)位置和當(dāng)前全局最優(yōu)位置的過程中具備了找到優(yōu)于當(dāng)前全局最優(yōu)個(gè)體的位置的能力.

通過倒位變異機(jī)制,使得IVMA 算法具備了良好的找到全局最優(yōu)的能力,提高算法了在高維非線性復(fù)雜問題中的全局收斂性能.

2.2 突變操作

改變?cè)惴ǖ淖儺惒僮?在進(jìn)行交配操作后從子代中隨機(jī)選擇一個(gè)個(gè)體xi,產(chǎn)生新個(gè)體xi.具體操作為,從子代蜉蝣種群中隨機(jī)選擇一個(gè)個(gè)體,通過改變它的單個(gè)隨機(jī)維度的蜉蝣位置來優(yōu)化算法.xi中隨機(jī)的維度d向蜉蝣全局最優(yōu)個(gè)體的隨機(jī)維度b靠近,公式如下:

其中,b,d∈{1,2,3,…,D}分別是隨機(jī)選取的一個(gè)值,λ∈[-1,1].

通過改變所選子代蜉蝣的隨機(jī)維度的位置,提高了種群多樣性.改善了MA 算法擺脫局部極值點(diǎn)的能力.

2.3 IVMA 算法流程

Step 1.基本參數(shù)設(shè)置,包括種群規(guī)模,最大迭代次數(shù)等.

Step 2.隨機(jī)產(chǎn)生初始種群,隨機(jī)蜉蝣的位置并且設(shè)置初始速度為零.

Step 3.根據(jù)式(1),式(3)分別更新雌蜉蝣的速度和位置,雌蜉蝣的位置帶入目標(biāo)函數(shù)比較適應(yīng)值,如果優(yōu)于個(gè)體最優(yōu)則根據(jù)式(5)更新個(gè)體最優(yōu)數(shù)據(jù).

Step 4.根據(jù)式(4),式(7)分別更新雄蜉蝣的速度和位置.

Step 5.雄蜉蝣的位置帶入目標(biāo)函數(shù)比較適應(yīng)值,如果優(yōu)于個(gè)體最優(yōu)則根據(jù)(5)更新個(gè)體最優(yōu)數(shù)據(jù),在此基礎(chǔ)上,如果優(yōu)于全局最優(yōu)則根據(jù)式(6)更新全局最優(yōu)數(shù)據(jù).

Step 6.對(duì)雄雌蜉蝣的適應(yīng)值根據(jù)優(yōu)劣性進(jìn)行排序.

Step 7.根據(jù)式(9),式(10)對(duì)蜉蝣進(jìn)行交配操作產(chǎn)生子代蜉蝣.

Step 8.根據(jù)式(14)對(duì)子代蜉蝣進(jìn)行突變操作.

Step 9.在進(jìn)行一次種群進(jìn)化后,如果符合閾值條件,則進(jìn)行倒位變異操作,通過比較適應(yīng)值決定是否更新.

Step 10.對(duì)于蜉蝣適應(yīng)值進(jìn)行排序,取較優(yōu)解,保持總?cè)簲?shù)量不變.更新舞蹈系數(shù)(式(12)),飛行系數(shù)(式(13)),動(dòng)態(tài)慣性系數(shù)(式(2)).

Step 11.判斷是否達(dá)到終止條件,若是則輸出最優(yōu)解:若否,則執(zhí)行Step 3.

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

為了測(cè)試IVMA 算法的優(yōu)化性能,從文獻(xiàn)[3]中隨機(jī)選取了10 個(gè)標(biāo)準(zhǔn)benchmark 函數(shù)進(jìn)行驗(yàn)證.各函數(shù)的參數(shù)說明及特征如表1所示.

表1 測(cè)試函數(shù)的維度,搜索空間,最優(yōu)值

將IVMA 算法和MA 算法,PSO 算法[9]、優(yōu)化的蜂群算法(CABC)[10]進(jìn)行對(duì)比仿真實(shí)驗(yàn).MA 算法,PSO 算法,CABC 算法,IVMA的種群數(shù)量均設(shè)定為40 個(gè),其中MA 算法,PSO 算法,CABA 算法其他參數(shù)設(shè)置參考所引文獻(xiàn).IVMA 算法具體的參數(shù)設(shè)置為:雄雌蜉蝣的數(shù)量各為20,迭代次數(shù)2000 次,蜉蝣的舞蹈系數(shù)為1,隨機(jī)飛行系數(shù)為1,ddamp為0.8,fldamp為0.99,gmax為1.5,gmin為0.4,a1=1,a2=1.5.為了測(cè)試算法在高維非線性復(fù)雜問題中的表現(xiàn),函數(shù)測(cè)試維度均為50 維,每個(gè)測(cè)試函數(shù)做100 次重復(fù)實(shí)驗(yàn)進(jìn)行對(duì)比分析,得出4 種算法的最優(yōu)值,最差值,平均值和標(biāo)準(zhǔn)差,結(jié)果如表2所示.

表2 4 種算法對(duì)10 個(gè)函數(shù)的計(jì)算結(jié)果比較

表2顯示,在50 維度的10 個(gè)函數(shù)優(yōu)化測(cè)試中,MA 算法,PSO 算法和ABC 算法的搜索能力較差.MA 算法,PSO 算法和CABC 沒有一個(gè)函數(shù)獲得理論最優(yōu)值,而IVMA 算法在f7,f9 兩個(gè)測(cè)試函數(shù)中獲取了理論最優(yōu)值.從整體函數(shù)測(cè)試結(jié)果來看,IVMA 算法具有更好的收斂精度,搜索能力優(yōu)于其他對(duì)比算法.

為了更直觀地反應(yīng)IVMA 算法的搜索性能.本文進(jìn)一步繪制了IVMA 算法,MA 算法,CABC 算法以及PSO 算法的適應(yīng)度收斂曲線圖,如圖2～圖11所示(其中橫坐標(biāo)為迭代次數(shù),縱坐標(biāo)為收斂精度)

圖2 f1 函數(shù)收斂性能比較

圖3 f2 函數(shù)收斂性能比較

圖4 f3 函數(shù)收斂性能比較

圖5 f4 函數(shù)收斂性能比較

圖6 f5 函數(shù)收斂性能比較

圖7 f6 函數(shù)收斂性能比較

圖8 f7 函數(shù)收斂性能比較

圖9 f8 函數(shù)收斂性能比較

圖10 f9 函數(shù)收斂性能比較

圖11 f10 函數(shù)收斂性能比較

由函數(shù)圖觀察發(fā)現(xiàn)在f1,f2,f4 函數(shù)中,MA 算法相較于PSO 算法和CABA 算法具有一定優(yōu)越性,IVMA提高了收斂精度.函數(shù)f5中其他3 種算法在迭代200次時(shí)都陷入了局部最優(yōu)區(qū)域收斂趨于平緩,但I(xiàn)VMA還是具有較好尋優(yōu)能力.函數(shù)f6中,MA 算法,PSO 算法,CABC 算法的全局收斂性能并不好,但I(xiàn)VMA 經(jīng)過倒位變異后,改善了早熟收斂的問題,提高了全局搜索的能力.函數(shù)f7 存在大量局部?jī)?yōu)值,MA 算法在迭代至400 次時(shí),陷入了局部最優(yōu),但I(xiàn)VMA 算法利用倒位變異保持了正確的搜索方向,持續(xù)地尋找全局最優(yōu)解.函數(shù)f8中其他3 種算法的收斂性能較差,但I(xiàn)VMA 算法從迭代開始至結(jié)束都具有良好的尋優(yōu)能力,在較少的迭代次數(shù)下獲取了較好的優(yōu)化結(jié)果.在函數(shù)f7,f9中,IVMA 算法較快的找到了全局最優(yōu),算法性能得到極大提高.

4 結(jié)論

為了改善MA 算法在高維復(fù)雜問題中全局收斂性能較差,容易出現(xiàn)早熟收斂的問題.本文提出了一種基于倒位變異的IVMA 算法,IVMA 算法引入倒位變異操作和改變MA 算法在變異上的操作,提高了跳出局部最優(yōu)的能力.對(duì)10 個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)尋優(yōu)的實(shí)驗(yàn)結(jié)果表明,MA 算法相對(duì)于MA 算,PSO 算法和CABC 算法,在高維非線性復(fù)雜問題中具有更好的收斂精度,優(yōu)化了算法的尋優(yōu)能力.