陳忠云，張達敏，辛梓蕓，張繪娟，閆 威

貴州大學 大數據與信息工程學院，貴陽 550025

1 引言

大自然充滿執(zhí)行不同任務的社交行為，雖然所有個體和群體行為的最終目標是生存，但生物在群體中進行合作和互動有以下幾個原因：狩獵、防御、導航和覓食。多種動物和昆蟲的智能群體行為多年來引起了研究者的關注。計算機科學研究人員將這些群體模型作為解決復雜現實世界問題的框架，從而產生了人工智能的一個分支，通常被稱為群體智能。目前已經提出了許多的智能優(yōu)化算法，例如遺傳算法（Genetic Algorithm，GA）[1]、粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）[2]、蝴蝶優(yōu)化算法（Butterfly Optimization Algorithm，BOA）[3]等。這些算法已成功應用于各種科學領域，如過程控制、生物醫(yī)學信號處理[4]、圖像處理以及許多其他工程設計問題[5]。

樽海鞘群算法（Salp Swarm Algorithm，SSA）是2017 年由Mirjalili 等人提出的一種新型啟發(fā)式智能算法[6]。樽海鞘群算法具有結構簡單、參數少、容易實現等優(yōu)點，受到國內外專家學者廣泛關注，已被成功應用到多目標優(yōu)化和工程設計問題[6-7]。雖然樽海鞘群算法在求解大部分優(yōu)化問題時具有優(yōu)越性，但是與其他群智能算法一樣，仍然存在求解精度低和收斂速度慢等缺陷。文獻[8]將樽海鞘群算法中跟隨者單步位置更新方式改為兩步，分別根據自適應平局移動策略和領域最優(yōu)引領策略進行更新，之后在引入方向學習策略以一定概率對個體位置進行擾動，提高種群多樣性，使算法跳出局部最優(yōu)。文獻[9]提出固定慣性權重，可以加快搜索過程中的收斂速度，并應用特征選擇問題。文獻[10]把樽海鞘群算法和混沌理論相結合提出混沌樽海鞘群算法，在解決特征提取問題時，能發(fā)現最優(yōu)特征子集，最大程度地提高分類精度，最小化所選特征的數目。文獻[11]提出基于樽海鞘群算法的無緣時差定位，利用SSA 解決TDOA（Time Difference of Arrival）定位結算問題，驗證算法在多站時差定位問題上的有效性與優(yōu)越性。文獻[12]提出基于Tent映射的灰狼優(yōu)化算法，通過混沌映射產生初始種群，增加種群個體的多樣性。文獻[13]提出自適應Tent混沌搜索的蟻獅優(yōu)化算法，自適應調整混沌搜索空間得到最優(yōu)解，改善適應度較差個體，提高種群整體的適應度和尋優(yōu)效率。文獻[14]改進Tent 映射，具有更優(yōu)越的混沌特性，能更好地實現混沌尋優(yōu)。文獻[15]選擇精英個體進行反向學習，拓展種群的搜索區(qū)域，增強多樣性和加速收斂。文獻[16]提出重心方向學習（Centroid Opposition-Based Learning，COBL），以整個群體重心為參考點計算反向點，這樣反向點包含了群體搜索經驗。

受上述文獻的啟發(fā)，本文提出了一種改進混沌精英質心拉伸機制的樽海鞘群算法，以解決標準樽海鞘群算法存在的求解精度不高和收斂速度慢等問題。通過改進Tent映射來生成樽海鞘群算法的初始種群，增強初始個體的均勻性。種群個體更新后，選擇部分精英個體并采用質心拉伸機制，有利于搜索更多的有效區(qū)域來提高群體的多樣性，增強算法的全局探索和局部開發(fā)能力。通過求解多種維度的12 個典型復雜函數以及部分CEC2014函數的最優(yōu)解來驗證混沌精英質心拉伸機制樽海鞘群算法（Chaotic and Elite centroid stretching mechanism Salp Swarm Algorithm，CESSA）的有效性。

2 樽海鞘群算法

樽海鞘群算法[6]是Mirjalili 等人揭示的一種全新的智能優(yōu)化算法，這種算法的思想出自于樽海鞘的聚集行為，即樽海鞘鏈。樽海鞘以水中的浮游植物（海藻等）為食，通過吸入噴出海水完成在水中的移動。在樽海鞘群算法中，樽海鞘鏈由兩種類型的樽海鞘組成：領導者和追隨者。領導者位于樽海鞘鏈的最前面，而其他個體則為追隨者的角色。

樽海鞘的種群行為與其他算法有所不同，其并不是以“群”分布，而是采用頭尾連接的形式，組成“鏈”的形態(tài)，順次跟隨著移動。樽海鞘鏈中的領導者排在隊伍的最前端，它對環(huán)境有著最優(yōu)的判斷，但與其他群智能算法不同的是，領導者不會直接影響整個種群的移動方向，而是直接影響緊接著的第二個樽海鞘個體的位置更新，第二個個體影響第三個個體，以此類推。因此，領導者的位置對其余樽海鞘位置影響程度會順位遞減，這使排在后面的個體有著更好的多樣性。

在樽海鞘群算法中，定義每個樽海鞘個體的位置矢量X用于在N維空間中搜索，其中N是決策變量的數目。樽海鞘群算法中位置向量X將由維度為d的N個樽海鞘個體組成。因此，種群向量由N×d維矩陣構成，如下公式所示：

在樽海鞘群算法中，食物源的位置是所有樽海鞘個體的目標位置。因此，領導者的位置更新公式如下所示：

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

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

在求解測試函數優(yōu)化問題中，搜索范圍變化大。為了使樽海鞘群算法前期搜索具有更好的全局性和隨機性，本文選取多個領導者來進行更新，但領導者太多，算法隨機性較強，這會導致算法穩(wěn)定性降低，因此為了權衡算法的隨機性和穩(wěn)定性，本文選取一半的樽海鞘個體作為領導者。

為了更新追隨者的位置，使用以下公式（牛頓運動定理）：

因此，由式（2）和式（5）可以模擬樽海鞘鏈的行為機制。

3 混沌精英質心拉伸機制的樽海鞘群算法

3.1 改進Tent映射的種群初始化

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

混沌序列具有隨機性、遍歷性和規(guī)律性等特點，通過其產生的樽海鞘群體有較好的多樣性。其基本思路是，通過映射關系在[0，1]區(qū)間產生混沌序列，然后再將其轉化到個體的搜索空間。產生混沌序列的模型有許多，文獻[18]提出，Tent 映射比 Logistic 映射能夠生成更好的均勻序列。但Tent 映射產生的混沌序列存在小周期和不確定周期點等缺點。為克服此類缺陷，在原有的Tent混沌映射中加入一個隨機變量r/N，改進后的Tent映射的數學表達式為：

其中，r為[0，1]之間的隨機數；μ∈[0,2]是混沌參數，μ越大，混沌性越好，本文取μ=2；i=1,2,…,N表示種群規(guī)模；j=1,2,…,d表示混沌變量序號。

Tent 混沌映射對初始值的選取非常敏感，給式（6）選取d個具有微小差異的初始值，則可得到d個混沌序列。然后再將d個混沌序列進行逆映射，得到相應的個體搜索空間變量。

其中，[lbi,ubi]為的搜索范圍。

3.2 精英質心拉伸機制

文獻[16]提出重心反向學習策略，利用種群的重心生成反向解，以更好利用群體信息。雖然這樣考慮到利用整個群體的信息，但包含的個體信息較多，算法運行成本較大。本文提出精英質心拉伸機制，選取群體中m個精英個體，求解其質心，然后根據質心對精英個體進行拉伸機制。質心和拉伸機制定義如下：

定義1（質心）設(x1,x2,…,xn)為D維搜索空間中n個個體，則其整體的質心定義為：

即得：

定義2（拉伸機制）若精英個體的質心為C，則某個精英個體xi的拉伸點定義為：

式中，w為[-1,1]之間的隨機數，a為一個極小的正數，F為適應度函數，LS為拉伸因子，衡量精英個體與全局最優(yōu)個體的差異程度，引導精英個體向質心個體學習。

由上述精英質心拉伸機制可以發(fā)現，利用精英個體的質心，作用于精英個體本身，以提升精英個體的性能。本文對當前種群中適應度最好的前m個精英個體運用拉伸機制。精英質心拉伸機制可從以下兩方面增強算法性能：首先，將拉伸后新群體與當前群體融合，選出融合后一半的最優(yōu)個體進入下一代種群中，以增強群體的多樣性，可減小算法陷入局部最優(yōu)的概率；其次，充分利用當前群體中精英個體搜索空間的有效信息，以此加快算法的收斂速度。由此可見，精英質心拉伸機制可較好平衡算法的探索和開發(fā)能力。

3.3 CESSA算法步驟

混沌精英質心拉伸機制的樽海鞘群算法步驟如下：

步驟1 初始化個體位置。使用改進的Tent 映射生成混沌序列，根據搜索空間的上下限，再把混沌序列逆映射為一個N×d維的矩陣。

步驟2 計算初始適應度值。根據測試函數計算N個樽海鞘的適應度值。

步驟3 選定食物源。把步驟2 中計算后的適應度值進行升序（或降序）排列，適應度值最好的樽海鞘位置選定為食物源位置。

步驟4 領導者和追隨者位置更新。確定食物源位置之后，選取種群中一半的樽海鞘個體根據式（2）更新領導者位置，其余的樽海鞘根據式（5）更新追隨者位置。

步驟5 精英質心拉伸機制。利用3.2節(jié)定義2所描述的精英質心拉伸的方法對當前種群中m個精英個體求解拉伸解，并比較更新每個樽海鞘個體的位置。

步驟6 計算適應值。計算更新后種群的適應度值，并更新食物源位置。

步驟7 重復步驟4～步驟6的更迭過程，如果達到設置的精度要求或規(guī)定的最大迭代次數，則終止算法，輸出全局最優(yōu)解。

4 仿真實驗與結果分析

為驗證本文提出的CESSA算法在求解優(yōu)化問題上的有效性和魯棒性，將CESSA 算法與SSA、PSO 以及GA 在12 個典型的標準測試函數最優(yōu)值求解上獨立進行50 次對比實驗1。另外還在CEC2014 基準函數中選取部分函數進行對比實驗2。

實驗1 采用如表1 所示的12 個復雜函數作為適應度函數。選取的測試函數中包含單峰、多峰等不同特征的測試函數。單峰函數為在定義上下限內只有一個嚴格上的極大值（或極小值），通常用來檢測算法收斂速度。多峰函數為含有多個局部最優(yōu)解或全局最優(yōu)解的函數，經常用于檢測算法探索能力和開發(fā)能力。另外，測試函數的求解維度也是一個重要因素，算法對低維度求解質量好時對高維度不一定也好。表1 中測試函數維度從2維到200維，這可以更加全面地驗證算法性能。

表1 基準函數

實驗環(huán)境為：Windows7系統，8GB內存，CPU 2.5GHz，算法基于Matlab14b用M語言編寫。

實驗設置最大迭代次數為1 000，初始樽海鞘群、粒子群和染色個體的規(guī)模都為30。對于CESSA、SSA、PSO和GA算法的其他相關參數設置如表2所示。

表2 算法參數設置

表3 記錄了50 次獨立實驗后從每種算法獲得結果的最佳值（Best）、平均值（Mean）和標準偏差（Std）以及求解成功率（Successful Rate，SR）和平均耗時（Time）等多個實驗對比數據。其中求解成功率為計算成功次數除以本次實驗的求解次數。判斷一次求解是否成功按照下式：

式中，FA為每次實際求解最佳值，FT為測試函數理論最佳值。

首先，表3 中的最優(yōu)值、平均值都可以反映算法的收斂精度和尋優(yōu)能力。對于6 個單峰函數(f1～f6) ，CESSA算法在求解精度上最高達到1E-33。同時，隨著搜索空間維度的增加，尋優(yōu)收斂精度4 種算法都在下降。另外標準SSA 算法在求解f4的時候，SSA 算法的求解能力就很差，與理論最優(yōu)值存在1E+03 級的誤差。而 CESSA 相對于 SSA、PSO 和 GA 尋優(yōu)精度都要好，并且其求解精度變化不大。伴隨求解維度的增加，對于算法求解難度也呈指數級別遞增，算法的收斂精度有所降低屬于正?，F象。對于6個多峰函數(f7～f12)，算法求解精度相對于單峰函數要低一些。同樣，隨著維度增加，算法求解精度也有所降低。當維度增加到200 維時，CESSA算法求解f12的精度降到1E-01，但CESSA算法較其他三種算法仍然具有很好的優(yōu)勢。因此，CESSA算法在求解單峰、多峰以及高維的基準函數時都有更好的尋優(yōu)效果和魯棒性。

表3 各算法基準函數的結果對比

其次，表3～表5中標準差和成功率可以反映算法的穩(wěn)定性和跳出局部最優(yōu)的能力。在f12函數的求解上，CESSA 算法的尋優(yōu)結果和理論結果還存在精度不足，但CESSA算法獨立50次計算的標準差基本比其他三種算法都要小。這說明CESSA算法對于低維和高維基準函數的尋優(yōu)求解有著很好的穩(wěn)定性，且在多峰函數上尋優(yōu)能力比較強，跳出局部最優(yōu)的能力相對于其他算法更好些。6個基準函數中有單峰、多峰、低維和高維，除了求解200 維成功率較差，CESSA 在成功率上基本為100%，而標準SSA在f1和f2這兩個基準函數的成功率為100%以外，其余基準函數成功率全部為0。隨著搜索維度的增加，標準SSA在尋優(yōu)求解能力上表現著很大不足。特別是在求解多維函數時，標準差和成功率都較差，說明標準SSA 跳出局部最優(yōu)的能力是較弱。而在CESSA 中引入精英質心拉伸機制后，這對算法后期跳出局部搜索具有很大作用。

再次，從平均耗時來看。由表3可知，改進的CESSA算法相對于標準SSA的平均耗時都要大，PSO算法和標準SSA算法互有優(yōu)劣，但總體運行時間均要優(yōu)于CESSA算法和GA 算法。CESSA 算法在SSA 種群更新后引入精英質心拉伸算子，使得算法能夠搜索到更多的解，這也就增加了算法運行時間。總體來看，CESSA 平均耗時比另外兩種算法增加得并不是很大，在允許范圍內。

Derrac 等在文獻[19]中提出，對于改進進化算法性能的評估，應該進行統計檢驗。換而言之，僅基于平均值和標準偏差值來比較算法優(yōu)劣還不夠，需要進行統計檢驗以證明所提出的改進算法比其他現有算法具有顯著的改進優(yōu)勢。為了判斷CESSA的每次結果是否統計上顯著地與其他算法的最佳結果不同，Wilcoxon 秩和檢驗在5%的顯著性水平下進行。表4給出所有基準函數的最優(yōu)值和其他算法的Wilcoxon 秩和檢驗中計算的p-value。例如，如果最佳算法是CESSA，則只在CESSA/SSA，CESSA/PSO、CESSA/GA 等之間進行成對比較。由于最佳算法無法與自身進行比較，針對每個函數中的最佳算法標記為N/A，表示“不適用”。這意味著相應的算法可以在秩和檢驗中沒有統計數據與自身進行比較。根據Derrac等人的論文，那些p-value<0.05的可以被認為是拒絕零假設的有力驗證。

表4 Wilcoxon秩和檢驗的p-value

根據表4 中的結果，CESSA 算法的p-value全部小于0.05，這表明該算法的優(yōu)越性在統計上是顯著的，即認為CESSA算法比SSA、PSO、GA具有更高的收斂精度。

所有算法的定量分析是基于12個基準函數的平均絕對誤差（Mean Absolute Error，MAE）。文獻[20]提出對優(yōu)化算法進行排序，MAE 是一種有效且可行的性能指標。表5 給出了這些基準函數的MAE 排序，其計算公式如下：

式中，mi為算法產生的最優(yōu)結果的平均值，oi為相應基準函數的理論最優(yōu)值，Nf為基準函數個數。計算出的MAE在表5中給出。

表5 MAE算法排名

由表5 可知，CESSA 排名為1，與另外三種算法相比，CESSA 提供了最小的MAE，進一步說明了CESSA的有效性。

圖1給出4個基準函數的平均收斂曲線。由于不同算法收斂精度存在較大差異，為便于觀察收斂情況，本文對尋優(yōu)適應度值（縱坐標）取10 為底的對數。由圖1（a）、（b）可看出，CESSA 算法的收斂曲線下降較快，并隨著更迭次數的增加持續(xù)尋優(yōu)，只在后期出現停滯。從圖1（a）、（b）可知，GA、PSO和SSA在迭代后期出現不同程度的停滯，且尋優(yōu)精度較低。圖1（c）、（d）是多峰函數的平均收斂曲線。從CESSA 算法的收斂性上可以看出，在f11上迭代前期收斂速度比較平緩，后期收斂速度較快。在f8函數上，CESSA算法在前期收斂速度較快，但算法前期收斂速度相對于PSO較慢。CESSA后期出現一定程度停滯，但收斂精度比另外三種算法要好。從圖中還可以看出，SSA、PSO和GA在后期基本都陷入局部最優(yōu)，但CESSA 算法最終的尋優(yōu)精度較其他算法仍然表現較好。無論單峰、多峰，還是低維和高維，對于每個基準函數CESSA比其他算法的收斂速度和尋優(yōu)精度要好。

圖1 部分基準函數平均收斂曲線

實驗2 為更好評估CESSA 算法的有效性和穩(wěn)定性。本文還在CEC2014 基準函數中選取部分單峰、多峰、混合（Hybrid）和復合（Composition）類型的函數進行優(yōu)化求解，如表6所示。在該實驗中，種群規(guī)模為30，最大迭代次數為500，維度為30。

表6 CEC2014基準函數

表7 記錄了CEC2014 中部分函數獨立運行30 次后每種算法的平均值和標準差的結果對比。CEC2014 函數具有復雜的特征，因此所有算法都較難找到函數最優(yōu)值。表7中結果顯示，CESSA算法在6個CEC2014基準函數上都求得比其他三種算法更優(yōu)的結果，進一步驗證了CESSA算法具有較好的有效性和魯棒性。

為比較本文改進算法與其他改進算法的優(yōu)劣性，將CESSA 算法與參考文獻[8]和文獻[10]中改進算法進行比較，其中直接引用了文獻[10]中CSSA1的數據，如表8所示（“—”表示參考文獻中未給出）。表1 基準測試函數中可變維度函數的dim 都設置為10，種群數目為50，最大迭代次數為500。

表7 CEC2014優(yōu)化結果對比

表8 與參考文獻中算法性能的對比

由表 8 可知，除了在求解f3、f8、f12時，文獻[10]算法的標準差好于CESSA算法，本文提出的CESSA算法在求解其他函數時的平均值和標準差都要好于文獻[8]和文獻[10]改進算法，進一步驗證了CESSA 算法的有效性。

綜上可知，混沌精英質心拉伸機制的樽海鞘群算法對本文所選取的基準函數都有很好的尋優(yōu)結果，特別是對于高維、多峰的函數，具有較好的穩(wěn)定性和尋優(yōu)能力。

5 結束語

本文在標準樽海鞘群算法的基礎上，引入改進的混沌映射和精英質心拉伸機制，提出一種改進的混沌精英質心拉伸機制的樽海鞘群算法，并將樽海鞘群算法應用于經典測試函數和CEC2014函數的尋優(yōu)問題中。本文不僅使用最優(yōu)值、標準差等指標對算法進行檢驗，還提出使用Wilcoxon 秩和檢驗對算法顯著性水平進行驗證。研究表明：基于混沌精英質心拉伸機制的樽海鞘群算法可以獲得更好的全局搜索和局部搜索能力，且可以收斂到質量更好的最優(yōu)解，算法的有效性和魯棒性也得到驗證。