基于混合優化策略的麻雀搜索算法研究*

易華輝，王雨璇，黃金香，宋文治，李 壘

（西安工業大學兵器科學與技術學院，西安 710021）

0 引言

近年來，優化已經成為一個熱門的研究領域，也是一種尋找復雜問題最優解的經濟方法[1]。麻雀搜索算法（Sparrow Search Algorithm，SSA）是一種新型智能算法，具有優化能力更強、效率更快的優點[2]。在求解全局優化問題時具有較強的搜索能力和并行性，相比較其他具有代表性的群智能優化算法相比，SSA 在收斂精度和穩定性方面具有明顯的優勢，但在處理復雜工程問題時會出現局部最優的現象。

針對上述問題，毛清華等[3]提出了一種融合柯西變異和反向學習的新型優化方法，在豐富解多樣性的同時，在全局和局部尋優方面都得到提高，加快了解的尋優速度。付華等[4]為增加種群的多樣性，采用柯西高斯變異策略。為提高算法的尋優速度，結合雞群算法的隨機跟隨策略優化跟隨者的位置更新公式，平衡算法的開發性能和搜索能力，提高了尋優精度和收斂速度。張偉康等[5]提出了自適應t 分布與黃金正弦算法改進的麻雀搜索算法，實驗結果表明所提算法具有更好的收斂性和求解精度。湯安迪等[6]將正余弦和反向學習策略引入到麻雀搜索算法中，提出了一種混沌麻雀搜索算法，增強了算法的魯棒性和尋優性。Xiong 等[7]為豐富解的多樣性，提升麻雀搜索算法全局搜索的充裕性，采用對立學習策略；為提高原始算法的局部極值的能力，在不同的迭代階段對最優解位置執行自適應干擾變異，提出自適應t 分布變異，整體來看，尋優精度和速度都優于對比算法。錢敏等[8]利用反向學習和混沌理論提出了一種新型的改進算法，增強了麻雀搜索算法的停滯性。上述文獻中，針對SSA 的缺點所提出的改進策略在一定程度上都得到了提升，但仍存在尋優速度慢、收斂精度不高等問題。

針對算法的不足，本文提出混合優化策略來改進麻雀搜索算法（ISSA）。首先，利用Piecewise 混沌映射以提高種群的多樣性；其次，引入黃金搜索策略更新生產者的位置，提高算法的搜索能力；然后，引入自適應權重策略來協調搜索的能力；最后，針對麻雀種群陷入局部極值的問題，引入模擬退火思想，解決跳出極值的缺陷；對比12 個基準函數從精度、穩定性和收斂速度3 個方面對其性能進行了評估。結果表明，與原始的SSA 搜索算法相比，ISSA 算法體現出較強的魯棒性和更快的收斂速度。

1 麻雀搜索算法

麻雀搜索算法（SSA）是新型的智能優化算法，該算法在實際應用中求解全局優化問題時具有很強的搜索能力和并行性。麻雀種群分為生產者和捕食者，生產者負責搜索食物來提供發現食物的地點和方向。捕食者通過跟隨生產者來獲得食物。生產者和捕食者的身份動態變化，但生產者和捕食者在整個種群中的比例是恒定的。偵察者主要是警戒威脅環境并及時發出警戒信號，警示麻雀向安全區域行進。

n只麻雀數量表示方式如下：

式中：i=1，2，3，…，n為當前迭代次數；tmax為最大迭代次數；α為rand（0，1）；變量Q服從高斯分布；L為元 素 大 小 都 為1 的1·d 的 矩 陣；R2（R2∈[0,1)）和ST(ST∈[0.5,1))分別為警戒值和安全值，R2＜ST表示此時周圍外界環境沒有危險發生，生產者可以充分執行搜索策略；R2≥ST表示捕食者被麻雀種群中的個體發現，此時需立即向種群中其余麻雀個體發出警戒信息，使麻雀種群能快速躲避到安全區域。

捕食者的位置更新方式如下：

式中：Xbest和Xworst分別為生產者最佳和最差位置；A∈[-1,1]的1·d 的矩陣，A+=AT(AAT)-1；N為種群的大小；i＞N/2 表明捕食者i沒有得到食物并處于饑餓態，需獲取更多能量補充自己。

警戒者的位置更新方式如下：

式中：Xtgbest表示當前全局最佳位置；K的范圍為rand（-1，1）；β為步長控制參數；fi為麻雀的最優適應值；fg為全局最優適應值；fw為適應度最差的值；ε為最小常數，可避免零除誤差；fi＞fg表明麻雀種群處在邊緣位置極易受到捕食者的攻擊；fi=fg表明麻雀感知到危險，在靠近其他麻雀的同時，來減少自身暴露在危險中。

2 麻雀搜索算法的改進

2.1 Piecewise混沌映射

基本SSA 算法以隨機的方式初始化種群，這樣生成的種群差異性較大，搜索空間的環境信息不能充分加以利用。盡可能提高麻雀初始種群的差異性和多樣性，降低局部最優的概率成為改進算法的先驗條件之一。目前常 用Logistic 混 沌 映 射[9]、Tent 混 沌 映 射[10]和Piecewise 混沌映射[11]等來解決初始化種群的問題。為了更好地得到初始解的位置，提高最優解的多元性。本文采用Piecewise 混沌映射初始化種群增加種群隨機出現的概率，豐富解的位置，Piecewise混沌映射定義如下：

Piecewise 映射相比于隨機分布的種群，改進后不僅擴大了種群中解空間的搜索范圍，也增加了麻雀種群的位置多樣性和均勻性，尋優效率得到了極大的提升。

2.2 黃金搜索策略

黃金搜索優化算法[12]（GSO）是一種結合了粒子群優化（PSO）和正余弦算法（SCA）的優化方法。黃金搜索算法主要包含勘探和開發兩個階段，可以很好地平衡這兩種相互矛盾的能力。黃金搜索算法的步長評估策略是搜索算法的核心，主要由3 部分組成：第一部分表示步長的先前值，目的是平衡算法的搜索能力；第二部分表示t在當前位置與個體最佳位置之間的距離；第三部分表示t在當前位置與所有最佳位置之間的距離。更新公式如下：

式中：r1和r2為[0，2]之間的隨機值；T為一種轉移因子，它將搜索從探索轉換為利用，以提高搜索性能，T= 100·exp(-20·t/tmax)；c1= 2.55- 2.05·t/tmax；c2=1.55-t·t/tmax；tmax為最大迭代次數。

在基本SSA 算法中，R2≥ST表示種群中的麻雀發現了捕食者，應快速躲避到安全區域。為了防止麻雀在搜索時因搜索速度過快而導致算法出現早熟收斂并陷入局部最優。本文引入黃金搜索策略更新生產者的位置更新公式，改進后公式如下：

2.3 自適應權重策略

慣性權重w的大小闡明了算法搜索能力的高低，w愈大全局尋優愈強，w愈小局部尋優能力愈強。本文受文獻[13]的啟發，引入[-4，4]的負雙曲正切函數控制的慣性權重，增強算法的局部尋優能力，更新公式如下：

式中：t為當前迭代次數；tmax為最大迭代次數。

設置參數時wmax= 0.9，wmin= 0.4尋優效果最好。

在SSA 算法中，警戒者代表麻雀預警能力的強弱，原始算法中，警戒者在初始化前設置為種群數量的10%～20%，但是固定不變的警戒者數量并不能最大化在整個過程中的作用。因此本文對警戒者的數量比例進行改進，步長控制參數β和K在平衡全局搜索與局部開發方面起到關鍵性的作用，但因β和K都是隨機數也無法滿足算法在解空間的探索性能，導致算法陷入局部最優，于是引入自適應權重對步長控制參數β和K進行優化。改進后位置更新公式如下：

2.4 模擬退火算法

模擬退火（SA）算法[14]是一種貪婪的方法，其思想借鑒于固體退火的原理，特點是從某一較高的溫度出發，以一定的概率P來接受劣質解從而跳出局部最優。依照Metropolis 準則，粒子在溫度t時趨于平衡的概率為exp(-?E/Kt)，E是溫度t時的內能，?E為內能的改變量，K是玻爾茲曼常數。為減少計算量將劣質解的接受概率設置為：

式中：E(Xj+1)為擾動產生新解時的能量值；t為第j次迭代時的溫度，模擬退火算法初始溫度為種群初始適應度最大值與最小值之差；當E(Xj+1)＜E(Xj)時，接受新的解Xj+1，否則以概率P接受劣質解Xj。

本文將模擬退火思想中的Metropolis準則引入到麻雀搜索算法中來解決SSA 易陷入局部最優的缺陷。以最初麻雀最優位置為依據設置初始溫度，每次迭代后計算更新后的適應度值與最優值的差距，判斷能否接受較差的解。式（11）中的概率調整如下：

式中：Enew(Xj)為新種群中第j個麻雀個體的適應度值，新舊位置適應度之差的大小是調節接受劣質解概率P的主要方式。

2.5 ISSA算法步驟

ISSA的基本步驟如下：

（1）初始化參數（種群數量和最大迭代次數即M和tmax），生產者比例PD，預警值ST，警戒者比例SD，根據式（6）初始化種群以增加搜索范圍的多樣性；

（2）計算種群中個體適應和全局最優適應度值，并記錄最優位置和個體；

（3）使用式（8）更新麻雀生產者位置；

（4）使用式（4）更新麻雀捕食者位置；

（5）使用式（10）更新警戒者位置；

（6）更新麻雀個體位置和全局最優位置；

（7）進入模擬退火階段，退火率為t=0.99，根據式（12）計算接受新解的概率P，對比概率P與隨機值rand，判斷是否接受新解來更換全局最優解并進行模擬退火操作，更新退火溫度；

（8）是否到達最大迭代次數，若未達到，t=t+ 1且則返回步驟4；

（9）輸出個體最優和全局最優值。

3 仿真實驗與分析

3.1 算法性能測試與分析

為了驗證本文所提出算法的可行性和尋優性，與ISSA、SSA、PSO、GWO、WOA 在12個基準測試函數下進行30次對比實驗（表1），進而客觀地反映算法改進的有效性。測試函數中F1～F5表示單峰函數，F6～F12表示多峰函數，見表1。

表1 基準函數優化結果比較

本文實驗環境均為Windows 10 系統，16GRAM 和2.49 GHz CPU 環境下進行仿真測試，軟件為Matlab2021a，最大迭代次數為500，種群個數為100，基本SSA 算法和改進ISSA 算法的參數設置為ST=0.8，PD=0.2，SD=0.2，見表2。

表2 基準測試函數優化結果對比

F4F7 30F5 30F6 30 30F8 30F9 30F1030F112F122 GWO SSA ISSA PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA 2.54E-16 0.00E+00 0.00E+00 2.83E-01 1.58E-02 1.17E-11 0.00E+00 0.00E+00 3.65E+02 2.57E+01 2.51E+01 1.38E-08 1.30E-10 1.81E-02 2.40E-05 2.16E-04 4.82E-06 1.01E-06-9.96E+03-1.26E+04-8.09E+03-1.00E+04-1.26E+04 3.94E+01 0.00E+00 0.00E+00 0.00E+00 0.00E+00 3.60E-01 8.88E-16 1.87E-14 8.88E-16 8.88E-16 6.38E-01 0.00E+00 0.00E+00 0.00E+00 0.00E+00-1.03E+00-1.03E+00-1.03E+00-1.03E+00-1.03E+00 9.98E-01 9.98E-01 9.98E-01 9.98E-01 9.98E-01 1.14E-12 0.00E+00 0.00E+00 2.00E+00 3.07E+01 1.76E-10 0.00E+00 0.00E+00 1.16E+03 2.67E+01 2.63E+01 7.83E-06 7.16E-06 7.49E-02 1.05E-03 5.93E-04 1.65E-04 7.81E-05-7.90E+03-1.16E+04-6.42E+03-8.72E+03-1.25E+04 7.42E+01 0.00E+00 4.92E-01 0.00E+00 0.00E+00 2.53E+00 4.44E-15 2.73E-14 8.88E-16 8.88E-16 8.87E-01 2.72E-03 2.65E+00 0.00E+00 0.00E+00-1.03E+00-1.03E+00-1.03E+00-1.03E+00-1.03E+00 3.82E+00 1.06E+01 2.18E+00 2.55E+00 9.98E-01 3.10E-12 0.00E+00 0.00E+00 8.89E-01 2.84E+01 1.63E-10 0.00E+00 0.00E+00 6.06E+02 2.88E-01 7.12E-01 1.23E-05 1.132E-05 4.82E-02 1.24E-03 2.94E-04 1.54E-04 7.86E-05 1.10E+03 1.11E+03 7.51E+02 6.07E+02 3.93E+01 2.30E+01 0.00E+00 1.51E+00 0.00E+00 0.00E+00 6.53E-01 2.64E-15 4.14E-15 0.00E+00 0.00E+00 1.17E-01 1.04E-02 5.46E-02 0.00E+00 0.00E+00 2.81E-18 5.90E-18 2.28E-18 3.23E-18 2.07E-18 2.43E+00 3.62E-01 1.90E+00 4.04E+00 0.00E+00

4F136 PSO WOA GWO SSA ISSA PSO WOA GWO SSA ISSA-3.32E+00-3.32E+00-3.32E+00-3.32E+00-3.32E+00-1.05E+01-1.05E+01-1.05E+01-1.05E+01-1.05E+01 7.16E-02 8.03E-02 6.73E-02 6.05E-02 8.35E-02 1.69E+00 2.44E+00 1.48E+00 1.37E+00 1.83E-05F14-3.22E+00-3.24E+00-3.24E+00-3.26E+00-3.21E+00-1.01E+01-9.45E+00-1.05E+01-1.02E+01-1.05E+01

由此可知，ISSA 的平均值、最優值、標準差在整體性能上，相比較PSO、GWO、WOA 和原SSA 算法，ISSA在尋優精度和搜索速度等方面都優于其他算法。

為了能更直觀地顯示ISSA 算法的優化效果，圖1 分別表示上述比較的5 種算法，在12 個基準測試函數上的迭代尋優曲線圖。

圖1 5種函數在12個基準函數上的迭代尋優圖

從圖中可以看出，ISSA 算法不管對于單峰還是多峰函數，在短時間內找到或者接近理論最優值的同時，收斂速度也較其他算法均得到了明顯的提升。

上述函數中F1～F5為單峰測試函數，主要測試算法全局開發的能力，在F1～F4的迭代曲線中，ISSA 尋優效果最優，均能在提高搜索速度的同時穩定得到全局最優解，收斂速度相較于其他算法較快，能明顯的看出ISSA跳出局部極值的特點；對于F5函數，雖然提升精度不高，但最優值和穩定性仍高于其他算法。

在多峰測試函數中，F7和F9這兩個測試函數可以看出ISSA 具有較強的尋有能力，收斂速度相較于其他算法比較明顯。在F6、F8和F10～F12測試函數中，對于F6和F8這兩個測試函數而言，伴隨迭代次數的遞增，各個算法都出現了不同程度的局部最優解現象，但改進的ISSA 算法在收斂的穩定性和搜索精度均高于其他優化算法。對于F10～F12雖然收斂精度相同，但可以看出每個算法都易找到局部最優點，但ISSA 收斂速度相比較其他算法效果明顯，陷入局部最優解的概率較小。

綜上所述，本文所提出的ISSA 在單峰和多峰測試函數上都有較強的尋優能力和搜索精度，處理結果更好，進一步說明了改進的算法的有效性和可行性。

3.2 ISSA算法改進比較

為了進一步驗證本文所提算法的有效性，將與呂鑫[15]所提出的混沌麻雀搜索算法（Chaos sparrow search algorithm，CSSA）進行比較，實驗中的測試函數選用幾種典型的基準函數，其余參數相關條件與文獻[14]中相同，比較結果如表3 所示。由表可知，對于ISSA 在搜索精度和穩定性方面都得到了提升。對于函數F6～F7其優化效果相當，其余函數在平均值和標準差上都能比CSSA更優。從整體指標來看，ISSA 的值更小，在尋優精度上更能跳出局部最優解，由此證明了ISSA算法相比及CSSA和SSA算法都體現出較強的尋優能力和更優的穩定性。

表3 測試函數仿真結果對比

4 結束語

考慮到SSA 在解決復雜優化問題時尋優速度慢、適應性差的問題，本文提出了一種基于混合優化策略的麻雀搜索算法，采用Piecewise 混沌映射初始化種群的位置，增加個體間多樣性的同時。引入黃金搜索策略，對生產者的位置進行更新，提升原算法的尋優速度；為改進算法后期陷入局部最優的缺陷，引入自適應權重策略和模擬退火策略，增強算法尋優精度。在此基礎上對12個函數的仿真測試，并和其他文獻算法進行對比。結果表明，改進的ISSA 算法在收斂速度和尋優精度上都優于其他對比算法。