融合學習機制的多混沌麻雀搜索算法

李光陽，潘家文，錢謙+，殷繼彬，伏云發，馮勇

1.昆明理工大學 信息工程與自動化學院，昆明650500

2.昆明理工大學 云南省計算機技術應用重點實驗室，昆明650500

3.中國農業大學 信息與電氣工程學院，北京100083

麻雀搜索算法（sparrow search algorithm，SSA）[1]是Xue 等人在2020 年提出的一種新型群智能算法，該算法受麻雀捕食行為的啟發，將群體分為發現者、跟隨者和警戒者，并根據麻雀遭遇天敵的應對策略來構建算法的數學模型。目前，SSA已廣泛應用于路徑規劃[2]、任務調度[3]、網絡覆蓋[4]等領域。

SSA 因收斂速度快、擴展性與魯棒性強等特點，受到不少學者的關注與研究[5]。但SSA 仍存在一些缺陷，例如收斂精度依賴于初始解的質量，搜索過程中種群多樣性衰減過快導致其易陷入局部極值，發現者易趨近于原點影響算法的收斂能力等。目前已有許多解決這類問題的方法，如混合擾動機制[6]、將麻雀搜索算法與其他算法結合[7]等，這些方法雖然在一定程度上提升了SSA 的性能，但仍存在進一步提高的可能性。現有的面向SSA性能改進的方法大致可以分為以下幾類：

（1）種群初始化：尹德鑫等人[8]在SSA 中引入反向學習機制（opposition-based learning，OBL）增加了初始種群的多樣性，但OBL 在計算反向點時僅僅考慮了搜索空間的邊界信息，并沒有充分考慮種群作為一個尋優整體所攜帶的有利信息，導致其優化效率仍然較低；張偉康等人[9]利用Circle 混沌映射產生初始種群，在一定程度上增強了算法的全局探索能力，但Circle混沌序列分布不夠均勻，且在[0.2,0.6]之間的取值較為密集，這種現象限制了初始種群的多樣性。為克服上述缺陷，本文借鑒重心反向學習[10]的思想提出了一種重心反向學習（centroid oppositionbased learning，COBL）策略，該策略根據種群的重心來計算反向解，有效提升了初始解的多樣性。

（2）個體位置更新：付華等人[11]借鑒雞群優化算法（chicken swarm optimization algorithm，CSOA）改良了SSA 中跟隨者的位置更新方式，提高了解的精度，但該方法仍存在著缺陷，CSOA 中的個體因移動幅度過大而頻繁越界，影響了算法的收斂速度；溫澤宇等人[12]在發現者的位置更新公式中引入了多項式變異因子，增強了算法逃逸局部最優的能力，但仍未從根本上解決發現者趨于原點的問題。因此，本文借鑒黃金正弦算法（golden sine algorithm，Gold-SA）[13]提出一種領導策略，該策略在發現者位置更新公式中加入最優個體來引導其余個體的搜索方向，增強了算法的全局搜索能力。此外，為平衡算法的勘探能力與開發能力，本文在領導策略中加入縮放因子，進一步提升了算法的性能。

（3）群體變異擾動：呂鑫等人[14]利用tent 混沌映射來擾動算法的種群，增強了算法擺脫局部最優的能力，但該方法受限于其單一的擾動模式使算法的性能提升有限；李愛蓮等人[15]使用柯西變異對跟隨者進行擾動，一定程度上強化了算法的全局尋優能力，但柯西變異本質上屬于鄰域擾動，當最優解不在當前個體附近時，其擾動效果較為有限。基于上述不足，本文提出一種基于學習機制的多混沌映射策略，該策略以輪盤賭的形式為算法動態地選擇合適的混沌映射，大大提高了個體跳出局部最優的成功率。此外，由于混沌擾動屬于全局擾動，其在算法局部區域擾動的能力較差，為了彌補該缺陷，在混沌映射策略的基礎上引入了高斯變異策略。

綜上所述，本文提出一種融合學習機制的多混沌麻雀搜索算法（multi-chaotic sparrow search algorithm based on learning mechanism，MMCSSA），算法中的四項改進策略協同作用、相互促進提升了算法的性能。為驗證MMCSSA的有效性，采用12個基準測試函數進行測試，同時進行了Friedman檢驗與Nemenyi統計實驗。實驗結果驗證了MMCSSA 的優越性和可行性。

1 麻雀搜索算法

在SSA中，存在三種主要的群體：發現者、跟隨者和警戒者。其中，適應度較高的個體被稱為發現者，其作用是帶領跟隨者尋找食物，相較于其他個體，發現者有更廣泛的搜索范圍，位置更新公式如下：式中，i表示第i只麻雀，i=1,2,…,n；j表示優化問題的第j個維度，j=1,2,…,D;t表示算法第t次迭代；iter表示最大迭代次數;α∈(0,1]，是一個隨機數；R2∈[0,1]代表預警值；ST∈[0.5,1.0]表示安全值；Q是服從正態分布的隨機數；L表示1×D的矩陣；當R2＜ST時，說明種群處于安全環境，此時發現者應擴大搜索范圍；當R2≥ST時，表明種群的周圍出現了天敵，為了保證安全，整個種群飛行到安全區域進行覓食。

在覓食過程中，跟隨者會時刻監視發現者，一旦看到發現者尋找到了食物，跟隨者會過去爭搶食物，若爭搶失敗，則飛行到其他位置繼續覓食。跟隨者的位置更新公式如下：

式中，Xworst表示當前種群中的最差位置；Xp是目前為止發現者探明的最優位置；A表示為一個1×D的矩陣，其中每個元素隨機為1 或-1，A+=AT(AAT)-1；當i>時，表示這部分跟隨者沒有搶到食物，需要移動到其他位置進行覓食；當i≤時，說明跟隨者與發現者爭奪食物。

種群覓食時，部分麻雀被選作警戒者負責偵查預警，當天敵靠近時，它們將會放棄當前的食物并向其他麻雀靠近以躲避危險。隨機選出的警戒者通常在種群中占10%或20%左右，警戒者的位置更新公式如下：

式中，Xbest表示當前種群中的最優位置；β是標準正態分布隨機數，用來控制移動步長；k是[-1,1]內的一個隨機數，用于控制麻雀的移動方向和距離；fi表示第i個麻雀的適應度值；fg和fw分別表示當前全局最優位置和全局最差位置的適應度值；為了避免分母為0，引入最小的常數ε；當fi>fg時，麻雀易受天敵攻擊，當fi=fg時，麻雀意識到了危險并向其他麻雀靠近。

2 MMCSSA的基本思想

2.1 重心反向學習策略

有效控制SSA初始種群的質量是提高算法性能的一個重要途徑。初始種群的質量主要取決于其搜索范圍和起始位置兩個因素，若初始種群的搜索范圍過小，會影響算法的勘探能力；若起始位置靠近全局最優解，種群能在更優質的解空間內挖掘有效信息。標準SSA 采用隨機初始化方法產生種群，該方法難以滿足上述兩個要求。為解決這個問題，算法考慮引入反向學習策略來產生初始種群，使用反向學習策略能夠在更廣闊的范圍內找到優質解，進而有效提升初始種群的質量。但該方法仍存在一些缺陷，反向學習的原理是利用搜索空間的邊界信息計算個體的反向解，但在面對含有“對稱山峰”的優化問題時[16]會“失效”（當前解的適應度與其反向解的適應度相同）。為克服這個缺陷，本文提出一種重心反向學習策略來產生初始種群，其基本思想是根據種群的重心來計算反向解。重心反向學習策略初始化種群的方式如下：

其中，離散均勻體Cj表示為種群重心，是Xi的重心反向點。

2.2 動態調整的黃金正弦領導策略

影響SSA性能的另一缺陷是發現者搜索范圍較小且易趨于原點，這導致了算法易陷入局部最優。當R2＜ST的條件滿足時，SSA根據式（1）更新發現者的位置，式（1）中的決定了發現者的勘探能力，假設其計算所得值為p，則p的取值變化如圖1所示。根據i取值的不同，p的值常落于[0.9,1.0]內，這會導致發現者的移動范圍過小，影響算法的全局探索能力；其次，p的取值總是小于1.0，隨迭代次數的增加，發現者的所有元素都不斷地向0 靠近，由于發現者起著引導種群的作用，上述現象將導致種群中所有個體都趨于原點，這使得SSA 求解最優解位置非原點的問題時，算法的搜索速度和收斂精度都受到影響。當條件R2≥ST被滿足時，算法會在個體的每個維度都賦予相同的正態隨機數以實現位置擾動，但該方法在定義域范圍較大的目標問題上所達到的效果有限。為解決上述問題，本文采用黃金正弦領導策略更新發現者的位置：

圖1 參數p的數值分布Fig.1 Value distribution of parameter p

式中，Xi表示種群的第i個個體；t是迭代次數；P為食物（全局最優個體）；r1和r2都是隨機數，r1的隨機范圍是[0,2π]，r1決定了下一次迭代中當前個體的移動距離，r2的隨機范圍是[0,π]，r2決定了下一次迭代中當前個體的位置更新方向；x1和x2是引入黃金分割系數得到的參數，這些參數共同起到縮放算法搜索空間的作用，有利于加快算法的收斂速度，其中

圖2 和圖3 分別表示某次實驗中原始的發現者與改進后的發現者的移動變化。圖中黑色圓點和紅色圓點分別表示個體移動前與移動后的位置，藍色五角星表示種群當前最優解的位置。由圖2可知，原始的發現者更新前后的位置有大量重合點，未重合情況下的移動距離也偏小，且所有點都朝空間中的原點移動，搜索方向較為單一，影響了算法的勘探能力；由圖3 可知，本文改進后的發現者在移動時會朝著多個方向移動，且移動距離較大，算法的全局搜索能力得到增強，同時，種群中其他個體也會朝最優解所在的方向移動，進一步增強了算法的收斂能力。由分析可知，本文引入的黃金正弦領導策略改善了發現者的移動路徑，避免了種群易趨于原點的缺陷。

圖2 原始發現者移動Fig.2 Original finder movement

圖3 改進后的發現者移動Fig.3 Improved finder movement

為了進一步調節算法在勘探能力和開發能力之間的平衡，本文在發現者的位置更新公式中引入縮放因子w。

式中，i為迭代次數，M代表最大迭代次數。縮放因子w與全局最優解P共同決定了最優解引導種群的能力。圖4 表示動態因子w隨迭代次數變化的函數曲線（實線表示），相比線性變換（虛線表示），w在迭代初期上升緩慢，全局最優解的引導力較小，有效避免了前期因聚集而導致的種群多樣性減少，保證了算法前期的搜索能力；隨著算法進入迭代后期，w值快速增加，使最優解對種群的引導力顯著增強，種群更迅速聚集在最優解周圍進行開發，增強了算法的收斂能力。由上述分析可知，w值的變化決定了全局最優解對種群的引導能力，通過分階段地調節w值，避免了算法前期搜索能力較弱、后期收斂速度較慢的情況，更好地平衡了算法在不同時期勘探能力和開發能力之間的平衡。

圖4 縮放因子w 隨迭代變化曲線Fig.4 Scaling factor w varies with iteration

2.3 學習選擇機制的多混沌映射策略

SSA 在搜索后期因種群多樣性急劇減少易陷入局部最優，使得SSA收斂精度降低。因此，需要在計算過程中對個體進行持續擾動來增加算法迭代后期的多樣性。利用混沌映射進行擾動是改善上述缺陷的一個有效方法，但已有研究大多使用單一的混沌映射對個體進行擾動，擾動效果一般。為提升擾動效率，本文在前人研究的基礎上[17-18]提出了一種基于學習機制的多混沌映射策略。

2.3.1 多混沌映射模型

通過對常見的混沌映射進行比較，本文選出概率分布均勻的Kent映射、概率分布非均勻的Logistic映射、Sine 映射、ICMIC 映射、Circle 映射、Chebyshev映射、Gauss映射7個具有代表性的混沌映射，用于該多混沌映射模型。每種混沌映射都有不同的分布特性，例如Circle 映射的概率分布呈現山峰形態，即中間有較高的概率密度值，而兩邊的密度值較低；ICMIC 映射的概率分布是一個山谷形態，中間的概率密度值較低，兩邊較高。每次迭代后期選擇混沌映射對種群中所有個體進行擾動，其計算公式和用到的混沌映射如下：

式中，U和L分別是搜索空間上邊界和下邊界；r=r×0.988 為混沌搜索半徑變化公式，其搜索半徑隨迭代次數的增加而減小，使得算法在迭代后期有更快的收斂速度；zt表示在第t代時所使用的混沌變量。個體經混沌擾動再使用貪心策略保留較優個體，其數學表達式為：

2.3.2 學習選擇機制

在某些研究中[19-20]，機器學習方法被用來分析歷史數據（如種群進化信息和問題特征信息），以便指導算法。借鑒該思想，本文使用學習周期的歷史信息來決定混沌轉盤的概率，這種概率是種群當前搜索特征的本質表達。如圖5所示，混沌映射所對應的概率越大，表明該混沌映射對種群的影響越大，在下一周期有更高的概率擾動成功（尋得更優解）。用表示第t次迭代時第j個混沌映射擾動成功的次數，計算公式如下：

圖5 初始概率輪盤Fig.5 Initial probability roulette

每過一個學習周期，成功次數需要重置為0。第一個學習周期中默認每個混沌映射以均勻概率被選擇，之后的每個學習周期混沌映射的選擇概率由以下公式計算：

式中，c指第c個學習周期，n表示種群中的個體數量，tj是第j個混沌映射在一個學習周期內被選中的次數。MMCSSA在每個學習周期的間隔都會通過式（12）更新概率輪盤并為下一學習周期選擇混沌映射。

2.4 引入高斯變異策略

多混沌映射策略的作用域是整個搜索空間，擾動失敗意味著搜索空間其他區域有更優解的可能性較小；由高斯分布的概率分布可知，高斯變異策略是在個體鄰域內進行深度開發，有利于提高解的收斂精度。為了進一步提升算法的性能，對個體擾動時，若混沌擾動失敗就使用高斯變異進行二次擾動。高斯分布的概率密度函數和高斯變異策略的數學模型分別如下所示：

2.5 MMCSSA實現流程

MMCSSA的具體實現流程如圖6所示。

圖6 改進算法流程圖Fig.6 Flow chart of improved algorithm

步驟1初始化種群X、各項參數，設置混沌概率輪盤。

步驟2初始種群根據式（4）、式（5）進行重心反向操作得到新種群Xrev，分別計算種群X和Xrev的適應度，選取適應度較好的個體組成精英種群Xeli。

步驟3按比例劃分發現者、跟隨者、警戒者，并分別根據式（7）、式（2）、式（3）更新個體位置。

步驟4根據概率輪盤選擇混沌映射并對當前種群進行擾動，利用式（10）判斷是否擾動成功；若擾動成功，記錄成功次數；否則使用式（14）對擾動失敗的個體進行高斯變異。

步驟5判斷迭代次數是否為50 的倍數；若判定為真，根據式（12）計算擾動成功率并更新概率輪盤，否則進入下一步。

步驟6判斷算法是否滿足終止條件，若滿足，輸出最優解；否則返回步驟3。

3 實驗仿真與結果分析

3.1 測試函數及對比算法

為了驗證本文所提MMCSSA 的有效性和優越性，采用國際上通用的12個經典函數（f1～f12）進行仿真實驗，詳細描述如表1 所示。表中的函數均來自IEEE CEC（IEEE Congress on Evolutionary Computation）競賽集[21-22]，f1～f4表示只有一個全局最優解的單峰函數，f5～f12是指具有多個局部最優解的多峰函數。本文選取SSA、GWO（grey wolf optimizer）、文獻[11]中的ISSA（improved sparrow search algorithm with multistrategy integration and its application）以及文獻[14]中的CSSA（chaos sparrow search optimization algorithm）作為對比算法進行實驗，其中CSSA 用于對比驗證MMCSSA逃逸局部極值的能力，ISSA用于對比驗證MMCSSA的全局搜索的能力。

表1 基準測試函數Table 1 Benchmark functions

3.2 仿真實驗參數設置

為保證實驗公平，所有算法均采用相同的參數，種群數目N設置為30，最大迭代次數M設為600，發現者在種群中的數目比例為0.2，警戒者為0.1。在MMCSSA中，經多次實驗，多混沌映射策略學習周期按經驗設置為50代時有最佳的擾動效果。所有仿真實驗均在Windows 10 操作系統，MATLAB R2019B仿真平臺下進行，每種算法獨立運行30次。

3.3 收斂精度與收斂速度分析

表2 展現了不同算法在12 個測試函數中不同維度下的實驗結果，旨在從單峰/多峰、低維/高維多個角度來分析所提算法的收斂精度。其中，每個函數的最佳值加粗顯示。單峰函數f1、f2、f3、f4一般用于測試算法的開發能力，由表2可以看出，MMCSSA在單峰函數上的表現優于CSSA，這是因為單混沌的擾動模式不能幫助CSSA 在迭代后期跳出局部最優解，而多混沌映射及時選取了合適的擾動模式加強了算法逃逸局部極值的能力；MMCSSA在f3、f4達到了理論最優解且領先其余算法數十個量級，這是因為MMCSSA 的4 個改進策略不是單純地疊加，而是有機互補的，共同提升了算法的收斂精度。另外，MMCSSA在f1～f4的標準差都為0，這說明MMCSSA求解單峰函數時穩定性較好，其背后的原因是將固定趨于原點的移動方式轉變為受全局最優位置與個體自身位置共同牽引的移動方式，提升了算法的搜索能力，進而保證了算法的優化穩定性。多峰函數f5～f12常用于測試算法的勘探能力，MMCSSA在f6、f10、f11、f12的收斂精度均優于其他算法，在f5、f7、f8、f9上持平于其他改進的SSA，說明MMCSSA 在復雜函數上的收斂精度優于其他算法。綜上所述，MMCSSA 與其他改進的SSA 相比，在單峰和多峰測試函數上表現出了更加高的收斂精度。

表2 函數測試結果Table 2 Function test results

為了驗證MMCSSA 收斂速度的優越性，圖7 描繪了測試函數的迭代收斂曲線。可以看出，MMCSSA在收斂速度上同樣優于其他算法，具體原因為：（1）圖7（d）、（e）、（h）、（i）、（j）中MMCSSA 的初始適應度值要優于其他算法，說明算法初始化時重心反向學習策略產生的精英種群賦予了算法足夠的解空間有效信息。（2）黃金正弦領導策略和多混沌映射策略中分別加入了縮放因子和混沌搜索半徑。在迭代后期，縮放因子使種群快速向全局最優解靠攏，搜索半徑使混沌擾動效果逐漸減小，兩者共同作用進一步提升了算法的收斂速度。（3）多混沌映射策略與高斯變異策略使算法的擾動成功率大大提升，顯著地增強了算法的搜索能力，進而促進了算法的快速收斂。

圖7 算法收斂曲線對比圖Fig.7 Algorithm convergence curve comparison diagram

3.4 Friedman檢驗與Nemenyi后續檢驗

為了更準確地評估每個算法的性能，本文采用Friedman 檢驗與Nemenyi 后續檢驗[23]作為模型的性能評價工具來驗證MMCSSA算法的優越性。

Friedman檢驗屬于統計假設檢驗，其基本步驟是：

首先建立一個假設檢驗問題：

H0:k個算法之間無顯著差異

H1:k個算法之間存在顯著差異

然后在同一個測試函數上按照測試結果對算法性能進行排序，根據性能由好到差對算法依次賦序值。若算法性能相同則將序值平分。結果見表3。

表3 序值表Fig.3 Sequence value table

平均序值ri一般符合自由度為k-1的x2分布，為了獲得更準確的檢驗結果，現使用式（15）進行假設檢驗，TF是服從自由度為k-1 和(k-1)(N-1)的F分布（N為數據集即測試函數數量）。將TF的值與F檢驗臨界值表中對應的數值進行對比，TF的值小于對應的數值，則表明“k個算法之間無顯著差異”這一假設被拒絕，即“k個算法之間存在顯著差異”。根據式（15）和式（16）計算出TF并查表比較，得出“5 個算法之間存在顯著差異”這一結論。

為了進一步評價算法間的性能差異，接著使用Nemenyi 后續檢驗。根據式（17）計算臨界值域CD，其中α表示顯著性水平，一般取值為0.05 和0.10，本文中取0.05，即置信度是95%，qα為Nemenyi后續檢驗中常用的參數。

通過計算，臨界值域CD為1.76。若兩個算法的平均序值的差值大于CD，則以相應的置信度拒絕“兩個算法性能相同”這一假設。Friedman 檢驗圖如圖8所示。

圖8 Friedman檢驗圖Fig.8 Friedman test diagram

圖8中橫軸表示序值，每個黑點代表其對應算法的平均序值，線段的長度為臨界值域CD。縱軸上一個刻度點代表一個算法。若線段末端垂下的虛線與其他線段沒有交點，則表示該線段對應的算法的性能顯著優于其余線段對應的算法性能。由圖8可知，MMCSSA 的性能顯著優于SSA、GWO，同時也優于CSSA和ISSA。

4 MMCSSA理論分析

4.1 時間復雜度分析

設種群規模為N，目標問題的維度為D，最大迭代次數為T。一般情況下，D>lbN。

SSA的時間復雜度主要由種群初始化、個體位置更新兩部分構成。初始化階段，計算N個個體適應度值的時間復雜度為O(N×D)，則初始化階段的時間復雜度為O(N×D)；迭代中，種群個體位置更新的時間復雜度為O(T(N×D))。綜上，SSA的總時間復雜度為O(N×D)+O(T(N×D))，略去低階項，SSA 的時間復雜度為O(T(N×D))。

MMCSSA 的時間復雜度主要由種群初始化、個體位置更新和群體擾動三部分構成。初始化階段，計算N個個體適應度值的時間復雜度為O(N×D)，按2.1 節對初始種群進行重心反向學習策略的時間復雜度為O(N)，選出精英種群的時間復雜度為O(NlbN)，則初始化階段時間復雜度為O(N×D)+O(N)+O(NlbN)，略去低階項，即O(N×D)；迭代中，種群個體位置更新的時間復雜度為O(T(N×D))，按2.3節進行多混沌擾動的時間復雜度為O(T(N×D))，多混沌擾動結果判別的時間復雜度為O(1)，按2.4 節進行高斯變異時間復雜度為O(T(N×D))，則迭代中的時間復雜度為O(T(N×D))。綜上，MMCSSA的總時間復雜度為O(N×D)+O(T(N×D))，略去低階項，MMCSSA的時間復雜度為O(T(N×D))。

可以看出MMCSSA 與SSA 的時間復雜度相同，且MMCSSA有更好的優化性能。

4.2 MMCSSA全局收斂性分析

MMCSSA 為隨機優化算法，根據算法全局收斂性定理[24]，隨機優化算法具有全局收斂性需要滿足以下兩個條件。

條件1f(D(z，ξ))≤f(z),若ξ∈S,則f(D(z，ξ))≤f(z)。其中，f為最小化問題的目標函數；D表示隨機算法；z為能夠使目標函數的值最小化的解；ξ為算法D迭代搜索中的解；S代表可行解空間。若滿足條件1，表明目標函數的值有可接受的下確界。

條件2對于S中的任意Borel 子集A，若其概率測度V[A]>0，則有：

其中，μk(A)=P(xk∈A|x0,x1,…,xk-1)為算法D第k次迭代的解在集合A中的概率測度。若滿足條件2，表明算法經過無窮次迭代后，不可能錯過解空間S的任意Borel 子集A，即滿足條件的算法無窮次迭代后搜索不到近似全局最優點的概率為0。

引理1（隨機優化算法全局收斂定理）若函數f可測，搜索空間S是n維實數集Rn，實數集上的可測子集，隨機優化算法D滿足條件1和條件2，則有：

其中，P[XK∈R]是算法第k代的結果落在R里的概率，R是全局最優點集合，即算法無窮次迭代后必定搜索到全局最優解。

定理1MMCSSA滿足條件1

證明根據MMCSSA中的描述將D定義為：

其中，Gt為第t代時全局最優解的位置，函數h對應動態調整的黃金正弦的位置移動操作，h(Xi,t)表示麻雀個體i按式（7）位置更新后的位置；函數y對應混沌擾動和高斯變異操作，y(Xi,t)表示麻雀i進行混沌擾動和高斯變異后的位置。以上操作都使用貪心策略進行位置更新，按照上述定義，可知Gt的適應度值單調不增，即條件1成立。

定理2MMCSSA滿足條件2

證明對于MMCSSA 中的自適應黃金正弦領導策略，有：

對于MMCSSA 中麻雀個體經過混沌擾動和高斯變異后，對較差個體進行替代的更新機制，支撐集的并集為δ，隨著迭代次數的增加，V[δ]也在逐漸變大。因此，對于MMCSSA，存在正整數t1，當t>t1時：

條件2成立。

由引理可知，MMCSSA具有全局收斂性。

4.3 改進策略的有效性分析

4.3.1 初始化策略的持續影響分析

為分析重心反向學習策略在算法迭代周期的性能影響，分別使用隨機初始種群與本文所提初始化方法產生的精英種群來優化Bent Cigar 函數。該函數在搜索空間內的全局最小值的空間坐標為x*=（0,0,0）。圖9～圖11分別給出了兩個種群在迭代初期、中期及后期的空間位置分布。圖中黑色圓點表示隨機初始種群中的個體（隨機個體），紅色圓點為隨機個體經過重心反向學習策略初始化產生的個體（精英個體），藍色五角星表示種群當前最優解的位置。

圖9 迭代初期Fig.9 In early iterations

圖10 迭代中期Fig.10 In mid iterations

圖11 迭代后期Fig.11 In late iterations

由圖9 可知，迭代初期，精英個體普遍接近全局最優解，說明初始種群經重心反向學習策略與貪心策略雙重處理后產生了更加優越的精英個體。由圖10 可以看出，在迭代中期，相比隨機個體，精英個體可以更快地接近全局最優解，說明精英個體所代表的種群在迭代周期變遷時仍保持了較好的收斂能力。圖11表明了種群在迭代后期仍產生了新的最優解，且全局最優位置是由精英個體發現的。一方面，精英個體的位置向量在一定程度上代表優秀的探索方向，可以充分利用種群已有的有效信息；另一方面，精英個體在搜索時會圍繞當前最優解不斷地挖掘其周邊區域的有效信息，兩者相互配合，共同推動了算法收斂精度的提高。綜上所述，重心反向學習策略持續引導了MMCSSA 種群的搜索方向，有效提升了算法的收斂精度。

4.3.2 學習機制的多混沌映射理論及有效性分析

混沌序列的概率分布特性和搜索速度是影響混沌擾動的兩個主要因素，分別用概率密度函數（probability density function，PDF）和Lyapunov 指數表示[25]。表4展示了每種混沌映射的函數表達式、使用到的參數以及Lyapunov 指數。Lyapunov 指數的值都大于0，表示在區間范圍內所有映射均處于混沌狀態。

表4 Lyapunov指數Table 4 Lyapunov exponents

圖12 展現了不同混沌映射的概率分布情況，圖中橫軸z表示混混變量的值，縱坐標P(z)是z對應的概率密度的值。由圖12（b）和圖12（f）可以看出，由于Logistic 映射與Chebyshev 映射可以通過線性變換互相轉換，兩種混沌映射的概率分布情況十分相似，僅在變量z的區間有所不同。此外，隨著參數的不同，混沌映射會同步變化，其對應的概率密度函數也在不斷地變化。

圖12 固定參數概率密度函數圖Fig.12 Fixed parameter probability density function diagram

為分析概率分布對混沌擾動效果的影響，比較多混沌擾動與單一混沌擾動的性能，選用標準SSA、單一混沌映射的SSA（X-sparrow search algorithm，X-SSA）[25]、隨機選擇機制的多混沌SSA（multiplechaotic sparrow search algorithm with random selection mechanism，RCSSA）[26]以及學習選擇機制的多混沌SSA（MMCSSA）四種不同的SSA變體對測試函數進行尋優實驗。其中，X-SSA 用來分析概率分布與擾動性能的內在聯系；X-SSA 與RCSSA 的比較用于驗證多混沌映射策略的有效性；RCSSA與MMCSSA的比較用來驗證學習機制的優越性。為了保證實驗的公平性，實驗結果取100 次實驗的平均值，MMCSSA只使用學習機制的多混沌映射策略。測試函數選取圖13中的5個基準函數[27]。

圖13 5個測試函數Fig.13 5 test functions

函數f1Rosenbrock 有一個全局最小值點x*=(1,1,…,1)，其最優目標函數值為f*=0 ；函數f2Schwefel 2.26 有多個局部極小值點和一個全局最小值點x*=(420.968,420.968,…,420.968)，f*=-418.98d,d為問題維度；函數f3Rastrigin’s 有很多局部極小點和一個全局最小值點x*=(0,0,…,0)，f*=0；函數f4Griewank’s 有多個局部極小值點和一個全局最小值點x*=(0,0,…,0)，f*=0；函數f5有多個局部極小值點和一個全局最小值點x*=(-2.905,-2.905,…,-2.905)，f*=-78.332。

為更清晰地描述不同分布特性對算法產生的擾動效果的影響，除了2.3.1 小節中提到的7 個混沌映射，表5、表6 中的實驗還加入與Kent 映射有相同概率分布的Bernoulli shift映射作為對照組。

表5、表6 展示了采用不同混沌策略的SSA 變體對基準函數進行測試的結果。表中LOC 代表Logistic；KET 代表Kent；BEI 代表Bernoulli；SIE 代表Sine；ICC 代表ICMIC；CIE代表Circle；CHY 代表Chebyshev；GAS代表Gauss。由表中數據分析可知：

表5 基準函數測試結果Table 5 Benchmark function test results

表6 算法性能排名Table 6 Algorithm performance ranking

（1）對于單一混沌擾動，KET-SSA、CIE-SSA、BEI-SSA 有較高的性能，LOC-SSA、GAS-SSA、SIESSA為一般性能，CHY-SSA 和ICC-SSA為較低性能。因為BEI-SSA和KET-SSA用到的混沌映射有相同的概率分布，所以兩種算法的性能非常接近，它們之間的細微差異來源于算法的內在隨機性。此外，由表5、表6 可以發現每個混沌映射所適用的函數是不同的，Logistic 映射在函數f2、f4上表現良好，對于函數f5的表現較差，Gauss 映射在函數f3、f5上表現良好，對于函數f1、f2的表現較差。

（2）混沌映射的概率密度函數的分布情況與混沌擾動的效果有著直接關系。因為上述5 個測試函數的最優解位置是確定的，所以其對應的混沌變量Zi的值也是確定的。對于f1，全局最優位置對應的混沌變量的值位于（0.4,0.6）區間，而Circle 映射的概率密度函數的峰值也出現在（0.4,0.6）區間內，這意味著經過Circle 映射擾動的個體有較大的概率移動到最優解附近，圖14 形象地展示了高成功率擾動的方式；而ICMIC 映射的概率分布在（0.4,0.6）區間內的值較小，因此其擾動后的個體出現在最優點附近的概率較低，導致混沌擾動的效果較差。

圖14 高成功率擾動Fig.14 High success rate disturbance

混沌映射產生序列的值是固定的，如果其值未出現在全局最優解對應的概率分布的區間內，那么算法經混沌擾動后找到全局最優解的概率會大大降低。為克服上述缺陷，需要動態地調整“軌道”。本文使用基于學習機制的概率輪盤動態地選擇混沌映射為算法切換不同的“軌道”。下面通過實驗來分析學習機制優勢產生的原因。

實驗分別使用RCSSA 和MMCSSA 求解函數f1。由于Bernoulli shift 映射和Kent映射具有相同的概率密度函數，其擾動模式重復，因此表7 和第3 章中的仿真實驗都只使用Kent映射。

表7 各階段概率輪盤Table 7 Probability wheel of each stage

表7給出了兩種算法在函數f1上進行10個周期（Cycle）測試的結果。第二列表示相應算法在每個周期中突破當前全局最優解的次數；Select probability表示每個周期所使用的概率輪盤。由于個體擾動成功次數的作用是設置概率輪盤，并不代表全局最優解得到突破，為了直觀地觀察每個周期全局最優解被突破的次數，第二列中記錄了最優位置擾動成功的次數。周期1是均勻概率輪盤，每個映射被選到的概率為14.28%；周期2中Logistic 映射有最高的擾動成功率，而Logistic 映射并不是最適合求解f1的映射，取得這一結果的原因是擾動的內在隨機性；周期3和周期4中Circle映射和Kent映射對種群擾動的成功率相比周期2有顯著的提高；在周期7與周期8中，Circle 映射逐漸占據了主導地位，這是因為Circle 映射的概率分布的峰值出現在[0.4,0.6]區間內，實現了高成功率擾動；從周期9開始，Gauss 映射擾動的成功率突然增加，而Circle 映射擾動的成功率快速下降，這種現象產生的原因是Circle 映射的分布特性已經不適用于算法的收斂階段，此時需要選擇更合適的Gauss映射對種群進行持續擾動。以上分析表明，即使是最有效的混沌映射，也不能在算法求解的整體擾動過程中都發揮最大的作用，而本文提出的多混沌映射策略解決了這一缺陷。此外，由MMCSSA 和RCSSA在各階段的全局最優解被擾動成功的次數可知，本文所提的學習機制的多混沌映射策略能夠有效提升算法的性能。

4.3.3 策略之間的互補性分析

本文從三個改進方向提出了下列改進策略：（1）提升初始種群質量的重心反向學習策略；（2）改善發現者位置更新方式的黃金正弦領導策略；（3）增強算法逃逸局部能力的多混沌映射策略和高斯變異策略。提高初始種群的質量是SSA提升其收斂精度的重要舉措，相比隨機種群，重心反向學習策略產生的精英種群因具有更高的質量使其更易發現全局最優解；動態調整的黃金正弦領導策略通過引導個體移動方向改善了SSA 搜索過程中缺乏方向性的問題，但在遇到特定復雜問題時（如局部最優解與全局最優解在空間上極為接近），種群仍會陷入局部極值；因此，需要對種群進行持續擾動以賦予其多樣性來克服上述缺陷，當個體陷入局部最優時，算法首先使用多混沌映射策略在整個解空間中探索優質解，若未發現更優解，說明搜索空間其他區域有更優解的可能性較小，接著使用高斯變異策略在當前區域進行開發以盡最大可能地跳出局部最優解。

綜上所述，在MMCSSA中，初始化策略產生的精英種群起到提升算法收斂速度的作用；黃金正弦策略能夠引導種群進行全局探索；多混沌映射策略和高斯變異策略增強了算法逃逸局部最優的能力，上述四個策略協同作用提高了算法的性能。

4.4 MMCSSA的種群多樣性分析

4.3.1 小節驗證了重心反向學習策略給算法帶來的持續性影響，本節為了驗證所有改進策略對種群多樣性的提升，將MMCSSA 和SSA 分別對Bent Cigar 函數進行尋優實驗。Bent Cigar 函數的三維全局最小值點是x*=(0,0,0)。下面繪制MMCSSA迭代過程中初始種群、迭代10次、50次后的麻雀種群位置分布圖和SSA相同時期的麻雀種群分布圖（圖15～圖20），圖中黑色圓點表示種群個體，紅色原點代表當前全局最優個體。以上實驗進行10次，取代表多次實驗的一次結果。

圖15 SSA隨機初始種群Fig.15 Random initial population of SSA

圖16中，通過重心反向學習策略初始化得到的精英種群均勻分布在最優解附近；由圖17、圖18對比可知，隨著迭代次數的增加，SSA 種群過快地向全局最優位置靠攏，種群多樣性急劇降低，MMCSSA引入黃金正弦領導策略和多混沌映射策略，使得其搜索空間顯著大于SSA；由圖19、圖20 對比可知，當迭代到50次時，MMCSSA和SSA都集中到全局最小值點(0,0,0) 附近，但MMCSSA 最優解的精度明顯高于SSA，這是由于多混沌擾動幫助算法擴大了搜索空間，找到了更優解。綜上，本文提出的MMCSSA 在種群多樣性和搜索空間大小方面均優于SSA。

圖16 MMCSSA重心反向學習策略初始種群Fig.16 Initial population of MMCSSA centroid opposition-based learning strategy

圖17 SSA迭代10次后Fig.17 After 10 iterations of SSA

圖18 MMCSSA迭代10次后Fig.18 After 10 iterations of MMCSSA

圖19 SSA迭代50次后Fig.19 After 50 iterations of SSA

圖20 MMCSSA迭代50次后Fig.20 After 50 iterations of MMCSSA

5 結論

針對麻雀算法易陷入局部極值、后期收斂速度慢等缺點，本文提出了一種融合學習機制的多混沌麻雀搜索算法（MMCSSA），并對12 個測試函數進行了仿真實驗。實驗選取了其他學者提出的改進麻雀算法進行比較，并將所得結果進行了統計學分析，最終得到以下結論：

（1）MMCSSA收斂精度高，有較強的全局搜索能力：重心反向學習策略使算法在初始化階段包含更多解空間的有效信息。迭代過程中，多混沌映射策略和高斯變異策略豐富了種群多樣性，有效地幫助算法擺脫局部極值，增強了算法的全局搜索能力。

（2）MMCSSA具有較強的魯棒性及穩定性：在不同類型、不同維度的函數測試中，相較對比算法，MMCSSA 有著最低的標準差，表現出了較好的優化穩定性。

（3）MMCSSA 收斂速度快，優化效率高：黃金正弦領導策略有效調整了算法在收斂速度和搜索能力上的平衡，使算法在更短的時間內達到了更高的收斂精度。