基于天牛須搜索自適應的樽海鞘算法

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

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

0 引 言

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

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

1 樽海鞘算法

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

(1)

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

(2)

式中，t為當前迭代次數，T為最大迭代次數。

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

(3)

2 改進的樽海鞘算法

2.1 領導者的改進

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

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

(4)

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

(5)

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

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

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

(6)

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

(7)

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

d0=C*d0

(8)

C為衰減因子，表示為：

C=e-30(t/T)

(9)

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

((ubd-lbd)*K+lbd)

(10)

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

2.2 追隨者的改進

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

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

(11)

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

(12)

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

2.3 BASSA偽代碼

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

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

(3)While(t

(4)For(i=1:N)

(5)if(i

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

(7)根據式(6)、(7)計算得到領導者位置的左右須。

(8)根據式(10)更新領導者位置。

(9)else

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

(11)end if

(12)end for

(13)通過目標函數計算樽海鞘算法位置更新后的種群個體的適應度值。

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

(15)t=t+1

(16)end while

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

2.4 BASSA算法的時間復雜度分析

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

o(ND)

(13)

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

(14)

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

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

(15)

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

3 算法仿真與分析

3.1 實驗設計

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

表1 參數設置

表2 測試函數

本實驗在Matlab16b環境下采用M語言進行，同一算法對相同的測試函數獨立運行50次，對每次運行結果的最優值進行統計，并計算其平均值和標準差。具體實驗結果如表3所示。

3.2 結果分析

3.2.1 與原算法SSA的比較分析

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

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

3.2.2 與已改進SSA的比較分析

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

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

通過表3相關算法的具體測試結果中，f5、f7、f8三者算法在收斂精度和標準差上相當，在f6上BASSA、RDSSA表現相當且在平均最佳值和標準差上優于ESSA。在其他測試函數上，BASSA均表現為更佳收斂能力和穩定性。

表3 各算法實驗測試結果

續表3

4 結束語

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