多策略融合的黃金正弦樽海鞘群算法

丁美芳 吳克晴 肖鵬

樽海鞘群算法;選擇反向學習;精英均值;黃金正弦算法

0 引言

優化問題在人工智能領域和現實生活中普遍存在,一直以來備受學者關注.元啟發式優化算法機制靈活,僅需改變部分參數或搜索策略便可運用于各類優化問題,兼容性很高.近幾十年來,學者們提出了許多元啟發式優化算法,例如粒子群優化算法(Particle Swarm Optimization,PSO)[1]、鯨魚優化算法(Whale Optimization Algorithm,WOA)[2]、郊狼優化算法(Coyote Optimization Algorithm,COA)[3]、哈里斯鷹優化算法(Harris Hawks Optimization,HHO)[4]、黑猩猩優化算法(Chimp Optimization Algorithm,ChOA)[5]等.

樽海鞘群算法(Salp Swarm Algorithm,SSA)是一種新型元啟發式優化算法,由Mirjalili等[6]于2017年首次提出.相較于其他群智能優化算法,樽海鞘群算法具有結構簡單、參數少、易于實現等優點.自提出以來,該算法被廣泛應用于無源時差定位[7]、PMSM參數辨識[8]、圖像分割[9]、特征選擇[10]、訓練神經網絡[11]、網頁排名[12]等多個領域.

然而,同其他群智能優化算法一樣,樽海鞘群算法仍存在收斂速度慢、容易陷入局部最優[13]等問題.為此,國內外學者做了一些改進:文獻[13]采用折射反向學習產生動態候選解,同時在跟隨者階段引入非線性遞減的自適應控制因子,提升算法開采能力;文獻[14]將Sigmoid函數的擾動參數應用于領導者位置更新的概率參數中,增強種群多樣性,提升算法的勘探能力;文獻[15]在領導者位置更新階段引入瘋狂算子,并通過一定概率隨機擾動食物源的位置,從而維持領導者個體的多樣性;文獻[16]在領導者位置更新階段引入控制搜索范圍的非線性衰減因子,有利于算法在前期跳出局部最優;文獻[17]采用平方指數和高斯模型相結合的方法,將平方指數策略引入領導者位置更新,增強了算法的收斂性能;文獻[18] 提出一種基于慣性權重和領導者-跟隨者自適應調節方法,實現了對全局搜索和局部搜索的優化,從而大大提高了尋優精度.

上述改進算法雖然都在一定程度上改善了基本SSA的性能,但是對一些復雜度較高、規模較大的問題,算法的收斂速度和穩定性仍有改進的空間.因此,本文提出一種多策略融合的黃金正弦樽海鞘群算法(Golden sine Salp Swarm Algorithm with Multi-strategy,MGSSA).首先,在初始階段引入選擇反向學習策略,豐富種群多樣性,改善初始解的質量.其次,將最優個體和精英均值個體引入跟隨者位置更新階段,增強整個種群之間的信息交互能力,使跟隨者位置在迭代初期更側重于跟隨全局最優個體,加快收斂速度,在迭代后期更側重于相鄰個體之間的交流,提升局部開采能力.該策略很好地平衡了算法的全局勘探和局部開采能力.最后,融合黃金正弦算子和判定參數對個體位置進行變異,強化算法跳出局部極值的能力.理論分析證明了本文提出的算法并未增加算法的時間復雜度,同時選取14個基準測試函數進行數值比較實驗,結果表明,在SSA中融合上述改進策略提升了SSA的收斂精度和穩定性,從而提高了算法性能.將MGSSA應用于拉壓彈簧工程問題,取得了較好的結果.

1 樽海鞘群算法

樽海鞘群算法[6]模擬了自然界中樽海鞘群以鏈式結構進行捕食的過程.該算法分為領導者位置更新和跟隨者位置更新兩個部分.算法將每一代的最優個體設為領導者,其余個體均為跟隨者.

與其他群智能優化算法類似,在求解問題時,樽海鞘群個體在D×N的空間中展開搜索,其中,D為給定問題的變量數,N為種群數量.這樣,樽海鞘群個體位置就被存儲在一個稱為X的二維矩陣中,空間中樽海鞘群的位置用Xn=[Xn1,Xn2,…,XnD]T表示,在搜索空間中有一個名為F的食物源位置用Fn=[Fn1,Fn2,…,FnD]T表示.

(1)

(2)

其中:t為當前迭代次數;T為最大迭代次數.

在基本的樽海鞘群算法中,每個跟隨者更新的位置只與其歷史位置以及前一名個體的位置有關.其位置更新公式如下:

(3)

2 改進樽海鞘群算法(MGSSA)

在基本SSA中,每次迭代通常取上一次迭代的最優個體作為整個種群的領導者,其余個體均為跟隨者.由于領導者數目單一,種群進化方向趨同,整個算法的全局勘探能力較弱,在求解復雜問題時,容易陷入局部最優.同時,基本SSA中跟隨者的位置更新僅與和它相鄰的個體位置有關,這在一定程度上限制了算法的收斂速度以及搜索方向.為改善基本SSA算法存在的問題,本文提出以下改進策略:

1)提出一種選擇反向學習策略,提高種群質量,同時協助種群在搜索后期跳出局部最優;

2)針對算法收斂速度慢的問題,在跟隨者位置更新階段引入最優個體和精英均值個體引導,吸收更多優質個體的有利信息;

3)根據不同的變異概率,選取不同的黃金正弦變異策略,使算法在前期以較大概率向群體均值方向前進,加快算法尋優速度,后期側重挑選隨機個體進行周邊搜索,便于跳出局部最優.

2.1 選擇反向學習策略

反向學習(Opposition-Based Learning,OBL)的基本概念最初是由Tizhoosh[19]提出的,其主要思想是通過同時比較當前位置的目標函數值及其相反位置的目標函數值,保留兩者中的適應度值更優的點,從而擴大搜索范圍.目前已經有許多研究將反向學習策略融入到智能優化算法中,算法的求解性能均有所增強[20].

選擇反向學習(Selective Opposition-Based Learning,SOBL)是一種由反向學習啟發的新型算法改進策略,其主要思想是通過將兩個體間各維度位置的距離與給定的閾值進行比較,在遠距離維數大于近距離維數的情況下,選擇距離大于閾值的維度進行反向學習,從而提高個體解的質量.SOBL近年來被應用于改進灰狼優化算法[21],且經過實驗證實對算法性能的改善有正向促進作用.本文將其應用于樽海鞘群算法改善搜索性能.SOBL基本原理如圖1所示.

圖1 SOBL原理示意圖Fig.1 Principle diagram of SOBL

在圖1中,假設有一個三維空間,(a,b,c)是食物源的位置,五角星的位置為問題最優解的位置,(a′,b′,c′)是(a,b,c)的完全相反點.最優解位置與(a,b,c)和(a′,b′,c′)的距離分別為d1和d3.同時假設(a′,b′,c)是(a,b,c)僅前二維相反的點(選擇性相反),其與解的距離為d2.從圖1中可以看出,d2

在介紹選擇反向的具體實現步驟前,需要先了解斯皮爾曼相關系數.

2.1.1 斯皮爾曼系數

斯皮爾曼相關性分析是一種查找兩個序列之間的統計相關性的方法(此處為兩個尋優個體的位置).假設有兩個序列k1,k2,k3,…,kn和l1,l2,l3,…,ln,令di=ki-li,i=1,2,…,n,則兩者間的斯皮爾曼相關系數[22]為

(4)

其中,n為序列維度.在每次迭代之后,根據食物源的位置計算每個個體的斯皮爾曼系數.若相關系數為負,則表明該個體位置與食物源位置相反,繼續朝該方向開采獲得更有益信息的概率相對較小,進行反向學習可以加大尋找到有益信息的概率;反之,若相關系數為正,則表明該個體位置與食物源位置一致,繼續朝該方向搜索有利于挖掘更多有益信息,因而無需進行反向學習.總體而言,使用斯皮爾曼系數有助于選擇需要反向學習的個體,減少不必要的個體反向操作.

2.1.2 選擇反向學習機制

對每個斯皮爾曼系數小于零的個體,給定一個閾值a,其計算公式如下:

(5)

其中:t為算法當前迭代次數;T為算法最大迭代次數.閾值a是隨迭代次數線性減少的,該值確定該個體位置是否接近食物源.對于當前個體和食物源的每個維度j,使用式(6)計算它們之間的差值:

D(j)=|X(j)-F(j)|,

(6)

其中:X(j)為當前個體第j維位置;F(j)為食物源第j維位置.如果差值D(j)大于閾值a,則差值較大的維數gno將增加.設總維數為n.若(n-gno)

(7)

選擇反向學習與傳統反向學習相比,優點在于:用斯皮爾曼系數篩選與食物源位置相反的個體進行反向,保留了相對優質個體的同時減少計算量,通過閾值決定反向的維度,細化反向的方向,使個體搜索更靠近最優方向.

2.2 引入最優個體和精英均值個體的跟隨者位置更新

在基本的樽海鞘群算法中,除了一個領導者之外,其余的都是跟隨者.跟隨者的搜索方向僅和自身位置及與它相鄰的個體位置有關,這在一定程度上影響了算法的收斂速度及搜索方向.為了使跟隨者能更快地搜索到有益信息,本文設計了一種受種群最優個體和精英群均值個體影響的跟隨者搜索策略.

文獻[23]提出一種自適應領導者結構,本文在此基礎上提出由1自適應增加到N/2的線性精英群.每次迭代的精英種群數量如下:

m=「(t/T)×(N/2)?,

(8)

(9)

引入種群最優個體和精英均值個體位置更新公式如下:

(10)

其中,c1更新參照式(2).

在迭代初期,個體搜索比較盲目,此時跟隨者的位置更新融合了種群最優個體和精英群均值個體位置,可以使跟隨者在前期開發出更多更好的解.而在算法后期,隨著參數c1的逐漸減小,精英個體對跟隨者的影響也會更小,而且此時種群搜索范圍也更小,即使是跟隨者,蘊含的有益信息量也很大,此時削弱精英個體的影響,對于整個算法而言,可以拓寬算法的勘探能力,這種機制有助于算法在迭代后期跳出局部最優.

2.3 黃金正弦算子變異策略

黃金正弦算法是2017年由Tanyildizi等[24]提出的新型智能算法.受正弦函數啟發,黃金正弦算法取黃金分割數使粒子在更優的搜索范圍進行尋優,加快了算法的收斂速度.選取的黃金正弦算子具體公式如下:

Xi(t+1)=Xi(t)|sinR1|+

R2sin(R1)|aXbest-bXi(t)|,

(11)

其中:R1為0到2π的隨機數,決定個體i下一代位置更新的移動步長;R2為0到π的隨機數,決定個體i下次更新的方向;a和b為黃金分割系數,影響著粒子的搜索空間,對搜索空間進行了一個更優的選擇,引領粒子趨近于更優值.計算公式如下:

a=-π(1-τ)+πτ,

b=-πτ+π(1-τ),

(12)

本文利用黃金正弦算子的優勢,對樽海鞘群算法個體進行變異,打開更優的搜索空間,向更優解靠攏.為避免陷入局部最優,分概率采用均值策略和隨機策略選取粒子進行變異操作.具體公式如下:

(13)

為了防止過早收斂并達到全局最優,需要在勘探和開采之間保持良好的平衡,這種平衡就是通過參數p實現的.在算法迭代前期,種群相對分散,精英均值個體蘊含較多有利信息,在周邊搜尋可以加快收斂速度,而此時c1較大,也使得在精英均值個體周圍搜索的概率更大.隨著種群不斷進化,后期p>c1/2的概率更大,算法更多在隨機選擇的個體周圍進行搜索,有利于跳出局部最優.

在進行黃金正弦變異后,將變異后的個體適應度值與原種群對應個體適應度值對比,保留適應度值小的,更新其位置.

2.4 MGSSA算法偽代碼

MGSSA算法偽代碼如下:

1)設置種群規模N,維數D,最大迭代次數T

2)隨機初始化種群{xi,i=1,2,…,N}

3)計算初代種群適應度并排序,記錄當前最優個體位置FoodPosition

4)Whilet≤T

5)根據式(5)更新閾值a

6)篩選種群進行選擇反向學習,計算適應度,比較學習后個體與之前的個體的適應度值大小,選更小的個體作為新的位置

7)fori=1 toN

8)if (i==1)

9)根據式(1)更新領導者個體位置

10)else

11)根據式(10)更新跟隨者位置

12)end

13)更新變異概率p

14)ifp≤c1/2

15)根據式(13)對每個個體xi位置進行變異

16)else

17)根據式(13)對每個個體xi位置進行變異

18)end

19)end

20)計算每個個體的適應度值,更新FoodPosition

21)end while

22)輸出最優位置FoodPosition及其適應度值FoodFitness

2.5 時間復雜度分析

在基本的SSA中,假設樽海鞘群種群規模為N,解空間為n維,求解目標函數所需的執行時間為f(n).根據文獻[18],SSA算法的時間復雜度為

T(n)=O(n+f(n)).

在MGSSA算法中,參數初始化執行時間η0,每維生成隨機數時間η1,求解目標函數執行時間f(n)對適應度值排序時間為η2,則初始化階段時間復雜度為

T1=O(η0+N(nη1+f(n)+η2)=

O(n+f(n)).

進行選擇反向學習階段,根據式(5)計算閾值a時間為η3,根據式(6)計算每個跟隨者與食物源之間的距離所需時間為η4,根據式(4)根計算對應斯皮爾曼系數時間為η5,假設斯皮爾曼系數為負的個體數為n0(n0

T2=O(η3+N(nη4+η5)+n0nη6)=O(n),

在領導者位置更新階段時間復雜度為

T3=O(n).

在跟隨者位置更新階段,跟隨者數目為N-1,設由式(10)對跟隨者每一維進行更新的時間為η7,則這一階段的時間復雜度為

T4=O((N-1)nη7)=O(n).

在黃金正弦算子變異階段,生成變異概率p時間為η8,根據式(13)對每個個體變異的時間為η9,則這一階段時間復雜度為

T5=O(η8+Nnη9)=O(n).

在邊界處理和更新食物源位置階段,時間復雜度與基本SSA一致,為

T6=O(n+f(n)).

綜上可得MGSSA算法的總時間復雜度為

T(n)=T1+T(T2+T3+T4+T5+T6)=

O(n+f(n)).

由此可知,MGSSA與基本SSA相比,并未增加時間復雜度.

3 實驗仿真及結果分析

3.1 仿真實驗設計及實驗環境

為了評估 MGSSA的性能,實驗從文獻[25]中選取了14個基準測試函數,包括7個單峰函數f1～f7和7個多峰函數f8～f14,在表1中列出了各函數的名稱及其他相關屬性.將MGSSA與14種算法進行比較,包括3種單策略改進算法、6種最近幾年提出的SSA改進算法和5種群智能優化算法.最后將改進算法應用于工程約束優化問題探究其求解效果.為了驗證數值的有效性,對14個基準函數運行30次的MGSSA和其他比較算法的結果進行非參數Wilcoxon秩和檢驗,根據每次運行獲得的均值,對實驗結果進行統計分析,幫助判斷各算法與最優算法之間是否具有顯著性差異,從而更好地評判算法的性能.其中顯著性水平校正為0.05,將均值最小的算法視為最優算法,記作NA.若均值相同,則認為標準差越小的算法越好.若p值小于0.05,則認為該算法與最優算法存在顯著性差異,若大于0.05,則該算法與最優算法無顯著性差異.符號“+”表示提出的算法得到的結果優于比較算法,而 “-”表示提出的算法得到的結果相較于比較算法更差,符號“=”表明彼此間沒有顯著差異.因此表中 “+/=/-”行給出算法在14個基準函數上優/等/劣的個數.所有實驗都是在操作系統為Windows 11的PC機上用Matlab2019a軟件實現的,PC機配置AMD R5 3500U處理器,主頻 2.10 GHz CPU,內存8 GB.

表1 基準測試函數

3.2 改進策略分析

為探究不同策略對算法改進的影響程度,對僅添加精英均值個體策略的改進算法ESSA,僅融合黃金正弦變異的算法GSSA和加入選擇反向學習策略的算法SOSSA與 MGSSA進行對比實驗.

4種算法獨立運行30次的統計結果如表2所示,部分函數收斂曲線如圖2所示.可以看出,在14個函數中,ESSA、GSSA和MGSSA分別在3、9、14個函數中尋到了最優,而SOSSA在14個函數的求解效果均差于其他3種算法.這表明黃金正弦融合策略與精英均值個體對標準SSA的改進起較大作用,選擇反向學習策略對標準SSA的改進幫助較弱.通過圖2也可以發現,與標準SSA相比,選擇反向學習策略在求解單峰函數時,雖然收斂效果方面的提升并不明顯,但在一定程度上改善了算法的求解精度.因此,將其用于算法開始,改善種群多樣性十分合適.同時可以看出在函數f12收斂曲線中,GSSA在200代左右就陷入了局部停滯,而MGSSA在800代左右仍然可以跳出局部最優,進一步尋找更優解,其搜索性能明顯更佳.綜合表2數據,MGSSA在14個函數上表現均優其他3種單策略改進算法,這表明將3種策略融合求解問題可以有效提升算法的求解性能.

表2 不同改進策略實驗測試結果

圖2 不同策略函數收斂曲線Fig.2 Convergence curves of different strategy functions

3.3 MGSSA與其他群智能算法比較

實驗選取5個群智能算法進行比較,分別為SSA[6]、GoldSA[24]、HHO[4]、WOA[2]、ChOA[5],為保證實驗的公平性,相應算法的參數根據對應參考文獻進行設置.本文的MGSSA與這5種算法比較的結果數據如表3所示.

表3 其他群智能算法比較實驗結果

根據表3的結果,MGSSA可以在7個單峰函數中找到6個函數的精確最優值,表明該算法具有較強的魯棒性和較高的收斂精度.對于唯一一個未尋到精確最優值的函數f5,其最優值、均值和標準差均優于其他5種算法.因此,MGSSA在求解單峰函數時具有良好的穩定性和較強的開采能力.對于7個多峰函數,MGSSA尋到了4個精確最優值,在另外3個函數上也找到了接近全局最優值,表明MGSSA有較強的擺脫局部最優的能力.對于函數f8和函數f14,GoldSA和HHO均尋到相似和相同最優值,但MGSSA的均值和標準差優于GoldSA和HHO,表明MGSSA的穩定性更強.從優/等/劣的結果中也可以看出,MGSSA分別在14、5、11、13、14個函數上結果優于SSA、GoldSA、HHO、WOA、ChOA,在6種算法中總體求解性能最佳.結果表明MGSSA在求解單峰函數中有較強的開采能力,在求解多峰函數時可以有效避免局部最優,有較強的勘探能力.圖3是各算法部分函數收斂曲線,可以更直觀地觀察算法的求解性能.

圖3 群智能優化算法函數收斂曲線Fig.3 Convergence curves of functions for swarm intelligence optimization algorithms

MGSSA可以有更好的測試結果,主要是均值個體策略優化了跟隨者的搜索方向,從而改善算法的開采能力,在算法后期又有黃金正弦擾動幫助其跳出局部最優.SOBL優化了整體種群位置,加快種群的收斂速度同時也改善解的質量.

3.4 MGSSA與其他改進SSA算法

為進一步測試MGSSA的性能,使用6種其他的SSA改進算法與MGSSA對比,包括CASSA[15]、RDSSA[16]、RCSSA[13]、 ALSSA[18]、AIWSSA[26]和AGHSSA[27].所有算法相關參數均按相應參考文獻設置,在14個基準函數上進行測試,各算法獨立運行30次,在α=0.05顯著水平下通過Wilcoxon秩和檢驗獲得的實驗結果如表4所示.

表4 SSA改進算法實驗測試結果

從表4可以看出:在14個基準測試函數中,MGSSA在6個單峰函數和7個多峰函數上具有最佳的平均值;針對未尋到精確最優值的函數f5,也優于除RCSSA以外的5個改進算法,總體求解效果最優.同時可以觀察到,與同樣融合了黃金正弦算法的AGHSSA相比,MGSSA在1個單峰函數(f5)和3個多峰函數(f8、f12、f14)上尋到了更優,而對比RDSSA、RCSSA、CASSA、ALSSA和AIWSSA,也分別在11、9、11、12和4個函數上尋到了更優解,表明精英均值個體策略與選擇反向學習策略在協助算法求解多峰函數時發揮了重要作用.因此,3種策略同時使用可有效提升SSA求解多峰函數的性能.

為了直觀地觀察7種SSA改進算法的收斂性能,本文選取幾個具有代表性的函數繪制尋優收斂曲線如圖4所示.

圖4 改進SSA函數收斂曲線Fig.4 Convergence curves of functions for improved Salp Swarm Algorithms

在單峰函數f5和多峰函數f12上,在CASSA、ALSSA、AGHSSA和RDSSA陷入局部最優的情況下,MGSSA能很好地跳出局部最優,找尋更優解,其勘探能力較強.同時在f8,f13兩個函數上,也可以觀察到MGSSA在搜索過程中收斂速度和跳出局部最優的能力十分顯著.

3.5 工程約束優化問題求解

為了更好地驗證MGSSA在求解工程約束問題時的性能,本文將MGSSA 與CASSA[15]、RDSSA[16]、RCSSA[13]、 ALSSA[18]、AIWSSA[26]和AGHSSA[27]6種改進SSA算法和基本SSA應用于拉壓彈簧設計問題中的求解.同時利用罰函數法,在目標函數中加入懲罰項,將約束優化問題轉化為無約束優化問題.將種群大小設為40,最大迭代次數設置為500,每個算法獨立運行30次取最優求解結果比較,各算法參數設置同對應參考文獻,比較結果如表5所示.

表5 8種算法求解拉壓彈簧設計問題最優結果

拉壓彈簧設計問題的目的是最小化拉伸或壓縮彈簧的質量,如圖5所示.此問題受最小撓度、剪切應力、浪涌頻率、外徑限制和設計變量的限制.設計變量是平均線圈直徑D=x1(0.05≤x1≤2)、導線直徑d=x2(0.25≤x2≤1.3)和活動線圈數量N=x3(2≤x3≤15).問題可以表述為

圖5 拉壓彈簧模型Fig.5 Model of tension/compression spring

目標函數:

約束函數:

從表5結果可以看出,在8種算法中,MGSSA求解結果最佳,RCSSA次之,RDSSA、ALSSA與AGHSSA在求解工程約束問題時效果相比于其他幾個改進算法效果差.

4 結束語

本研究引入的選擇反向學習策略,相較于傳統的反向學習策略,減少了計算維度,同時保留了種群的多樣性,改善了每代種群解的質量.在跟隨者位置更新階段引入的精英均值策略,通過均值個體和最優個體的有效引導,使算法的尋優速度加快,改善了標準SSA的收斂速度慢的問題,同時收斂精度大幅提升.黃金正弦變異策略的加入,使算法在前期在均值個體周圍尋找更優,后期隨機選擇個體在周圍進行搜索,既有利于前期加快收斂速度,又有利于后期跳出局部最優.

通過在14個基準測試函數上進行對比實驗,驗證了MGSSA相較于RDSSA、RCSSA、CASSA、ALSSA和AIWSSA的穩定性和先進性.通過拉壓彈簧設計問題可以觀察到MGSSA在求解工程約束優化問題時表現良好.在接下來的研究中,將進一步改進樽海鞘群算法并將其應用到現實問題的求解.