偏移進化蜉蝣優(yōu)化算法①

王克逸,符 強,陳嘉豪

(寧波大學科學技術(shù)學院 信息工程學院,寧波 315300)

在現(xiàn)實生活中存在大量需要優(yōu)化的問題,且隨著時代的發(fā)展,這些問題的特征也在不斷改變,從最簡單的線性問題,到現(xiàn)在的多模態(tài)問題,問題的求解難度不斷上升,由此有學者提出群智能算法.群智能算法通過模擬生物的群體行為,群體中的個體通過學習不斷改變自身位置和搜索方向,使個體往更好的方向進化,進而達到種群群體進化的效果.經(jīng)典的群智能算法有粒子群算法(PSO)[1]、螢火蟲算法(FA)[2]、蟻群算法(ACO)[3]、狼群算法(WPA)[4]、混合蛙跳算法(SFLA)[5]和進化算法(EAS)[6]等,群智能算法現(xiàn)已廣泛應(yīng)用于各個領(lǐng)域[7-10].

蜉蝣算法(mayfly algorithm,MA)[11]是Zervoudakis和Tsafarakis 在2020年提出的一種新型的群智能算法.MA 從蜉蝣的飛行和交配過程中得到啟發(fā)并遵循了達爾文進化理論中的交叉、變異、選擇和適應(yīng)決策.對于求解簡單問題具有較好的尋優(yōu)能力,但由于MA不具備良好的跳出局部最優(yōu)的性能,且在迭代前期,慣性系數(shù)較小,雄雌蜉蝣增速較慢導(dǎo)致種群整體進化效率較低,而在迭代后期,雄蜉蝣婚禮舞蹈系數(shù)、雌蜉蝣飛行系數(shù)和慣性系數(shù)的減小導(dǎo)致雄雌蜉蝣移動緩慢.因此,在高維復(fù)雜問題上,MA 體現(xiàn)出較為乏力的尋優(yōu)能力.在低維問題上,收斂速度較慢,收斂性較差.為增強算法跳出局部最優(yōu)的能力和提升種群整體進化速度,本文提出偏移進化蜉蝣優(yōu)化算法(migration evolutionary mayfly algorithm,MEMA).MEMA 在MA 基礎(chǔ)上添加了一項新策略,從種群的進化角度出發(fā),剔除種群中進化性能較差的蜉蝣,并以特殊方式生成進化性能較好的蜉蝣以此來加快種群進化速度從而使算法快速趨向目標問題的最優(yōu)解.本文將引用MA、PSO、ABC[12]、RPSO[13]、IOABC[14]和本文所提算法,通過不同函數(shù)特性隨機抽取benchmark 標準測試函數(shù),進行綜合性能對比,驗證算法的有效性.

1 蜉蝣算法簡介

MA的靈感來源于蜉蝣的飛行和交配過程.雄蜉蝣皆群居于水面之上,雄蜉蝣進行移動時,將受到種群整體和自身的影響向更優(yōu)方向進發(fā).每過一段時間,雄蜉蝣會通過舞動來吸引雌蜉蝣,雌蜉蝣則會隨機飛向雄蜉蝣進行交配.交配產(chǎn)生若干個子代蜉蝣,極少數(shù)子代蜉蝣會發(fā)生變異.MA 中,雄蜉蝣和子代蜉蝣參與尋優(yōu),即作為解空間中的候選解決方案.隨后,對種群中所有個體通過精英保留策略保留較好個體,形成新種群進行下一輪迭代.

算法最初的時候會隨機產(chǎn)生雄蜉蝣和雌蜉蝣,每一只蜉蝣的位置都是隨機的.由D維向量表示的蜉蝣的位置xi={x1,x2,x3,···,xD},速度表示為Vi={V1,V2,V3,···,VD},每次迭代通過在當前位置上加上速度來進行位置更改.

1.1 雄性蜉蝣的位置更新

雄性蜉蝣是群居的生物,每只雄蜉蝣的位置根據(jù)自己的情況以及種群整體的情況來調(diào)整,雄蜉蝣一般在水面上進行上下移動,假設(shè)蜉蝣不能快速移動,雄蜉蝣的速度為:

雄雌蜉蝣的移動,通過在當前位置添加速度vti+1來改變位置.假設(shè)xti是在時間步長為t時蜉蝣i在搜索空間中的位置,公式如下:

笛卡爾距離公式為:

1.2 雌性蜉蝣的位置更新

雌蜉蝣會尋找適應(yīng)值更好雄蜉蝣繁衍后代,即雌蜉蝣將被適應(yīng)值更好的雄蜉蝣所吸引,所以雌蜉蝣會向更好雄蜉蝣靠近.MA 中種群雄雌蜉蝣的相互吸引定性為最優(yōu)匹配,即最優(yōu)雄蜉蝣與最優(yōu)雌蜉蝣相互吸引,次優(yōu)雄蜉蝣與次優(yōu)雌蜉蝣相互吸引,以此類推.若對應(yīng)雄蜉蝣的適應(yīng)值更差,雌蜉蝣將選擇隨機向周圍飛行.雌蜉蝣的速度的計算公式為:

其中,ytij為雌蜉蝣i對應(yīng)的雄蜉蝣i的位置,rmf是雌性蜉蝣與雄性蜉蝣的笛卡爾距離,fl是一個隨機飛行系數(shù).

1.3 蜉蝣交配行為

MA 采用最優(yōu)匹配的機制來抽取雄雌蜉蝣進行交配產(chǎn)生后代,公式如下:

其中,offs1為第一個子代,offs2為第二個子代,male為雄蜉蝣,female為雌蜉蝣,L為[-1,1]的隨機值.

1.4 子代蜉蝣突變

MA 引入了高斯變異[15],假設(shè)種群數(shù)量為N,設(shè)定變異因子為m,則子代蜉蝣中發(fā)生變異個體為N·m,變異子代蜉蝣的隨機一個維度將發(fā)生突變,突變公式為:

其中,offsn為被選中的子代offs的n維度,σ為正態(tài)分布的標準差,Nn(0,1)為均值為0,方差為1的標準正態(tài)分布.

1.5 動態(tài)慣性權(quán)重

為了平衡全局探索能力和局部搜索能力,MA 加入了動態(tài)慣性權(quán)重.在迭代過程中,蜉蝣的慣性權(quán)重將線性減少小,公式如下:

其中,g為慣性權(quán)重,gmax是最大慣性權(quán)重,gmin是最小慣性權(quán)重,iter為迭代次數(shù),itermax為最大迭代次數(shù),iter為迭代次數(shù).

算法前期,較大的g能更好地滿足全局探索能力增加算法的收斂速度,算法后期,較小的g增加局部搜索能力提高算法的搜索精度.

1.6 婚禮舞蹈系數(shù)與隨機飛行系數(shù)

為了尋找更好的解,蜉蝣算法引入婚禮舞蹈系數(shù),當雄蜉蝣適應(yīng)值大于全局最優(yōu)時,將進行隨機移動以尋找更優(yōu)解,引入飛行系數(shù),當雌蜉蝣未被雄蜉蝣吸引時,會向四周隨機飛行尋找更好的雄蜉蝣.婚禮舞蹈系數(shù)和隨機飛行系數(shù)會隨迭代次數(shù)減小以此減少蜉蝣步長,增加局部搜索能力,在算法后期提高收斂精度,公式如下:

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

2 偏移進化蜉蝣優(yōu)化算法

MA 算法在迭代前期,種群較快收束于當前全局最優(yōu)位置,不利于種群整體進化,在迭代中后期,易出現(xiàn)早熟收斂現(xiàn)象.對這個問題提出MEMA,添加年齡到蜉蝣的屬性中,剔除群體中較為年長且進化程度較低的蜉蝣,并在該個體附近重新生成新個體保證種群完整性,同時對該蜉蝣進行指向性動態(tài)進化訓練,促進蜉蝣良性進化,提升種群整體利用率,提升算法尋優(yōu)性能.

2.1 偏移進化機制

抽象蜉蝣良性進化的思想為算法的偏移進化機制,在每次迭代后,記錄種群中雄蜉蝣的進化次數(shù),由于當蜉蝣進化次數(shù)超過一定次數(shù)時會存在適應(yīng)值較差的個體,為了排除進化2 次到3 次存在的偶然性,而4 次以上會使適應(yīng)值較差的浮游在外徘徊次數(shù)過多浪費進化次數(shù),所以選取4 次當蜉蝣數(shù)進化次數(shù).超過4 次且適應(yīng)值較差時,說明該蜉蝣的進化速度始終在跟隨整體的進化疲于奔向最優(yōu)位置,判定這樣的解為失效解,不具備較好進化能力對算法求解幫助較小.剔除該蜉蝣并引入新蜉蝣,從原蜉蝣的位置上進行一次偏移操作,生成新蜉蝣.新蜉蝣出現(xiàn)位置為:

其中,mayflyw為被剔除蜉蝣的位置,W為拉伸因子,公式為:

其中,Lower為解空間下限,Upper rand為解空間上限(0,1]為的隨機值.

為了保證新蜉蝣是優(yōu)秀的個體且能有效地對種群進化起到幫助.在加入種群前,將對新蜉蝣進行隨機次數(shù)的進化.規(guī)定該蜉蝣會根據(jù)速度調(diào)節(jié)因子ρ 進行指向性動態(tài)進化訓練,但不會超過當前種群進化次數(shù),其公式為:

新蜉蝣在加入種群前的進化移動與種群進化移動相同,通過在當前位置添加速度來改變位置.但更改速度的變化為:

根據(jù)速度公式,在速度調(diào)節(jié)因子 ρ的影響下,蜉蝣將進行分段尋找,重力因子g的存在,可以減小前一次進化速度的影響,同時蜉蝣的速度受到gbest和pbest兩個位置因子影響,若蜉蝣找到比偏移后的初始位置更優(yōu)的位置,將受到上一次速度的影響繼續(xù)向前前進一段距離,之后受到兩個位置因子的影響快速減速,并反向加速回到更新后的全局最優(yōu)位置附近,否則將進行先加速后減速的分段尋找.這一過程蜉蝣將仔細搜索更新后的全局最優(yōu)位置的附近位置以期能將失效個體轉(zhuǎn)換為引導(dǎo)種群進化的個體,填補MA 算法的缺陷,增加算法收斂性能.這些策略都是為了能更好地適應(yīng)復(fù)雜的自然環(huán)境,讓其算法在保持多樣性的條件下讓其在全局搜索與局部搜索方面更為靈活.

2.2 MEMA 算法流程

Step 1.初始化參數(shù).

Step 2.初始化雄雌蜉蝣位置與速度,計算并找出當前最優(yōu)解.

Step 3.根據(jù)式(1),式(2),式(4)更新雄雌性蜉蝣速度與位置.

Step 4.所有蜉蝣根據(jù)當前適應(yīng)值排序.

Step 5.根據(jù)式(5)生成后代,并根據(jù)變異可能性和式(6)隨機產(chǎn)生變異后將其后代隨機變成雄蜉蝣或者雌蜉蝣.

Step 6.根據(jù)種群的適應(yīng)值,對雄雌蜉蝣進行排序,用當前更優(yōu)解代替劣解.

Step 7.根據(jù)式(8)和式(9)更新舞蹈系數(shù)和隨機飛行系數(shù),根據(jù)式(7)更新慣性權(quán)重.

Step 8.若超過4 次且能力較差,則根據(jù)式(10)和式(11)產(chǎn)生新蜉蝣,根據(jù)式(12)產(chǎn)生隨機進化次數(shù),根據(jù)式(13)進化新蜉蝣,將淘汰的個體替換.

Step 9.判斷是否到達迭代上限,若是,轉(zhuǎn)Step 10,若否,轉(zhuǎn)Step 3.

Step 10.輸出當前最優(yōu)解.

3 實驗及數(shù)據(jù)比對

3.1 實驗環(huán)境

實驗中所使用的軟硬件參數(shù)如下:

(1)操作系統(tǒng):Windows 10;

(2)硬件參數(shù):Intel(R) Core(TM) i7-8750H CPU @2.20 GHz 2.21 GHz 8 GB RAM 內(nèi)存;

(3)編譯環(huán)境及工具:Matlab 2018a.

3.2 測試函數(shù)

為了說明算法的普遍適用性,本文為突出該算法的全面性隨機抽取了標準benchmark 測試函數(shù)中6 個具有不同特點的函數(shù)(見表1).

表1 測試函數(shù)

首先抽取兩個典型的單峰函數(shù)Sphere 函數(shù)和Ackley 函數(shù),其中Sphere 函數(shù)常用于檢驗算法的收斂效率,而Ackley 函數(shù)是一個梯度式的函數(shù),在高維問題上,算法收斂將會非常慢,常用于檢驗算法的全局收斂速度.

其次抽取兩種底部較平緩的單峰函數(shù)Powell Sum函數(shù)和Rosenbrock 函數(shù),前一種單峰函數(shù)底部較平,導(dǎo)致算法接近最優(yōu)值附近區(qū)域時,尋優(yōu)較慢,可以用于檢驗算法尋優(yōu)效率.Rosenbrock 函數(shù)是病態(tài)單峰函數(shù),也稱為香蕉函數(shù).函數(shù)面可以看作為陡坡,底部較為平緩,最優(yōu)值位于陡坡底部,底部區(qū)域很容易找到,但由于底部的值變化不大,要找到全局最優(yōu)很困難,一般用于檢驗算法的局部搜索能力.

最后抽取兩個經(jīng)典的多峰函數(shù)Schwefel 2.22 函數(shù)和Rastrigin 函數(shù).Schwefel 2.22 函數(shù)較為平滑,但全局最優(yōu)值位于定義域的界限處.Rastrigin 函數(shù)是一個多模態(tài)多峰函數(shù),具有大量的局部最小值,尤其在高維問題上,易使算法陷入局部最優(yōu),常用于檢驗算法跳出局部最優(yōu)的能力.

將MEMA與MA[11]、ABC[12]、IQABC[14]、PSO[1]、RPSO[13]5 種算法進行對比,來測試算法的性能.

3.3 參數(shù)設(shè)置

設(shè)置迭代次數(shù)為500 次,所有算法的種群數(shù)量都為40,MEMA的參數(shù)設(shè)置為:最大慣性權(quán)重為1.5,最小慣性權(quán)重為0.4,婚禮舞蹈系數(shù)為1,婚禮舞蹈系數(shù)的衰減系數(shù)為0.8,隨機飛行系數(shù)為1,隨機飛行系數(shù)的衰減系數(shù)為0.99,子代數(shù)量為20,變異可能性為0.01,種群學習參數(shù)a1為1.0,蜉蝣個體學習參數(shù)a2為1.5,其他算法的參數(shù)設(shè)置參考文獻內(nèi)容.

實驗將偏移進化蜉蝣優(yōu)化算法(MEMA)與蜉蝣算法(MA),蜂群算法(ABC),改進蜂群算法(IQABC),粒子群算法(PSO)和改進粒子群算法(RPSO)進行對比,為避免因隨機因素造成算法結(jié)果影響,因此本文對每個測試函數(shù)獨立運行100 次實驗取平均值作為算法的最終結(jié)果以降低隨機數(shù)對結(jié)果的影響.為了綜合考慮算法的有效性,記錄了6 種算法的平均值,最優(yōu)解,最劣解和方差.

為了更全面地驗證各算法在低維及高維空間的有效性,本文將從低維和高維進行算法測試.低維我們?nèi)?0 維,數(shù)據(jù)見表2,高維我們?nèi)?00 維,數(shù)據(jù)見表3.

表2 6 種算法對比數(shù)據(jù)表(10 維)

表3 6 種算法對比數(shù)據(jù)表(100 維)

由表2中數(shù)據(jù)可見,在6 個10 維的測試函數(shù)上，MEMA 所找到的最優(yōu)值與最劣值均能達到測試函數(shù)的全局最優(yōu)解,說明算法的收斂精度相較于對比算法更強.時可以看出MEMA 方差有5 個都趨于0,對于F3和F6 函數(shù)未收斂完成的測試函數(shù),相比較其他5 種算法,MEMA 在收斂精度和算法穩(wěn)定性上也都體現(xiàn)了卓越的性能.

對于表3中的數(shù)據(jù),同樣的,對于10 維的問題中可以收斂完成的測試函數(shù),MEMA 在100 維的問題上也完成收斂,充分體現(xiàn)了MEMA 對于解決高維問題的優(yōu)異性能,對于F3和F6 函數(shù)未能有效完成收斂,但是MEMA 相較于其他的算法體現(xiàn)了較強的能力尋優(yōu)能力和尋優(yōu)穩(wěn)定性.因此表現(xiàn)了MEMA 在求解高維問題時更能體現(xiàn)出算法的尋優(yōu)能力.

綜上數(shù)據(jù)結(jié)果可得,MEMA 相比較其他算法,對于問題的處理能力更加出色,說明在MA 中加入生命周期的屬性,將生命周期較長且進化能力較弱的個體替換為更優(yōu)個體,可以有效地將蜉蝣的利用率提升,提升種群整體進化速度.為了清晰的體現(xiàn)算法的收斂效率,同樣采用圖1與圖2畫出了在10 維與100 維的問題上不同函數(shù)的收斂曲線.同樣采用低維和高維兩種維度進行算法測試.低維我們?nèi)?0 維,數(shù)據(jù)見圖1,高維我們?nèi)?00 維,數(shù)據(jù)見圖2.

結(jié)合表2、表3的數(shù)據(jù)和圖1、圖2的收斂曲線可以得出,對于對比函數(shù),其他5 種算法在收斂速度上明顯低于MEMA.在圖1的低維問題上F1 函數(shù)在迭代25 次時完成收斂,F2 函數(shù)在迭代50 次左右時完成收斂.圖1中F5 函數(shù)在其他算法都沒有找到最優(yōu)解時,MEMA 大約20 次的時候就找到了最優(yōu)解.在圖2高維問題上難以在短時間內(nèi)收斂完成,而MEMA 除F6都在迭代50 次左右完成了收斂并達到全局最優(yōu)值,而F6 也能在圖中可以看出當其他對比算法都陷入局部最優(yōu)時,MEMA 還能繼續(xù)向下收斂,且該函數(shù)為單峰函數(shù),函數(shù)面較平,在最優(yōu)值附近區(qū)域較小,較為考驗算法的收斂速度,充分說明了在高維問題上MEMA 求解效率快,尋優(yōu)精度高.從圖2中F5 可以看出,其他測試算法由于全局搜索能力較慢,難以快速接近最優(yōu)解,而MEMA 迭代50 次左右就可以快速接近最優(yōu)值.對于100 維的收斂曲線圖可以看到在收斂速度上MEMA遠超其他算法.對于F1、F2、F4、F5 函數(shù),MEMA 在迭代50 次內(nèi),已經(jīng)收斂完成,證明算法充分利用了蜉蝣群體中的較劣蜉蝣,提升了算法的收斂性能.

圖1 10 維問題函數(shù)收斂曲線圖

圖2 100 維問題函數(shù)收斂曲線圖

3.4 運行效率

為驗證MEMA的尋優(yōu)能力,我們設(shè)計運行效率的實驗,因為篇幅原因,我們隨機抽取4 個benchmark 測試函數(shù),假設(shè)算法在求解精度達到1 0-20時,判定為算法尋找到最優(yōu)解,停止算法運行,若未找到,則運行算法直到迭代上限500 次,通過測試CPU 運行時間,得出算法運行時間,最快運行時間標黑,數(shù)據(jù)見表4.

表4 運行時間 (s)

從數(shù)據(jù)表上看,MEMA的CPU 運行時間遠小于其他5 種算法,也表明在實際優(yōu)化方面找到最優(yōu)值的概率會大幅增加.即證明MEMA的尋優(yōu)能力優(yōu)于其他算法.

4 結(jié)束語

本文分析了蜉蝣算法難以有效利用失效蜉蝣的缺點,引入了偏移進化后的蜉蝣去替換原有物種中失效個體,在陷入局部極值時能夠快速的跳出循環(huán),已趨于最優(yōu)解空間,以此來加快算法收斂效率并提高算法收斂性,最終提出了基于偏移進化的改進型蜉蝣優(yōu)化算法MEMA.本文從多方面對算法性能進行實驗,使用6 個具有典型代表的benchmark 標準測試函數(shù),將MEMA與MA、ABC、PSO、IQABC、RPSO 五種算法進行對比,證實了改進后的該算法無論在高緯度還是低維度反面都可以有效地進行全局收斂,并且在圖中也能更為直觀地看出全局收斂能力能是遠超于其他算法的.為了證明該算法的效率方面的情況,設(shè)計了運行時間比對實驗,實驗結(jié)果表明,MEMA 算法不但結(jié)構(gòu)簡潔,而且針對測試函數(shù)集表現(xiàn)出良好的尋優(yōu)性能,在收斂精度和收斂速度等方面均具有明顯優(yōu)勢.后期研究方向為提出相應(yīng)的離散化算法及多目標優(yōu)化算法.