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

(1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025；2.貴州大學(xué) 貴州省大數(shù)據(jù)產(chǎn)業(yè)發(fā)展應(yīng)用研究院，貴州 貴陽 550025)

0 引 言

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

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

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

1 麻雀搜索算法

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

在設(shè)計(jì)SSA時，根據(jù)麻雀的生物特性，制定了相應(yīng)的理想化規(guī)則：

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

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

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

SSA的具體實(shí)現(xiàn)步驟如下：

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

步驟2 計(jì)算個體的適應(yīng)度，并求出此時的最優(yōu)值fMin和最優(yōu)解Xbest作為全局的最優(yōu)值。

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

(1)

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

(2)

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

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

(3)

式中：Xbest為當(dāng)前全局最優(yōu)位置，β為一個均值是0且方差為1的符合標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)，K∈[-1,1] 是一個均勻隨機(jī)數(shù)，fi為當(dāng)前個體的適應(yīng)度值，fg和fw分別為當(dāng)前全局最好和最差的適應(yīng)度值，ε是一個最小常數(shù)以避免分母為0。

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

步驟7 判斷是否達(dá)到最大迭代次數(shù)：若是，則終止循環(huán)并輸出最優(yōu)值fMin和最優(yōu)解Xbest， 否則，回到步驟3。

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

2.1 反向?qū)W習(xí)初始化種群

反向?qū)W習(xí)作為一種智能計(jì)算中的新技術(shù)，是Tizhoosh[13]提出。其目的是基于當(dāng)前解，找出與其對應(yīng)的反向解，再通過適應(yīng)度計(jì)算選擇并保存較好的解。受周克良等[14]的啟發(fā)，通過反向?qū)W習(xí)策略初始化能有效提高種群的多樣性，避免陷入局部最優(yōu)。反向?qū)W習(xí)初始化過程如下：

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

(4)

式中：ubi,j和lbi,j分別為Xi,j對應(yīng)的第i個個體當(dāng)中第j維的上限和下限。

2.2 非線性權(quán)重因子

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

λ=(t/itermax)2

(5)

此時對發(fā)現(xiàn)者位置更新式(1)進(jìn)行簡化和改進(jìn)為

(6)

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

(7)

2.3 融入差分進(jìn)化和精英策略

2.3.1 DE算法

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

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

變異操作：在第k次迭代時，隨機(jī)從種群中選擇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(xiàn)∈[0,2] 是縮放因子用于控制變異的概率，通常取0.5。

交叉操作：針對目標(biāo)個體Yr,k和變異個體Vr,k進(jìn)行交叉操作，通過式(9)產(chǎn)生新的交叉?zhèn)€體Ur,k

(9)

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

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

(10)

2.3.2 精英策略

為了提升算法局部的尋優(yōu)能力，引入精英策略在第t次迭代后得到的當(dāng)前最優(yōu)解best附近產(chǎn)生符合正態(tài)分布的隨機(jī)數(shù)，公式如式(11)

(11)

2.4 DEH-SSA算法描述

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

圖1 改進(jìn)算法流程

3 仿真實(shí)驗(yàn)結(jié)果與分析

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

(1)把DEH-SSA與反向?qū)W習(xí)和非線性權(quán)重因子改進(jìn)得來的SSA1、融合差分進(jìn)化和精英策略的SSA2做實(shí)驗(yàn)比較，驗(yàn)證不同策略的有效性。

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

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

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

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

3.1 與不同策略比較

通過將DEH-SSA與反向?qū)W習(xí)和非線性權(quán)重因子改進(jìn)得來的SSA1、融合差分進(jìn)化和精英策略的SSA2在表1的10個測試函數(shù)求解下作比較，進(jìn)一步地驗(yàn)證不同改進(jìn)策略的有效性。實(shí)驗(yàn)結(jié)果見表2，各策略算法獨(dú)立運(yùn)行30次后的平均收斂曲線如圖2所示。

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

表1 測試函數(shù)說明

表2 DEH-SSA與SSA、SSA1、SSA2結(jié)果分析

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

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

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

3.2 與GWO、GSA和SSA比較

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

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

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

從結(jié)果與算法設(shè)計(jì)的關(guān)系角度分析，F(xiàn)1～F5是高維的單峰函數(shù)，當(dāng)中以F3最為典型且智能算法很難處理，因?yàn)樗匦允欠峭骨也B(tài)的單峰函數(shù)，主要測試算法的收斂速度和精度，從表1它的取值范圍上結(jié)合圖3中F3走勢看出，極小可能會收斂到全局最優(yōu)，由于非線性權(quán)重因子具有能夠平衡算法的局部和全局搜索能力，同時改善算法的收斂速度，而差分進(jìn)化能夠提升算法的收斂精度和開發(fā)能力，因此引入非線性權(quán)重因子和差分進(jìn)化使得DEH-SSA的收斂精度和速度都明顯優(yōu)于了其它算法。F6～F10為非線性多峰函數(shù)，有著許多局部極值點(diǎn)，主要是測試算法跳出局部的能力以及全局搜索的能力，從表3和圖3得出DEH-SSA也明顯優(yōu)于其它算法，這是因?yàn)榉聪驅(qū)W習(xí)初始化能夠改善算法跳出局部最優(yōu)的能力和非線性權(quán)重因子能夠加快算法收斂速度，差分進(jìn)化和精英策略更重于提升算法全局尋優(yōu)能力以及跳出局部的能力。

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

3.3 Wilcoxon秩和檢驗(yàn)

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

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

4 結(jié)束語

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

表3 DEH-SSA與GWO、GSA、SSA結(jié)果分析

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

表4 Wilcoxon 秩和檢驗(yàn)的p值

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