基于天體運(yùn)動更新機(jī)制的改進(jìn)樽海鞘群算法

張文彬

(上海電力大學(xué) 自動化工程學(xué)院, 上海 200090)

樽海鞘群算法(Salp Swarm Algorithm,SSA)是2017年由MIRJALILI S等人[1]提出的一種新的智能算法。作為一種元啟發(fā)式算法,SSA具有收斂速度快、設(shè)定參數(shù)少、簡單易懂等優(yōu)點(diǎn),但也存在易陷入局部極值點(diǎn)、收斂精度不高等問題。目前,已有學(xué)者對該算法進(jìn)行了改進(jìn)并應(yīng)用于相關(guān)研究。文獻(xiàn)[2]引入了評估移動策略來增強(qiáng)算法的開發(fā)能力,并成功用于永磁同步電機(jī)的多參數(shù)辨識;文獻(xiàn)[3]通過引入levy飛行機(jī)制來提高算法的全局搜索能力,并用于多閾值圖像分割時的優(yōu)化;文獻(xiàn)[4]結(jié)合了混沌精英質(zhì)心拉伸機(jī)制,有效地提高了SSA的收斂速度和收斂精度;文獻(xiàn)[5]用Tent映射來初始化種群個體,并在食物源的位置中加入“瘋狂”算子,提高了算法的開發(fā)能力。本文在SSA中引入天體運(yùn)動算子來提高算 法的開發(fā)能力,并通過7個常用的算法測試函數(shù)驗證改進(jìn)算法的有效性。

1 樽海鞘群算法

1.1 基本原理

SSA的思想來源于樽海鞘聚集成一條鏈?zhǔn)降男袨?即前后個體之間相互影響。將樽海鞘群中的個體劃分為領(lǐng)導(dǎo)者和追隨者,其中領(lǐng)導(dǎo)者在鏈的前端,對周圍的環(huán)境有更好的判斷。SSA的具體運(yùn)算步驟如下[6]。

1.1.1 種群的隨機(jī)初始化

設(shè)種群總數(shù)為N,其中領(lǐng)導(dǎo)者個數(shù)為Nl,追隨者個數(shù)為Nf,解空間維數(shù)為D維,搜索空間的上限和下限分別為:ub=[ub1ub2ub3…ubD]和lb=[lb1lb2lb3…lbD],那么樽海鞘個體的位置可以表示為xi=[x1x2x3…xD]。

1.1.2 領(lǐng)導(dǎo)者的位置更新

對第i個領(lǐng)導(dǎo)者在第j維上的位置進(jìn)行更新,表達(dá)式為

(1)

(2)

式中:Fj——目標(biāo)食物的位置;

c2,c3——隨機(jī)產(chǎn)生的數(shù),范圍均為[0,1];

t,tmax——當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

參數(shù)c1的值對于算法的開發(fā)和探索能力的平衡起著至關(guān)重要的作用。由式(2)可以看出c1的值由2遞減到0。

1.1.3 追隨者的位置更新

對第i個追隨者在第j維上的位置進(jìn)行更新,表達(dá)式為

(3)

式中:a——加速度;

t0——時間;

v0——初始速度。

(4)

1.2 算法改進(jìn)

天體運(yùn)動更新的思想來自于天體物理學(xué)中行星繞太陽運(yùn)動的軌跡[7]。本文將這一思想與SSA結(jié)合,得到天體運(yùn)動更新的樽海鞘群算法(Astrophysics-inspired Salp Swarm Algorithm,ASSA)。其具體改進(jìn)方法如下。

從N個種群中隨機(jī)選擇k個樽海鞘個體,讓這k個個體圍繞當(dāng)前種群中最優(yōu)的個體來更新位置,其更新表達(dá)式為

Yi,new=Ybest+Ri,bestU(-2,2)

(5)

式中:Yi,new——被選擇的個體更新后的位置;

Ybest——當(dāng)前最優(yōu)個體;

Ri,best——個體i與最優(yōu)個體間的距離;

U(-2,2)——區(qū)間[-2,2]內(nèi)的隨機(jī)數(shù),與參數(shù)c1的變化相對應(yīng)。

同時,最優(yōu)個體也更新其自身位置,更新公式為

Ybest,new=YbestU(-2,2)

(6)

將更新后的位置與原位置相比,選擇適應(yīng)度較好的作為最終更新位置,即

(7)

改進(jìn)后的樽海鞘群算法流程如圖1所示。

圖1 ASSA的流程示意

2 實驗分析

文獻(xiàn)[4-5]中為了驗證所提出的改進(jìn)算法的有效性,將其與其他智能算法對基準(zhǔn)函數(shù)進(jìn)行了多次獨(dú)立重復(fù)實驗,并最終比較了各個算法的最佳值(Best)、平均值(Mean)、標(biāo)準(zhǔn)差(Standard Deviation,Std),以及算法的成功率(Success Rate,SR)。為了驗證本文所提出的ASSA的有效性,對7個常用的測試函數(shù)進(jìn)行最小值尋優(yōu)仿真,并將結(jié)果與SSA、蟻獅算法(Ant Lion Optimization,ALO)[8-9]、灰狼優(yōu)化算法(Gray Wolf Optimization,GWO)[10-11]、粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)進(jìn)行比較,測試函數(shù)的詳細(xì)信息如表1所示。其中,U表示單峰,M表示多峰,S表示可分,N表示不可分。

表1 測試函數(shù)信息

為了避免單次測試帶來的偶然性影響,對每個函數(shù)進(jìn)行30次獨(dú)立實驗,比較每種算法結(jié)果的最佳值、平均值、標(biāo)準(zhǔn)差和算法的成功率。判斷每次試驗是否成功的公式為

(8)

式中:FA——每次實際求解最佳值;

FT——測試函數(shù)理論最佳值。

算法參數(shù)設(shè)置如下:上述4種算法的種群數(shù)N=30;最大迭代次數(shù)tmax=200;PSO算法的慣性權(quán)重和學(xué)習(xí)因子分別為w=1,c1,PSO=c2,PSO=1.5[4];SSA和ASSA中領(lǐng)導(dǎo)者個數(shù)Nl和追隨者個數(shù)Nf設(shè)成Nl=Nf[2,12-13],且Nl=Nf=N/2=15;ASSA中k=15%×N≈5。

表2為5種算法的實驗結(jié)果。其中,最優(yōu)值和平均值這兩個指標(biāo)能夠很好地反映算法的收斂精度,而收斂精度的高低在很大程度上決定了算法的優(yōu)劣。由表2可以看出,對于單峰函數(shù)f1～f4,ASSA的收斂精度非常高,達(dá)到了1.0×10-50以上,而SSA對這4種函數(shù)的尋優(yōu)最優(yōu)值均較大,其中對函數(shù)f3的尋優(yōu)值甚至超過890,具有較大的誤差。由此可見,ASSA能夠改善SSA存在的收斂精度不高的問題。對于多峰函數(shù)f6,ASSA的收斂精度達(dá)到了1.0×10-16,遠(yuǎn)高于其他4種算法(GWO的收斂精度為1.0×10-5,PSO為2.7,SSA為5,ALO為8),滿足了算法的精度要求。對于多峰函數(shù)f5和f7,ASSA收斂到了理論上的最優(yōu)值零,這是其他算法所不能比擬的。

標(biāo)準(zhǔn)差和成功率能夠反映算法的穩(wěn)定性。ASSA的標(biāo)準(zhǔn)差遠(yuǎn)小于其他4種算法,采用ASSA優(yōu)化的7個基準(zhǔn)函數(shù)的標(biāo)準(zhǔn)差基本保持在1.0×10-30,SSA的標(biāo)準(zhǔn)差在1～200,GWO的標(biāo)準(zhǔn)差最好的也只有1.0×10-8。由此可以看出,ASSA對于不同函數(shù)的運(yùn)算結(jié)果的穩(wěn)定性比其他算法要好。對7個基準(zhǔn)測試函數(shù),在規(guī)定的200次迭代次數(shù)內(nèi),ASSA優(yōu)化結(jié)果的成功率都是100%,而其他算法如GWO在對函數(shù)f3～f5時均難以達(dá)到100%,PSO和SSA的成功率甚至為零。

以上是基于30次獨(dú)立運(yùn)行的平均值、標(biāo)準(zhǔn)差的對比實驗,無法反映每一次運(yùn)行時各個算法之間的差異。文獻(xiàn)[14]提出,應(yīng)該對改進(jìn)的算法進(jìn)行統(tǒng)計性檢驗,以驗證其是否具有明顯優(yōu)勢。

因此,本文在5%顯著性水平下進(jìn)行了Wilcoxon秩和檢驗。在7個基準(zhǔn)測試函數(shù)下,5種算法在Wilcoxon秩和檢驗中求得的p-value值如表3所示。將每個函數(shù)的最佳算法的值標(biāo)記為N/A,以符號“+,=,-”分別表示ASSA的性能優(yōu)于、等于和劣于相比較的算法。

文獻(xiàn)[14]指出,p-value值小于0.05就可以被認(rèn)為是拒絕秩和假設(shè)。由表3可以看出,與其他算法相比,ASSA的p-value值均小于0.05,可以認(rèn)為在統(tǒng)計上ASSA比其他算法更具優(yōu)越性,即ASSA具有更高的收斂精度。

文獻(xiàn)[15]提出了一個有效并且可行的判別算法性能的指標(biāo),即為平均絕對誤差(Mean Absolute Error,MAE)。其計算公式為

表2 各個算法的結(jié)果對比

表3 7個基準(zhǔn)函數(shù)下5種算法的Wilcoxon秩和檢驗的pvalue值

(9)

式中:mi——算法多次獨(dú)立測試后得到的最優(yōu)結(jié)果的平均值;

Nb——測試函數(shù)的個數(shù);

oi——測試函數(shù)的理論最優(yōu)值。

本文同樣用MAE來鑒別5種算法的優(yōu)劣性,其結(jié)果如表4所示。

表4 5種算法的MAE排名

由表4可以看出,ASSA的MAE值最小,幾乎為零,遠(yuǎn)遠(yuǎn)小于SSA算法的MAE值524,再一次驗證了ASSA算法的優(yōu)越性。

圖2是5種算法對不同基準(zhǔn)測試函數(shù)的平均收斂曲線。其中,ASSA在函數(shù)f5和函數(shù)f7的尋優(yōu)過程中達(dá)到了最優(yōu)值為零,故ASSA曲線的后面部分沒有顯示。

圖2 不同基準(zhǔn)測試函數(shù)下5種算法的平均收斂曲線

由圖2可以看出,對于7個基準(zhǔn)函數(shù),ASSA的收斂速度很快,并且在200次的迭代中并沒有出現(xiàn)陷入局部極值點(diǎn)的現(xiàn)象。其他4種算法的收斂速度遠(yuǎn)遠(yuǎn)不及ASSA,并且在迭代后期曲線平緩,下降速度慢,容易陷入局部極值點(diǎn)。對于函數(shù)f1,函數(shù)f3和函數(shù)f4,ASSA均以非?？斓乃俣仁諗?而SSA,GWO,ALO的收斂速度十分緩慢,PSO則容易陷入局部極值點(diǎn);對于函數(shù)f2,PSO,SSA,ALO分別在迭代到18次、20次和100次左右便陷入局部極值;對于函數(shù)f5和f7,ASSA經(jīng)不到100次迭代就達(dá)到了理論最優(yōu)值,而其他3種算法依舊收斂速度緩慢,且最終精度也不高。

不論是針對單峰還是多峰函數(shù),ASSA的收斂速度都很快,且收斂精度高。

3 結(jié) 語

本文在SSA的基礎(chǔ)上,隨機(jī)選取部分個體圍繞全局最優(yōu)個體進(jìn)行位置更新,以探索最優(yōu)個體附近的區(qū)域。通過7個基準(zhǔn)測試函數(shù)對ASSA的性能進(jìn)行檢驗,結(jié)果表明,ASSA的最優(yōu)值、平均值、標(biāo)準(zhǔn)差等各項指標(biāo)都十分優(yōu)異,與SSA算法相比,其性能有了極大的提高。