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

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

0 引 言

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

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

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

1 樽海鞘群算法

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

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

(1)

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

(2)

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

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

(3)

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

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

(4)

(5)

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

2 算法設(shè)計(jì)

2.1 Logistics映射的種群初始化

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

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

(6)

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

(7)

2.2 正弦余弦算法(SCA)

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

(8)

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

2.3 差分演化變異策略

(9)

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

(10)

2.4 SCSSA步驟

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

(11)

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

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

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

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

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

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

表4 Wilcoxon 秩和檢驗(yàn)的p-value

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

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

表5 MAE算法排名

MAE的計(jì)算公式為：

(12)

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

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

圖1為8個(gè)基準(zhǔn)函數(shù)在50維的平均收斂曲線。由于不同算法收斂精度存在較大差異，為了便于觀察收斂情況，本文對(duì)尋優(yōu)適應(yīng)度值(縱坐標(biāo))取10為底的對(duì)數(shù)。由圖1(a)-(d)可看出，SCSSA的收斂曲線下降最快。在迭代前期，SCSSA有一小段時(shí)間收斂曲線下降很快，這說(shuō)明引入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)一步說(shuō)明使用Logistics映射初始化種群的作用。在迭代后期，雖然SCSSA收斂速度較前期平緩，但也一直在尋優(yōu)，而其他3種算法后期基本都陷入局部最優(yōu)，出現(xiàn)不同程度的停滯現(xiàn)象。SCSSA最終的尋優(yōu)精度較其他算法仍然表現(xiàn)較好。無(wú)論單峰、多峰，還是低維和高維，對(duì)于每個(gè)基準(zhǔn)函數(shù)，SCSSA比其他算法的收斂速度和尋優(yōu)精度都更佳。由表3可知，對(duì)于函數(shù)f5、f7，SCSSA的最佳值為0，故圖1(e)、(g)中，SCSSA曲線的后面部分未顯示。

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

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

4 結(jié) 語(yǔ)

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