基于等級制度和布朗運動的混沌麻雀搜索算法

湯安迪， 韓 統， 徐登武， 謝 磊

(1.空軍工程大學航空工程學院，西安，710038； 2.94855部隊，浙江衢州，324000)

群智能優化算法是一類模擬自然界生物行為和自然現象的元啟發式優化算法，具有良好的并行性和自主探索性。自1975年美國教授Holland根據達爾文進化論以及自然界優勝劣汰機制提出了遺傳算法[1]以后，越來越多的學者通過對不同生物種群和物理現象進行分析，從中獲取靈感，提出多種群智能優化算法。包括粒子群算法[2](particle swarm optimization，PSO)、鯨魚優化算法[3](whale optimization algorithm，WOA)、灰狼優化算法[4](grey wolf optimization，GWO)等。

麻雀搜索算法(sparrow search algorithm，SSA)是薛建凱等[5]于2020年提出的群智能優化算法，具有搜索精度高、收斂快等特點，但其在接近全局最優時，仍舊會出現種群多樣性減小、易于陷入局部最優等缺陷。

為了改善群體的多樣性，防止算法陷入局部最優，楊萬里等[6]利用Logistic映射調整PSO算法慣性權重，通過混沌映射的隨機遍歷性，使算法在迭代過程中隨機選擇開發或探索行為；IBRAHIM等[7]利用Logistic映射初始化GWO算法種群，增加初始種群個體多樣性，以此增加算法收斂效率；呂鑫等[8]利用Tent映射對SSA算法個體進行擾動，防止算法陷入局部最優。

上述文獻主要利用某一種混沌映射對算法進行改進，但沒有討論不同混沌映射對于算法性能改進的影響。本文為解決麻雀搜索算法在迭代后期多樣性減弱、易于陷入局部最優的問題，提出利用混沌映射調整麻雀搜索算法關鍵參數，通過函數測試確定使用哪種混沌映射，并引入GWO算法的等級制度，增強種群多樣性，利用布朗運動擴大搜索范圍，增強算法探索能力，當算法陷入停滯時，使用布朗運動策略對個體施加擾動，幫助算法跳出局部最優，最后利用貪婪策略有效保留優勢個體，加快算法收斂速度。

1 麻雀搜索算法

麻雀搜索算法是一種新興的群智能優化算法。SSA主要模擬了麻雀覓食的過程。麻雀覓食過程是發現者-跟隨者模型的一種，同時還疊加了偵查預警機制。種群中找到食物較好的個體作為發現者，其他個體作為跟隨者，同時種群中選取一定比例的個體進行偵查預警，如果發現危險則放棄食物，安全第一。

SSA算法中有發現者、追隨者以及警戒者。分別按照各自規則進行位置更新，更新規則如下：

(1)

(2)

式中：Xp表示被發現者占據的最佳位置；Xworst表示當前最差位置，A是一個一行多維的元素為1或-1的矩陣。

(3)

式中：Xbest是當前全局最佳位置；β是步長控制參數；fi是當前麻雀的適應度；fg和fw是當前最佳適應度和最差適應度；ε是一個常數，用于避免分母為零。

2 基于等級制度和布朗運動的混沌麻雀搜索算法

2.1 混沌映射

混沌是一種在非線性動力系統中產生的隨機現象，具有規律性、隨機性，對初始條件和遍歷性敏感。根據這些特征，構造了不同方程表示的混沌圖，用以更新優化算法中的隨機變量[9]。

在本文中，使用一維且不可逆的混沌映射來生成一組混沌值來改善基本SSA算法的參數，如表1，這10種混沌映射在生成數值時效果不同，且已在文獻[10～12]中證明其有效性。

表1 混沌映射

2.2 等級制度策略

麻雀搜索算法在對警戒者更新時，僅考慮當前狀態最優解，沒有考慮其他次優解，缺少群體間交流，降低種群個體多樣性，易使算法陷入局部最優，因此學習灰狼優化算法中的等級制度策略，選取前3個最優解對警戒者進行位置更新，更新公式如下：

(4)

2.3 布朗運動

布朗運動是一個隨機過程，其步長取決于一個均值為0、方差為1的高斯分布概率函數，能夠更均勻、更可控的步長覆蓋搜索空間，布朗運動在點x處的概率密度函數如下：

(5)

麻雀位置更新公式為：

（一）加深學生對于課文的理解激發學生的興趣。興趣是最好的老師，要想學生真正的喜歡掌握一門知識，最重要的是讓學生對這門課產生極大的興趣。而具體情境的建設，就可以通過這樣的方式讓孩子們對語文產生極大的興趣。并能夠更加直觀的感受、理解每一篇課文背后的深層含義。

(6)

式中：P=0.5；R為0到1均勻分布的隨機數；RB為布朗運動步長。

2.4 改進算法描述

本文針對麻雀搜索算法種群多樣性減少、易于陷入局部最優的不足，提出了基于等級制度和布朗運動的混沌麻雀搜索算法(chaos sparrow search algorithm based on hierarchy and Brownian motion，CSSA-HB)。首先利用混沌映射調整麻雀搜索算法的警戒值參數，然后利用等級制度策略和布朗運動策略對種群中優勢個體和劣勢個體分別進行更新，當算法陷入停滯時，使用布朗運動策略，幫助算法跳出停滯，最后利用貪婪策略保留優勢個體，加快算法收斂效率。改進算法流程見圖1。

圖1 CSSA-HB流程圖

3 仿真實驗

為確定使用哪種混沌映射調整SSA參數，將SSA與各混沌映射結合，與第1種混沌映射結合的算法命名為SSA-1，與第2種混沌映射結合的算法命名為SSA-2，以此類推，將SSA與上述10種混沌映射分別與SSA結合的算法在12種測試函數中進行比較，測試函數如表2所示。為公平比較，在相同實驗平臺上，設置種群數為50，最大迭代數為300，算法參數與原文獻保持一致。所有算法均使用MATLAB R2018b編程，計算機操作系統為Windows10，處理器為AMD R7 4700 U 16 GB。表3為各算法獨立運行30次的統計結果。

表2 測試函數

表3 11種混沌映射組合算法計算平均值比較

從表3可以得知，對于F1、F2，有5種映射結合算法優于SSA算法；對于F3、F8，有4種映射結合算法優于SSA算法；對于F4、F9，有6種映射結合算法優于SSA算法；對于F5，有3種映射結合算法優于SSA算法；對于F6、F7、F11，所有算法性能相近；對于F10，則有7種映射結合算法優于SSA算法；而對于F12，僅有2種映射結合算法優于SSA算法。其中，SSA-4算法在7個測試函數中優于原算法，在3個測試函數中與原算法性能差異不大，僅在1個測試函數中表現劣于SSA算法；SSA-3在6個測試函數中優于原算法，在3個測試函數中與原算法性能相近，同樣僅在1個測試函數中表現劣于SSA算法。

為了進一步分析混沌映射對于SSA算法的改進能力，根據表3的平均值對各算法進行比較排序，結果如表4所示，最后一欄為各算法平均排序結果。可以得知，其中4種映射結合算法表現優于SSA算法，SSA-4排序第1，尋優性能在11種算法中最強，SSA-3次之，其余算法排名為：SSA-2和SSA-8并列，SSA、SSA-5和SSA-6并列，SSA-10、SSA-9、SSA-1。結合以上分析，混沌映射對于SSA算法的性能具有促進作用，且第4種混沌映射表現最佳，因此在后文對改進算法進行性能測試時，使用該映射進行參數調整。

表4 11種混沌映射組合算法排序結果

為了充分驗證CSSA-HB算法的有效性與優越性，選擇WOA[3]、GWO[4]、BSO[15]、PSO[14]、FPA[15]以及傳統SSA算法進行對比分析，參數同前，表5為各算法獨立運行30次的統計結果。最優值加粗體表示。

表5 7種算法平均值比較

分析表5可知，對于單峰測試函數F1～F5，CSSA-HB在7種算法中表現最佳，尋優精度和尋優穩定性較其他算法有較大提升，對于多峰測試函數F6～F9，CSSA-HB在F6和F7中表現與原算法相近，但優于其他對比算法，在F8和F9中，CSSA-HB性能優于所有對比算法，對于固定維度測試函數F10～F12，CSSA-HB在F10中尋優效果弱于SSA，但差異不大，在F11中，各算法性能相近，在F12中，CSSA-HB優于所有對比算法。因此，本文提出的CSSA-HB算法在其中8個測試函數中尋優性能最佳，在3個測試函數中與SSA性能相近，優于其余對比算法，僅在1個測試函數中表現差于SSA，證明CSSA-HB算法改進的有效性。

為了進一步驗證CSSA-HB算法的尋優性能，根據表5的均值對各算法進行排序，結果如表6所示。

表6 7種算法性能排序結果

圖2 7種算法性能雷達圖

圖3為7種算法獨立求解12個基準測試函數30次所得結果的箱式圖，從圖中可以得知，在進行求解時，CSSA-HB求得的異常點均少于對比算法，且在求解所有測試函數時，收斂值的分布相比其它對比算法整體上更為集中，明顯優于其他對比算法，說明改進的CSSA-HB算法具有較強的魯棒性。

圖3 7種算法收斂箱式圖

為了進一步闡述CSSA-HB的收斂性能，7種算法獨立運行30次求解12個基準測試函數收斂曲線如圖4所示。在求解F1～F5、F7、F9和F10時，CSSA-HB有更快的收斂速度和收斂精度，在求解F6和F8時，CSSA-HB收斂速度在前期弱于SSA，但在犧牲一定的收斂速度的情況下，能夠在后期更快收斂到全局最優值，且收斂精度優于所有對比算法，在求解F12時，PSO算法性能最佳，但CSSA-HB能在后期收斂到全局最優值。因此CSSA-HB相比SSA，其尋優性能具有明顯提升，具有較強局部最優規避能力和更高的收斂精度與收斂速度。

圖4 7種算法收斂曲線圖

算法運行時間也是衡量算法性能的重要指標，表7列出了各算法求解測試函數的平均計算耗時，由表7可知，CSSA-HB的計算耗時平均排名排在最后，這是由于每一次迭代中都會使用混沌映射，以及在更新警戒者位置時，使用了高斯概率密度函數，同時SSA排在第4，而改進策略的加入進一步加大了計算耗時。另一方面，由前文的收斂性分析可知，相較對比算法，CSSA-HB的收斂速度更快，收斂精度更高，因此增加的計算耗時換來了更好的巡游精度，這是可以接受的。

表7 7種算法計算耗時比較

為進一步體現本文提出的CSSA-HB的有效性，選取幾個具有代表的測試函數與文獻[8]提出的改進算法在同一條件下進行對比。仿真結果如表8所示。由表8可知，對于單峰測試函數F1和F3，CSSA-HB在平均值和標準差上相較于CSSA至少提升了20個數量級，提升效果明顯，對于F2和F4，CSSA-HB至少提升了10個數量級，對于F5，相較于CSSA，CSSA-HB能夠更穩定地求解最優值。對于多峰測試函數F6～F12，兩種算法各有優劣，對于F7-F9，兩種算法性能相似，CSSA-HB在F11上效果好于CSSA，CSSA則在F6、F10、F12上效果更好。總體來說，CSSA-HB在12個測試函數中的9個測試函數上的效果不差于CSSA，表明CSSA-HB的性能更好，再一次驗證了本文改進算法的有效性。

表8 CSSA-HB與CSSA算法性能比較

4 結語

本文首先探討混沌映射調整麻雀搜索算法參數對于麻雀搜索算法性能的影響，然后引入等級制度和布朗運動策略，提出了基于等級制度和布朗運動的混沌麻雀搜索算法，通過12個測試函數驗證，結果表明使用迭代映射調整麻雀搜索算法參數效果最佳；利用6個對比算法和改進算法以及原始算法進行比較，證明了本文提出的改進算法尋優性能具有明顯提升，具有較強局部最優規避能力和更高的收斂精度與收斂速度。

本文對于麻雀搜索算法的改進主要集中在搜索算子的改進，這些改進策略不僅可以應用于麻雀搜索算法，也可以應用于其他智能優化算法的研究，但改進策略的適用性需進一步驗證。同時，機器學習是近些年優化領域的研究熱點，可以將麻雀搜索算法與機器學習方法進行結合。此外，隨著工業生產需求增大，復雜的現實優化問題對于智能優化算法的要求增多，對于麻雀搜索算法的改進需適應不同問題的特性。尤其是對于實時性要求較高的工程優化問題，需要在算法的精度和速度做更多考慮。