混沌映射與動態學習的自適應樽海鞘群算法

卓 然，王未卿

(1.浙江特殊教育職業學院 基礎教學部，浙江 杭州 310023；2.北京科技大學 東凌經濟管理學院，北京 100083)

0 引 言

樽海鞘群算法SSA是一種全新智能優化算法[1]，其思想源于樽海鞘的聚集行為。該生物通過吸收海水的推動力移動，并以鏈式結構順次跟隨。樽海鞘可劃分為兩個群組：領導者和追隨者。鏈首為領導者，在搜索食物源中具備最優判斷，主導種群移動。其它稱為追隨者，追隨者相互跟隨，相互領導。每次迭代中，樽海鞘按適應性排序，個體相互跟隨，而非所有個體只向當前最優個體移動，降低了搜索過程陷入局部最優的概率，其尋優精度和收斂性能優于傳統粒子群算法、遺傳算法、蟻群算法、灰狼優化算法。此外，SSA的控制參數相對更少，大大減少了算法對控制參數的依賴。同時，其模型更為簡單，已廣泛應用于光伏系統功率控制[2]、無源時差定位[3]、網絡學習[4]、頻譜分配[5]、工程優化[6]和圖像分割[7]等領域。然而，傳統SSA依然存在尋優精度不高、易于陷入局部最優的不足，主要體現在：①隨機種群初始化無法確保初始種群在空間中的均勻分布；②執行全局搜索的領導者只受目標位置引導，雖然收斂較快，但搜索不充分，遍歷性不足。而執行局部開發的追隨者會在領導者已知最優區域內做精細搜索，但跨度不足，在領導者無法獲得全局最優時無法跳出局部區域，開辟新空間，尋優精度受到影響；③傳統SSA中領導者和追隨者規模的固定劃分模式無法實現局部開發和全局勘探、搜索速度與遍歷、精度及擾動的均衡，使得搜索過程無法穩定獲取目標精度和收斂速度。

1 相關工作

針對SSA的不足，文獻[8]引入混沌映射到SSA中，以混沌序列替代位置更新的隨機變量，融合動態特性提升算法搜索能力。文獻[9]則將單純形法引入SSA中，在確定種群多樣性的同時，可以有效提高個體的局部開發能力。文獻[10]在領導者和追隨者更新階段分別引入衰減因子和動態學習機制對SSA進行改進，有效增強了局部開發和全局搜索能力。文獻[11]在食物源和追隨者的位置更新方式中分別引入瘋狂算子和自適應慣性權重，在提升種群多樣性的同時，使SSA具有更優更均衡的局部開發和全局搜索能力，尋優精度和收斂速度均有所增強。文獻[12]調整了領導者和追隨者位置更新中的隨機參數，使領導者個體能夠更好的趨向最優解，提升SSA的尋優精度。文獻[13]將粒子群算法與SSA進行融合，利用粒子尋優的靈活性和多樣性提升算法的全局尋優能力。文獻[14]則將模擬退火的思路引入SSA中，在多目標優化問題上進一步提升的算法的尋優效率。

以上對于樽海鞘群算法的改進雖然可以在某一方面作出優化，但在局部開發和全局勘探的均衡、收斂速度、如何避免陷入局部最優及提升尋優精度等綜合性能方面仍然具有許多不足。尤其，在實際問題優化中，求解的問題往往是高維度單峰、高維度多峰式的復雜優化問題，解決這類優化問題，樽海鞘群算法SSA的尋優精度和求解效率需要進一步全面提升。為了進一步提高SSA的尋優精度和收斂速度，盡可能避免局部收斂與個體早熟，以更加均衡的方式協調樽海鞘個體的局部開發和全局勘探過程，本文主要改進工作體現如下：

(1)設計了基于改進混沌Tent映射機制的種群初始化方法，使個體盡可能均勻分布于搜索空間內；

(2)設計了基于Logistic映射的領導者更新機制，有效增強種群多樣性；

(3)設計了基于動態學習機制的追隨者更新機制，使算法跳出局部最優，擴大搜索范圍，提升全局搜索能力；

(4)設計了領導者/追隨者種群規模的自適應調整機制，有效均衡個體的局部開發和全局勘探能力。

2 樽海鞘群算法SSA

SSA算法中，個體位置矢量X用于在n維空間中搜索，n相當于決策變量數量。樽海鞘種群由N個維度為n的個體構成。因此，樽海鞘種群由以下矩陣構成

(1)

對于SSA，追蹤食物源是所有樽海鞘個體的目標。因此，領導者位置更新方式為

(2)

其中，x1,j表示領導者的j維位置，Fj表示食物源的j維位置，ubj和lbj分別為搜索維度j的上限和下限，c2、c3為[0,1]間的隨機數，決定j維更新位置的移動方向(正向或反向)及移動步長。c1為收斂因子，用于均衡方法迭代過程中樽海鞘個體的局部開發和全局勘探能力。式(2)表明，領導者的位置更新主要由食物源的位置決定。收斂因子c1定義為

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

(3)

其中，t為當前迭代，Tmax為最大迭代。

追隨者位置的更新方式為

(4)

其中，i≥2，xi,j表示追隨者的j維位置，Δt表示時間，v0表示追隨者的初始速率，加速度a=(vfinal-v0)/Δt， 其中，vfinal=(xi-1,j-xi,j)/Δt，xi-1,j表示第i-1個樽海鞘在j維的位置。由于時間是迭代次數之差，故Δt=1。而每次迭代開始時，追隨者初始速度v0=0，故追隨者位置更新可表示為

xi,j=xi,j+xi-1,j/2

(5)

式(5)表明：追隨者i的j維位置更新等于上一迭代中該樽海鞘對應的位置與追隨者i-1的j維位置之和的一半。

3 改進樽海鞘群算法CDSSA

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

初始種群直接影響群體智能算法的收斂速度和尋優精度。傳統的SSA的種群初始化主要以隨機方式生成。而隨機化初始化種群無法確保種群在搜索空間中的均勻分布。混沌序列呈現規律性、隨機性和遍歷性等特點。比較完全隨機化，融合混沌序列的樽海鞘群初始種群具有更好的多樣性。混沌序列的主要思想是通過在區間[0,1]間的映射關系產生混沌序列，并將其轉換至種群的搜索空間中。混沌序列的生成方式有多種，以Tent映射生成序列均勻性更好。但Tent映射生成的混沌序列存在小周期和不確定周期點的不足。綜合考慮以上問題，結合完全隨機化特點，將傳統Tent混沌映射中添加隨機變量r/N，得到Tent映射為

(6)

式中：i表示種群規模，i=1,2,…,N，j表示混沌序號，j=1,2,…,d，r表示[0,1]間的隨機數，μ表示混沌參數，μ∈[0,2]，μ值越大，混沌性能越優，式(6)即為一種混沌系統。對式(6)取相應初始值后，即可得到d個混沌序列di,j。 然后對混沌序列進行逆映射，即可生成種群個體的位置變量xi,j， 表示為

xi,j=lbj+yi,j×(ubj-lbj)

(7)

式中： [lbj,ubj] 表示個體位置xi,j的搜索范圍。

3.2 基于Logistic映射的領導者更新

SSA中，領導者以食物源為目標進行全局搜索。然而，以食物源為牽引的領導者更新可以加速算法收斂，但其全局勘探不夠充分，遍歷性不足，且受初始種群影響較大，易于陷入局部最優。由式(2)可知，領導者更新主要受收斂因子c1和縮放因子c2的影響，c1隨迭代數變化，而c2是均勻分布的隨機量，決定算法全局勘探范圍。然而，完全隨機搜索存在盲目性，會導致全局勘探階段中的領導者位置準確性較低。本文引入混沌Losgitic映射提升領導者搜索的有效性，在每一次迭代中生成偽隨機分布狀態值，擴展SSA搜索過程的隨機性以及遍歷性，實現比完全均勻分布更為合理的搜索過程。

如前文所述，混沌是一種非線性的動態隨機非重復決策系統，表征對初始條件的敏感性，是一種無限非穩定的周期運動。由于混沌的可遍歷性及非重復性，它可以更有效實現比隨機搜索(由隨機值c2決定)更為廣泛的搜索過程。將混沌系統融入SSA的領導者位置更新中可以增強算法的搜索能力，更好預防陷入局部最優解。算法利用Logistic 混沌映射生成混沌序列，形式化為

Ch(t+1)=β×Ch(t)×(1-Ch(t))

(8)

其中，Ch即為生成的[0,1]間的混沌值，迭代初始時的混沌初值Ch0在每次獨立運行過程中隨機生成，但不可取值為0、0.25、0.5、0.75和1，這是由Logistic混沌映射的非周期性決定的。β取值為4，在迭代趨向無窮時，用于控制混沌值的行為。對于可變的β取值的Logistic映射行為如圖1所示。對于較小的β取值，即β<3，混沌值Ch始終收斂在單一量上。當β=3時，混沌值Ch開始在兩個取值間振蕩，這一特征行為改變稱為分歧點。對于β>3時，Ch進一步出現分歧，并導致最終的混沌行為。

圖1 Logistic映射

基于Logistic映射的領導者位置更新方式如下

(9)

3.3 基于動態學習的追隨者更新

SSA中，追隨者完成局部開發過程。由式(5)可知，SSA的追隨者位置更新不受任意隨機參數的影響，完全取決于樽海鞘個體的前次迭代位置和緊鄰的前一個體位置的影響，與領導者位置不發生直接作用。這種首尾相連機制可以使算法進行充分的局部開發過程。若領導者未陷入局部最優，可以尋得全局最優，追隨者順勢可以在最優解區域進一步做精細搜索，可以避免全局最優區域內的小范圍局部最優解，尋優精度更極致。然而，當領導者陷入局部最優時，追隨者在局部最優區域的精細搜索會導致搜索無法跳出局部最優，尋優精度和整體穩定性都會受影響。為了增強領導者精英個體對于追隨者的影響，引入動態學習機制的追隨者更新機制。具體方法是：首先，比較前次迭代中個體位置xi,j和相鄰個體位置xi-1,j的適應度，在適應度較大的位置上(即離最優值距離較遠的位置)引入慣性權重w，降低適應度較差個體位置的影響權重，而增加適應度較優的個體位置的影響權重。基于動態學習自適應慣性權重的追隨者位置更新方式為

(10)

式中：w表示學習權重，隨迭代次數發生改變，定義為

w=(Tmax-t)/Tmax

(11)

3.4 種群自適應劃分機制

SSA中，若樽海鞘種群規模為N，領導者是樽海鞘種群中鏈首位置的個體，數量為1，剩余個體均為追隨者個體，故數量為N-1。極少的領導者導致算法迭代早期進行全局勘探的領導者數量極度不足，追隨者數量過高，全局勘探不充分，局部開發過于精細，易于陷入局部最優；而在迭代晚期則正好相反，局部開發過程缺乏，尋優精度過低。為了解決這一問題，引入種群自適應劃分機制，利用正切三解函數的非線性控制方法，將樽海鞘種群中領導者和追隨者數量做自適應調整，使領導的規模隨迭代次數自適應遞減趨勢，追隨者數量相應隨迭代次數自適應遞增，使SSA在迭代早期側重于多領導者的全局勘探，提升收斂速度，而晚期側重于多追隨者的局部開發，提升尋優精度。具體數量計算如下：

種群中領導者數量為N×P，追隨者數量為 (1-P)×N，P表示比例因子，定義為

(12)

式中：Pini表示比例初值，Pfinal表示比例終值，ξ表示調節系數，ξ>0。可知，比例因子P隨著迭代數呈非線性改變，可以動態變更種群中領導者和追隨者的配比，從而均衡算法的局部開發和全局勘探能力。

3.5 算法步驟

CDSSA算法的執行步驟如下：

步驟1 參數初始化，具體包括：種群規模N、最大迭代Tmax、收斂因子c1、隨機變量r和c3、混沌值Ch、調節系數ξ、比例因子初值Pini、比例因子終值Pfinal、慣性權重w、位置上限值ub和位置下限值lb。

步驟2 利用3.1節改進Tent映射機制實現樽海鞘群中個體位置的初始化操作。

步驟3 根據基準函數計算初始樽海鞘群中所有N個樽海鞘個體的適應度。

步驟4 確定食物源位置。根據初始種群中個體的適應度，對所有樽海鞘個體進行降序排列，將適應度值最小即最優調度解的樽海鞘個體作為當前種群中的食物源位置。

步驟5 確定領導者和追隨者。除食物源之外，將種群中剩余排序的N-1個樽海鞘個體作為領導者和追隨者。具體地，根據種群自適應劃分機制計算比例因子P，根據3.4節中的方法確定領導者數量和追隨者數量。

步驟6 領導者位置更新。根據式(8)計算混沌值Ch，根據式(9)更新領導者位置。

步驟7 追隨者位置更新。根據式(11)計算慣性權重w，根據式(10)更新領導者位置。

步驟8 重新計算個體適應度。重新計算領導者和追隨者更新后的適應度，從中選擇適應度最小的個體，將其適應度與食物源位置適應度比較，若該適應度小于原食物源適應度，則將該個體作為新食物源位置；否則，保留原食物源位置。同時，根據步驟6和步驟7中的方法更新領導者個體和追隨者個體位置。

步驟9 若未達到預設最大迭代次數，則返回步驟5執行；否則，結束迭代，輸出食物源代表的最優解。

圖2是CDSSA算法的完整執行流程。

圖2 CDSSA算法流程

4 數值仿真實驗

4.1 實驗環境及測試函數

搭建數值仿真驗證算法有效性，測試過程側重關注對于SSA中領導者和追隨者的更新機制。將基于混沌Logistic映射的領導者更新的樽海鞘群算法命名為CLSSA，將基于動態學習權重的追隨者更新的樽海鞘群算法命名為DWSSA，CDSSA算法則是本文設計的全面改進算法，3種算法在種群初始化和領導者與追隨者規模更新方面均采用本文在3.1節和3.4節中設計的方法。選取典型的10個標準測試函數進行數值仿真，相關屬性見表1，包括函數表達式、搜索區間、函數維度、理論最優值及搜索的目標精度等要素。測試函數中，單峰值函數f1(x)～f5(x) 可測試尋優精度，多峰值函數f6(x)～f10(x) 可測試全局尋優能力和收斂速度。對于連續多峰值函數，隨著函數維度遞增，其局部極值點會呈現指數級增長。

表1 標準測試函數

表2給出改進樽海鞘群算法的相關參數配置。仿真實驗執行環境為Intel(R) Core i7 CPU 3.0 G，內存4 GB，64位微軟操作系統WIN10，數值仿真軟件為Matlab 2014a。

表2 SSA算法的參數

4.2 實驗結果分析

實驗一觀察CLSSA算法、DWSSA算法、CDSSA算法以及基本SSA算法的性能，通過設置固定的算法迭代次數，觀測算法的收斂速度和尋優精度變化。如圖3所示是4種算法在10個基準函數測試下的收斂曲線，此時測試函數維度為30維。可以看出，CLSSA算法、DWSSA算法和CDSSA算法都可以在若干次的迭代過程之后逐步接近于目標函數的理論最優解，且3種算法的無論尋優精度還是收斂速度都要優于SSA。同時可以觀測到，迭代約220次后，CLSSA算法曲線的下降趨勢變得逐步明顯起來，說明CLSSA收斂速度明顯加快。在多峰值函數測試結果中，可以看到該算法在避免局部最優以及迭代晚期的收斂速度方面要明顯優于SSA。DWSSA則明顯不同，其早期迭代時的下降速度更快，迭代后期逐步變得穩定，在部分測試函數上其尋優精度和收斂速度也是明顯優于SSA的。綜合10個基準函數的測試結果來看，在領導者、追隨者位置更新方式以及種群自適應劃分優化機制下的CDSSA算法基本具有最佳的尋優精度和最快的收斂速度。

圖3 算法的收斂情況

表3是算法在10個基準函數下測試得到的收斂精度結果，包括適應度的最大值、最小值、均值和標準方差。可以看出，CLSSA和DWSSA兩種算法的收斂精度較傳統SSA的基礎均得到了提高，個體基準函數的測試上CDSSA與尋優精度與CLSSA相當，但多數基準函數(單峰值函數和多峰值函數)的測試中CDSSA擁有最佳的精度表現。對于多峰值基準函數而言，CDSSA的尋優精度遠遠高于傳統的樽海鞘群算法SSA，這說明本文所采取的四方面的改進機制是有效可行的。

表3 算法的尋優結果

實驗二觀察本文涉及的CLSSA算法、DWSSA算法、CDSSA算法以及基本SSA算法在固定目標收斂精度的同時，算法達到該尋優精度時所需要進行算法迭代次數和尋優成功率。尋優成功率[11]表示計算成功次數與實驗求解次數之比，求解是否成功的判定標準為

(13)

式中：FA為實際求解最優解，FT為基準函數理論最優解。

表4是測試結果，函數維度為30，最大迭代數為500，取30次獨立運行的實驗結果均值進行比較。若達到最大迭代次算法運行結果仍然沒有達到所需的尋優精度，則將迭代次數定義為最大迭代次數。從表中結果可以看到，未作任何優化的傳統SSA在前500次迭代中基本無法達到目標尋優精度，其成功率基本為0，說明該算法在處理復雜優化問題時仍然存在尋優精度低的問題，性能有待提升。此外，在處理多峰值基準函數時，DWSSA算法的尋優成功率平均高于65%以上，說明該算法處理多峰函數優化時性能表現較好。CLSSA的尋優成功率基本穩定在100%，說明領導者位置更新主導了樽海鞘群算法中種群的尋優方向，對于該部分的優化可以加速傳統SSA的收斂速度。而本文的綜合算法CDSSA的尋優成功率不僅穩定在100%，且其得到目標尋優精度時所需要的迭代次數也是遠小于另外兩種算法的，說明處理復雜優化問題時，該算法能夠有效提升尋優精度和收斂速度。

表4 尋優成功率及收斂迭代數

實驗三觀察本文算法與同類型的SSA改進算法、較新的灰狼優化算法的性能對比情況。SSA的改進算法選取文獻[10]的RDSSA、文獻[11]的CASSA和文獻[12]的ESSA進行性能對比研究，灰狼優化算法選取文獻[15]中的基于精英對立學習與混沌擾動融合的混合灰狼優化算法HGWO、文獻[16]中的混合差分進化策略的灰狼優化算法DEGWO進行性能對比。測試過程中，種群規模、迭代最大次數和函數維度設置相同。表5是6種算法在10個基準函數中計算得到的適應度的平均值和標準方差，前者可以衡量算法的尋優精度，后者可以衡量算法尋優穩定性。從結果可以看出，在絕大多數的單峰值函數和多峰值函數測試下，CDSSA算法在尋優精度和穩定性上均要優于同類型的改進SSA算法和灰狼優化算法。基于灰狼優化算法的改進算法與樽海鞘群算法的改進表現上各有不同，總體來說SSA的平均性能要好于灰狼算法，這取決于改進機制。較為全面的改進算法CDSSA的性能明顯優于兩種灰狼優化算法的改進，而ESSA改進較為局部性，其性能不如融合了差分進化的灰狼優化算法。

表5 同類算法的對比結果

進一步引入平均絕對誤差MAE指標[17]輔證對比算法的性能，該指標是在所有10個基準函數的基礎上計算得到。MAE指標的計算公式為

(14)

其中，mi為測試算法在基準函數測試中產生的最優解的均值，oi為基準函數的理論最優解，Nf為測試基準函數的數量，本實驗取值為10。表6是6種算法的MAE指標表現，明顯地，本文的CDSSA算法表現是最佳的，驗證了算法的有效性。

表6 MAE指標表現

5 結束語

提出一種基于混沌映射與動態學習機制的自適應樽海鞘群算法CDSSA。算法采用了改進混沌Tent映射進行種群初始化，利用Logistic映射的領導者更新機制，提升種群多樣性；同時，設計了動態學習追隨者更新機制，使算法跳出局部最優，提升全局搜索能力，并利用領導者/追隨者種群規模的自適應調整機制，有效均衡局部開發和全局勘探能力。大規模數值仿真實驗的結果驗證，改進樽海鞘群算法在尋優精度和收斂速度上均有較大提升，符合算法設計的性能改進初衷。