復(fù)數(shù)編碼的樽海鞘群算法及其應(yīng)用*

彭石燕，鄭洪清

（1.柳州鐵道職業(yè)技術(shù)學(xué)院，廣西柳州 545616；2.廣西職業(yè)師范學(xué)院教育學(xué)院，廣西南寧 530007）

0 引言

群智能算法作為一種新興的演化計算技術(shù)，已引起越來越多研究者的關(guān)注并在許多領(lǐng)域發(fā)揮著重要作用，但是當(dāng)優(yōu)化問題越來越復(fù)雜，傳統(tǒng)優(yōu)化算法的收斂精度和速度難以滿足要求，因此設(shè)計一種新算法勢在必行。

樽海鞘群算法(Slap Swarm Algorithm，SSA)[1]由Mirjalili等人于2017年提出，由于其參數(shù)調(diào)節(jié)少、計算簡單和尋優(yōu)能力相對較強，一經(jīng)提出便得到廣泛應(yīng)用。[2-4]為了進一步提高其性能，不同學(xué)者提出不同改進方法：文獻[5]采用折射反向?qū)W習(xí)機制和引入自適應(yīng)控制因子于追隨者位置中，增強了算法的局部開發(fā)能力；文獻[6]引入慣性權(quán)重因子和結(jié)合種群成功率來平衡算法的全局和局部搜索能力；文獻[7]將正弦余弦算法嵌入SSA中并對最優(yōu)樽海鞘的空間進行差分演化變異策略，增強了算法局部搜索能力；文獻[8]對SSA的領(lǐng)導(dǎo)者的更新公式進行改進并引入領(lǐng)導(dǎo)者—跟隨者數(shù)量自適應(yīng)調(diào)整策略提升尋優(yōu)精度和穩(wěn)定性；文獻[9]引入自適應(yīng)變化的權(quán)重因子和黃金正弦算法增強算法的全局搜索和局部開發(fā)能力；文獻[10]結(jié)合引力搜索技術(shù)和正態(tài)云發(fā)生器，提升了算法的搜索效率。

上述算法雖然在不同程序上提高了算法的性能，但很少結(jié)合種群編碼的角度來改進，本文借鑒文獻[11]的思想提出一種復(fù)數(shù)編碼的樽海鞘群算法(A Complex Encoding Slap Swarm Algorithm，CESSA)。該算法從以下兩個方面進行改進：(1)構(gòu)建復(fù)數(shù)編碼樽海鞘群，拓展種群多樣性；(2)融合灰狼算法中頭狼的搜索思想，利用食物源位置分別指導(dǎo)當(dāng)前追隨者和上一個追隨者的搜索行為并取兩者平均值。通過13個基準(zhǔn)函數(shù)和4個非線性方程組對算法進行測試，驗證了CESSA算法的有效性。

1 樽海鞘群算法

在海洋中，樽海鞘在覓食過程中彼此形成環(huán)狀的長鏈，該長鏈分為兩部分：一部分為領(lǐng)導(dǎo)者，位于長鏈的前端；另一部分為追隨者，位于領(lǐng)導(dǎo)者其后，逐個相連。領(lǐng)導(dǎo)者以食物源為目標(biāo)，其位置更新公式如下：

其中，F(xiàn)j表示第j 維領(lǐng)導(dǎo)者的位置，c1表示收斂因子，c2，c3∈[0，1]之間均勻分布的隨機數(shù)，lbj，ubj為搜索空間第j維的下界和上界。l為當(dāng)前迭代次數(shù)，lmax為最大迭代次數(shù)。

追隨者的位置更新公式如下：

2 復(fù)數(shù)編碼樽海鞘群算法

2.1 復(fù)數(shù)編碼

對于一個d維函數(shù)優(yōu)化問題，則構(gòu)建一個d維的復(fù)數(shù)空間，記第i個復(fù)數(shù)為：

其中Ri和Ii分別表示第i個復(fù)數(shù)的實部和虛部。

2.2 復(fù)數(shù)編碼樽海鞘群初始化

由（6）式可知一個復(fù)數(shù)可以用模和幅角來表示，則需按（5）式分別隨機產(chǎn)生一個 d 維模 ρi空間和 d 維幅角 θi空間。

i=1，2，…，d，于是構(gòu)成d維復(fù)數(shù)，[ai，bi]為問題變量的取值范圍，即第i個復(fù)數(shù)可以寫成如下：

2.3 復(fù)數(shù)編碼樽海鞘群搜索行為及模與幅角更新

在灰狼算法(Grey Wolf Optimizer，GWO)[12]中，狼群群體構(gòu)建了嚴(yán)格的等級制度，它們分為α，β，δ和ω狼，在覓食過程中α，β，δ狼指導(dǎo)ω狼向食物源搜索前進。其搜索獵物的數(shù)學(xué)公式為：

其中，Xp(t)為食物源的位置，X(t)為第t代個體的位置，r1，r2∈[0，1]之間的隨機數(shù)，·表示乘法運算。而在SSA算法中的性能取決于領(lǐng)導(dǎo)者的搜索能力，若領(lǐng)導(dǎo)者陷入局部最優(yōu)，則跟隨者必陷入局部最優(yōu)。因此本文嘗試在復(fù)數(shù)編碼的樽海鞘群追隨者過程中，利用食物源位置分別指導(dǎo)當(dāng)前樽海鞘和上一個樽海鞘的搜索行為；又由于在種群初始化階段分別產(chǎn)生了模和幅角種群，所以追隨者的位置更新公式分為模與幅角更新，其公式重新定義如下：

其中，bestρ表示最佳模的位置，ρi-1j表示i-1個模第j維的位置；bestθ表示最佳幅角的位置，θi-1j表示i-1個幅角第j維的位置，A1，A2，C1，C2分別由式(9～10)產(chǎn)生的值。

2.4 適應(yīng)度計算

為計算目標(biāo)函數(shù)值，必須將復(fù)數(shù)編碼轉(zhuǎn)換為實數(shù)編碼，實數(shù)值為復(fù)數(shù)模，其符號由幅角決定，具體做法：

其中RVi為復(fù)數(shù)轉(zhuǎn)換為實數(shù)后的值。

2.5 CESSA實施步驟

通過上述分析，CESSA的實施步驟如下。

步驟1：設(shè)置種群規(guī)模、最大迭代次數(shù)和由問題邊界計算出模和幅角的取值范圍等參數(shù)。

步驟2：在邊界范圍內(nèi)按（5）式隨機初始化模和幅角種群，按(6)式構(gòu)成復(fù)數(shù)編碼種群，再按(17～18)式轉(zhuǎn)換為實數(shù)編碼，并求解此時目標(biāo)函數(shù)值fmin、最佳模位置和最佳幅角位置。

步驟3：判斷算法是否終止，如果是，輸出目標(biāo)函數(shù)值fmin、最佳模位置和最佳幅角位置，否則進入步驟4。

步驟4：分別對實部和虛部更新，即對模和幅角更新，首先按(11～13)式對模更新并處理變量越界，其次按(14～16)式對幅角更新并處理變量越界，最后按(17～18)式轉(zhuǎn)換為實數(shù)編碼。

步驟5：對更新后模與幅種群中的每一個樽海鞘求解其目標(biāo)函數(shù)值，并判斷是否優(yōu)于上一代目標(biāo)函數(shù)值，如果是則替換目標(biāo)函數(shù)值、對應(yīng)的模和幅角。再對整個種群求解此時目標(biāo)函數(shù)值fnew、最佳模位置和最佳幅角位置。

步驟6：判斷fnew是否小于fmin，如果是則替換fmin、最佳模位置和最佳幅角位置。迭代次數(shù)加1，跳轉(zhuǎn)至步驟3。

2.6 CESSA算法時間復(fù)雜度分析

假設(shè)種群規(guī)模N，問題維數(shù)n，最大迭代次數(shù)MaxIter，目標(biāo)函數(shù)f (x)，式(3)的運行時間t1，由SSA的實現(xiàn)步驟可知SSA 的時間復(fù)雜度為：MaxIter×(N×( N 2×n+N 2×t1)+N×f (n))=O( f (n)+n)，設(shè)式(11～16)的運行時間t2，則CESSA 算法的時間復(fù)雜度為：MaxIter×(N2×n+N×(t1+t2)+2×N×n+N×f (n))=O( f (n)+n)，雖然運行時間有所增加，但當(dāng)問題規(guī)模足夠大時，算法的時間復(fù)雜度并未增加。

3 仿真實驗與結(jié)果

3.1 基準(zhǔn)函數(shù)測試

為了驗證CESSA算法的性能，選取文獻[1]中13個基準(zhǔn)函數(shù)進行測試，其中f1～f7屬于單峰函數(shù)，僅包含一個全局最優(yōu)，這些函數(shù)能夠測試算法的局部開發(fā)能力；f8～f13屬于多峰函數(shù)，包含多個局部最優(yōu)，這些函數(shù)能夠測試算法的全局搜索能力。函數(shù)表達式、維度、自變量取值范圍和理論值如表1所示。

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

利用CESSA算法對13個基準(zhǔn)函數(shù)進行求解，并與基本SSA算法、GWO算法進行對比，以驗證綜合改進策略的效果。為了公平比較，所有算法的參數(shù)設(shè)置：種群規(guī)模為30，最大迭代次數(shù)為500，其余參數(shù)設(shè)置與原論文一致。每種算法在Matlab 2016a中獨立運行30次，計算結(jié)果如表2所示，表中的加粗字體表示最佳實驗結(jié)果。

從表2可知，對13個基準(zhǔn)函數(shù)而言，對f6和f13這2個函數(shù)，CESSA算法求解平均值Mean和方差Std僅次于基本SSA算法，但優(yōu)于GWO算法；但是，對f1～f4，f9和f11這6個函數(shù)，CESSA算法求解的平均值Mean達到理論最優(yōu)值，方差Std均為0，明顯勝出基本SSA和GWO算法；而未達到理論最優(yōu)值的函數(shù)f5，f7，f8，f10，f12，無論是平均值Mean還是方差Std也都優(yōu)于基本SSA和GWO算法。

表2 基準(zhǔn)函數(shù)的實驗結(jié)果

為了直觀地展示CESSA算法的收斂性能，圖1～圖5給出了部分基準(zhǔn)函數(shù)前100代的收斂曲線（隨機選取30次實驗結(jié)果中某一次），從圖1～圖4可知，CESSA算法收斂速度最快，幾乎呈直線下降；從圖5可知，雖然CESSA算法初期收斂速度不是最快，但中后期進化明顯?？梢娋C合改進策略有助于提升算法的求解精度、收斂速度和魯棒性。

圖1 f3函數(shù)收斂曲線

圖4 f7函數(shù)收斂曲線

圖5 f8函數(shù)收斂曲線

3.2 非線性方程組測試

為了進一步驗證CESSA算法的性能，采用文獻[13]中含有較多根的4個方程組，這里表示例1～例4；并與文獻[13-14]中部分算例進行比較，參數(shù)設(shè)置與其相同，每個方程組用CESSA算法(鑒于篇幅，未列出SSA、GWO算法計算結(jié)果)獨立運行50次的計算結(jié)果如表3～表6所示。

例1：

其中：xi∈[-10,10],i=1,2,共有13個根。

例2：

其中：xi∈[-1,1],i=1,2,共有8個根。

例3：

其中：xi∈[-2,2],i=1,2,共有10個根。

例4：

由表3～表6可知，對例1而言，CESSA算法獲取9個根且與理論值較為接近，而文獻[14](IBOA)僅獲取8個根，從求解根效果來看，CESSA算法略優(yōu)于IBOA算法；對例2而言，CESSA算法獲取全部根且與理論值較為接近，求解成功率為100%，與文獻[13]效果一致；對例3 而言，CESSA算法獲取全部根且與理論值較為接近，與IBOA算法求解效果一致；對例4而言，CESSA算法獲取8個根且與理論值較為接近，丟失1個根，次于文獻[13]。

表3 CESSA算法求例1的結(jié)果

表6 CESSA算法求例4的結(jié)果

綜上所述，所有實驗結(jié)果表明CESSA算法在全局搜索和局部開發(fā)方面具有相對優(yōu)勢。

4 結(jié)語

本文基于復(fù)數(shù)編碼與灰狼算法頭狼搜索獵物行為提出一種復(fù)數(shù)編碼的樽海鞘群算法。首先構(gòu)建復(fù)數(shù)編碼樽海鞘群，拓展種群多樣性；其次對樽海鞘群追隨者方式進行改進，利用食物源位置分別指導(dǎo)當(dāng)前樽海鞘和上一個樽海鞘個體。通過13個基準(zhǔn)測試函數(shù)和4個非線性方程組的仿真實驗，所有實驗結(jié)果表明：采用綜合改進策略的CESSA算法可以有效提升原SSA算法的性能。

圖2 f4函數(shù)收斂曲線

圖3 f6函數(shù)收斂曲線

表4 CESSA算法求例2的結(jié)果

表5 CESSA算法求例3的結(jié)果