楊 興，郭明昊，方 霞，祝忠明，蔣美琪

(成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610059)

0 引 言

樽海鞘算法(salp swarm algorithm，SSA)[1]是Mirjalili等人基于樽海鞘鏈在海洋中覓食的種群機制開發(fā)的一種群體仿生優(yōu)化算法。與其他著名的優(yōu)化算法相比，SSA在許多問題上都證明了它的優(yōu)越性。但SSA作為一種隨機群體優(yōu)化算法，依舊存在著與其他相似算法[2-3]同樣的易陷入局部最優(yōu)解以及收斂速度慢等缺點。文獻[4]提出一種基于反向?qū)W習(xí)和新的局部搜索算法改進樽海鞘算法用于特征選擇和特征的最優(yōu)子集選擇，并驗證了算法在大多數(shù)使用的數(shù)據(jù)集中的優(yōu)越性。文獻[5]在樽海鞘算法中引入反向?qū)W習(xí)與混沌局部搜索， 對測試函數(shù)進行全局尋優(yōu)驗證算法的性能。文獻[6]在樽海鞘算法中食物源位置引入動態(tài)權(quán)重因子，構(gòu)成自適應(yīng)樽海鞘算法，并與BP神經(jīng)網(wǎng)絡(luò)結(jié)合形成一種新的預(yù)測模型用于對土壤墑情預(yù)測。文獻[7]將樽海鞘算法運用于TDOA問題，取得了更高的定位精度。文獻[8]提出一種具有交叉變換的二進制樽海鞘算法，引入交叉算子增強算法的探索能力，改進的算法在特征選擇過程中約90%的數(shù)據(jù)集優(yōu)于其他算法。文獻[9]提出了混沌樽海鞘算法，使用十個不同的混沌圖來提高收斂速度和結(jié)果精度，并在特征選擇中驗證了通過邏輯混沌映射可以顯著提高原始SSA的性能。文獻[10]提出基于二次積分和火神經(jīng)模型的混沌樽海鞘算法，將二次積分和火模型產(chǎn)生的混沌振蕩引入到SSA算法中。這樣可以改善勘探與開發(fā)之間的平衡，從而在不同種群之間產(chǎn)生多樣性， 跳出局部最優(yōu)。并在不同的工程應(yīng)用中驗證了改進的樽海鞘算法的可行性。文獻[11]提出一種增強型樽海鞘算法，對其進行函數(shù)優(yōu)化驗證性能并運用于變速風(fēng)力發(fā)電機中。

為提高樽海鞘算法在求解問題時的優(yōu)化性能，引入天牛須搜索策略和自適應(yīng)權(quán)重值，提出一種基于天牛須搜索自適應(yīng)的樽海鞘算法(beetle antennae search and adaptive salp swarm algorithm，BASSA)。主要的改進為：(1)在樽海鞘算法的領(lǐng)導(dǎo)者位置更新中引入洛倫茲函數(shù)替代樽海鞘算法中c2隨機值，控制領(lǐng)導(dǎo)者的全局搜索范圍；(2)引入天牛須搜索機制替代樽海鞘算法的c3的隨機值，決定領(lǐng)導(dǎo)者位置更新方向；(3)在追隨者位置更新中，為了更好地權(quán)衡全局搜索和局部搜索，引入自適應(yīng)慣性權(quán)重，調(diào)節(jié)自身位置和上一個個體位置對追隨者位置更新的權(quán)重。通過對多個不同類型的基準(zhǔn)函數(shù)進行求解優(yōu)化對比，驗證了改進的樽海鞘算法的可行性與魯棒性。

1 樽海鞘算法

樽海鞘算法起源于樽海鞘鏈的群聚行為，樽海鞘鏈群體分為兩部分：領(lǐng)導(dǎo)者和追隨者。在樽海鞘鏈中最前端的個體被認(rèn)為是領(lǐng)導(dǎo)者，其他個體認(rèn)為是追隨者。領(lǐng)導(dǎo)者根據(jù)食物源位置引導(dǎo)著追隨者移動。將樽海鞘群體對最佳食物源搜索的過程類比為對函數(shù)尋優(yōu)。在樽海鞘算法中，為了更加平衡算法的全局性和魯棒性，選取一半的種群為領(lǐng)導(dǎo)者。在一個N×d維的空間內(nèi)搜尋食物源，N為樽海鞘種群數(shù)量，d為空間維度，則樽海鞘個體的位置表示為Xn=[Xn1,Xn2,…,Xnd]T,n=1,2,…,N，對應(yīng)的食物源表示為F=[F1,F2,…,Fd]T，在一個搜索上下界分別為ubd，lbd的搜索空間范圍中進行尋優(yōu)。故在SSA中領(lǐng)導(dǎo)者根據(jù)下式進行位置更新：

(1)

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

(2)

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

追隨者位置更新如下所示：

(3)

2 改進的樽海鞘算法

2.1 領(lǐng)導(dǎo)者的改進

在樽海鞘算法的領(lǐng)導(dǎo)者位置更新公式中c2、c3的隨機值分別控制領(lǐng)導(dǎo)者搜索范圍和方向。首先引入洛倫茲函數(shù)替代c2，提高領(lǐng)導(dǎo)者位置搜索空間的有效性；再引入天牛須搜索算法中的左右須搜索機制替代c3的隨機值，決定樽海鞘算法中領(lǐng)導(dǎo)者位置更新方向，使算法中領(lǐng)導(dǎo)者位置前進方向更加有利于對全局最優(yōu)的搜索。

樽海鞘算法領(lǐng)導(dǎo)者位置更新中，c2是屬于均勻分布的隨機值，在算法中對其取值具有一定的盲目性，在算法迭代過程中，算法前期為尋找出全局最優(yōu)解需要算法的個體盡可能地遍歷整個搜索空間區(qū)域，算法后期，較小的搜索空間能一定程度跳出局部最優(yōu)解，故該文引入具有緩慢下降速度的洛倫茲函數(shù)替代c2值。具體函數(shù)如下：

(4)

K=H(t/T;0,1,1)

(5)

式中，A為峰值，x0為位置參數(shù)，r為尺度參數(shù)，K為通過洛倫茲函數(shù)計算出來的參數(shù)，t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)。

天牛須搜索算法(beetle antennae search，BAS)是Jiang等人[12-13]通過對天牛的覓食行為模擬出來的一種仿生算法。天牛覓食的過程通過自身的左右須對食物的濃度感知情況，天牛朝著食物源濃度強的方向移動。天牛須搜索算法中天牛每次迭代后頭朝向都是隨機的，左右須的位置與兩須之間距離和自身的位置有關(guān)，具體表示如下：

X(l)=X+d0*dir/2

(6)

X(f)=X-d0*dir/2

(7)

式中，X(l)、X(f)分別表示天牛的左右須，X表示天牛個體自身的位置，dir表示天牛的朝向是隨機的。d0為左右須之間的距離，兩須之間距離的大小，影響天牛在搜索空間中對最優(yōu)食物源位置方向的判斷，故對兩須之間位置根據(jù)迭代次數(shù)進行衰減。

d0=C*d0

(8)

C為衰減因子，表示為：

C=e-30(t/T)

(9)

在樽海鞘算法中，引入天牛須搜索算法中的左右須搜索尋優(yōu)方向的策略，得到一種改進的樽海鞘算法(beetle antennae search salp swarm algorithm，BSSA)。將領(lǐng)導(dǎo)者類比為天牛，首先由式(6)、式(7)構(gòu)建領(lǐng)導(dǎo)者左右須，再通過目標(biāo)函數(shù)計算出領(lǐng)導(dǎo)者左右須位置的適應(yīng)度值，比較左右須適應(yīng)度值大小，使領(lǐng)導(dǎo)者在進行位置更新時向具有更佳的適應(yīng)度值的方向移動。改進的樽海鞘算法領(lǐng)導(dǎo)者位置更新如下：

((ubd-lbd)*K+lbd)

(10)

式中，f(X(l))、f(X(f))分別表示通過目標(biāo)函數(shù)所計算出來的左須和右須的適應(yīng)度值，sign為符號函數(shù)，K為通過洛倫茲函數(shù)計算出來的參數(shù)。

2.2 追隨者的改進

該文將自適應(yīng)慣性權(quán)重引入到追隨者位置更新中改進樽海鞘算法(adaptive weighted salp swarm algorithm，ASSA)。SSA中追隨者的位置更新取決于自身的位置和上一個個體的位置，在上一個個體位置較差或是陷入局部最優(yōu)解時，追隨者盲目的跟隨，將會使算法陷入局部最優(yōu)。文獻[14]提出權(quán)重值的大小對全局搜索空間尋找最優(yōu)解和跳出局部最優(yōu)解均有不同程度的影響。較大的權(quán)重值有助于算法在全局搜索空間中找到最優(yōu)解，而較低的權(quán)重值則有助于其跳出局部最優(yōu)解。故該文在追隨者位置更新中引入自適應(yīng)慣性權(quán)重，決定了自身個體和上一個個體對位置更新的影響程度。

追隨者位置更新如下所示：

(11)

ω=ωmax*(ωmax-ωmin)*(t-T)/T

(12)

式中，rand為[0,1]上的隨機值，ω為慣性權(quán)重，ωmax=0.9,ωmin=0.4，自適應(yīng)慣性權(quán)重值主要根據(jù)當(dāng)前迭代次數(shù)t與最大迭代次數(shù)T決定。追隨者位置的改進，進一步提升了算法的局部搜索能力。

2.3 BASSA偽代碼

(1)設(shè)置BASSA參數(shù):最大迭代次數(shù)T，兩須距離d0，洛倫茲函數(shù)相關(guān)參數(shù)，種群數(shù)量大小N等。

(2)隨機初始化BASSA種群，計算每個樽海鞘位置的適應(yīng)度值，將最佳的適應(yīng)度值對應(yīng)的位置作為食物源位置Xbest。

(3)While(t

(4)For(i=1:N)

(5)if(i

(6)根據(jù)式(4)、(5)得到洛倫茲函數(shù)值。

(7)根據(jù)式(6)、(7)計算得到領(lǐng)導(dǎo)者位置的左右須。

(8)根據(jù)式(10)更新領(lǐng)導(dǎo)者位置。

(9)else

(10)根據(jù)式(11)更新追隨者位置。

(11)end if

(12)end for

(13)通過目標(biāo)函數(shù)計算樽海鞘算法位置更新后的種群個體的適應(yīng)度值。

(14)選取最佳適應(yīng)度值對應(yīng)的樽海鞘個體位置與食物源位置進行比較，并更新食物源位置。

(15)t=t+1

(16)end while

(17)返回最佳食物源位置Xbest及其適應(yīng)度值。

2.4 BASSA算法的時間復(fù)雜度分析

SSA在一個N×D維的空間內(nèi)優(yōu)化問題的時間復(fù)雜度分析如下:在種群初始化設(shè)置所產(chǎn)生的時間為θ1，設(shè)均勻分布隨機值在D維空間中每一維度產(chǎn)生時間為η1，SSA中通過目標(biāo)函數(shù)計算每個個體位置的適應(yīng)度值的時間為λ1，則求解初始化后所有位置的適應(yīng)度值所需要的時間為N*λ1。排序得到食物源位置的時間復(fù)雜度為η2，故在未進入迭代前所產(chǎn)生的時間為o(ND)。

o(ND)

(13)

在追隨者位置更新，引入的自適應(yīng)慣性權(quán)重在每次迭代中只運行一次，所需要時間為η2。故BASSA追隨者部分時間復(fù)雜度為：

(14)

綜上，改進的BASSA的整體時間復(fù)雜度為：

T=o(ND)+T1+T2=o(ND)

(15)

故改進的BASSA與SSA相比，沒有增加時間復(fù)雜度。

3 算法仿真與分析

3.1 實驗設(shè)計

為驗證提出的BASSA的有效性和魯棒性，在8個包含單峰、多峰、可分、不可分等不同特征的測試函數(shù)上對BASSA、BSSA、ASSA、文獻[10]的RDSSA、文獻[11]中的ESSA以及基本的SSA進行測試。實驗設(shè)置為在相同的迭代次數(shù)下，對比各算法在同一測試函數(shù)中的收斂速度和收斂精度。對BASSA算法設(shè)置的參數(shù)如表1所示，RDSSA、ESSA所需參數(shù)根據(jù)相關(guān)文獻中設(shè)置相同。測試函數(shù)如表2所示。

表1 參數(shù)設(shè)置

表2 測試函數(shù)

本實驗在Matlab16b環(huán)境下采用M語言進行，同一算法對相同的測試函數(shù)獨立運行50次，對每次運行結(jié)果的最優(yōu)值進行統(tǒng)計，并計算其平均值和標(biāo)準(zhǔn)差。具體實驗結(jié)果如表3所示。

3.2 結(jié)果分析

3.2.1 與原算法SSA的比較分析

通過圖1中各算法對不同的函數(shù)優(yōu)化的收斂曲線可以看出，經(jīng)過改進的BSSA、ASSA、BASSA與SSA相比，除了在f5函數(shù)上，BSSA與SSA基本持平，在其余優(yōu)化函數(shù)上改進的樽海鞘算法在收斂速度和收斂精度上均優(yōu)于SSA。改進的BSSA與SSA相比，后期的尋優(yōu)精度上具有明顯的優(yōu)勢。改進的ASSA與SSA相比，ASSA在迭代前期能夠快速的收斂，并在迭代后期依舊具有較高的收斂速度，且收斂精度明顯高于SSA。BASSA綜合了BSSA和ASSA的優(yōu)勢后，在收斂速度和收斂精度上，表現(xiàn)出了明顯的優(yōu)勢。

經(jīng)過表3中的BASSA、BSSA、ASSA、SSA在相同的迭代次數(shù)下，50次最佳適應(yīng)度值Best，平均最佳適應(yīng)度值Mean，最佳適應(yīng)度值標(biāo)準(zhǔn)差Std的具體實驗值表明，在單峰測試函數(shù)中改進的BASSA最高達到了E-190級別，其次ASSA、BSSA，相比SSA，尋優(yōu)效果均具有更加明顯的優(yōu)勢。在多峰測試函數(shù)中，BASSA和ASSA均能達到理論最優(yōu)值，而BSSA相比于SSA的尋優(yōu)精度更高。通過表3中的平均值、標(biāo)準(zhǔn)差值，BASSA、BSSA、ASSA在對相同的函數(shù)進行優(yōu)化時均為最小。表明BASSA具有一定的魯棒性。

3.2.2 與已改進SSA的比較分析

將該文改進的BASSA與文獻[10]的RDSSA和文獻[11]中的ESSA進行對比。通過觀察圖1的收斂曲線，在單峰測試函數(shù)中改進的BASSA與ESSA以及RDSSA相比，在迭代前期，具有更快的收斂速度，而在迭代后期，BASSA的收斂速度依舊較快，收斂至一個最優(yōu)的結(jié)果。在多峰測試函數(shù)中，BASSA與ESSA、RDSSA均能達到理論最優(yōu)值，但BASSA達到理論最優(yōu)值所需迭代次數(shù)最少。

圖1 各算法平均收斂曲線比較

通過表3相關(guān)算法的具體測試結(jié)果中，f5、f7、f8三者算法在收斂精度和標(biāo)準(zhǔn)差上相當(dāng)，在f6上BASSA、RDSSA表現(xiàn)相當(dāng)且在平均最佳值和標(biāo)準(zhǔn)差上優(yōu)于ESSA。在其他測試函數(shù)上，BASSA均表現(xiàn)為更佳收斂能力和穩(wěn)定性。

表3 各算法實驗測試結(jié)果

續(xù)表3

4 結(jié)束語

該文提出的BASSA在標(biāo)準(zhǔn)的樽海鞘算法的領(lǐng)導(dǎo)者位置引入天牛須搜索機制使樽海鞘領(lǐng)導(dǎo)者向著更優(yōu)的方向搜索最優(yōu)解，引入洛倫茲函數(shù)控制算法的搜索空間，加快了收斂速度，在追隨者位置引入自適應(yīng)慣性權(quán)重改善了算法的局部搜索能力。通過對不同的基準(zhǔn)測試函數(shù)優(yōu)化，實驗結(jié)果表明：改進的BASSA相較于SSA、已經(jīng)改進的ESSA、RDSSA具有更快的收斂速度，在相同的測試條件下，能夠達到更高的收斂精度，并在可行性以及魯棒性方面都更具有優(yōu)勢。在下一步研究中，嘗試將改進的算法應(yīng)用到具體的工程中。