湯安迪， 韓 統(tǒng)， 徐登武， 謝 磊

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

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

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

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

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

1 麻雀搜索算法

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

SSA算法中有發(fā)現(xiàn)者、追隨者以及警戒者。分別按照各自規(guī)則進行位置更新，更新規(guī)則如下：

(1)

(2)

式中：Xp表示被發(fā)現(xiàn)者占據(jù)的最佳位置；Xworst表示當(dāng)前最差位置，A是一個一行多維的元素為1或-1的矩陣。

(3)

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

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

2.1 混沌映射

混沌是一種在非線性動力系統(tǒng)中產(chǎn)生的隨機現(xiàn)象，具有規(guī)律性、隨機性，對初始條件和遍歷性敏感。根據(jù)這些特征，構(gòu)造了不同方程表示的混沌圖，用以更新優(yōu)化算法中的隨機變量[9]。

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

表1 混沌映射

2.2 等級制度策略

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

(4)

2.3 布朗運動

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

(5)

麻雀位置更新公式為：

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

(6)

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

2.4 改進算法描述

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

圖1 CSSA-HB流程圖

3 仿真實驗

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

表2 測試函數(shù)

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

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

為了進一步分析混沌映射對于SSA算法的改進能力，根據(jù)表3的平均值對各算法進行比較排序，結(jié)果如表4所示，最后一欄為各算法平均排序結(jié)果?？梢缘弥渲?種映射結(jié)合算法表現(xiàn)優(yōu)于SSA算法，SSA-4排序第1，尋優(yōu)性能在11種算法中最強，SSA-3次之，其余算法排名為：SSA-2和SSA-8并列，SSA、SSA-5和SSA-6并列，SSA-10、SSA-9、SSA-1。結(jié)合以上分析，混沌映射對于SSA算法的性能具有促進作用，且第4種混沌映射表現(xiàn)最佳，因此在后文對改進算法進行性能測試時，使用該映射進行參數(shù)調(diào)整。

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

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

表5 7種算法平均值比較

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

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

表6 7種算法性能排序結(jié)果

圖2 7種算法性能雷達(dá)圖

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

圖3 7種算法收斂箱式圖

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

圖4 7種算法收斂曲線圖

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

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

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

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

4 結(jié)語

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

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