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

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

群智能優(yōu)化算法是一類模擬自然界生物行為和自然現(xiàn)象的元啟發(fā)式優(yōu)化算法，具有良好的并行性和自主探索性。自1975年美國(guó)教授Holland根據(jù)達(dá)爾文進(jìn)化論以及自然界優(yōu)勝劣汰機(jī)制提出了遺傳算法[1]以后，越來(lái)越多的學(xué)者通過(guò)對(duì)不同生物種群和物理現(xiàn)象進(jì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)化算法，具有搜索精度高、收斂快等特點(diǎn)，但其在接近全局最優(yōu)時(shí)，仍舊會(huì)出現(xiàn)種群多樣性減小、易于陷入局部最優(yōu)等缺陷。

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

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

1 麻雀搜索算法

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

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

(1)

(2)

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

(3)

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

2 基于等級(jí)制度和布朗運(yùn)動(dòng)的混沌麻雀搜索算法

2.1 混沌映射

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

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

表1 混沌映射

2.2 等級(jí)制度策略

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

(4)

2.3 布朗運(yùn)動(dòng)

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

(5)

麻雀位置更新公式為：

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

(6)

式中：P=0.5；R為0到1均勻分布的隨機(jī)數(shù)；RB為布朗運(yùn)動(dòng)步長(zhǎng)。

2.4 改進(jìn)算法描述

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

圖1 CSSA-HB流程圖

3 仿真實(shí)驗(yàn)

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

表2 測(cè)試函數(shù)

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

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

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

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

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

表5 7種算法平均值比較

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

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

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

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

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

圖3 7種算法收斂箱式圖

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

圖4 7種算法收斂曲線圖

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

表7 7種算法計(jì)算耗時(shí)比較

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

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

4 結(jié)語(yǔ)

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

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