基于混合優(yōu)化策略的麻雀搜索算法研究*

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

（西安工業(yè)大學(xué)兵器科學(xué)與技術(shù)學(xué)院，西安 710021）

0 引言

近年來，優(yōu)化已經(jīng)成為一個(gè)熱門的研究領(lǐng)域，也是一種尋找復(fù)雜問題最優(yōu)解的經(jīng)濟(jì)方法[1]。麻雀搜索算法（Sparrow Search Algorithm，SSA）是一種新型智能算法，具有優(yōu)化能力更強(qiáng)、效率更快的優(yōu)點(diǎn)[2]。在求解全局優(yōu)化問題時(shí)具有較強(qiáng)的搜索能力和并行性，相比較其他具有代表性的群智能優(yōu)化算法相比，SSA 在收斂精度和穩(wěn)定性方面具有明顯的優(yōu)勢(shì)，但在處理復(fù)雜工程問題時(shí)會(huì)出現(xiàn)局部最優(yōu)的現(xiàn)象。

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

針對(duì)算法的不足，本文提出混合優(yōu)化策略來改進(jìn)麻雀搜索算法（ISSA）。首先，利用Piecewise 混沌映射以提高種群的多樣性；其次，引入黃金搜索策略更新生產(chǎn)者的位置，提高算法的搜索能力；然后，引入自適應(yīng)權(quán)重策略來協(xié)調(diào)搜索的能力；最后，針對(duì)麻雀種群陷入局部極值的問題，引入模擬退火思想，解決跳出極值的缺陷；對(duì)比12 個(gè)基準(zhǔn)函數(shù)從精度、穩(wěn)定性和收斂速度3 個(gè)方面對(duì)其性能進(jìn)行了評(píng)估。結(jié)果表明，與原始的SSA 搜索算法相比，ISSA 算法體現(xiàn)出較強(qiáng)的魯棒性和更快的收斂速度。

1 麻雀搜索算法

麻雀搜索算法（SSA）是新型的智能優(yōu)化算法，該算法在實(shí)際應(yīng)用中求解全局優(yōu)化問題時(shí)具有很強(qiáng)的搜索能力和并行性。麻雀種群分為生產(chǎn)者和捕食者，生產(chǎn)者負(fù)責(zé)搜索食物來提供發(fā)現(xiàn)食物的地點(diǎn)和方向。捕食者通過跟隨生產(chǎn)者來獲得食物。生產(chǎn)者和捕食者的身份動(dòng)態(tài)變化，但生產(chǎn)者和捕食者在整個(gè)種群中的比例是恒定的。偵察者主要是警戒威脅環(huán)境并及時(shí)發(fā)出警戒信號(hào)，警示麻雀向安全區(qū)域行進(jìn)。

n只麻雀數(shù)量表示方式如下：

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

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

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

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

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

2 麻雀搜索算法的改進(jìn)

2.1 Piecewise混沌映射

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

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

2.2 黃金搜索策略

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

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

在基本SSA 算法中，R2≥ST表示種群中的麻雀發(fā)現(xiàn)了捕食者，應(yīng)快速躲避到安全區(qū)域。為了防止麻雀在搜索時(shí)因搜索速度過快而導(dǎo)致算法出現(xiàn)早熟收斂并陷入局部最優(yōu)。本文引入黃金搜索策略更新生產(chǎn)者的位置更新公式，改進(jìn)后公式如下：

2.3 自適應(yīng)權(quán)重策略

慣性權(quán)重w的大小闡明了算法搜索能力的高低，w愈大全局尋優(yōu)愈強(qiáng)，w愈小局部尋優(yōu)能力愈強(qiáng)。本文受文獻(xiàn)[13]的啟發(fā)，引入[-4，4]的負(fù)雙曲正切函數(shù)控制的慣性權(quán)重，增強(qiáng)算法的局部尋優(yōu)能力，更新公式如下：

式中：t為當(dāng)前迭代次數(shù)；tmax為最大迭代次數(shù)。

設(shè)置參數(shù)時(shí)wmax= 0.9，wmin= 0.4尋優(yōu)效果最好。

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

2.4 模擬退火算法

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

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

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

式中：Enew(Xj)為新種群中第j個(gè)麻雀?jìng)€(gè)體的適應(yīng)度值，新舊位置適應(yīng)度之差的大小是調(diào)節(jié)接受劣質(zhì)解概率P的主要方式。

2.5 ISSA算法步驟

ISSA的基本步驟如下：

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

（2）計(jì)算種群中個(gè)體適應(yīng)和全局最優(yōu)適應(yīng)度值，并記錄最優(yōu)位置和個(gè)體；

（3）使用式（8）更新麻雀生產(chǎn)者位置；

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

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

（6）更新麻雀?jìng)€(gè)體位置和全局最優(yōu)位置；

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

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

（9）輸出個(gè)體最優(yōu)和全局最優(yōu)值。

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

3.1 算法性能測(cè)試與分析

為了驗(yàn)證本文所提出算法的可行性和尋優(yōu)性，與ISSA、SSA、PSO、GWO、WOA 在12個(gè)基準(zhǔn)測(cè)試函數(shù)下進(jìn)行30次對(duì)比實(shí)驗(yàn)（表1），進(jìn)而客觀地反映算法改進(jìn)的有效性。測(cè)試函數(shù)中F1～F5表示單峰函數(shù)，F(xiàn)6～F12表示多峰函數(shù)，見表1。

表1 基準(zhǔn)函數(shù)優(yōu)化結(jié)果比較

本文實(shí)驗(yàn)環(huán)境均為Windows 10 系統(tǒng)，16GRAM 和2.49 GHz CPU 環(huán)境下進(jìn)行仿真測(cè)試，軟件為Matlab2021a，最大迭代次數(shù)為500，種群個(gè)數(shù)為100，基本SSA 算法和改進(jìn)ISSA 算法的參數(shù)設(shè)置為ST=0.8，PD=0.2，SD=0.2，見表2。

表2 基準(zhǔn)測(cè)試函數(shù)優(yōu)化結(jié)果對(duì)比

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 的平均值、最優(yōu)值、標(biāo)準(zhǔn)差在整體性能上，相比較PSO、GWO、WOA 和原SSA 算法，ISSA在尋優(yōu)精度和搜索速度等方面都優(yōu)于其他算法。

為了能更直觀地顯示ISSA 算法的優(yōu)化效果，圖1 分別表示上述比較的5 種算法，在12 個(gè)基準(zhǔn)測(cè)試函數(shù)上的迭代尋優(yōu)曲線圖。

圖1 5種函數(shù)在12個(gè)基準(zhǔn)函數(shù)上的迭代尋優(yōu)圖

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

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

在多峰測(cè)試函數(shù)中，F(xiàn)7和F9這兩個(gè)測(cè)試函數(shù)可以看出ISSA 具有較強(qiáng)的尋有能力，收斂速度相較于其他算法比較明顯。在F6、F8和F10～F12測(cè)試函數(shù)中，對(duì)于F6和F8這兩個(gè)測(cè)試函數(shù)而言，伴隨迭代次數(shù)的遞增，各個(gè)算法都出現(xiàn)了不同程度的局部最優(yōu)解現(xiàn)象，但改進(jìn)的ISSA 算法在收斂的穩(wěn)定性和搜索精度均高于其他優(yōu)化算法。對(duì)于F10～F12雖然收斂精度相同，但可以看出每個(gè)算法都易找到局部最優(yōu)點(diǎn)，但I(xiàn)SSA 收斂速度相比較其他算法效果明顯，陷入局部最優(yōu)解的概率較小。

綜上所述，本文所提出的ISSA 在單峰和多峰測(cè)試函數(shù)上都有較強(qiáng)的尋優(yōu)能力和搜索精度，處理結(jié)果更好，進(jìn)一步說明了改進(jìn)的算法的有效性和可行性。

3.2 ISSA算法改進(jìn)比較

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

表3 測(cè)試函數(shù)仿真結(jié)果對(duì)比

4 結(jié)束語

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