正弦余弦算法的樽海鞘群算法

陳忠云 張達敏 辛梓蕓

(貴州大學大數據與信息工程學院 貴州 貴陽 550025)

0 引 言

近年來，元啟發式算法作為一種有效的演化計算技術，已受到眾多學者的重視。元啟發式算法是指受到生物行為和物理現象的啟發提出的一類算法，其核心思想是實現搜索過程中隨機性行為和局部搜索的平衡。常用的元啟發式算法包括粒子群優化算法(Particle Swarm Optimization,PSO)[1]、正弦余弦算法(Sine Cosine Algorithm,SCA)[2]等。在解決眾多多模態、離散和非差異的現實尋優問題中，元啟發式算法呈現了優良的可操作性以及尋優能力，并成功應用于各種科學領域，如過程控制、生物醫學信號處理、圖像處理以及許多其他工程設計問題。

樽海鞘群算法 (Salp Swarm Algorithm,SSA)是2017年由Mirjalili等[3]提出的一種新型群智能算法，具有結構簡單、參數少、容易實現等優勢，但仍存在求解精度低和收斂速度慢等缺陷。文獻[4]將樽海鞘群算法中跟隨者單步位置更新方式改為兩步，分別根據自適應平局移動策略和領域最優引領策略進行更新，再引入方向學習策略以一定概率對個體位置進行擾動，提高種群多樣性，使算法跳出局部最優。文獻[5]提出固定慣性權重，可以加快搜索過程中的收斂速度，并應用于特征選擇問題。文獻[6]結合樽海鞘群算法和混沌理論提出混沌樽海鞘群算法，在解決特征提取問題時，能發現最優特征子集，最大限度地提高分類精度，最小化所選特征的數目。文獻[7]提出基于樽海鞘群算法的無緣時差定位，利用SSA解決TDOA定位結算問題，驗證算法在多站時差定位問題上的有效性與優越性。文獻[8]提出基于Logistics混沌方法對粒子進行初始化，增加初始個體多樣性。文獻[9]將正弦余弦算法作為一種局部算法嵌入到花授粉中，對花粉個體分別進行正弦和余弦優化。文獻[10]提出差分演化策略，可增強算法的局部開采能力。

為解決標準樽海鞘群算法存在的求解精度不高和收斂速度慢等問題，本文提出一種正弦余弦算法的樽海鞘群算法(Salp Swarm Algorithm Using Sine Cosine Algorithm,SCSSA)。選用Logistics映射來生成樽海鞘群算法的初始種群，增強初始個體的均勻性。種群個體更新后，將正弦余弦算法作為局部因子嵌入到樽海鞘群算法中，并對最優樽海鞘個體采用差分演化變異策略，有助于增強算法的全局探索和局部開發能力。通過求解8個典型復雜函數的最優解來驗證正弦余弦算法的樽海鞘群算法的有效性。

1 樽海鞘群算法

樽海鞘群算法[3]是Mirjalili等提出的一種全新的智能優化算法，其思想源于樽海鞘的聚集行為，即樽海鞘鏈。它以水中的浮游植物(海藻等)為食，通過吸入噴出海水完成在水中的移動。在樽海鞘群算法中，樽海鞘鏈由兩種類型的樽海鞘組成：領導者和追隨者。領導者位于樽海鞘鏈的最前面，而其他個體則為追隨者。

該算法定義每個樽海鞘個體的位置向量X用于在N維空間中搜索，N是決策變量的數目。X將由維度為d的N個樽海鞘個體組成。因此，種群向量由N×d維矩陣構成：

(1)

在樽海鞘群算法中，食物源的位置是所有樽海鞘個體的目標位置。因此，領導者的位置更新公式為：

(2)

由式(2)可知，領導者位置更新主要受到食物源位置影響。系數c1是樽海鞘群算法中最重要的參數，其可以使SSA的探索能力和開發能力處于平衡狀態。c1定義如下：

c1=2e-(4t/Tmax)2

(3)

式中：t為當前迭代次數；Tmax為最大迭代次數。

利用牛頓運動定理更新追隨者的位置：

(4)

(5)

因此，由式(2)和式(5)可以模擬樽海鞘鏈的行為機制。

2 算法設計

2.1 Logistics映射的種群初始化

樽海鞘群體的初始化對SSA的收斂速度和尋優精度至關重要。在樽海鞘群初始時，由于沒有任何先驗知識可使用，基本上大部分群智能算法的初始位置都是隨機生成的。初始種群均勻分布在搜索空間，對提高算法尋優有很大幫助。

混沌序列具有隨機性、遍歷性和規律性，通過其產生的樽海鞘群體有較好的多樣性。其基本思路是：通過映射關系在[0, 1]區間產生混沌序列，然后將其轉化到個體的搜索空間。產生混沌序列的模型有許多，本文采用Logistics映射生成的混沌序列來初始化樽海鞘群算法群體。Logistics映射的數學表達式為：

(6)

式中：μ∈[0, 4]是混沌參數，μ越大，混沌性越好，本文取μ=4；i= 1,2,…,N表示種群規模；j= 1,2,…,d表示混沌變量序號。

(7)

2.2 正弦余弦算法(SCA)

由式(5)追隨者位置更新公式可知，第i只樽海鞘位置會根據第i和i-1只樽海鞘位置坐標中點進行更新。在此過程中并沒有判別xi是否優于原來位置，這種單方向根據第i只樽海鞘的位置信息機制，樽海鞘個體之間缺少交流，信息利用率較低。為使群體之間擁有更多的交流機會，進一步優化樽海鞘群算法的探索和開發能力，本文引入正弦余弦算法[2]作為局部優化算子嵌入到樽海鞘群算法中，即在更迭后期對全部樽海鞘個體采用正弦余弦操作，指導樽海鞘個體更新樽海鞘位置，更新公式如下：

(8)

正弦余弦優化策略的嵌入，一方面能夠很好地填補樽海鞘群算法位置更新公式存在依賴性的缺陷，無論是正弦機制還是余弦機制，樽海鞘個體都能夠與食物源進行位置交流，促進最優信息在種群中得到傳遞，每一個樽海鞘個體都能較好運用自身和食物源的位置差信息，促使樽海鞘個體朝向最優解移動；另一方面，使得樽海鞘個體進一步在同一個搜索空間的不同范圍中進行全局搜索和局部開發。正弦機制可使全局搜索找到最優解降低余弦機制的尋優盲點，減少樽海鞘個體陷入局部最優，而余弦機制可使局部開發填補正弦全局搜索收斂速度滿的缺點，提高探索能力，加快算法收斂。正弦余弦的相互使用，可較好平衡算法的探索和開發能力，共同促進算法性能的優化。

2.3 差分演化變異策略

(9)

式中：F是縮放因子；R1、R2、R3、R4是區間[1,N]上互不相同的隨機整數，代表不同樽海鞘個體；j是維度；mj為擾動后的食物源位置。使用式(10)交叉操作選擇新的食物源位置。

(10)

2.4 SCSSA步驟

正弦余弦算法的樽海鞘群算法步驟如下：

Step1初始化個體位置。使用Logistics映射生成混沌序列，根據搜索空間的上下限，把混沌序列逆映射為一個N×d維的矩陣。

Step2計算初始適應度值。根據測試函數計算N個樽海鞘的適應度值。

Step3選定食物源。將Step2中計算后的適應度值升序(或降序)排列，適應度值最好的樽海鞘位置選定為食物源位置。

Step4更新領導者和追隨者位置。確定食物源位置之后，選取種群中一個的樽海鞘個體根據式(2)更新領導者位置，其余的樽海鞘根據式(5)更新追隨者位置。

Step5正弦余弦指引策略。利用式(8)對Step4所生成的樽海鞘個體進行正弦或余弦操作，以更新到新的樽海鞘位置。

Step6計算適應值。計算更新后種群的適應度值，引入差分演化變異策略，根據式(9)和式(10)更新食物源位置。

Step7重復Step4-Step6，如果達到設置的精度要求或規定的最大迭代次數，則終止算法，輸出全局最優解。

3 仿真實驗

為了驗證本文提出的SCSSA在求解優化問題上的有效性和魯棒性，將SCSSA與標準的SSA[3]、PSO以及SCA在8個典型的標準測試函數上進行仿真實驗，在最優值求解上獨立進行50次對比實驗。8個復雜函數如表1所示，其中包含單峰、多峰等不同特征的測試函數。單峰函數為在定義上下限內只有一個嚴格上的極大值(或極小值)，通常用來檢測算法收斂速度。多峰函數為含有多個局部最優解或全局最優解的函數，經常用于檢測算法探索能力和開發能力。測試函數維度設置為50維。

表1 基準函數

實驗環境為：Windows 7系統，8 GB內存，CPU 2.5 GHz，算法基于MATLAB 2014b用M語言編寫。實驗最大迭代次數為1 000，種群個數為30，各算法參數設置如表2所示。

表2 算法參數設置

表3記錄了50次獨立實驗后各算法尋優結果的最佳值(Best)、平均值(Mean)、標準偏差(Std)、求解成功率(SR/%)和平均耗時(Time/s)等數據。其中求解成功率為計算成功次數除以本次實驗的求解次數。判斷一次求解是否成功的公式如下：

(11)

式中：FA為每次實際求解最佳值；FT為測試函數理論最佳值。

表3 各算法的尋優結果

最優值、平均值都可以反映算法的收斂精度和尋優能力。對于4個單峰函數(f1-f4)，SCSSA在求解精度上最高達到1.00E-40。求解f3(Schwefel 2.21)時，SSA和SCA的求解能力很差，與理論最優值存在1.00E+01級的誤差。而SCSSA的尋優精度相比SSA、PSO和SCA都更好，且求解精度變化不大。對于4個多峰函數(f5-f8)，SCSSA在求解f5和f7(Rastrigin和Griewank)的精度時獲得了理論最優值0，且SCSSA較其他3種算法仍然具有很好的尋優精度。因此，SCSSA在求解單峰、多峰的基準函數時都有更好的尋優效果。

標準差和成功率可以反映算法的穩定性和跳出局部最優的能力。由表3可知，SCSSA獨立50次計算的標準差始終比其他三種算法都要小。這說明SCSSA對于低維和高維基準函數的尋優求解有著很好的穩定性，且在多峰函數上尋優能力比較強，跳出局部最優的能力相比其他算法更好。8個基準函數中有單峰和多峰，除了Penalized這個多峰基準函數外，SCSSA在成功率基本上為100%，而標準SSA在f1的成功率為100%，但在其余基準函數的成功率幾乎為0。SSA在尋優求解能力上的表現有很大不足，特別是在求解f3和f5時，標準差和成功率都較差，說明標準SSA在跳出局部最優的能力是較弱。而在SCSSA中引入正弦余弦優化策略，對算法后期跳出局部搜索具有很大作用。

從平均耗時來看。SCSSA相對于標準SSA的平均耗時都要大，PSO總體運行時間均優于SCSSA、SSA和SCA。SCSSA在SSA的基礎上引入多個算子，使得算法能夠搜索到更多的解，同時增加了算法運行時間?？傮w來看，SCSSA平均耗時的增加不大，在允許范圍內。

基于50次獨立運行算法的平均值和標準差不會比較每次運行結果。Derrac等[11]提出，對于改進進化算法性能的評估，應該進行統計檢驗。為了判斷SCSSA的每次結果在統計學上是否明顯與其他算法的最佳結果不同，在5%的顯著性水平下進行Wilcoxon統計檢驗。表4為所有基準函數的SCSSA和其他算法的Wilcoxon秩和檢驗中計算的p-value。例如，如果最佳算法是SCSSA，則在SCSSA/SSA, SCSSA/PSO、SCSSA/SCA等之間進行成對比較。由于最佳算法無法與自身進行比較，因此，針對每個函數中的最佳算法標記為N/A，表示“不適用”。這意味著相應的算法在秩和檢驗中沒有統計數據與自身進行比較。符號“+”“?”和“≈” 分別表示SCSSA的性能要優于、劣于和相當于對比算法。p-value小于0.05的可以被認為是拒絕零假設的有力驗證。

表4 Wilcoxon 秩和檢驗的p-value

可以看出，SCSSA的p-value全部小于0.05，這表明其優越性在統計學上是顯著的，即SCSSA比其余算法具有更高的收斂精度。

選擇平均絕對誤差MAE作為評價指標對算法進行定量分析，結果如表5所示。

表5 MAE算法排名

MAE的計算公式為：

(12)

式中：mi為算法產生的最有結果的平均值；oi為相應基準函數的理論最優值；Nf為基準函數個數。

可以看出，SCSSA排名均為1，與另外3種算法相比，SCSSA提供了最小的MAE，進一步證明了SCSSA的有效性。

圖1為8個基準函數在50維的平均收斂曲線。由于不同算法收斂精度存在較大差異，為了便于觀察收斂情況，本文對尋優適應度值(縱坐標)取10為底的對數。由圖1(a)-(d)可看出，SCSSA的收斂曲線下降最快。在迭代前期，SCSSA有一小段時間收斂曲線下降很快，這說明引入Logistics映射初始化種群增加了種群多樣性，使得算法前期收斂速度就較快，且隨著更迭次數的增加持續尋優，未出現停止狀況。由圖1(b)和(c)可知，SCA、PSO和SSA在迭代后期出現不同程度的停滯，且尋優精度較低。

圖1(e)-(h)是多峰函數的平均收斂曲線。SCSSA引入Logistics映射初始化種群算法的收斂性在f5-f8上迭代前期收斂速度很快，這也進一步說明使用Logistics映射初始化種群的作用。在迭代后期，雖然SCSSA收斂速度較前期平緩，但也一直在尋優，而其他3種算法后期基本都陷入局部最優，出現不同程度的停滯現象。SCSSA最終的尋優精度較其他算法仍然表現較好。無論單峰、多峰，還是低維和高維，對于每個基準函數，SCSSA比其他算法的收斂速度和尋優精度都更佳。由表3可知，對于函數f5、f7，SCSSA的最佳值為0，故圖1(e)、(g)中，SCSSA曲線的后面部分未顯示。

圖1 基準函數平均收斂曲線

綜上可知，正弦余弦算法的樽海鞘群算法對于所有基準函數都有很好的尋優結果，特別是對于多峰的函數，具有較好的穩定性和尋優能力。

4 結 語

本文在標準樽海鞘群算法的基礎上，引入混沌映射和使初始化種群均勻分布，將正弦余弦算法嵌入樽海鞘算法中，更好地平衡探索和開發能力，最后加入差分演化變異策略使算法易于跳出局部最優。本文提出一種改進的正弦余弦算法的樽海鞘群算法，并將其應用于復雜函數的尋優問題中。不僅使用最優值、標準差等指標對算法進行檢驗，還提出使用Wilcoxon秩和檢驗對算法顯著性水平進行驗證。研究表明：基于正弦余弦算法的樽海鞘群算法可以獲得更好的全局搜索和局部搜索能力，且收斂到質量更好的最優解，算法的有效性和魯棒性也得到驗證。