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

劉成漢，何 慶

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

1 引言

20世紀(jì)90年代以來(lái)，群智能優(yōu)化算法憑借其簡(jiǎn)單的結(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ú)優(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)化問(wèn)題上。

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

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

2 麻雀搜索算法

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

(1)

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

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

(2)

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

(3)

偵察者大約占種群總數(shù)的10%～20%，它們?cè)诜N群中隨機(jī)產(chǎn)生，負(fù)責(zé)預(yù)警危險(xiǎn)。偵察者位置更新數(shù)學(xué)模型如式(4)所示：

(4)

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

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

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

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

(5)

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

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

3.2 改進(jìn)偵察機(jī)制

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

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

(6)

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

3.3 單純形法策略

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

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

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

Step3判斷，如果fr

Step4判斷，如果fr

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

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

3.4 SMSSA實(shí)現(xiàn)步驟

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

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

步驟2計(jì)算個(gè)體適應(yīng)度值并排序，記錄最優(yōu)、次優(yōu)和最差適應(yīng)度個(gè)體位置：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，對(duì)m個(gè)位置較差的個(gè)體w進(jìn)行反射操作，Xr=Xc+α(Xc-Xw)，反射個(gè)體適應(yīng)度值為fr。

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

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

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

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

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

本文仿真實(shí)驗(yàn)采用的計(jì)算機(jī)配置為：Intel Core i5-7500U，32 GB內(nèi)存，64 bit操作系統(tǒng)，計(jì)算環(huán)境為Matlab2016(a)。為了檢驗(yàn)SMSSA的性能，本文選取PSO算法、GWO算法、WOA和SSA與SMSSA進(jìn)行對(duì)比，基本參數(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為粒子的學(xué)習(xí)因子，wmax和wmin分別為慣性因子的最大值和最小值；WOA的參數(shù)b為常數(shù)，用來(lái)定義鯨魚(yú)優(yōu)化算法螺旋更新位置時(shí)螺旋的形狀；SMSSA的相關(guān)參數(shù)介紹見(jiàn)第3節(jié)。

4.2 基準(zhǔn)測(cè)試函數(shù)說(shuō)明

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

Table 2 Introduction of benchmark functions

4.3 與其他改進(jìn)SSA性能對(duì)比

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

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

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)性能對(duì)比

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

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

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

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

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

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

4.6 Wilcoxon秩和檢測(cè)

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

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

4.7 CEC2014測(cè)試函數(shù)仿真對(duì)比

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

Table 6 Part of the CEC2014 functions

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

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

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

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

5 結(jié)束語(yǔ)

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

Table 7 CEC2014 function optimization comparison