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

陳忠云 張達(dá)敏 辛梓蕓

(貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院 貴州 貴陽 550025)

0 引 言

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

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

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

1 樽海鞘群算法

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

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

(1)

在樽海鞘群算法中，食物源的位置是所有樽海鞘個體的目標(biāo)位置。因此，領(lǐng)導(dǎo)者的位置更新公式為：

(2)

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

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

(3)

式中：t為當(dāng)前迭代次數(shù)；Tmax為最大迭代次數(shù)。

利用牛頓運(yùn)動定理更新追隨者的位置：

(4)

(5)

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

2 算法設(shè)計

2.1 Logistics映射的種群初始化

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

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

(6)

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

(7)

2.2 正弦余弦算法(SCA)

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

(8)

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

2.3 差分演化變異策略

(9)

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

(10)

2.4 SCSSA步驟

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

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

Step2計算初始適應(yīng)度值。根據(jù)測試函數(shù)計算N個樽海鞘的適應(yīng)度值。

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

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

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

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

Step7重復(fù)Step4-Step6，如果達(dá)到設(shè)置的精度要求或規(guī)定的最大迭代次數(shù)，則終止算法，輸出全局最優(yōu)解。

3 仿真實驗

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

表1 基準(zhǔn)函數(shù)

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

表2 算法參數(shù)設(shè)置

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

(11)

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

表3 各算法的尋優(yōu)結(jié)果

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

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

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

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

表4 Wilcoxon 秩和檢驗的p-value

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

選擇平均絕對誤差MAE作為評價指標(biāo)對算法進(jìn)行定量分析，結(jié)果如表5所示。

表5 MAE算法排名

MAE的計算公式為：

(12)

式中：mi為算法產(chǎn)生的最有結(jié)果的平均值；oi為相應(yīng)基準(zhǔn)函數(shù)的理論最優(yōu)值；Nf為基準(zhǔn)函數(shù)個數(shù)。

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

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

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

圖1 基準(zhǔn)函數(shù)平均收斂曲線

綜上可知，正弦余弦算法的樽海鞘群算法對于所有基準(zhǔn)函數(shù)都有很好的尋優(yōu)結(jié)果，特別是對于多峰的函數(shù)，具有較好的穩(wěn)定性和尋優(yōu)能力。

4 結(jié) 語

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