基于混沌映射的自適應樽海鞘群算法*

童斌斌何 慶*陳 俊

(1.貴州大學大數據與信息工程學院，貴州 貴陽550025；2.貴州大學貴州省公共大數據重點實驗室，貴州 貴陽550025)

隨著社會的不斷發(fā)展，各種科學計算和應用問題的復雜性和規(guī)模也在日益增多，傳統(tǒng)的數值優(yōu)化方法難以在時間和求解精度上保持合理的平衡[1]。 近年來，群智能優(yōu)化算法由于高效、易于實現、參數少等優(yōu)點，受到了學者的廣泛關注。 群智能優(yōu)化算法作為一種仿生學優(yōu)化算法，是通過模擬自然界生物的個體和群體行為發(fā)展而來，例如粒子群算法(Particle Swarm Optimization，PSO)[2]、 蝙 蝠 算 法(Bat Algorithm，BA)[3]、 正 弦 余 弦 算 法(Sine Cosine Algorithm，SCA)[4]、蜻蜓算法(Dragonfly Algorithm，DA)[5]、蟻獅算法(Ant Lion Optimizer，ALO)[6]、蚱蜢優(yōu)化算法(Grasshopper Optimisation Algorithm，WOA)[7]等。

2017 年，Mirjalili 等提出了一種樽海鞘群算法(Salp Swarm Algorithm，SSA)[8]，樽海鞘群算法是一種新型的群智能優(yōu)化算法，通過模擬海洋中樽海鞘的個體和群體行為發(fā)展而來，在算法中由領導者和追隨者兩個子群組成，領導者處于樽海鞘鏈的前端，余下的作為追隨者。

樽海鞘群算法由于參數少、計算量小、易于實現等優(yōu)點[9-10]，自提出后得到了廣泛的應用，例如，張成軍等[11]將混合樽海鞘差分進化算法應用于三維航跡規(guī)劃；林國營等[12]將樽海鞘群算法應用于電網公司需求響應補貼定價；姚遠遠等[13]采用一種多目標樽海鞘群算法來解決TFT-LCD 面板陣列制程調度問題，并取得了較好效果。 Sayed 等人[14]把樽海鞘群算法和混沌理論相結合用于最小化所選特征的數目。

在算法層面上，雖然樽海鞘群算法與其他優(yōu)化算法相比更加易于操作和理解，但算法仍然存在收斂速度較慢，迭代后期種群多樣性較差、尋優(yōu)精度不高等缺點。 針對上述缺點，很多學者對樽海鞘群算法進行改進。 劉景森等[1]針對基本樽海鞘群算法易陷入局部最優(yōu)、尋優(yōu)結果不穩(wěn)定等問題，提出了一種面向全局搜索的自適應領導者樽海鞘群算法，通過在領導者位置上引入上一代位置和慣性權重，自適應的調整領導者和追隨者的數量來提高算法的收斂精度。 陳雷等[15]為了進一步提升樽海鞘群算法的尋優(yōu)效率和收斂精度，提出了一種基于衰減因子和動態(tài)學習的改進樽海鞘群算法，在領導者位置和追隨者位置更新上各自引入衰減因子和動態(tài)學習策略，以提高算法的局部開發(fā)能力和全局搜索能力。陳忠云等[16]提出了一種多子群的共生非均勻高斯變異樽海鞘群算法，按適應度將種群分成三個子群:領導者，追隨者和鏈尾者，對領導者進行新的位置更新策略，在追隨者位置上加入共生策略以及對鏈尾者進行非均勻高斯變異操作，使改進的樽海鞘群算法具有更好的收斂速度和尋優(yōu)精度。 張嚴等[17]提出了一種基于萊維飛行的改進樽海鞘群算法，利用萊維飛行策略對領導者位置進行隨機更新，同時追加對追隨者的更新條件來增強算法的全局尋優(yōu)能力以及加快算法的收斂速度。 Hegazy 等人[18]提出了一種固定慣性權重的改進樽海鞘群算法，加快搜索過程中的收斂速度，并應用于特征選擇問題。 上述算法均從不角度對樽海鞘群算法進行改進，雖然算法取得了較好的效果，但算法的求解精度和收斂速度仍需進一步提高。

綜上所述，本文針對樽海鞘群算法收斂速度慢、易陷入局部最優(yōu)等問題，提出了一種基于混沌映射的自適應樽海鞘群算法(CASSA)。 首先，將混沌映射代替原來的隨機初始化種群方式，使得種群初始化階段能夠均勻的分布在上下限內，以增強種群的多樣性，同時能使種群更快的接近食物源位置，加快算法的收斂速度；其次，采用自適應權重方式來更新領導者的位置，讓領導者能更加快速的接近最好的食物源；最后，對原有追隨者的位置進行新的更新策略，使其不再進行盲目跟隨，同時更多的保留自身信息。 通過對10 個標準測試函數的仿真結果表明，本文方法相比于其他優(yōu)化算法具有更高的魯棒性。

1 基本樽海鞘群算法

樽海鞘群算法是Mirjalili 等人[8]通過模擬海洋中樽海鞘個體及群體行為發(fā)展而來的一種群智能優(yōu)化算法。 將樽海鞘群分為兩個子種群:領導者和追隨者，領導者位于樽海鞘鏈的前端，其余個體作為追隨者，樽海鞘群算法具體數學描述如下。

1.1 種群初始化

在樽海鞘群算法中，假設樽海鞘的捕食空間是N×D維，其中，N為種群大小，D為空間的維度，種群初始化的數學描述如式(1)所示:

式中:ub，lb 分別代表了捕食空間的上限和下限，種群初始化過程完全隨機。

1.2 領導者的移動方式

在捕食空間中尋找到最優(yōu)的食物源是種群的目標，在種群探索階段，食物源的位置即是全局最優(yōu)解，影響著領導者的位置移動，領導者的位置更新如式(2)所示:

式中:代表領導者i在第j維的位置，Fj表示食物源在第j維的位置，c2，c3是[0，1]上的隨機數，參數c1的數學描述如式(3)所示

式中:t和Tmax分別代表了當前迭代次數和最大迭代次數，m為常量的冪指數。 從式(3)可以看出，c1隨著迭代次數的增加非線性降低，當c1值較大時，有利于種群的探索能力，反之，有利于種群的局部開發(fā)能力，系數c1使得種群的開發(fā)和探索能力處于較好的平衡狀態(tài)，因此，c1是樽海鞘群算法最為重要的參數。

1.3 追隨者的移動方式

在樽海鞘群算法中，追隨者跟隨領導者移動，移動方式滿足牛頓第二定律，如式(4)所示。

式中:代表了追隨者i所在第j維空間的位置，代表了追隨者i-1 所在第j維空間的位置，a代表加速度，v0表示初速度，Δt即為迭代次數之差，故Δt＝1，由于初速度為0，因此式(4)可以表示為式(7)。

2 改進的樽海鞘群算法

為了進一步提高樽海鞘群算法的求解精度和收斂速度，同時保證算法探索和開發(fā)能力的平衡，在保持種群個體不變的條件下，本文從種群初始化、領導者的位置更新和追隨者位置更新三個角度改善算法性能，分別側重于收斂速度、全局搜索和局部搜索，具體描述如下。

2.1 混沌映射

研究表明，種群初始化作為群能算法的重要環(huán)節(jié)，初始化的位置的好壞可以直接影響算法的收斂速度和解質量[19-20]，例如，均勻分布比隨機分布解空間的覆蓋率更全，更容易得到好的初始解。 基本樽海鞘群算法采用隨機種群初始化操作，無法覆蓋整個解空間。 混沌序列在一定范圍內具有遍歷性、隨機性及規(guī)律性的特點與隨機搜索相比，混沌序列能以更高的概率對搜索空間進行徹底搜索，可使算法跳出局部最優(yōu)，保持群體的多樣性。

基于以上分析，為了更大幾率的得到好的初始解位置，加快種群的收斂速度，本文采用具有較好遍歷均勻性和更快迭代速度的Tent 混沌映射方法，提高初始解的覆蓋空間，計算方法如式(8)所示。

式(8)中:為區(qū)間[0，1]的混沌序列，再根據式(9)進行逆映射得到種群的初始位置，這樣的混沌映射方法能夠大幅度的增大初始解空間的覆蓋率，讓種群能夠更快的靠近最優(yōu)解，從而加快算法的收斂速度。

2.2 自適應權重變化

在基本樽海鞘群算法中，從領導者的位置更新方式我們可以看出，領導者的位置更新主要受到食物源和參數c1的影響，c1值越大時有利于算法的探索能力，c1值越小時，有利于算法的開發(fā)能力，同時領導者的位置移動還受到縮放因子c2的影響，c2為均勻分布的隨機數，這樣的縮放因子使得領導者的移動具有很大的盲目性，且c2的取值多為無效取值。 針對上述問題，本文提出了一種新的領導者位置更新方式，在食物源的位置添加自適應權重，算法前期權重較大，讓算法有足夠強的探索能力，隨著迭代次數的增加，權重自適應減小，用于增強算法的局部開發(fā)能力，在算法的中后期，權重開始增大，使領導者具備跳出局部最優(yōu)的能力，具體數學描述如式(10)所示。

式中:表示個體i在捕食空間j維的位置，Fj為食物源位置，c1為先遞減后遞增的權重，t代表當前迭代次數，Tmax代表最大迭代次數。

2.3 追隨者機制變化

在基本樽海鞘群算法中，追隨者根據式(7)進行位置更新，從式中可以看出，第i只個體根據第i-1 只個體進行位置移動，而沒有考慮上一個體適應度的好與壞，即追隨者的位置移動具有一定的盲目性，追隨者i的位置移動只與個體i-1 有關，缺乏與其他個體進行信息交流的能力，這種移動方式極易導致算法陷入局部最優(yōu)。 針對上述缺點，本文提出了一種新的追隨者移動方式，具體數學描述如式(12)所示。

式中:表示追隨者的位置，F是權重因子，隨迭代次數逐漸遞減，c2 代表了隨機從領導者中選擇的個體，如果當前個體i的適應度大于領導者c2 的適應度，則在適應度較大的個體位置上添加權重因子，用來降低較差位置個體的影響，進而提升了較優(yōu)個體的權重；否則，個體i只在自己周圍波動。 這種移動方式，可以大大的降低盲目追隨性，增強了種群間的信息交流，同時還能保留追隨者的自身信息，保證種群的多樣性。

2.4 算法描述

本文通過添加混沌映射和自適應權重，同時改變領導者和追隨者的位置更新方式，得到了改進的樽海鞘群算法(CASSA)，平衡了領導者的探索和開發(fā)能力，降低了追隨者盲目性，更好的保留了個體信息，同時保證種群的多樣性，CASSA 的具體算法流程如下所示。

Step 1 參數設定。 包括最大迭代次數Tmax、種群規(guī)模N、上下界等。

Step 2 初始化種群。 改變原始的位置隨機方式，采用混沌映射的方法，增大解空間的覆蓋率。

Step 3 生成自適應權重c1，根據式(10)，更新領導者位置。

Step 4 隨機產生領導者c2，跟隨式(12)，更新追隨者位置。

Step 5 判斷結束條件，若滿足條件，則輸出最佳食物源位置；否則，執(zhí)行step 3。

CASSA 的偽代碼如下所示:

3 實驗仿真及結果分析

3.1 函數說明及實驗參數設置

為了檢驗本文方法的性能，通過選擇多組標準測試函數進行驗證，函數的具體形式如表1 所示，測試函數集中的函數包含單峰、多峰、高維、低維等特征，該測試函數集能夠全面客觀的反映算法的尋優(yōu)性能，其中，F1～F5 為單峰函數，只有一個全局最優(yōu)值，能很好的反映算法的收斂性能，F6 ～F10 為多峰函數，有很多局部最優(yōu)值，能很好的反映算法跳出局部最優(yōu)的能力。 仿真實驗環(huán)境是基于Windows 10操作系統(tǒng)，8 GB 內存，利用MATLABR2016b 進行編程測試。 仿真測試中，CASSA 算法的最大迭代次數M為1 000，種群大小N為30，所有為了消除算法的偶然性，每個測試函數獨立運行30 次，得到每個測試函數的最佳值、平均值、標準差、運行時間，記只改變追隨者位置移動方式為CASSA1、只改變領導者位置移動方式為CASSA2，結果如表2 所示。

表1 基準函數

表2 基準函數結果對比

3.2 實驗結果及分析

隨著搜索空間維度的增加，算法的求解難度會呈指數級遞增，為了驗證CASSA 算法的尋優(yōu)精度，對于F1 ～F5 單峰函數分別設置了200 維、200 維、200 維、30 維、30 維進行實驗分析，從表2 的實驗結果可以得到，在求解這5 個函數最優(yōu)值時，SSA、SCA、ALO、GOA 算法求解精度較差，30 次獨立重復實驗，上述算法均無法找到理論最優(yōu)值，且存在10＋3 級誤差，本文提出的CASSA 算法在F1～F4 函數求解上的最佳值和平均值在30 次獨立重復實驗中都能達到算法的理論最優(yōu)值，同時，4 個單峰函數求解的標準差均為0，證明了算法具有很好的穩(wěn)定性。從圖1(a)、1(b)、1(c)、1(d)上可以看出，在單峰高維求解問題上，CASSA 算法均在400 代以內得到收斂，再次證明了CASSA 算法具有很好的收斂精度和收斂速度，函數F5 雖然不能找到理論最優(yōu)值，但算法的標準差最小，算法更為穩(wěn)定。

在求解F6～F10 多峰函數的問題上，F7、F9、F10的維度分別設為100 維、100 維、4 維，CASSA 算法均能找到理論最優(yōu)解，其中F7 和F9 在30 次獨立重復實驗中均能找到理論最優(yōu)值，平均值及標準差都為0，在求解時間上也具有很強的競爭性，在函數F10 求解上，CASSA 算法能找到理論最優(yōu)解，算法的平均值和標準差也較小，從圖1(g)(i)可以看出，函數F7 和F9 均能在200 代以內得到收斂，證明了算法具有很好的收斂性能，從圖1(j) 可以看出，CASSA 算法的收斂曲線呈現階梯狀下降，在100 ～200 代陷入第一次局部最優(yōu)，在200 ～400 代陷入第二次局部最優(yōu)，在400 代之后多次陷入局部最優(yōu)，但算法都能很好的跳出當前局部最優(yōu)，也證明了領導者自適應更新策略的有效性。 在函數F6、F8 求解上分別設置了100 維和50 維，從表2 可以看出，在上述2 個測試函數中，CASSA 算法均不能找到理論最優(yōu)值，但和原始的SSA 算法及其他優(yōu)化算法相比，具有更好的尋優(yōu)性能，在平均值和標準差方面也比其他算法好，再次證明算法具有一定的穩(wěn)定性，從圖1(f)、1(h)可以看出，CASSA 算法的尋優(yōu)虛線呈階梯狀下降，在圖1(f)表現的更為突出，尋優(yōu)曲線呈現多個階梯，再次證明CASSA 算法策略具有跳出局部最優(yōu)的能力。

圖1 CASSA 算法的收斂曲線圖

為分析改進策略的有效性，表2 給出了兩種改進策略的尋優(yōu)結果，記只改變追隨者位置移動方式為CASSA1、 只改變領導者位置移動方式為CASSA2，對于單峰函數F1 ～F4，CASSA1 和CASSA2都能找到理論最優(yōu)值，同時改進策略的平均耗時，平均值和標準差都為0，表明算法具有很好的性能，在F5 函數的求解上，CASSA1、CASSA2 算法均不能找到理論最優(yōu)值，但算法的標準差較小，算法具有很強的穩(wěn)定性。 對于多峰函數F6 ～F10，在F7、F9、F10三個函數求解問題上，CASSA1、CASSA2 都能找到理論最優(yōu)值，在求解函數F6、F8 時，均能提升十個左右的數量級，同時兩種改進策略相比其他優(yōu)化算法的平均耗時、均值和標準差都較小，再次證明了兩種改進策略的有效性。

從平均耗時上來看，SSA 和SCA 平均耗時最短，ALO 和GOA 的平均耗時最長，本文所提CASSA算法在時間上具有很強的競爭性，在F1 和F2 函數求解上耗時最短，效果最佳，在F3～F10 函數求解時間上相當，出現這種情況是合理的，因為算法引入了混沌映射，使得算法前期解空間的覆蓋率更大，導致運行時間變長，總體來看，CASSA 算法的平均耗時增加幅度不大，但尋優(yōu)性能更好，達到了求解精度和求解時間的平衡。

3.3 與其他改進算法的比較

為了進一步驗證CASSA 算法的收斂精度和收斂速度，將CASSA 算法與目前最新的增強型SSA 算法:RDSSA[14]、MSNSSA[15]、ALSSA[16]進行平均值和標準差的比較，結果如表3 所示。

表3 與參考文獻中算法的對比

從表3 可以看出，在F1～F4 單峰函數中，CASSA算法在收斂精度能找到理論最優(yōu)值，要優(yōu)于其他3 個算法，同時通過參考RDSSA[14]、MSNSSA[15]、ALSSA[16]的收斂曲線圖發(fā)現，CASSA 算法能在400 代以內得到收斂，而其他3 個算法都要到500 代以后才能收斂，且無法找到理論最優(yōu)值，尤其是RDSSA 在30 維F1～F4函數求解問題上沒有CASSA 的100 維高維尋優(yōu)好，但是對于函數F5，CASSA 要比MSNSSA16 的尋優(yōu)結果差，但耗時更短，出現這種情況也是合理的，MSNSSA 算法引入了更多的算子，使得算法能搜索到更多的解，同時也導致了運行時間邊長。 在多維函數F6～F9 求解問題上，CASSA 算法的平均尋優(yōu)結果都要優(yōu)于另外3 個算法，雖然在函數F6 和F8 上無法找到理論最優(yōu)值，但標準差更小，算法更為穩(wěn)定。 在求解函數F10 問題上，CASSA 算法的尋優(yōu)結果和MSNSSA[15]算法平均值上僅差1 個數量級。

綜上所示，通過對F1 ～F10 函數求解的結果比較可以得到，CASSA 算法在高維單峰函數上比其他3 個算法具有更好的性能，同時算法的平均耗時短，收斂速度更快；在高維多峰函數求解問題上，CASSA算法也能找到理論最優(yōu)值，同時算法的標準差更小，算法更加穩(wěn)定，具有很強的競爭力。

3.4 CASSA 算法的時間復雜度分析

除了算法的收斂精度和收斂速度，時間復雜度更是檢驗算法性能的關鍵指標，用符號O表示。 在SSA 算法中，假設算法的種群數為N，維度為n，參數設置和產生隨機數的時間分別為t1和t2，求解適應度的時間為f(n)，對適應度排序時間為t3，那么，種群初始化時間為:

進入在算法迭代階段，領導者和追隨者的數目都為N/2，假設計算c1的時間為t4，隨機數c2，c3生成時間與t1保持一致，領導者和跟隨著更新每一維的時間為t5，那么迭代時間的時間復雜度為:

在更新食物源和邊界處理階段，設求解適應度的時間仍然為f(n)，每一維邊界處理時間為t6，食物源位置替換時間為t7，那么此階段的時間復雜度為:

綜上，SSA 算法的時間復雜度為:

在改進的CASSA 算法中，設種群初始化，求解適應度時間，參數設置時間等與SSA 算法保持一致，每一維混沌映射的時間設為t8，則CASSA 算法種群初始化階段的時間復雜度為:

在領導者和追隨者位置更新階段，設由式(11)產生自適應權重c1的時間為t9，追隨者隨機選擇領導者C2 的時間為t10，適應度比較的時間為t11，則該階段的時間復雜度為:

在更新食物源和邊界處理階段，由于CASSA 算法跟SSA 算法相比沒有任何改變，所以該階段的時間復雜度為:

綜上，CASSA 算法總的時間復雜度為:

綜上所述，本文所提CASSA 算法和基本SSA 算法在時間復雜度相同，并未降低算法的執(zhí)行效率。

4 結束語

本文提出了一種基于混沌映射的自適應樽海鞘群算法(CASSA)，將混沌映射引入種群初始化，使得算法在解空間的覆蓋率更大，以使種群更快的接近食物源位置，加快算法的收斂速度，改進領導者和追隨者位置的位置更新方式，使得算法具有更強的收斂精度和跳出局部最優(yōu)能力。 通過使用最佳值、平均值、標準差等指標在10 個標準測試函數對算法進行檢驗，結果表明，本文方法相比于其他優(yōu)化算法具有更好的魯棒性。 在后續(xù)的研究中，將考慮將CASSA 算法應用于工程實踐問題中。