混合正弦余弦算法和Lévy飛行的麻雀算法

毛清華 ，張強(qiáng) *，毛承成 ，柏嘉旋

（1.燕山大學(xué) 經(jīng)濟(jì)管理學(xué)院，河北 秦皇島 066004；2.莫納什大學(xué) 商學(xué)院，澳大利亞 墨爾本 VIC 3145）

0 引言

近幾年新的群智能優(yōu)化算法如雨后春筍一般不斷浮現(xiàn)，學(xué)者們通過模擬自然界眾多生物的行為，提出了一系列的群智能優(yōu)化算法，如：灰狼優(yōu)化算法（GWO），飛蛾火焰優(yōu)化算法（MFO），鯨魚優(yōu)化算法（WOA），麻雀搜索算法（SSA）等等。由于群智能優(yōu)化算法操作簡單，求解問題能力強(qiáng)，被眾多學(xué)者所青睞。其中麻雀搜索算法是2020年由薛建凱［1］首次提出，是一種新型群智能優(yōu)化算法。麻雀搜索算法與其他算法相比，具有求解速率高、精確度高等特點(diǎn)，然而，在算法搜索后期仍然和其余智能算法一樣，面臨無法躍出局部極值的問題。

為加強(qiáng)算法抗局部最優(yōu)的能力，眾多學(xué)者都提出了各自的改進(jìn)方法：Hegazy等［2］通過引入慣性權(quán)重，提高算法的求解速率，并成功優(yōu)化特征選擇問題。Wang等［3］提出自適應(yīng)慣性權(quán)重，動(dòng)態(tài)調(diào)整速度變化，使蝙蝠在靠近最優(yōu)解過程中能夠自適應(yīng)改變速度。崔志華等［4］引入了平均聚類的多樣性度量指標(biāo)，保持了種群的多樣性。Wang等［5］加入柯西擾動(dòng)操作，避免螢火蟲算法困于局部極值。Li等［6］通過引入非線性控制參數(shù)和柯西變異，提高了粒子群算法收斂速度和精度。Cui等［7］結(jié)合質(zhì)心策略及改變蝙蝠速度更新方程，以提高算法全局開拓能力。Cui等［8］在布谷鳥算法中引入Lévy分布和指數(shù)分布，提高了后期算法擾動(dòng)變異能力，進(jìn)而擺脫局部區(qū)域。Elaziz等［9］引進(jìn)差分算法，在局部搜索區(qū)域內(nèi)，以差分變異算子作為住操作符，提升了樽海鞘群算法的特征開掘能力。Xu等［10］在飛蛾算法中，利用高斯變異增強(qiáng)局部挖掘能力，借助柯西變異提升全局探索能力。Mafarja等［11］將模擬退火思想融合到鯨魚優(yōu)化算法中，提升算法逃離局部空間的能力。Li等［12］將Lévy飛行分布應(yīng)用到飛蛾算法中，以此提高算子變異能力。

以上文獻(xiàn)對群智能算法的改進(jìn)，對算法抗局部最優(yōu)能力均有一定的提高，但是，仍存在精確度差，開掘能力不足的弱點(diǎn)。考慮到自適應(yīng)權(quán)重能夠有效平衡局部和全局的挖掘能力，以及Lévy飛行策略具備較強(qiáng)的局部擾動(dòng)能力，提出一種混合正弦余弦算法和Lévy飛行的麻雀算法（ISSA）。首先，融入正弦余弦思想并添加非線性學(xué)習(xí)因子，動(dòng)態(tài)調(diào)整發(fā)現(xiàn)者位置更新機(jī)制，并加快求解速率；然后，在跟隨者位置更新方式中引進(jìn)Lévy飛行策略，對當(dāng)前最優(yōu)解進(jìn)行擾動(dòng)變異，加強(qiáng)局部逃逸能力；最后對8個(gè)基準(zhǔn)測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證了ISSA改進(jìn)策略的有效性與可行性。

1 基本麻雀搜索算法

麻雀搜索算法是受到生物界麻雀捕食和反捕食行為的啟發(fā)而提出的。麻雀集合矩陣如下：

式（1）中：n是麻雀的數(shù)量，i＝（1，2，…，n），d是變量的維數(shù)。

麻雀的適應(yīng)度值矩陣表示如下：

其中：n表示麻雀的數(shù)量，而Fx中的每個(gè)值表示個(gè)體的適應(yīng)性值。適應(yīng)度值更好的麻雀優(yōu)先獲得食物，并作為發(fā)現(xiàn)者帶領(lǐng)整個(gè)種群向食物源靠近。發(fā)現(xiàn)者的位置更新方式如下：

其中：t表示當(dāng)前迭代次數(shù)，j＝（1，2，…，d），表示第i個(gè)麻雀在第j維的位置，itermax表示最大迭代次數(shù)，α∈(0，1)范圍的一個(gè)隨機(jī)數(shù)，R2（R2∈［0，1］）、ST（ST∈［0.5，1］）分別代表預(yù)警值和安全值，Q代表服從［0，1］正態(tài)分布的隨機(jī)數(shù)，L表示1×d的矩陣，且矩陣內(nèi)每個(gè)元素為1。當(dāng)R2＜ST，這表明周圍沒有天敵，發(fā)現(xiàn)者能夠進(jìn)行大范圍搜索食物。如果R2≥ST，則意味著一些麻雀已經(jīng)發(fā)現(xiàn)了天敵，整個(gè)種群需要快速飛到其他安全區(qū)域。

除發(fā)現(xiàn)者外，剩余都是跟隨者，跟隨者的位置更新公式如下：

其中，Xworst表示全局最差的位置，A表示1×d的矩陣，矩陣中每個(gè)元素隨機(jī)賦值1或—1，且A+＝AT(AAT)—1。當(dāng)i＞n/2時(shí)，表示適應(yīng)度值較差的第i個(gè)跟隨者沒有獲得食物，能量值極低，此時(shí)需要飛往其他地方覓食，以獲得更多的能量。

偵查預(yù)警行為：

種群覓食時(shí)，會(huì)選取少量麻雀負(fù)責(zé)警戒，當(dāng)天敵出現(xiàn)時(shí)，不論是發(fā)現(xiàn)者還是跟隨者，都將會(huì)放棄當(dāng)前的食物而飛到一個(gè)新的位置。每代從種群中隨機(jī)選取SD（一般取10%～20%）只麻雀進(jìn)行預(yù)警行為。其位置更新公式為：

其中：Xbest表示全局最佳的位置，β為步長控制參數(shù)，是一個(gè)均值為0、方差為1的正態(tài)分布隨機(jī)數(shù)，k∈［—1，1］范圍內(nèi)的一個(gè)均勻隨機(jī)數(shù)。這里，fi是當(dāng)前麻雀的適應(yīng)度值。fg和fw分別為當(dāng)前的全局最佳和最差適應(yīng)度值，ε為最小常數(shù)，以避免分母出現(xiàn)0。當(dāng)fi＞fg時(shí)，表示麻雀在種群的邊緣，極容易受到天敵的攻擊；fi＝fg表明，處于種群中間的麻雀意識(shí)到了被天敵攻擊的危險(xiǎn)，需要靠近其他麻雀。k表示麻雀移動(dòng)的方向，即步長控制參數(shù)。

2 混合正弦余弦算法和Lévy飛行的麻雀算法（ISSA）

2.1 融合正弦余弦算法（SCA）思想

基本SSA算法中，在R2＜ST時(shí)，發(fā)現(xiàn)者隨著迭代次數(shù)的進(jìn)行，麻雀個(gè)體每一維都在變小，搜索空間逐漸減小，增大了墜入局部空間的概率。為改善此問題，在發(fā)現(xiàn)者位置更新方式中融合正弦余弦（SCA）算法思想［13］，并引入非線性正弦學(xué)習(xí)因子，在搜索前期具有較大的值，有助于全局探索，在搜索后期，具有較小的值，有助于提升局部開拓能力、提高精確度。學(xué)習(xí)因子公式和改進(jìn)后的發(fā)現(xiàn)者位置公式如下：

式（8）中，r1為［0，2π］內(nèi)的隨機(jī)數(shù)，r2是［0，2］內(nèi)的隨機(jī)數(shù)。

2.2 Lévy飛行策略

當(dāng)發(fā)現(xiàn)者迭代一定次數(shù)且適應(yīng)度值不變時(shí)，此時(shí)跟隨者成了發(fā)現(xiàn)者，為避免算法陷入局部最優(yōu)，在跟隨者更新公式中引入Lévy飛行策略，提高全局搜索能力。改進(jìn)后的公式如下：

式（10）中r3、r4均為［0，1］范圍內(nèi)的隨機(jī)數(shù)，ξ的值可取1.5，σ計(jì)算方式如下：

其中 Γ(x)＝(x—1)！。

混合正弦余弦算法和Lévy飛行的麻雀算法步驟流程圖見圖1。

圖1 ISSA算法流程圖Fig.1 Flow of ISSA algorithm

3 算法性能測試

3.1 算法參數(shù)設(shè)置

為驗(yàn)證ISSA算法的有效性，以及發(fā)現(xiàn)者比例對算法性能的影響，選取粒子群算法（PSO）［15］、灰狼算法（GWO）［16］、飛蛾火焰算法（MFO）［17］、基本麻雀算法（SSA）［1］以及改變發(fā)現(xiàn)者比例的兩種麻雀算法SSA1、SSA2進(jìn)行對比。算法參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置表Table1 Parameters settings

3.2 算法性能結(jié)果對比分析

本文在表2所示的基準(zhǔn)測試函數(shù)上進(jìn)行算法性能的測試，使用Matlab2019a編寫算法和仿真實(shí)現(xiàn)。為增強(qiáng)實(shí)驗(yàn)結(jié)果說服力，降低偶然誤差的可能性，各個(gè)算法在每一個(gè)基準(zhǔn)測試函數(shù)上獨(dú)立運(yùn)行30次。求解結(jié)果如表3所示。

表2 基準(zhǔn)測試函數(shù)Table 2 Benchmarking functions

表3 基準(zhǔn)測試函數(shù)優(yōu)化結(jié)果比較Table 3 Comparison among optimal results of benchmarking functions

由表3可以發(fā)現(xiàn)，ISSA求解各個(gè)基準(zhǔn)測試函數(shù)的平均值比其余6種算法更接近理論全局最優(yōu)值，標(biāo)準(zhǔn)差的數(shù)值更小，標(biāo)準(zhǔn)差低表明求解數(shù)據(jù)波動(dòng)較小，尋優(yōu)過程魯棒性更強(qiáng)。因此ISSA算法在尋優(yōu)性能上相較于 SSA、SSA1、SSA2、GWO、PSO 和MFO等算法精確度更高，更容易尋到最優(yōu)解。

3.3 算法收斂曲線對比分析

為直觀體現(xiàn)ISSA算法的收斂性能，圖2展示了7種算法的迭代收斂曲線。橫坐標(biāo)代表迭代次數(shù)，縱坐標(biāo)代表適應(yīng)度的對數(shù)值。

圖2 8個(gè)基準(zhǔn)測試函數(shù)收斂曲線Fig.2 Convergence curves of 8 benchmark functions

從以上收斂曲線圖可知，不論是在高維或是低維條件下，ISSA都具備更佳的收斂性能，其收斂曲線更加平滑，較大的拐點(diǎn)很少。與其他四種算法相比，ISSA曲線一直處于最下方，表示收斂速度更快，對數(shù)值越小，表明求解精度更高。此外，改變發(fā)現(xiàn)者的比例，由10%增加到30%的過程中，10%的發(fā)現(xiàn)者比例效果最差，20%與30%的發(fā)現(xiàn)者比例效果性能差異較小，優(yōu)化能力相當(dāng)，但均不及ISSA。

3.4 與混沌麻雀算法（CSSA）比較

為進(jìn)一步體現(xiàn)改進(jìn)之后麻雀搜索算法的優(yōu)越性，選取幾個(gè)具有代表性的測試函數(shù)與呂鑫［18］中所提出的混沌麻雀搜索算法（CSSA），SSA進(jìn)行算法性能比較，通用條件以文獻(xiàn)［18］為準(zhǔn)，比較結(jié)果如表4所示。

表4 ISSA與CSSA算法性能比較Table 4 Comparison of algorithm performance between CSSA and ISSA

從表4可知，對于優(yōu)化單峰函數(shù)，ISSA在平均值和標(biāo)準(zhǔn)差兩個(gè)指標(biāo)上，比CSSA尋優(yōu)性能至少提升了49個(gè)數(shù)量級(jí)，效果提升較大，對于優(yōu)化多峰函數(shù)f6至f8，ISSA與CSSA優(yōu)化效果不分上下?？偠灾琁SSA的平均值和標(biāo)準(zhǔn)差更小，說明ISSA在求解過程中，精確度更高、穩(wěn)定性更強(qiáng)，是一種效率更高的算法。

4 結(jié)論

本文提出一種改進(jìn)的麻雀搜索算法（ISSA），并基于基準(zhǔn)測試函數(shù)進(jìn)行仿真實(shí)驗(yàn)，比較算法性能，得出以下結(jié)論：

（1）融合正弦余弦算法思想和引入非線性學(xué)習(xí)因子改變發(fā)現(xiàn)者的位置更新機(jī)制，可進(jìn)一步協(xié)調(diào)局部挖掘和全局開拓的能力；引進(jìn)Lévy飛行策略，改進(jìn)跟隨者位置更新方式，可提升抗局部極值的能力。

（2）在基準(zhǔn)函數(shù)上的測試比較發(fā)現(xiàn)，ISSA比GWO、PSO、MFO、SSA、SSA1、SSA2、CSSA具備更強(qiáng)的優(yōu)化性能，在求解速率、精確度、穩(wěn)定性等方面展現(xiàn)出了顯著的優(yōu)越性。

（3）后續(xù)研究可將ISSA算法應(yīng)用于一些實(shí)際的工程優(yōu)化問題，如數(shù)據(jù)預(yù)測、路徑規(guī)劃、選址研究等，以驗(yàn)證ISSA在實(shí)際問題中的有效性。