基于天牛須搜索自適應(yīng)的樽海鞘算法

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

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

0 引 言

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

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

1 樽海鞘算法

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

(1)

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

(2)

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

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

(3)

2 改進(jìn)的樽海鞘算法

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

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

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

(4)

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

(5)

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

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

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

(6)

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

(7)

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

d0=C*d0

(8)

C為衰減因子，表示為：

C=e-30(t/T)

(9)

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

((ubd-lbd)*K+lbd)

(10)

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

2.2 追隨者的改進(jìn)

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

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

(11)

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

(12)

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

2.3 BASSA偽代碼

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

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

(3)While(t

(4)For(i=1:N)

(5)if(i

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

(7)根據(jù)式(6)、(7)計(jì)算得到領(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ù)計(jì)算樽海鞘算法位置更新后的種群個(gè)體的適應(yīng)度值。

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

(15)t=t+1

(16)end while

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

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

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

o(ND)

(13)

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

(14)

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

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

(15)

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

3 算法仿真與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

表2 測(cè)試函數(shù)

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

3.2 結(jié)果分析

3.2.1 與原算法SSA的比較分析

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

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

3.2.2 與已改進(jìn)SSA的比較分析

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

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

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

表3 各算法實(shí)驗(yàn)測(cè)試結(jié)果

續(xù)表3

4 結(jié)束語

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