陳偉超,符 強

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

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

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

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

1 標(biāo)準蜉蝣優(yōu)化算法簡介

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

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

1.1 雌蜉蝣更新

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

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

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

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

1.2 雄蜉蝣更新

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

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

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

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

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

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

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

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

1.3 蜉蝣交配

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

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

1.4 蜉蝣變異

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

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

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

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

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

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

圖1 Griewank 函數(shù)

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

2.1 倒位變異機制

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

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

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

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

2.2 突變操作

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

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

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

2.3 IVMA 算法流程

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗及分析

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

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

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

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

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

為了更直觀地反應(yīng)IVMA 算法的搜索性能.本文進一步繪制了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次時都陷入了局部最優(yōu)區(qū)域收斂趨于平緩,但IVMA還是具有較好尋優(yōu)能力.函數(shù)f6中,MA 算法,PSO 算法,CABC 算法的全局收斂性能并不好,但IVMA 經(jīng)過倒位變異后,改善了早熟收斂的問題,提高了全局搜索的能力.函數(shù)f7 存在大量局部優(yōu)值,MA 算法在迭代至400 次時,陷入了局部最優(yōu),但IVMA 算法利用倒位變異保持了正確的搜索方向,持續(xù)地尋找全局最優(yōu)解.函數(shù)f8中其他3 種算法的收斂性能較差,但IVMA 算法從迭代開始至結(jié)束都具有良好的尋優(yōu)能力,在較少的迭代次數(shù)下獲取了較好的優(yōu)化結(jié)果.在函數(shù)f7,f9中,IVMA 算法較快的找到了全局最優(yōu),算法性能得到極大提高.

4 結(jié)論

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