一種混沌映射動態(tài)慣性權(quán)重的樽海鞘群算法

周 密,王瀟棠,閆 河,謝 敏

1(重慶理工大學(xué) 理學(xué)院,重慶 400054)2(重慶理工大學(xué) 兩江人工智能學(xué)院,重慶 401135)

1 引 言

樽海鞘,被囊動物亞門中的紐鰓樽科[1],體型呈桶狀,全身透明,通過吸入噴出海水在水中移動,有孤立和群居兩種生活形式.群居生活時,樽海鞘群體運(yùn)動方式呈螺旋狀,群中會有一個領(lǐng)導(dǎo)者位于食物鏈前端,其后的個體被稱為追隨者,位置隨著領(lǐng)導(dǎo)者覓食位置的變化而變化.Mirjalili等人受此啟發(fā),提出了樽海鞘群算法(Salp Swarm Algorithm,SSA)[2],其主要思想是將所有的樽海鞘個體位置存儲在二維矩陣中,樽海鞘群在N維空間搜索最佳食物源的位置,樽海鞘群分為領(lǐng)導(dǎo)者和追隨者,領(lǐng)導(dǎo)者的位置更新受食物源的位置影響,與其他群優(yōu)化算法不同的是,追隨者的位置更新不完全受領(lǐng)導(dǎo)者影響,只與前一個樽海鞘個體位置有關(guān),通過不斷迭代更新領(lǐng)導(dǎo)者和追隨者的位置,最終使得樽海鞘群找到最優(yōu)的食物源位置.

SSA作為一種新型的群智能優(yōu)化算法,具有參數(shù)少,結(jié)構(gòu)簡單,易于實(shí)現(xiàn)等優(yōu)點(diǎn)[3],自2017年提出后就被廣泛于各領(lǐng)域[4-6].但是原始算法和其他群智能優(yōu)化算法一樣,依然存在求解精度低和收斂速度慢等問題[7],且追隨者的位置更新方法具有一定的盲目性[8],在迭代后期,追隨者的位置移動應(yīng)該逐漸變緩,而原始算法的追隨者位置更新在迭代過程中沒有變化,缺少了自適應(yīng)性[9].為此,邢致愷等人[10]提出了基于萊維飛行的樽海鞘群優(yōu)化算法(Levy Flight Trajectory-based Salp Swarm Algorithm,LSSA),利用萊維飛行的隨機(jī)性來擾動領(lǐng)導(dǎo)者的位置更新,提升了算法全局搜索能力,使得算法有效陷入局部最優(yōu);針對SSA收斂速度慢等問題,文獻(xiàn)[11]提出了一種基于瘋狂自適應(yīng)的樽海鞘群算法(Salp Swarm Algorithm based on craziness and adaptive,CASSA),通過引入瘋狂算子來增強(qiáng)種群的多樣性,并在追隨者的位置更新公式中引入自適應(yīng)慣性權(quán)重,平衡了算法的全局搜索能力和局部搜索能力;為了增強(qiáng)算法全局搜索能力和提升收斂速度,張嚴(yán)等人[12]提出了基于Levy飛行策略的改進(jìn)樽海鞘群算法(Levy Flight-based Conditional Updating Salp Swarm Algorithm,LECUSSA),首先利用Levy飛行策略的長短跳躍特點(diǎn)隨機(jī)更新領(lǐng)導(dǎo)者位置,以此提升算法的全局搜索能力,再增加追隨者位置更新判定條件,減少追隨者位置更新的盲目性.

雖然改進(jìn)算法都在不同程度上提升了算法性能,但經(jīng)過試驗(yàn)發(fā)現(xiàn),采用萊維飛行進(jìn)行隨機(jī)擾動時,算法的整體時長有所增加.針對此問題以及追隨者位置更新的盲目性,本文提出了一種基于混沌映射動態(tài)慣性權(quán)重的樽海鞘群算法,首先利用混沌映射在搜索空間中生成分布均勻的樽海鞘群初始位置序列,計(jì)算個體適應(yīng)度,保留適應(yīng)度最高的個體作為初始食物源位置;引入瘋狂算子對領(lǐng)導(dǎo)者位置進(jìn)行更新擾動,避免算法過早陷入局部最優(yōu);最后,對適應(yīng)度值高于種群平均適應(yīng)度值的個體通過引入非線性慣性權(quán)重,對其進(jìn)行動態(tài)更新,低于平均值的個體則通過柯西擾動進(jìn)行位置更新.在求解12個標(biāo)準(zhǔn)測試函數(shù)的最優(yōu)解問題方面,通過與其他7個優(yōu)化算法對比,有效驗(yàn)證了本文改進(jìn)算法的有效性.

2 基于混沌映射動態(tài)慣性權(quán)重的SSA算法

2.1 基于混沌映射的種群初始化策略

樽海鞘群初始位置對于食物源位置的搜索具有一定影響,原始SSA是在搜索空間中隨機(jī)生成位置序列,單梁等人[13]發(fā)現(xiàn)并提出當(dāng)初始位置序列均勻分布在搜索空間時,能有效提升算法尋優(yōu)性能.混沌映射可以在[0,1]區(qū)間內(nèi)生成混沌序列,并將其轉(zhuǎn)化到群海鞘個體的搜索空間,使得個體位置在搜索空間內(nèi)能夠較為均勻的分布,計(jì)算方法如下:

(1)

(2)

2.2 基于瘋狂算子的領(lǐng)導(dǎo)者位置更新策略

因領(lǐng)導(dǎo)者的位置更新受食物源的影響,而食物源的位置更新則是根據(jù)樽海鞘群最優(yōu)適應(yīng)度來進(jìn)行更新,所以當(dāng)有一方陷入局部最優(yōu)時,另一方也會隨之受到影響.因此,本文將瘋狂算子[14]引入領(lǐng)導(dǎo)者位置更新公式中,通過對增加食物源位置變化的意外性來提升種群搜索的多樣性.基于瘋狂算子的領(lǐng)導(dǎo)者位置更新公式如下所示:

(3)

(4)

(5)

其中,r1,r2,r3,r4為(0,1)區(qū)間內(nèi)均勻分布的隨機(jī)數(shù),FPj為第t次迭代食物源的位置,C=0.0001,AC為瘋狂概率,本文取值0.3.為了使得算法搜索具有更好的全局性,本文選取一半數(shù)量的樽海鞘個體作為領(lǐng)導(dǎo)者[11].

2.3 基于精英保留及動態(tài)慣性權(quán)重的追隨者位置更新策略

原始SSA算法追隨者的位置更新是基于當(dāng)前個體的前一個樽海鞘個體位置,在算法后期,食物源的搜索應(yīng)逐漸縮小范圍,即,當(dāng)前個體的位置更新受前一個個體的影響應(yīng)隨著迭代次數(shù)的增加而減少.因此本文在此基礎(chǔ)上增加了非線性遞減慣性權(quán)重參數(shù),且對追隨者采用了精英保留策略,對適應(yīng)度值高于種群平均適應(yīng)度值的個體采用帶有慣性權(quán)重的公式進(jìn)行更新,對低于種群平均適應(yīng)度的個體進(jìn)行柯西擾動,以此增加種群的多樣性.改進(jìn)后的追隨者位置更新公式如下:

(6)

ω(t)=ω0+(ωE-ω0)exp(-(εt/Iter_max)2)

(7)

2.4 改進(jìn)算法流程

改進(jìn)算法具體步驟如下:

Step 1.初始化種群參數(shù).初始化種群個數(shù)N,最大迭代次數(shù)Iter_max,混沌參數(shù)γ,利用式(2)生成初始種群,計(jì)算初始種群適應(yīng)度,選取適應(yīng)度最優(yōu)的個體作為食物源位置;

Step 2.更新種群個體位置.將種群均分為兩部分,前半部分個體作為領(lǐng)導(dǎo)者,使用式(3)進(jìn)行更新,后半部分作為追隨者,并對追隨者進(jìn)行精英保留計(jì)劃,對適應(yīng)度低于平均值的個體進(jìn)行柯西擾動,高于平均值的個體采用式(6)中基于慣性權(quán)重的更新策略;

Step 3.計(jì)算種群適應(yīng)度,尋找適應(yīng)度最優(yōu)的個體以更新食物源位置;

Step 4.判斷是否滿足迭代次數(shù)要求,若是,則進(jìn)行下一步,否則返回Step 2;

Step 5.輸出最優(yōu)個體的適應(yīng)度值.

3 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文提出的算法(本文將改進(jìn)算法縮寫為ISSA)在求解優(yōu)化問題上的有效性和魯棒性,將ISSA算法與鯨魚優(yōu)化算法(Whale Optimization Algorithm,WOA)[15]、正弦余弦算法(Sine Cosine Algorithm,SCA)[16]、蝴蝶優(yōu)化算法(Butterfly Optimization Algorithm,BOA)[17]、LSSA、LECUSSA、CASSA和SSA在12個典型的標(biāo)準(zhǔn)測試函數(shù)[18,19]進(jìn)行了50次獨(dú)立實(shí)驗(yàn),以求解最優(yōu)值.12個函數(shù)中具有單峰、多峰等不同特征,各函數(shù)數(shù)學(xué)表達(dá)式、維度、搜索空間以及函數(shù)最小值如表1所示.

表1 標(biāo)準(zhǔn)測試函數(shù)Table 1 Standard test functions

其中,單次實(shí)驗(yàn)最大迭代次數(shù)為1000,種群個數(shù)為30,各算法主要參數(shù)如表2所示.

表2 參數(shù)設(shè)置Table 2 Parameter settings

在50次獨(dú)立重復(fù)實(shí)驗(yàn)后,計(jì)算出各算法所求最優(yōu)解的均值(mean)、最小值(min)、標(biāo)準(zhǔn)差(std)、求解成功率(SR)和平均耗時(time)結(jié)果如表3所示.求解成功率為計(jì)算50次獨(dú)立重復(fù)實(shí)驗(yàn)中算法所求最優(yōu)解為對應(yīng)正解的總次數(shù)除以總實(shí)驗(yàn)次數(shù),其中,判斷單次求解是否成功的計(jì)算公式如下所示[3]:

(8)

其中,fA為算法單次實(shí)驗(yàn)實(shí)際求出的最佳值,fT為標(biāo)準(zhǔn)測試函數(shù)的理論最佳值.

從表3可以看出,本文改進(jìn)算法因?yàn)樵黾恿诵碌乃阕?所以比原算法耗時更長一點(diǎn),12個標(biāo)準(zhǔn)測試函數(shù)中,本文算法只有F6的成功率稍低,其余均是100%的成功率.從表中可以看出,LSSA和LECUSSA成功率雖高,但卻因?yàn)槿谌肓巳R維飛行策略使得算法整體耗時增加;SCA的耗時雖少,但穩(wěn)定性稍差;融入了瘋狂算子的CASSA在性能和耗時上表現(xiàn)良好,但F4的成功率較低.所以從整體上來看,ISSA算法從性能和耗時角度綜合來看,均優(yōu)于其余7個比較算法.

表3 標(biāo)準(zhǔn)測試函數(shù)結(jié)果對比Table 3 Comparison of standard test function results

為了進(jìn)一步的驗(yàn)證改進(jìn)算法的性能,通過計(jì)算所有算法的平均絕對誤差(Mean Absolute Error,MAE)來進(jìn)行定量分析[20],表4為MAE結(jié)果對比,其計(jì)算公式如下:

(9)

其中,avg_Ai為算法最優(yōu)解的平均值,Fi為對應(yīng)標(biāo)準(zhǔn)測試函數(shù)的理論最優(yōu)解,NF為標(biāo)準(zhǔn)測試函數(shù)個數(shù),本文為12.

從表4可以看出,除了對比CASSA算法優(yōu)勢不夠明顯,與其他6個算法相比,本文算法提供了最小的MAE,進(jìn)一步證明了改進(jìn)算法的有效性.

表4 MAE結(jié)果對比Table 4 Comparison of MAE results

圖1為12個標(biāo)準(zhǔn)函數(shù)的平均適應(yīng)度進(jìn)化曲線,為了使得對比結(jié)果更加清晰,圖中橫坐標(biāo)只顯示了算法前100次的迭代情況,實(shí)際迭代次數(shù)為1000次.

圖1 標(biāo)準(zhǔn)測試函數(shù)平均適應(yīng)度進(jìn)化曲線Fig.1 Average fitness curve of standard test function

從圖1中可以看出,本文算法能夠更快速的完成迭代,SCA的適應(yīng)度變化雖然也呈現(xiàn)較好的算法性能,與表3的數(shù)據(jù)結(jié)果一致,但從圖1(c)可以看出,SCA算法的穩(wěn)定性稍差.原始的SSA則陷入了局部最優(yōu),因?yàn)楸疚脑黾恿睡偪袼阕雍涂挛鲾_動,使得算法有效地避免了陷入局部最優(yōu).

4 結(jié) 論

為提升群海鞘群算法求解精度和收斂速度,提出了基于混沌映射動態(tài)慣性權(quán)重的群海鞘群算法.該算法首先利用Tent混沌序列完成種群的初始化,再通過引入的瘋狂算子完成對領(lǐng)導(dǎo)者的位置更新,提出了基于精英保留及動態(tài)慣性權(quán)重的追隨者位置更新策略,使得算法能夠保留優(yōu)質(zhì)追隨者個體,并利用柯西擾動策略豐富了追隨者的多樣性.通過與WOA、SCA、BOA、LSSA等算法對比,驗(yàn)證了本文改進(jìn)算法在收斂速度和求解精度上效果更好,雖然改進(jìn)算法擁有較好的求解精度,但因增加了新的算子,使得算法時間略高于原始算法,未來將繼續(xù)深入研究各種群優(yōu)化算法,使得改進(jìn)算法能夠有效平衡求解精度與時間復(fù)雜度.