基于混合策略改進(jìn)的麻雀搜索算法

胡樹斌,魏霖靜

(1.甘肅農(nóng)業(yè)大學(xué) 理學(xué)院,甘肅 蘭州 730070;2.甘肅農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院,甘肅 蘭州 730070)

0 引 言

群智能優(yōu)化算法(Intelligence Optimization Algorithm,IOA)靈感來于自然界中物理現(xiàn)象或生物群體行為,可用于求解函數(shù)最優(yōu)化問題,其方便易操作且處理問題高效,為解決某些實際應(yīng)用問題提供了新的思路。Xue等人[1]受麻雀群體覓食活動啟發(fā),于2020年提出麻雀搜索算法(SSA)。試驗表明,對比其他傳統(tǒng)優(yōu)化算法,它具有優(yōu)化能力強、易于實現(xiàn)、調(diào)節(jié)參數(shù)較少的優(yōu)勢。然而SSA算法同樣存在不足,如迭代過程中種群豐富性降低、早熟收斂、易陷入局部最優(yōu)停滯。為進(jìn)一步提升原算法的性能,呂鑫等人[2]借鑒鳥群算法思想,優(yōu)化SSA算法的發(fā)現(xiàn)者和加入者迭代方式,并將改進(jìn)算法應(yīng)用于多閾值圖像分割中,在減少分割時間的同時提升了分割精度。魏曉鴿等人[3]采用精英反向?qū)W習(xí)策略改善初始種群,發(fā)現(xiàn)者位置迭代更新引入正余弦算法及動態(tài)權(quán)重因子,最后將改進(jìn)算法用于火災(zāi)路徑規(guī)劃。付華等人[4]首先通過立方混沌序列初始化麻雀種群,然后引入透鏡成像反向策略提升初始解質(zhì)量,借鑒雞群算法優(yōu)化跟隨者位置更新方式,最后引入柯西-高斯變異策略對最優(yōu)個體進(jìn)行變異幫助算法脫離局部最優(yōu)停滯狀態(tài)。Yuan等人[5]使用重心反向?qū)W習(xí)策略改善初始種群質(zhì)量,并用學(xué)習(xí)系數(shù)改善發(fā)現(xiàn)者位置變換方式提升算法全局尋優(yōu)能力。Yan等人[6]將加入者追隨發(fā)現(xiàn)者時進(jìn)一步劃分為全局與局部搜索,并通過觀察超出邊界個體的數(shù)量變化來驗證可變螺旋因子與改進(jìn)迭代搜尋策略的有效性。Jiang等人[7]引入隨機游走策略,可有效幫助算法擺脫局部最優(yōu)狀態(tài)。Tang等人[8]借鑒遺傳算法思想,將交叉和變異思想引入SSA算法中,保障種群多樣性的同時可提升個體跳出局部最優(yōu)的概率。

上述研究中學(xué)者們從各個方面對SSA算法的缺陷加以改善,提升算法性能,不過探索更多有效的改進(jìn)策略提升算法收斂精度、全局尋優(yōu)性能仍需深入研究。基于此,該文提出了一種基于混合策略改進(jìn)的麻雀搜索算法。首先,利用精英反向?qū)W習(xí)機制改善種群迭代后期多樣性降低的問題,為算法全局尋優(yōu)奠定基礎(chǔ);然后,在發(fā)現(xiàn)者位置采用黃金正弦策略改進(jìn),提升算法開發(fā)能力;最后,加入者跟隨發(fā)現(xiàn)者時融入萊維飛行步長,使搜索方向與范圍多樣化,避免算法“早熟收斂”。

1 基本麻雀搜索算法

麻雀搜索算法根據(jù)個體在覓食活動中的不同分工,將種群成員劃分為發(fā)現(xiàn)者、加入者、警戒者。發(fā)現(xiàn)者與加入者身份可動態(tài)轉(zhuǎn)換,但占群體比例不變。規(guī)模為N的麻雀種群可用矩陣表示為:

(1)

式中,N為麻雀群體的規(guī)模,d為待優(yōu)化問題的空間維度。每只麻雀表示為xi=[xi,1,xi,2,…,xi,d],適應(yīng)度值為f(xi),全部麻雀的適應(yīng)度值矩陣為Fx=[f(x1),f(x2),…,f(xN)]。

發(fā)現(xiàn)者為種群中位置較好的個體,占種群比例為10%～20%,負(fù)責(zé)尋找食物。

其位置更新如下:

(2)

式中,t是當(dāng)前迭代次數(shù);Max-iter為最大迭代次數(shù);α∈(0,1)為隨機數(shù),隨機數(shù)Q服從正態(tài)分布;L是元素取值均為1的1×d矩陣。R2∈[0,1]為預(yù)警值;ST∈[0.5,1]是安全閾值。

當(dāng)R2

加入者通過監(jiān)視發(fā)現(xiàn)者的行為覓食,適應(yīng)度值較高的在最佳位置的發(fā)現(xiàn)者附近搜索食物,適應(yīng)度較低的則移動到空間其他位置。加入者位置更新如下:

(3)

警戒者數(shù)量占種群總數(shù)的10%～20%,隨機在發(fā)現(xiàn)者和加入者中選取,負(fù)責(zé)偵察警戒,初始位置更新公式為:

(4)

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

該文混合三種有效策略改善SSA算法迭代時種群豐富性降低、早熟收斂、難以脫離局部最優(yōu)現(xiàn)象,具體策略如下。

2.1 精英反向?qū)W習(xí)機制

反向?qū)W習(xí)機制[9]靠近最優(yōu)解的概率可提升50%,在可行解及其反向解中選擇更優(yōu)的個體作為新種群是其核心思想。精英反向?qū)W習(xí)(Elite Opposition-Based Learning,EOBL)則是在此基礎(chǔ)上只針對種群精英個體構(gòu)造反向種群。精英個體攜帶更多有效信息,相比較普通反向?qū)W習(xí)既提高了種群質(zhì)量,又提升了搜索效率,有效地使種群避免尋優(yōu)時掉入局部最優(yōu)陷阱。

定義1(精英反向解)。

(5)

(6)

該文采用精英反向?qū)W習(xí)策略對初始種群以及迭代后期種群精英個體計算反向解時,根據(jù)式(5)計算種群適應(yīng)度排名前N/2個體的反向解,將反向種群與原種群依據(jù)個體適應(yīng)度排序,挑選最優(yōu)的N個精英個體組成下一代尋優(yōu)種群。該策略可有效避免算法盲目搜索而降低求解效率,為提升求解精度、加快收斂速度奠定基礎(chǔ)。

2.2 黃金正弦機制

黃金正弦算法(Golden Sine Algorithm,Golden-SA)是Tanyildizi 等人[10]結(jié)合正弦函數(shù)原理在2017年提出,其原理簡單、易于操作、收斂性能好。最大特點是可遍歷單位圓上全部正弦值,其中黃金分割系數(shù)可幫助個體在迭代過程中極大程度縮小解空間,并進(jìn)行充分尋優(yōu),提升了算法求解速度,更有效平衡了算法全局“搜索”與“開發(fā)”。

Golden-SA的核心是位置迭代方式,數(shù)學(xué)描述如下:

(7)

觀察SSA算法式(2)可知,發(fā)現(xiàn)者在迭代初期就快速向全局最優(yōu)靠近,容易造成早熟收斂現(xiàn)象,且相互之間缺乏足夠的交流,難以對優(yōu)質(zhì)解空間全面探索。針對此不足,引入黃金正弦機制改善發(fā)現(xiàn)者探索方式,改進(jìn)后更新方式描述如下:

(8)

2.3 萊維飛行機制

萊維飛行[11]是對自然界中昆蟲與鳥類覓食路徑隨機游走過程的模擬,其以大概率短距離搜索與小概率長距離搜索的方式交錯移動,產(chǎn)生服從重尾分布的隨機步長[12]。萊維飛行步長較大時可適當(dāng)擴大搜索范圍,較小時可提升算法局部尋優(yōu)能力,其多樣變化的特性使個體在空間內(nèi)搜索更加全面。

觀察SSA算法式(3)可知,發(fā)現(xiàn)者找到食物時,距離近的加入者會迅速靠近,算法得以快速收斂,但也因此造成短時間內(nèi)麻雀在局部空間大量聚集,種群多樣性降低,增大了算法“早熟收斂”的風(fēng)險。因此,該文在加入者位置更新中加入萊維飛行隨機步長step,可以對與最優(yōu)位置之間的空間全面搜索,最大限度降低算法陷入局部最優(yōu)陷阱的風(fēng)險。萊維飛行產(chǎn)生的隨機步長為:

(9)

(10)

式中,Γ為標(biāo)準(zhǔn)伽瑪函數(shù);β1為固定步長,一般取值為1.5;συ、σμ為正態(tài)分布中的標(biāo)準(zhǔn)差。式(3)引入萊維飛行隨機步長step后改進(jìn)為:

(11)

3 EGSSA算法

3.1 EGSSA算法步驟

(1)參數(shù)設(shè)置。種群規(guī)模N、最大迭代次數(shù)Max-iter、發(fā)現(xiàn)者比例PD、警戒者比例SD、空間維度d、安全閾值ST;

(2)初始化種群。對麻雀種群隨機初始化,根據(jù)目標(biāo)函數(shù)計算麻雀個體的適應(yīng)度值并排序;

(3)計算精英反向解。選取種群排名前N/2的麻雀個體根據(jù)式(5)求解反向種群,根據(jù)式(6)對超過邊界的個體進(jìn)行重置,計算反向種群適應(yīng)度值;

(4)從當(dāng)前種群和反向種群中選取適應(yīng)度值排名前N的個體組成新一代種群并依據(jù)個體適應(yīng)度排序,找到新一代種群中最差和最優(yōu)適應(yīng)度值:fworst、fbest,以及對應(yīng)的麻雀個體位置Xworst、Xbest;

(5)根據(jù)公式(8)更新發(fā)現(xiàn)者位置;

(6)根據(jù)公式(11)更新加入者位置;

(7)根據(jù)公式(4)更新警戒者位置;

(8)判斷結(jié)束條件,若迭代次數(shù)滿足t>Max-iter,則終止操作,輸出全局最優(yōu)位置及最優(yōu)解,否則跳轉(zhuǎn)步驟(3)繼續(xù)執(zhí)行。

3.2 EGSSA算法偽代碼

設(shè)置相關(guān)參數(shù):種群規(guī)模N、最大迭代次數(shù)Max-iter、發(fā)現(xiàn)者比例PD、警戒者比例SD、空間維度d、安全閾值ST;

初始化種群,計算個體適應(yīng)度值并排序

t=1

Whilet

foriin range(0,N/2):

forjin range(0,d):

根據(jù)公式(5)計算反向解

計算適應(yīng)度值

檢查是否超過邊界,若超過,根據(jù)公式(6)重置

從當(dāng)前種群和反向種群選取適應(yīng)度值前N的個體組成新一代種群

對新種群按適應(yīng)度值排序,記錄最優(yōu)、最差個體位置及適應(yīng)度

隨機取值R2并判斷與ST關(guān)系:

foriin range(0,pNum):

根據(jù)公式(8)更新發(fā)現(xiàn)者位置

foriin range(pNum+1,N):

根據(jù)公式(11)更新加入者位置

foriin range(0,N*SD):

根據(jù)公式(4)更新警戒者位置

計算適應(yīng)度值并更新最優(yōu)個體適應(yīng)度值及最優(yōu)位置

返回最優(yōu)位置及適應(yīng)度值

ift% 1 == 0:

print('在第t代,種群最優(yōu)適應(yīng)度值為:fbest')

t=t+1

3.3 EGSSA時間復(fù)雜度分析

時間復(fù)雜度[13]是反映算法性能的一個重要指標(biāo)。假定麻雀種群規(guī)模為N,空間維度為d,求解目標(biāo)函數(shù)所需的時間為f(d)。根據(jù)文獻(xiàn)[14],SSA算法的時間復(fù)雜度為T=O(d+f(d))。在EGSSA算法中,參數(shù)初始化的時間為η0,種群初始化的時間為η1,按式(5)生成反向種群所需時間為η2,則麻雀種群初始化階段的時間復(fù)雜度為:

T1=O(η0+N(f(d)+d(η1+η2)))=

O(d+f(d))

(12)

對上一代種群求精英反向解階段,按式(5)更新麻雀精英個體所需的時間為η3,生成隨機變量k∈[0,1]所需的時間為η4,對兩個種群排序所需時間為η5,在這一階段的時間復(fù)雜度為:

T2=O(N/2×((η3+η4)d+f(d))+η5)=

O(d+f(d))

(13)

麻雀種群中發(fā)現(xiàn)者數(shù)量為PD×N,PD為發(fā)現(xiàn)者比例,每一維位置按式(8)進(jìn)行更新的時間為η6,兩個隨機參數(shù)以及兩個黃金分割系數(shù)生成時間均為η7,則該階段時間復(fù)雜度為:

T3=O(PD×N((η6+4×η7)d+f(d)))=

O(d+f(d))

(14)

麻雀種群中加入者數(shù)量為(1-PD)×N,(1-PD)為加入者比例,每一維位置按式(11)進(jìn)行更新的時間為η8,生成萊維飛行隨機步長算子的時間為η9,則該階段的時間復(fù)雜度為:

T4=O((1-PD)×N((η8+η9)d+f(d)))=

O(d+f(d))

(15)

麻雀種群中警戒者數(shù)量為SD×N,SD為警戒者比例,每一維位置按式(4)進(jìn)行更新的時間為η10,兩個正態(tài)分布隨機參數(shù)更新的時間為η11,則這一階段的時間復(fù)雜度為:

T5=O(SD×N((η10+2×η11)d+f(d)))=

O(d+f(d))

(16)

最大迭代次數(shù)為Max-iter,綜上,EGSSA算法的時間復(fù)雜度為:

T'=T1+Max-iter(T2+T3+T4+T5)=

O(d+f(d))

(17)

綜上可知,EGSSA與標(biāo)準(zhǔn)SSA算法的時間復(fù)雜度在數(shù)量級上一致,該文針對標(biāo)準(zhǔn)SSA的不足所提出的改進(jìn)策略沒有增加計算負(fù)擔(dān)。

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

4.1 仿真實驗環(huán)境

仿真實驗環(huán)境為:操作系統(tǒng)Windows10(64 bit),CPU為Intel(R)Core(TM) i5-4200M,內(nèi)存12 GB,主頻2.50 GHz,仿真軟件為python3.9。

4.2 比較對象和參數(shù)設(shè)置

為驗證改進(jìn)EGSSA算法的優(yōu)越性以及可行性,將提出的EGSSA算法分別與其他經(jīng)典元啟發(fā)式算法(鯨魚優(yōu)化算法(WOA)[15]、粒子群算法(PSO)[16]、灰狼算法(GWO)[17]、飛蛾撲火算法(MFO)[18])、三種其他文獻(xiàn)所提改進(jìn)算法(自適應(yīng)變異麻雀算法(AMSSA)[19]、自適應(yīng)t分布與隨機游走麻雀算法(ARSSA)[20]、基于等級制度與布朗運動的混沌麻雀算法(CSSAHB)[21])在基準(zhǔn)函數(shù)上進(jìn)行仿真對比,通過最優(yōu)值、平均數(shù)以及標(biāo)準(zhǔn)差三個指標(biāo)的比較來檢驗所提改進(jìn)算法的求解精度與穩(wěn)定性。所選的基準(zhǔn)測試函數(shù)中F1-F5、F6-F9、F10-F12依次是單峰、多峰、低維多峰函數(shù),單峰函數(shù)用來驗證算法的開發(fā)能力,多峰函數(shù)用來檢驗算法能否脫離局部最優(yōu)。

所選基準(zhǔn)測試函數(shù)見表1。設(shè)定種群規(guī)模N=50,

表1 基準(zhǔn)測試函數(shù)

F1-F9維度d=30,Max-iter為500。為保證公平,實驗中各算法均獨立運行30次。其余各參數(shù)設(shè)置見表2。

表2 各算法參數(shù)設(shè)置

4.3 EGSSA與其他元啟發(fā)式算法對比分析

為驗證EGSSA的尋優(yōu)性能,將提出的EGSSA算法與傳統(tǒng)元啟發(fā)式算法:標(biāo)準(zhǔn)麻雀搜索算法(SSA)、鯨魚優(yōu)化算法(WOA)、粒子群算法(PSO)、灰狼算法(GWO)、飛蛾撲火算法(MFO)在12個測試函數(shù)上進(jìn)行仿真實驗,實驗維度為30,其余參數(shù)設(shè)置見表2,獨立運行30次的實驗結(jié)果見表3。

由表3的仿真實驗結(jié)果可見,在所選12個基準(zhǔn)測試函數(shù)上,EGSSA算法尋優(yōu)穩(wěn)定性和求解精度均表現(xiàn)最優(yōu),在F4函數(shù)上雖未找到最優(yōu)值,但是平均值以及標(biāo)準(zhǔn)差是所選算法中最優(yōu)的,算法收斂精度以及穩(wěn)定性更能得到保證。SSA算法在F1、F3、F4、F7、F8、F10～F12函數(shù)上雖能偶爾尋到最優(yōu)解,但較小的平均值以及較大的標(biāo)準(zhǔn)差表明算法具有強烈的不穩(wěn)定性,在低維固定維度函數(shù)F10～F12上,其他群智能算法存在與標(biāo)準(zhǔn)SSA算法同樣的問題,改進(jìn)的EGSSA算法明顯克服了這一不足,提高算法收斂精度的同時保證了算法求解的穩(wěn)定性。綜合對比實驗結(jié)果的平均值、標(biāo)準(zhǔn)差可得出,EGSSA的收斂精度更高,穩(wěn)定性更好,明顯優(yōu)于其余5種算法。

表3 與其他群智能算法實驗結(jié)果對比

為更直觀地對比EGSSA與GWO、MFO、PSO、WOA、SSA的尋優(yōu)速度和性能,圖1給出在12個測試函數(shù)上獨立運行30次的平均收斂曲線。圖中橫坐標(biāo)為迭代次數(shù),為便于比較,縱坐標(biāo)中函數(shù)值為正值的圖像作以10為底的對數(shù)處理。

圖1 不同群智能算法收斂曲線

由圖1收斂曲線可看出,EGSSA算法的收斂曲線在12個基準(zhǔn)測試函數(shù)上均表現(xiàn)更平滑,收斂速度更快。在單峰測試函數(shù)F1-F4上,EGSSA表現(xiàn)出遠(yuǎn)超于其他算法的收斂速度和求解精度(見圖1(a)-(d));在F5函數(shù)上雖未達(dá)到理論最有值,但結(jié)合收斂曲線圖實驗結(jié)果來看,EGSSA收斂速度在所有算法中最快(見圖1(e)),平均值與標(biāo)準(zhǔn)差更小;在F6-F12多峰測試函數(shù)上,EGSSA都能在迭代100次以內(nèi)快速靠近全局最優(yōu),并未像其他算法一樣陷入局部最優(yōu),與其他算法相比表現(xiàn)出明顯的優(yōu)越性(見圖1(f)-(l))。

4.4 Wilcoxon秩和檢驗

僅比較平均值和標(biāo)準(zhǔn)差并不能完全說明算法之間的差異性,為充分證明提出的EGSSA算法相比其他算法的優(yōu)越性,本節(jié)采用統(tǒng)計方法Wilcoxon秩和檢驗來驗證EGSSA算法與其他算法性能是否有顯著差異。實驗設(shè)定顯著性水平為5%。當(dāng)p<0.05時,拒絕原假設(shè),判定EGSSA與其他算法具有顯著差異;否則判定EGSSA與其他算法并無顯著差異,尋優(yōu)性能相當(dāng)。

表4為在顯著性水平5%下EGSSA與SSA、GWO、MFO、PSO、WOA之間的Wilcoxon秩和檢驗結(jié)果。

表4 Wilcoxon秩和檢驗p值

由表4數(shù)據(jù)可知,大部分p值遠(yuǎn)小于0.05,表明EGSSA在優(yōu)化性能上優(yōu)于所選傳統(tǒng)智能優(yōu)化算法。

4.5 EGSSA與其他改進(jìn)策略的SSA算法對比分析

為進(jìn)一步驗證所提算法具有優(yōu)越性能,本節(jié)將EGSSA算法與文獻(xiàn)[19]提出的自適應(yīng)變異麻雀算法(AMSSA)、文獻(xiàn)[20]提出的自適應(yīng)t分布與隨機游走麻雀算法(ARSSA)、文獻(xiàn)[21]提出的基于等級制度與布朗運動的混沌麻雀算法(CSSAHB)進(jìn)行對比分析。測試函數(shù)選取表1中F1-F8,其中F1-F6迭代次數(shù)為1 000,F7、F8兩個函數(shù)迭代次數(shù)依舊為500。種群規(guī)模N=50,實驗維度為30,各算法在測試函數(shù)上獨立運行30次,其余參數(shù)設(shè)置見表2。為保證實驗對比公平合理性,對比的三種改進(jìn)算法實驗結(jié)果與文獻(xiàn)[20]數(shù)據(jù)結(jié)果相同,對比結(jié)果見表5。

表5 不同改進(jìn)算法實驗結(jié)果對比

由表5可知,對于函數(shù)F3、F7、F8所有改進(jìn)算法均尋到理論最優(yōu)值,且標(biāo)準(zhǔn)差為0;EGSSA算法在函數(shù)F5上各項指標(biāo)略差于其他三種改進(jìn)算法,在其余函數(shù)上,EGSSA算法尋優(yōu)精度及穩(wěn)定性均優(yōu)于AMSSA算法;對于函數(shù)F2和F4,EGSSA算法可以穩(wěn)定收斂到理論最優(yōu),而其他算法僅ARSSA算法在F2函數(shù)上尋到最優(yōu)值;四種算法在函數(shù)F6上均未穩(wěn)定收斂到最優(yōu)值,但是EGSSA算法的平均值和標(biāo)準(zhǔn)差兩個指標(biāo)均優(yōu)于其他三種算法。綜上,融合精英反向?qū)W習(xí)與黃金正弦的麻雀搜索算法尋優(yōu)能力更強、穩(wěn)定性更好,與其他策略改進(jìn)算法相比同樣具有一定的競爭優(yōu)勢。

5 結(jié)束語

針對標(biāo)準(zhǔn)SSA算法迭代后期種群多樣性減少、早熟收斂等不足,提出一種基于混合策略改進(jìn)的麻雀搜索算法。在迭代過程中融入精英反向?qū)W習(xí)機制,豐富種群多樣性,提高種群質(zhì)量,提升算法搜索效率和收斂精度;在發(fā)現(xiàn)者搜索時采用黃金正弦策略,有效協(xié)調(diào)算法搜索能力和開發(fā)能力;最后在加入者靠近發(fā)現(xiàn)者時引入萊維飛行步長,增加個體位置變化多樣性,有助于跳出局部最優(yōu),避免算法“早熟收斂”。選擇單峰、多峰、固定維度多峰12個基準(zhǔn)測試函數(shù)進(jìn)行仿真實驗,對比經(jīng)典元啟發(fā)式算法、其他改進(jìn)算法尋優(yōu)性能。研究結(jié)果表明,所提改進(jìn)算法具有更好的收斂性能、全局尋優(yōu)性能以及穩(wěn)定性。