融合差分進化和混合多策略的麻雀搜索算法

朱 鵬，杜逆索,+，歐陽智

(1.貴州大學 計算機科學與技術學院，貴州 貴陽 550025；2.貴州大學 貴州省大數據產業發展應用研究院，貴州 貴陽 550025)

0 引 言

隨著群智能算法廣泛地應用于各個領域，越來越多的新算法也相繼被提出，如海獅優化算法[1]、海鷗優化算法[2]、蝴蝶優化算法[3]、鯨魚優化算法[4]、旗魚優化算法[5]等。

麻雀搜索算法(sparrow search algorithm，SSA)是由Xue、Shen提出的一種新型群智能算法[6]，該算法相比其它群智能算法，具有參數少、魯棒性強、收斂精度高、收斂速度快等優點，然而，SSA在搜索后期仍存在易陷入局部最優、收斂速度和精度有限、穩定性差等缺陷，但目前國內外對該算法的研究還相對較少，因此對該算法的研究具有必要性。針對類似群智能算法，已經有大量的研究從算法的收斂精度和速度、魯棒性等多方面進行優化改進。例如翟軍昌等[7]利用反向學習策略針對和聲搜索算法能夠很好提升種群的多樣性；Ouyang等[8]也是將反向學習技術引入和聲搜索算法當中,以此提高了算法的開發能力；李銀通等[9]通過引入非線性權重因子，以此平衡了算法的局部和全局的搜索能力并提高了算法的收斂速度；滕志軍等[10]也采用了非線性控制參數權衡了算法局部以及全局的搜索能力，同時加快了算法尋優速度；Nenavath等[11]融合差分進化算法，改善了正弦余弦優化算法的搜索能力并提升了收斂精度；謝聰等[12]通過融入差分進化和精英策略，提升了蝴蝶優化算法的尋優精度和穩定性。然而，針對于SSA目前還沒有通過類似方法對算法性能進行改進優化的研究。

綜上所述，針對SSA存在收斂速度慢、易陷入局部最優和穩定性差的問題，本文提出了融合差分進化和混合多策略的麻雀搜索算法(DEH-SSA)，將從3個方面對SSA進行改進：①采用反向學習初始化以增加種群的多樣性；②引入非線性權重因子改進麻雀發現者的位置更新公式，更好平衡算法局部和全局的搜索能力，加快收斂速度；③融入差分進化算法和精英策略提升算法的全局搜索能力和收斂精度。通過上述3方面的改進，在基于10個經典基準測試函數上進行測試，驗證了DEH-SSA算法在性能上的效果。

1 麻雀搜索算法

麻雀搜索算法(SSA)是受麻雀覓食和躲避捕食者的行為啟發于2020年所提出的一種新型群智能算法[6]，該算法在模擬麻雀覓食和抗捕食的行為過程中，把整個種群分為了發現者和追隨者，其中能夠找到較好食物的個體為發現者，其它剩下的個體為追隨者；同時在整個種群當中還隨機抽取了一定比例的麻雀，這部分麻雀具有偵察警戒危險的屬性，相當于額外疊加了一個預警機制。

在設計SSA時，根據麻雀的生物特性，制定了相應的理想化規則：

(1)能夠找到較好食物源的麻雀作為發現者，發現者在警戒值安全范圍內積極搜尋食物，當超出警戒值時則逃到安全區域；剩下的部分麻雀作為追隨者繼續跟隨發現者一起覓食或是逃到安全區域，而在追隨者當中最差的那部分麻雀則自己單獨去覓食，以獲取更好的食物。

(2)種群中的每個個體只要能夠找到更好的食物源都可以成為發現者，但發現者個體的比例在整個種群當中是恒定的。

(3)不管是發現者還是追隨者，當有危險信號時，處在種群外圍的個體會朝著安全區域移動；處在種群中間的個體則會隨機地靠近其它個體。

SSA的具體實現步驟如下：

步驟1 初始化種群規模數n、個體空間維度dim、迭代次數itermax，設置種群中發現者個體的比例為PD，具有偵察警戒屬性個體的比例為SD。

步驟2 計算個體的適應度，并求出此時的最優值fMin和最優解Xbest作為全局的最優值。

步驟3 針對所得的適應度值，對相應的個體進行排序，按發現者比例PD選擇適應度好的為發現者，再通過式(1)更新發現者的位置

(1)

步驟4 剩下的n-PD個個體為追隨者，其位置更新通過式(2)更新

(2)

式中：XP為發現者位置更新后的種群中最好適應度值的個體位置，Xworst為當前種群中個體最差位置，A是一個1×dim矩陣且當中元素為隨機的1或-1，A+=AT(AAT)-1。

步驟5 在種群當中隨機抽取比例為SD的個體作為具有警戒屬性的麻雀，此時警戒屬性個體位置更新通過式(3)更新

(3)

式中：Xbest為當前全局最優位置，β為一個均值是0且方差為1的符合標準正態分布的隨機數，K∈[-1,1] 是一個均勻隨機數，fi為當前個體的適應度值，fg和fw分別為當前全局最好和最差的適應度值，ε是一個最小常數以避免分母為0。

步驟6 通過式(1)～式(3)進行位置更新后，計算各個個體的適應度，求出當前的最優值pMin和最優解pbest，ifpMin

步驟7 判斷是否達到最大迭代次數：若是，則終止循環并輸出最優值fMin和最優解Xbest， 否則，回到步驟3。

2 麻雀搜索算法的改進

2.1 反向學習初始化種群

反向學習作為一種智能計算中的新技術，是Tizhoosh[13]提出。其目的是基于當前解，找出與其對應的反向解，再通過適應度計算選擇并保存較好的解。受周克良等[14]的啟發，通過反向學習策略初始化能有效提高種群的多樣性，避免陷入局部最優。反向學習初始化過程如下：

(1)隨機生成臨時的初始化種群Xi,j。

(4)

式中：ubi,j和lbi,j分別為Xi,j對應的第i個個體當中第j維的上限和下限。

2.2 非線性權重因子

通過對SSA算法的模型進行實驗分析，SSA在迭代求解的過程中，種群中的發現者作為相對較優位置個體，它的位置更新對自身位置的依賴性較強，導致算法迭代前期的搜索能力不足和收斂速度過慢；而在迭代后期又會導致陷入局部最優。由此，引入非線性權重因子λ來改進種群中發現者的位置更新公式以平衡算法的局部和全局的搜索能力，同時改善算法的收斂速度。算法迭代前期，應降低發現者個體對于自身位置的依賴性，以獲取更大的解空間并提升全局優化能力；迭代后期，應加大對自身位置的依賴程度，以提高收斂速度。非線性權重因子公式為

λ=(t/itermax)2

(5)

此時對發現者位置更新式(1)進行簡化和改進為

(6)

為了簡化式(3)把具有警戒屬性個體的位置更新規則改進為：不管是發現者還是追隨者，當有危險信號時，處在種群外圍的個體還是會朝著安全區域移動；處在種群中間的個體則會逃到最優位置和最差位置之間的一個隨機位置，此時式(3)改為

(7)

2.3 融入差分進化和精英策略

2.3.1 DE算法

DE算法[15]是Storn、Price在遺傳算法的思想基礎上提出來的優化方法，已被廣泛地應用于各個工程領域[16]。由于差分進化算法具有較好的魯棒性和全局的尋優能力，所以把它融入到SSA當中試圖提升SSA的收斂精度和全局的尋優能力。

DE算法與遺傳算法類似，擁有包括變異、交叉、選擇的進化過程。

變異操作：在第k次迭代時，隨機從種群中選擇3個個體Yp1,k,Yp2,k,Yp3,k，然后通過式(8)生成新的個體Vr,k

Vr,k=Yp1,k+F·(Yp2,k-Yp3,k)

(8)

式中：r=(1,2,…,n)，p1、p2、p3∈(1,2,…,n) 且r≠p1≠p2≠p3，F∈[0,2] 是縮放因子用于控制變異的概率，通常取0.5。

交叉操作：針對目標個體Yr,k和變異個體Vr,k進行交叉操作，通過式(9)產生新的交叉個體Ur,k

(9)

式中：cr∈(0,1) 是服從均勻分布的隨機數，CR∈[0,1] 為交叉的概率，jrand∈[1,dim] 為隨機整數。

選擇操作：對于當前個體Yr,k和交叉后生成的新個體Ur,k， 通過式(10)對其采用貪婪算法選擇適應度值小的作為下一代種群的個體Yr,k+1

(10)

2.3.2 精英策略

為了提升算法局部的尋優能力，引入精英策略在第t次迭代后得到的當前最優解best附近產生符合正態分布的隨機數，公式如式(11)

(11)

2.4 DEH-SSA算法描述

綜上所述，DEH-SSA算法的具體步驟如圖1所示。

圖1 改進算法流程

3 仿真實驗結果與分析

為驗證DEH-SSA算法具有更好的性能和在不同改進策略上的有效性，仿真實驗從以下3方面進行：

(1)把DEH-SSA與反向學習和非線性權重因子改進得來的SSA1、融合差分進化和精英策略的SSA2做實驗比較，驗證不同策略的有效性。

(2)把DEH-SSA與灰狼優化算法(GWO)、引力搜索算法(GSA)和原始的SSA做實驗比較，通過實驗數據論證本算法的可行性、有效性和優越性。

(3)將DEH-SSA與其它算法進行Wilcoxon秩和檢驗以此驗證本文算法相較于其它算法具有顯著性差異。

實驗引入具有不同特征屬性的10個經典標準測試函數進行仿真實驗，如表1所示，其中F1～F5為單峰函數，常用來檢驗算法的收斂精度和速度；F6～F10為多峰函數，主要用于檢測算法的開發能力和跳出局部的能力。為了降低誤差的影響，算法分別在獨立運行30次的情況下，通過最優值、平均值和標準差3個性能指標進行評估，其中平均值反應算法的真實收斂精度和速度；標準差反映算法的魯棒性和穩定性。

算法參數設置：種群規模n為100，最大迭代次數itermax為1000，發現者PD和警戒屬性個體SD的比例為種群數的20%，警戒閾值ST為0.8，縮放因子F為0.5，交叉概率CR為0.1。實驗環境：Intel?CoreTMi5-7500 CPU@3.40 GHz，RAM 8.0 GB，Windows 10 操作系統，MATLAB R2018b。

3.1 與不同策略比較

通過將DEH-SSA與反向學習和非線性權重因子改進得來的SSA1、融合差分進化和精英策略的SSA2在表1的10個測試函數求解下作比較，進一步地驗證不同改進策略的有效性。實驗結果見表2，各策略算法獨立運行30次后的平均收斂曲線如圖2所示。

從表2數據和圖2平均收斂曲線分析可知，對于單峰函數F1～F5，其中F1、F2，DEH-SSA均達到了理論值，且SSA1與DEH-SSA具有同樣的收斂速度，SSA1收斂速度也明顯比SSA2快，就尋優精度，SSA1和SSA2都比SSA更優，進一步驗證了改進策略的有效性；F3、DEH-SSA的精度略優于SSA2，由于改進SSA1的策略收斂速度過快，抑制了DEH-SSA的尋優精度，但為了平衡尋優精度和速度，融合SSA1和SSA2的DEH-SSA也會更穩健；F4、DEH-SSA與SSA2擁有同樣的收斂精度，提升了15個數量級以上，在最優值時相較于SSA1、SSA，都找到了理論值0；F5、SSA1與SSA2在尋優精度和收斂速度優于SSA，融合了SSA1和SSA2后的DEH-SSA性能效果則是最優。

表1 測試函數說明

表2 DEH-SSA與SSA、SSA1、SSA2結果分析

圖2 各策略算法的平均收斂曲線

對于多峰函數F6～F9，其中F6、F8，DEH-SSA在融合了SSA1和SSA2后的性能是最好的，且SSA2在精度上已經接近了DEH-SSA，驗證了SSA2比SSA具有更好的全局尋優能力，不管是SSA1還是SSA2，在收斂精度和速度、魯棒性性能指標上，都比SSA提升了不少；F7，雖精度上沒變，但從收斂曲線可知，SSA1與DEH-SSA具有同樣的收斂速度且都優于SSA、SSA2，驗證了引入非線性權重能更好的改善收斂速度；F9、SSA2和DEH-SSA接近于理論值，但都比SSA1、SSA效果好且精度、穩定性都更高，驗證了融合差分進化和精英策略的SSA2擁有更好的跳出局部的能力；F10，所有算法都達到理論值，表明DEH-SSA具有更優的魯棒性。

綜上所述，通過對表2和圖2的分析，SSA1采用反向學習初始化可以增加種群的多樣性，同時引入非線性權重因子可以加強平衡算法局部和全局的搜索能力，加快收斂速度；SSA2融入差分進化和精英策略能更好提升算法全局搜索能力和收斂精度；最后，融合了SSA1和SSA2的DEH-SSA具有更優的局部和全局搜索能力、尋優精度和速度、穩定性，充分驗證了不同改進策略的有效性。

3.2 與GWO、GSA和SSA比較

為了驗證DEH-SSA的效能優勢，將分別與WGO、GSA和SSA在表1的10個測試函數下求解作比較分析。實驗的結果見表3，平均收斂曲線如圖3所示。

從表3的數據和圖3的平均收斂曲線分析可知，對于單峰函數F1～F5，其中F1、F2、DEH-SSA均找到了理論值0，其對應的收斂曲線也是最快的；F3、F5、DEH-SSA雖沒有達到理論值，但相比GWO、GSA、SSA在精度和穩定性上也有明顯的提升，其收斂曲線迭代到相同的次數時，具有更好的收斂精度和速度；F4、DEH-SSA直接在SSA精度上提升了15個數量級以上，其最優值也尋到了理論值0，魯棒性比另外3個算法更好，對應的收斂曲線也明顯得優于GWO、GSA、SSA。

對于多峰函數F6～F10，其中F6、DEH-SSA相比另外3個算法，不管在精度、還是魯棒性上，其性能都得到了大幅度的提升，對應的收斂曲線也更快；F7雖精度上沒提升，但從迭代曲線得出，收斂速度明顯快于其它算法；F8、DEH-SSA在收斂精度上提升了15個數量級上，精度、穩定性、速度都明顯更優；F9、DEH-SSA接近于達到了理論值，收斂速度更快，魯棒性也是最穩定的；F10、SSA、DEH-SSA均達到理論值，但穩定性上DEH-SSA更優于其它算法。

從結果與算法設計的關系角度分析，F1～F5是高維的單峰函數，當中以F3最為典型且智能算法很難處理，因為它特性是非凸且病態的單峰函數，主要測試算法的收斂速度和精度，從表1它的取值范圍上結合圖3中F3走勢看出，極小可能會收斂到全局最優，由于非線性權重因子具有能夠平衡算法的局部和全局搜索能力，同時改善算法的收斂速度，而差分進化能夠提升算法的收斂精度和開發能力，因此引入非線性權重因子和差分進化使得DEH-SSA的收斂精度和速度都明顯優于了其它算法。F6～F10為非線性多峰函數，有著許多局部極值點，主要是測試算法跳出局部的能力以及全局搜索的能力，從表3和圖3得出DEH-SSA也明顯優于其它算法，這是因為反向學習初始化能夠改善算法跳出局部最優的能力和非線性權重因子能夠加快算法收斂速度，差分進化和精英策略更重于提升算法全局尋優能力以及跳出局部的能力。

綜上，DEH-SSA不管在單峰函數還是在多峰函數上，它的尋優精度、收斂速度、魯棒性和全局尋優能力都明顯優于其它算法，展現了DEH-SSA具有更好的可行性、有效性和優越性。

3.3 Wilcoxon秩和檢驗

在上述實驗中，基于30次獨立運行后算法的3個評價指標都沒有對每次運行的結果進行獨立比較。為驗證DEH-SSA相較于其它算法存在著顯著性差異，采用Wilcoxon秩和檢驗進行統計分析，Wilcoxon秩和檢驗在5%的顯著性水平下進行，當檢驗結果p值小于5%時，拒絕H0假說，表明對比的兩種算法存在顯著性差異；否則接受H0假說，表明進行對比的兩種算法在整體上的尋優結果是相同的[17]。

在10個測試函數下DEH-SSA與其它算法的Wilcoxon秩和檢驗結果p值見表4，由于最佳算法不能與自身進行比較，因此在表中標記為‘Na’表示此算法與最佳算法尋優結果一致，無法判斷顯著性差異。從表4檢驗結果分析，對于SSA、SSA1和SSA2算法中存在小部分函數p值為Na，表明在對這部分函數尋優時，SSA、SSA1和SSA2算法與DEH-SSA表現相同；而對于其中4個函數，如F2、F3、F8、F9，SSA2的p值略小于0.05，表明DEH-SSA與SSA2在這4個函數上尋優效果無明顯差異；在函數F9上，也與SSA1無明顯差異。除此之外，在表4中可以看出大部分的p值是遠小于0.05，因此拒絕H0假說，表明DEH-SSA算法相較于其它的5種算法存在著顯著性差異且在統計上的優越性也是顯著的。

4 結束語

本文針對SSA算法存在的收斂速度慢、穩定性差和易陷入局部最優等缺陷，把反向學習策略引入到種群中進行初始化，增加種群的多樣性，進一步利用非線性權重因子來改進公式，提升算法的收斂速度并平衡算法局部和全局的搜索能力；同時融入差分進化和精英策略提升算法的局部和全局尋優能力，提出了融合差分進化和混合多策略的麻雀搜索算法(DEH-SSA)。在10個基準測試函數上與不同策略進行對比實驗，通過結果分析，表明了DEH-SSA的

表3 DEH-SSA與GWO、GSA、SSA結果分析

圖3 各算法的平均收斂曲線

表4 Wilcoxon 秩和檢驗的p值

改進策略在尋優精度、速度和穩定性上的優勢。同時，與其它算法進行的比較分析，結果表明DEH-SSA在局部和全局的搜索能力、收斂速度和精度、魯棒性方面都要優于SSA、GWO等算法。其中，就尋優精度，DEH-SSA對部分函數精度提升到15個數量級以上、部分函數的收斂精度達到理論值；穩定性方面，DEH-SSA的標準差在大部分函數上比其它算法提升都在5個數量級以上，進一步驗證了DEH-SSA具有更好的尋優精度、速度和穩定性。通過Wilcoxon秩和檢驗也驗證了DEH-SSA具有更顯著性的差異。在接下來的研究中，考慮將DEH-SSA算法應用于圖像分割領域，進一步驗證算法的性能。