改進搜索機制的單純形法引導(dǎo)麻雀搜索算法*

劉成漢，何 慶

(貴州大學大數(shù)據(jù)與信息工程學院，貴州 貴陽 550025)

1 引言

20世紀90年代以來，群智能優(yōu)化算法憑借其簡單的結(jié)構(gòu)和優(yōu)秀的求解性能被研究人員廣泛關(guān)注。隨著研究的不斷深入，各種優(yōu)秀的群智能優(yōu)化算法被相繼提出，例如：粒子群優(yōu)化PSO(Particle Swarm Optimization)算法[1]、灰狼優(yōu)化GWO(Grey Wolf Optimization)算法[2]、鯨魚優(yōu)化算法WOA(Whale Optimization Algorithm)[3]、禿鷹搜索BES(Bald Eagle Search)算法[4]、蜉蝣算法MA(Mayfly Algorithm)[5]和黏菌算法SMA(Slime Mould Algorithm)[6]等。這些智能算法已被成功應(yīng)用于路徑規(guī)劃[7]、圖像分割[8]和神經(jīng)網(wǎng)絡(luò)優(yōu)化[9]等多種優(yōu)化問題上。

麻雀搜索算法SSA(Sparrow Search Algorithm)[10]是由薛建凱于2020年提出的一種新型群智能優(yōu)化算法。SSA是基于自然界麻雀種群的捕食行為和偵察機制提出的，具有參數(shù)少、尋優(yōu)性能強等優(yōu)點。然而，群智能算法普遍存在收斂速度慢、精度低和易早熟收斂的問題，SSA也不例外。因此，針對上述問題，許多研究人員對SSA做出了改進，例如：呂鑫等人[11]提出了一種混沌麻雀優(yōu)化算法，采用混沌序列初始化種群并對陷入局部最優(yōu)個體進行混沌擾動，從而提高了算法搜索能力；毛清華等人[12]在SSA中引入正弦余弦算法和萊維飛行相關(guān)思想更新種群位置，平衡了算法的局部搜索能力和全局開發(fā)能力；Ouyang等人[13]使用K-means聚類方法對麻雀的個體位置進行聚類和區(qū)分，提高了算法的穩(wěn)定性和魯棒性；Zhu等人[14]提出了一種自適應(yīng)麻雀搜索算法，通過引入自適應(yīng)學習因子提高了SSA的收斂速度；Yuan等人[15]利用重心反向?qū)W習策略初始化SSA種群并引入變異算子更新加入者位置，提高了算法搜索效率。雖然上述改進策略在一定程度上改善了SSA的尋優(yōu)能力，但SSA仍存在收斂慢和易陷入局部最優(yōu)的問題。

針對SSA的局限性，本文提出了一種改進搜索機制的單純形法引導(dǎo)麻雀搜索算法SMSSA(Simplex Method guided with improved search mechanism Sparrow Search Algorithm),分別對麻雀種群中發(fā)現(xiàn)者的搜索機制和偵察者的偵察機制進行改進，同時引入單純形法對算法每次迭代中適應(yīng)度較差的部分個體進行收縮、擴張和壓縮操作，以提高算法性能。最后通過8個基準函數(shù)、Wilcoxon秩和檢測以及部分CEC2014測試函數(shù)的仿真實驗，驗證了本文改進算法的有效性。

2 麻雀搜索算法

SSA的靈感來源于自然界中麻雀種群的捕食和偵察預(yù)警行為。一個麻雀種群中存在發(fā)現(xiàn)者、加入者和偵察者3種個體。發(fā)現(xiàn)者在搜索空間中擁有較好的位置并帶領(lǐng)其它發(fā)現(xiàn)者覓食。偵察者隨機產(chǎn)生，負責偵察預(yù)警。算法起源于一個由n只麻雀組成的種群X，X由式(1)所示的矩陣所示：

(1)

其中，D表示問題維度，n表示種群數(shù)量,X中每一行表示一只麻雀的位置向量。

在一個麻雀種群中，發(fā)現(xiàn)者通常有很高的能量儲備，能為其他搜尋者提供覓食區(qū)域或方向[10]。發(fā)現(xiàn)者位置更新數(shù)學模型如式(2)所示：

(2)

加入者在發(fā)現(xiàn)者的帶領(lǐng)下進行覓食，加入者具備搶奪發(fā)現(xiàn)者食物從而改變身份成為發(fā)現(xiàn)者的能力，同時部分未獲得食物的加入者飛往其他區(qū)域覓食。加入者位置更新數(shù)學模型如式(3)所示：

(3)

偵察者大約占種群總數(shù)的10%～20%，它們在種群中隨機產(chǎn)生，負責預(yù)警危險。偵察者位置更新數(shù)學模型如式(4)所示：

(4)

其中，Xbest為全局最優(yōu)位置;β控制步長，是服從正態(tài)分布的隨機數(shù);K是[-1,1]的隨機數(shù);fi、fg和fw分別表示當前個體適應(yīng)度值、當前全局最佳適應(yīng)度值和最差適應(yīng)度值;ε為常數(shù)，作用是防止出現(xiàn)分母為零的情況。

3 改進麻雀搜索算法

3.1 改進發(fā)現(xiàn)者搜索機制

發(fā)現(xiàn)者負責搜索具有豐富食物的區(qū)域，并為其它個體提供搜索方向，是整個種群運作的核心，因此發(fā)現(xiàn)者的搜索能力對整個算法的收斂起著重要作用。由式(2)可知，當搜索范圍內(nèi)沒有出現(xiàn)捕食者時，發(fā)現(xiàn)者的位置更新算子存在一定的隨機性，這種隨機性可能會導(dǎo)致算法穩(wěn)定性降低，收斂速度變慢。針對上述問題，本文改進了SSA的發(fā)現(xiàn)者搜索機制，改進后的發(fā)現(xiàn)者位置更新數(shù)學模型如式(5)所示：

(5)

其中，k為調(diào)節(jié)因子，通過k值可以自適應(yīng)調(diào)節(jié)發(fā)現(xiàn)者位置更新算子下降速率，k值越大，算子下降速率越大。

由式(5)可知，改進的位置更新公式中引入了迭代次數(shù)t，使發(fā)現(xiàn)者位置更新算子隨迭代次數(shù)增加呈非線性變化，增加了算法的多樣性；同時，結(jié)合調(diào)節(jié)因子k，可自適應(yīng)調(diào)節(jié)位置更新算子的下降速率，平衡了算法的搜索能力；最后，發(fā)現(xiàn)者位置更新脫離了隨機因子α的影響，算法更加穩(wěn)定。

3.2 改進偵察機制

在原始SSA中，當偵察者預(yù)警到危險(即意識到有陷入局部極值的風險)時，對于處于種群中心的偵察者，SSA選擇讓其靠近鄰居以減少被捕食的風險，這樣會導(dǎo)致算法陷入局部最優(yōu)值而停止搜索；對于處在種群邊緣的偵察者，SSA利用隨機步長控制偵察者向安全區(qū)域靠近，而這種隨機步長可能會導(dǎo)致算法收斂速度變慢。

針對SSA偵察機制中存在的局限性，本文通過引入新的偵察因子來改進SSA的偵察機制。對于處于種群中心的偵察者，通過非線性遞增的偵察因子Ф1使其逐步遠離當前位置，防止算法陷入局部最優(yōu)值；對于處在種群邊緣的偵察者，采用非線性遞減的偵察因子Ф2代替隨機步長因子，在保證偵察者安全的同時使其逐步靠近最優(yōu)位置，加快算法收斂。Ф1和Ф2的數(shù)學模型如式(6)所示：

(6)

其中，Фs和Фl分別表示偵察因子的初始值和最終值，Tmax為最大迭代次數(shù)，μ為非線性調(diào)節(jié)系數(shù)。

3.3 單純形法策略

單純形法在多維優(yōu)化問題中表現(xiàn)出色，具有魯棒性高、局部優(yōu)化能力強和參數(shù)簡單等優(yōu)點[16]。單純形法通過對適應(yīng)度較差的個體進行反射、擴張、壓縮和收縮的操作來改變個體位置，其中反射操作能使個體反方向搜索，擴大個體搜索空間；擴張操作使個體遠離最優(yōu)解，防止算法陷入局部極小值點；壓縮和收縮操作能使個體更加接近最優(yōu)位置。其具體實現(xiàn)步驟如下所示：

Step1初始化種群，計算個體適應(yīng)度值并排序，記錄全局最優(yōu)個體位置Xb和次優(yōu)個體位置Xt以及它們的適應(yīng)度值fb和ft，Xc定義為Xc=(Xb+Xt)/2。

Step2對m個位置較差的點w進行反射操作，Xr=Xc+α(Xc-Xw)，其中α表示反射系數(shù)。

Step3判斷，如果fr

Step4判斷，如果fr

Step5判斷，如果fw>fr>ft，則進行收縮操作，Xs=Xc-σ(Xw-Xc)，σ為收縮系數(shù)，且σ=γ；如果fs

為了改善SSA求解速度慢、精度不高的問題，本文算法在每次迭代結(jié)束時，對位置較差的m個麻雀個體進行單純形法操作，以增強SSA的搜索能力。

3.4 SMSSA實現(xiàn)步驟

SMSSA實現(xiàn)步驟如下所示：

步驟1初始化種群和SMSSA參數(shù)：Tmax為最大迭代次數(shù)，n為種群規(guī)模，ub和lb為搜索上下界，D為維度，P為發(fā)現(xiàn)者比例。

步驟2計算個體適應(yīng)度值并排序，記錄最優(yōu)、次優(yōu)和最差適應(yīng)度個體位置：Xb、Xt和Xw，及它們的適應(yīng)度值fb、ft和fw。

步驟3根據(jù)式(5)更新發(fā)現(xiàn)者位置。

步驟4根據(jù)式(3)更新加入者位置。

步驟5根據(jù)式(6)更新偵察者位置。

步驟6定義Xc=(Xb+Xt)/2，對m個位置較差的個體w進行反射操作，Xr=Xc+α(Xc-Xw)，反射個體適應(yīng)度值為fr。

步驟7根據(jù)單純形法判斷fr、fb、fw和ft之間大小關(guān)系，然后決定對適應(yīng)度最差的m個個體行執(zhí)行擴張、壓縮或伸縮操作。

步驟8循環(huán)執(zhí)行步驟2～步驟7，判斷是否滿足迭代條件，滿足則跳出循環(huán)。

步驟9算法結(jié)束，返回最優(yōu)位置及其適應(yīng)度值。

4 仿真實驗及結(jié)果分析

4.1 參數(shù)設(shè)置說明

本文仿真實驗采用的計算機配置為：Intel Core i5-7500U，32 GB內(nèi)存，64 bit操作系統(tǒng)，計算環(huán)境為Matlab2016(a)。為了檢驗SMSSA的性能，本文選取PSO算法、GWO算法、WOA和SSA與SMSSA進行對比，基本參數(shù)設(shè)置為：最大迭代次數(shù)Tmax=500，種群規(guī)模n=30，維度D=200,500,1000，各算法內(nèi)部參數(shù)設(shè)置如表1所示。

Table 1 Parameters setting

表1中，SSA的參數(shù)P為發(fā)現(xiàn)者所占比例；PSO算法的參數(shù)c1和c2為粒子的學習因子，wmax和wmin分別為慣性因子的最大值和最小值；WOA的參數(shù)b為常數(shù)，用來定義鯨魚優(yōu)化算法螺旋更新位置時螺旋的形狀；SMSSA的相關(guān)參數(shù)介紹見第3節(jié)。

4.2 基準測試函數(shù)說明

為了測試SMSSA在基準函數(shù)上的尋優(yōu)效果，本文采用了8個基準測試函數(shù)進行仿真實驗，其中f1～f5為單峰測試函數(shù)，f6～f8為復(fù)雜多峰測試函數(shù)。測試函數(shù)基本信息如表2所示。

Table 2 Introduction of benchmark functions

4.3 與其他改進SSA性能對比

為了驗證SMSSA中改進策略的優(yōu)越性，本文還將SMSSA與基本SSA、CSSA(a Chaotic Sparrow Search optimization Algorithm)、SASSA、ISSA(an Improved Sprrow Search Algorithm combining cauchy variation and reverse learning)進行基準測試函數(shù)尋優(yōu)實驗對比。其中,CSSA為混沌麻雀搜索算法[11]，SASSA為融合K-means的多策略改進麻雀搜索算法[13]，ISSA為混合正弦余弦算法和Lévy飛行的麻雀算法[12]。仿真實驗維度D=30，種群規(guī)模n=30，最大迭代次數(shù)Tmax=500，其中CSSA的最大迭代次數(shù)為100次，SSA和SMSSA內(nèi)部參數(shù)已由表1給出。每個函數(shù)進行30次后求平均值和標準差，實驗結(jié)果如表3所示。

從表3對比結(jié)果可知，對于單峰測試函數(shù)f1～f4以及多峰測試函數(shù)f6和f7，SMSSA能夠收斂到理論上的最優(yōu)值0；對于復(fù)雜多峰測試函數(shù)f8，原始SSA陷入了局部最優(yōu)值，而SMSSA能夠跳出局部極值，并收斂到接近理論最優(yōu)值；對于單峰測試函數(shù)f5，雖然SMSSA沒有收斂到0，但是相比于其他SSA和SSA變體，其收斂精度有一定提升；雖然CSSA迭代次數(shù)只有100次，但是SMSSA在迭代100次時的結(jié)果也優(yōu)于CSSA的，對于f1函數(shù)，SMSSA在迭代100次時收斂精度比CSSA高48個數(shù)量級，在相同參數(shù)設(shè)置下，SMSSA對于其他函數(shù)尋優(yōu)的收斂精度也都高于CSSA。上述分析表明，本文提出的SMSSA相較于其他SSA變體具有明顯優(yōu)勢。

Table 3 Performance comparison of the improved algorithms

Figure 1 Comparison of the average convergence curves of the optimization algorithms on 200 dimensional benchmark functions

4.4 各算法高維尋優(yōu)性能對比

為了驗證SMSSA在面對高維問題時的求解能力，仿真實驗將PSO算法、GWO算法、WOA和SSA與SMSSA進行高維基準函數(shù)尋優(yōu)性能對比，參數(shù)統(tǒng)一設(shè)置為:種群規(guī)模n=30，最大迭代次數(shù)Tmax=500，維度D=200，各算法相關(guān)參數(shù)參考表1。對于200維基準測試函數(shù)，各函數(shù)獨立運行30次的平均收斂曲線如圖1所示。

從圖1可以看出，SMSSA在高維函數(shù)的優(yōu)化上有很大優(yōu)勢，相比于其他優(yōu)化算法，SMSSA不管是在收斂速度和精度上還是在跳出局部最優(yōu)的能力上都有很大提升。對于單峰測試函數(shù)f1～f4，SMSSA在200維時仍然能夠找到理論全局最優(yōu)解，這說明本文提出的改進發(fā)現(xiàn)者搜索機制能夠提高算法的收斂精度；對于復(fù)雜多峰測試函數(shù)f6和f7，SMSSA能在50次迭代以內(nèi)找到最優(yōu)值，比SSA和WOA收斂更快，這說明本文引入的單純形法操作能加快算法收斂，提高算法搜索能力；對于單峰測試函數(shù)f5和多峰測試函數(shù)f8，SMSSA能夠跳出局部極小值干擾，收斂到更接近于理論最優(yōu)值，這說明改進的偵察機制對于提高算法跳出局部最小值的能力有一定幫助。

4.5 SMSSA超高維尋優(yōu)測試

上節(jié)給出了SMSSA在200維基準測試函數(shù)上的尋優(yōu)對比測試，SMSSA表現(xiàn)良好。本節(jié)對SMSSA進行超高維基準函數(shù)尋優(yōu)實驗，參數(shù)統(tǒng)一設(shè)置為：維度D=500,1000，種群規(guī)模n=30，最大迭代次數(shù)Tmax=500，選取PSO算法、GWO算法、WOA和SSA與SMSSA進行超高維基準函數(shù)尋優(yōu)性能對比，各算法相關(guān)參數(shù)參考表1，實驗結(jié)果如表4所示。

從表4可以看出，當維度達到500維時，PSO算法、GWO算法、WOA和SSA的尋優(yōu)收斂結(jié)果出現(xiàn)指數(shù)級增加；SSA在基準測試函數(shù)的尋優(yōu)上，與30維度時的尋優(yōu)結(jié)果相差10個數(shù)量級，基本失去尋優(yōu)能力；GWO算法、WOA和SSA在基準測試函數(shù)的尋優(yōu)上也均有多個指數(shù)量級的出入；對于500維和1 000維單峰測試函數(shù)f1～f4和多峰測試函數(shù)f6、f7，SMSSA仍然能夠收斂到理論最優(yōu)值；對于測試函數(shù)f5和f8，SMSSA收斂精度也優(yōu)于其他對比算法。這說明SMSSA對于超高維問題的優(yōu)化同樣具有較好的穩(wěn)定性和魯棒性。

Table 4 Performance comparison of the optimization algorithms on ultra-high dimensional benchmark functions

4.6 Wilcoxon秩和檢測

為了進一步驗證SMSSA的優(yōu)化性能，本文采用Wilcoxon秩和非參數(shù)統(tǒng)計檢驗方法檢驗SMSSA與SSA、PSO算法、GWO算法、WOA、SSA1、SSA2和SSA3之間在統(tǒng)計上存在的顯著差異，其中SSA1、SSA2和SSA3是SSA的變體，分別表示本文改進發(fā)現(xiàn)者搜索策略的SSA、改進偵察機制的SSA和引入單純形法的SSA。本文選取了12個基準測試函數(shù)的仿真結(jié)果進行秩和統(tǒng)計分析，假設(shè)對比數(shù)據(jù)結(jié)果優(yōu)于SMSSA的概率為p，如果p值很小，說明原假設(shè)情況的發(fā)生概率很小。當p<5%時，可以被認為是拒絕零假設(shè)的有力驗證[17]。實驗結(jié)果中，“+”表示SMSSA秩和統(tǒng)計結(jié)果優(yōu)于對比算法；“-”表示SMSSA秩和統(tǒng)計結(jié)果差于對比算法;“=”表示SMSSA秩和統(tǒng)計結(jié)果等于對比算法;沒有檢測結(jié)果用NaN表示。Wilcoxon秩和檢驗結(jié)果如表5所示。

從表5可以看出，SMSSA與其他算法的秩和統(tǒng)計對比結(jié)果中80%的p值小于5%，這說明從統(tǒng)計學上來說，SMSSA對于基準函數(shù)的尋優(yōu)結(jié)果優(yōu)勢是明顯的，從而進一步驗證了ISMA的優(yōu)越性。

4.7 CEC2014測試函數(shù)仿真對比

為了評價SMSSA對于更復(fù)雜的混合以及復(fù)合類型函數(shù)的求解能力，本文采用部分具有復(fù)雜特征的CEC2014測試函數(shù)進行仿真實驗。CEC2014測試函數(shù)相關(guān)信息見表6，其中UN表示單峰函數(shù)，MF表示多峰函數(shù),HF表示混合函數(shù),CF表示復(fù)合函數(shù)。選取基本SSA、PSO[18]、SCA[17]和L-SHADE[20]與SMSSA進行實驗對比，其中L-SHADE在CEC2014測試函數(shù)上表現(xiàn)優(yōu)秀，常被用于對比實驗。實驗參數(shù)統(tǒng)一設(shè)置為：種群規(guī)模n=50，最大迭代次數(shù)Tmax=2000，維度D=30，各函數(shù)獨立運行30次后取平均值和標準差。實驗結(jié)果如表7所示。

Table 6 Part of the CEC2014 functions

從表7可以看出，SMSSA求解復(fù)雜函數(shù)的性能總體優(yōu)于其他對比算法。雖然SMSSA在單峰CEC03函數(shù)上尋優(yōu)結(jié)果略差于L-SHADE的，但在多峰函數(shù)、混合函數(shù)和復(fù)合函數(shù)的求解上，SMSSA的求解能力遠高于L-SHADE的，對于CEC12、CEC13和CEC19測試函數(shù)，SMSSA基本能夠找到最優(yōu)值，對于多峰CEC06函數(shù)及其它復(fù)合函數(shù)，SMSSA也能收斂到最優(yōu)值附近，說明SMSSA在求解復(fù)雜問題上同樣具有很好的魯棒性。

4.8 SMSSA時間復(fù)雜度分析

設(shè)SSA的時間復(fù)雜度為O(N×Tmax×D)，其中,n為種群規(guī)模，Tmax表示最大迭代次數(shù)，D為函數(shù)維度。SMSSA的時間復(fù)雜度包括基本SSA時間復(fù)雜度、改進搜索機制的SSA時間復(fù)雜度和引入單純形法的SSA時間復(fù)雜度3個部分。由于改進發(fā)現(xiàn)者搜索機制和改進偵察機制并未對算法時間復(fù)雜度造成影響，因此改進搜索機制的SSA時間復(fù)雜度為O(n×Tmax×D),引入單純形法的SSA的時間復(fù)雜度為O(n×Tmax×D)+O(m×Tmax×D)=O(n×Tmax×D)。

由此可知，本文提出的SMSSA時間復(fù)雜度與SSA時間復(fù)雜度一致，且SMSSA算法穩(wěn)定性更高，尋優(yōu)性能遠高于SSA。

5 結(jié)束語

針對基本麻雀搜索算法存在的收斂速度慢、易陷入局部極值點的問題，本文提出了一種改進搜索機制的單純形法引導(dǎo)麻雀搜索算法(SMSSA);考慮到麻雀種群中發(fā)現(xiàn)者和偵察者在搜索中存在的局限性，本文改進了發(fā)現(xiàn)者搜索機制和偵察者偵察機制，提高了算法的搜索能力，改善了算法易早熟收斂的問題；通過引入單純形法中的反射、擴張、收縮和壓縮操作，幫助種群中位置較差的個體向較好位置移動，提高了算法的收斂速度。通過8個基準測試函數(shù)以及部分CEC2014測試函數(shù)的仿真對比實驗以及Wilcoxon秩和檢測，驗證了SMSSA的有效性。下一步工作考慮將SMSSA應(yīng)用到實際工程優(yōu)化問題中，進一步驗證SMSSA在處理實際問題時的魯棒性。

Table 7 CEC2014 function optimization comparison