基于反向策略的混沌麻雀搜索算法

錢(qián) 敏，黃海松，范青松

(貴州大學(xué)現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽(yáng) 550025)

1 引言

近期，群體智能(Swarm Intelligence，SI)優(yōu)化算法備受學(xué)者的關(guān)注，如Kennedy等人[1]模擬自然界中鳥(niǎo)群捕食行為，研究種群覓食的搜索機(jī)制從而提出了一種全局尋優(yōu)的粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)；Suash Deb等人[2]模擬布谷鳥(niǎo)獨(dú)特的寄生行為，運(yùn)用與其它鳥(niǎo)類(lèi)相似的飛行搜索策略，從而提出了一種布谷鳥(niǎo)搜索算法(Cuckoo Search Via Lévy Flights，CS)；Seyedali Mirjalili等人[3]模擬狼群中的頭狼引導(dǎo)群體捕食的社會(huì)行為進(jìn)行數(shù)學(xué)建模，從而提出了一種灰狼算法(Grey Wolf Optimizer，GWO)。此外，根據(jù)鯨魚(yú)自身的泡泡網(wǎng)覓食方法進(jìn)行食物的搜索，與改進(jìn)螺旋方式進(jìn)行位置的更新，而提出了一種鯨魚(yú)優(yōu)化算法[4](Whale Optimization Algorithm，WOA)。由于SI算法參數(shù)僅存在少數(shù)需要調(diào)整、易于實(shí)現(xiàn)且操作難度低，所以在各個(gè)領(lǐng)域應(yīng)用廣泛[5-8]。

無(wú)免費(fèi)午餐定理(No Free Lunch，NFL)[9]表明任何一種算法只能解決一部分問(wèn)題而不能優(yōu)化工程實(shí)際中存在的所有問(wèn)題，因而不斷有學(xué)者提出改進(jìn)的SI算法。如劉雪紅等人[10]提出一種可行領(lǐng)域結(jié)構(gòu)與精英分批兩種策略對(duì)候鳥(niǎo)算法進(jìn)行改進(jìn)，有效提高了算法全局搜索效率(Improved Migrating Birds Optimization，IMBO)：張文勝等人[11]提出一種自適應(yīng)遞減的收斂因子，并在灰狼位置更新公式引入慣性權(quán)重從而協(xié)調(diào)算法的全局領(lǐng)導(dǎo)與開(kāi)發(fā)能力(Transformed Grey Wolf Optimizer Algorithm，TGWO)；王樂(lè)洋等人[12]通過(guò)采用分段慣性因子調(diào)整粒子速度，修改局部和全局最優(yōu)解的加速因子從而降低算法后期陷入局部最優(yōu)的風(fēng)險(xiǎn)(Dynamic Particle Swarm Optimization，DPSO)；吳澤忠等人[13]在初始化種群時(shí)采用反向?qū)W習(xí)策略及隨機(jī)調(diào)整控制參數(shù)策略，利用正態(tài)變異算子與改進(jìn)螺旋更新位置對(duì)鯨魚(yú)種群進(jìn)行干擾從而提高全局搜索速度(Improved The Whale Optimization Algorithm，IMWOA)。麻雀搜索算法(Sparrow Search Algorithm，SSA)是由Jiankai Xue等人[14]于2020年提出的一種新型SI優(yōu)化算法。該算法模擬麻雀的覓食和反捕食行為，具體為一類(lèi)麻雀領(lǐng)導(dǎo)覓食，另一類(lèi)麻雀跟隨并搶奪食物等過(guò)程找尋全局最優(yōu)食物來(lái)源等一系列的捕食行為。與其它現(xiàn)有算法相比，SSA求解精度、收斂速度、穩(wěn)定性和魯棒性均有較好的性能，但仍無(wú)法避免種群尋優(yōu)前期多樣性較差導(dǎo)致搜尋速度較慢，降低了整體搜索速度，后期也存在陷入局部最優(yōu)的風(fēng)險(xiǎn)。

本文針對(duì)SSA種群初始質(zhì)量較差與后期易陷入局部最優(yōu)的缺陷提出了新的改進(jìn)方案，在SSA搜索前期，利用反向?qū)W習(xí)策略豐富種群多樣性加快全局收斂速度，后期引入混沌策略進(jìn)行干擾以降低陷入局部最優(yōu)的風(fēng)險(xiǎn)。通過(guò)與其余四種SI算法相比，ISSA在求解12個(gè)基本測(cè)試函數(shù)函數(shù)上尋優(yōu)性能更好，且能夠有效提高算法的收斂精度及穩(wěn)定性。

2 麻雀搜索算法

SSA是模擬自然界中麻雀覓食和搶食行為的一種新型SI優(yōu)化算法。SSA將麻雀種群分為領(lǐng)導(dǎo)者與跟隨者兩類(lèi)，種群中的領(lǐng)導(dǎo)者積極尋找食物來(lái)源，跟隨者則由領(lǐng)導(dǎo)者引導(dǎo)覓食從而獲取食物。為更快地獲取食物，跟隨者會(huì)不停地監(jiān)視領(lǐng)導(dǎo)者的行為，若發(fā)現(xiàn)比自身更好的食物來(lái)源時(shí)，便上前進(jìn)行搶奪。成功掠食則意味跟隨者擁有了更好的食物來(lái)源，麻雀的身份便由跟隨者轉(zhuǎn)換為領(lǐng)導(dǎo)者，發(fā)現(xiàn)危險(xiǎn)時(shí)引導(dǎo)麻雀逃離[14]。種群中領(lǐng)導(dǎo)者位置更新的數(shù)學(xué)模型如下

(1)

其中，第i只麻雀在第d維空間上的位置由xi，d表示。j=1，2，…，d，t是當(dāng)前迭代次數(shù)。M是最大迭代次數(shù)，α∈(0，1]是隨機(jī)數(shù)，R2∈(0，1]和ST∈(0.5，1.0]分別表示警報(bào)值和安全閥值。Q是服從均值為0標(biāo)準(zhǔn)差為1的高斯分布的隨機(jī)數(shù)，L是每個(gè)元素都為1的1×d矩陣。當(dāng)R2

種群里的追隨者在覓食的同時(shí)會(huì)監(jiān)視領(lǐng)導(dǎo)者，一旦發(fā)現(xiàn)位置更好的領(lǐng)導(dǎo)者便立即前往進(jìn)行搶奪。若搶奪失敗，則繼續(xù)跟隨覓食；其位置更新如下

(2)

意識(shí)到危險(xiǎn)的麻雀占種群數(shù)量的20%，其位置更新如下

(3)

SSA算法流程見(jiàn)圖1。

圖1 SSA算法流程圖

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

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

反向?qū)W習(xí)策略 (Opposition-based Learning，OBL)由Tizhoosh 等人[15]引入，此策略被學(xué)者廣泛應(yīng)用于SI算法，并取得了較好的實(shí)驗(yàn)效果[16-19]。SSA在尋優(yōu)前期采用隨機(jī)初始化種群，導(dǎo)致搜索初期種群的多樣性較差從而影響全局搜索的效率。種群初始化的質(zhì)量好壞是影響全局尋優(yōu)快慢的重要因素，因此本文在麻雀種群初始位置引入反向?qū)W習(xí)策略，擴(kuò)大麻雀的搜索空間提高種群初期質(zhì)量以增強(qiáng)全局搜索能力。反向?qū)W習(xí)策略通過(guò)選擇原始種群和對(duì)立種群的最優(yōu)解形成新的麻雀種群，其偽代碼如下。

Algorithm 1 initiation based on opposition-based learning

Set population size n，Search range boundary maximumμ，boundary minimum l，opposite solution oxi，j

fori=1to n do

for j=1to n do

xi，j=li，j+rand(0，1)·(μi，j-li，j)

end for

end for

for i=1 to n do

for j=1 to n do

oxi，j=li，j+μi，j-xi，j

end for

end for

{x(n)∪ox(n)}，Choose a better population

3.2 Sinusoidal map種群擾動(dòng)

混沌系統(tǒng)具有隨機(jī)性、遍歷性，因此將混沌理論與SI算法結(jié)合是改進(jìn)優(yōu)化算法的一種思路，研究表明其能有效逃離局部最優(yōu)和提高收斂精度[20-23]。SSA在尋找最優(yōu)解時(shí)可能會(huì)陷入局部最優(yōu)，其會(huì)導(dǎo)致尋優(yōu)精度與收斂速度的降低。因此，本文在麻雀搜索后期引入Sinusoidal map混沌映射[24]，避免麻雀種群在搜索過(guò)程中陷入局部最優(yōu)。Sinusoidal map映射的數(shù)學(xué)表達(dá)式如下

(4)

麻雀經(jīng)過(guò)擾動(dòng)后的位置如下

xSi=g(i)·xi

(5)

通過(guò)對(duì)比擾動(dòng)前后種群中麻雀的位置，保留適應(yīng)度值較優(yōu)的麻雀。其中g(shù)(1)=0.7，a=2.3。

3.3 改進(jìn)麻雀算法(ISSA)算法步驟

ISSA算法流程圖見(jiàn)圖2，詳細(xì)步驟如下：

Step1：設(shè)置麻雀算法初始參數(shù)，麻雀種群數(shù)量n，當(dāng)前迭代次數(shù)t，領(lǐng)導(dǎo)者數(shù)量PD，跟隨者數(shù)量SD，最大迭代次數(shù)G。

Step2：隨機(jī)生成麻雀?jìng)€(gè)體位置，再引入反向策略得到麻雀對(duì)立位置。

Step3：計(jì)算麻雀種群適應(yīng)度值并進(jìn)行排序，得到xp及xworst。

Step4：根據(jù)等式(1)更新種群中的領(lǐng)導(dǎo)者位置。R2

Step5：根據(jù)等式(2)更新跟隨者位置，跟隨者覓食同時(shí)會(huì)監(jiān)視領(lǐng)導(dǎo)者并搶奪食物。

Step6：根據(jù)等式(3)更新意識(shí)到危險(xiǎn)的麻雀位置。

Step8：重復(fù)Step4至Step7，直至滿足尋優(yōu)要求結(jié)束。

圖2 ISSA算法流程圖

4 仿真研究

4.1 測(cè)試函數(shù)及對(duì)比函數(shù)

為驗(yàn)證改進(jìn)麻雀算法的尋優(yōu)能力，本文將它用于求解12個(gè)國(guó)際上通用的標(biāo)準(zhǔn)測(cè)試函數(shù)，并與SSA、TGWO、WOA與DPSO進(jìn)行實(shí)驗(yàn)比較。測(cè)試函數(shù)見(jiàn)表1所示，其中F1-F7是單峰測(cè)試基準(zhǔn)函數(shù)，F(xiàn)8-F12是多峰測(cè)試基準(zhǔn)函數(shù)其測(cè)試函數(shù)具體表達(dá)式及變量范圍。單峰函數(shù)用來(lái)衡量算法的局部開(kāi)發(fā)能力，多峰函數(shù)衡量全局搜索與局部開(kāi)發(fā)的平衡性能。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)(維度=30)

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

本文算法參數(shù)設(shè)置為：迭代次數(shù)為1000，種群數(shù)量為100。TGWO算法中，φmax=0.9，φmin=0.4；WOA算法參數(shù)a在整個(gè)搜索中由2下降為0；DPSO中C1s=C2e=1，C1e=C2s=2.05。本文實(shí)驗(yàn)中ISSA與其余四種算法各運(yùn)行30次，分別計(jì)算Ave與Std并把保存結(jié)果。算法的優(yōu)化性能的好壞采用平均值(Ave)與標(biāo)準(zhǔn)差(Std)去衡量。平均值的大小代表了算法的收斂速度的快慢，算法的魯棒性的優(yōu)劣則由標(biāo)準(zhǔn)差的大小衡量，實(shí)驗(yàn)結(jié)果見(jiàn)表2、表3、表4及表5。

4.3 實(shí)驗(yàn)分析

表2 基準(zhǔn)函數(shù)測(cè)試結(jié)果1

表3 基準(zhǔn)函數(shù)測(cè)試結(jié)果2

表4 基準(zhǔn)函數(shù)測(cè)試結(jié)果3

表5 基準(zhǔn)函數(shù)測(cè)試結(jié)果4

由表2至表4可知，ISSA，SSA與TGWO三種算法在求解單峰基準(zhǔn)測(cè)試函數(shù)F1、F3時(shí)皆能收斂至函數(shù)最小值0且算法的穩(wěn)定性強(qiáng)，WOA與DPSO算法則相對(duì)表現(xiàn)較差。在求解函數(shù)F2，F(xiàn)4，F(xiàn)5，F(xiàn)6時(shí)，Ave值與Std值可以清晰得到ISSA收斂精度與穩(wěn)定性?xún)?yōu)于其余四種算法。在求解函數(shù)F7時(shí)，ISSA局部開(kāi)發(fā)能力相比于TGWO算法表現(xiàn)較差，但明顯優(yōu)于SSA，WOA，DPSO其余三種算法。根據(jù)上述分析可得，ISSA能有效增強(qiáng)原算法的尋優(yōu)性能與局部開(kāi)發(fā)能力，并有效提高了SSA的全局收斂精度。

多峰基準(zhǔn)測(cè)試函數(shù)含有多個(gè)局部高峰，優(yōu)化算法求解時(shí)極易陷入局部最優(yōu)，因此多峰基準(zhǔn)測(cè)試函數(shù)通常用于測(cè)試算法逃離局部最優(yōu)的能力。ISSA，SSA，TGWO，WOA在求解函數(shù)F8時(shí)皆能收斂到全局最優(yōu)值，同時(shí)四種算法的穩(wěn)定性也相對(duì)較優(yōu)。求解函數(shù)F9時(shí)，ISSA與SSA沒(méi)有收斂到函數(shù)最小值，但也明顯優(yōu)于其余三種算法。針對(duì)求解F11，F(xiàn)12函數(shù)時(shí)，其尋優(yōu)精度顯然高于其余四種算法且能很好地平衡算法全局搜索與局部開(kāi)發(fā)。總體而言，ISSA在求解多峰函數(shù)時(shí)較于其它算法均表現(xiàn)更優(yōu)，能更好地降低算法陷入局部最優(yōu)的風(fēng)險(xiǎn)從而提高整體搜索速度。

為更直觀顯示實(shí)驗(yàn)對(duì)比分析結(jié)果，本文給出ISSA與其余四中算法在相同實(shí)驗(yàn)條件下得到的函數(shù)仿真曲線，見(jiàn)圖3。

由圖3可知，與另外四種算法相比，ISSA在函數(shù)F1，F(xiàn)2，F(xiàn)3上收斂速度更快。針對(duì)函數(shù)F4，F(xiàn)5，ISSA前期搜索速度較慢，但后期局部搜索速度明顯優(yōu)于SSA。求解函數(shù)F6時(shí)，ISSA收斂速度與精度略?xún)?yōu)于SSA。

圖3 算法對(duì)比尋優(yōu)曲線

根據(jù)上述實(shí)驗(yàn)數(shù)據(jù)可知，TGWO在求解F7時(shí)速度顯然比其余四種算法更好，但由收斂曲線圖可看出ISSA算法性能與TGWO接近。通過(guò)求解F8，F(xiàn)10函數(shù)結(jié)果也可看出ISSA收斂更快，從其余的收斂曲線也能清晰得到ISSA收斂速度與逃離局部最優(yōu)的能力都優(yōu)于SSA，TGWO，WOA，DPSO。

綜上所述，改進(jìn)后的算法在搜索中能有效改善全局尋優(yōu)精度，提高了算法穩(wěn)定性，并使算法具有較強(qiáng)的逃離局部最優(yōu)的能力。

5 結(jié)語(yǔ)

麻雀算法是模擬麻雀覓食行為的一種仿生智能算法，本文針對(duì)其尋優(yōu)過(guò)程中精度不足的缺陷，并具有陷入局部最優(yōu)的風(fēng)險(xiǎn)提出一種改進(jìn)的麻雀算法。麻雀尋優(yōu)前期實(shí)施反向?qū)W習(xí)策略以增加初始種群的多樣性，從而增加全局搜索速度；在后期引入Sinusoidal map混沌思想以增強(qiáng)逃離局部最優(yōu)的能力。通過(guò)求解12個(gè)基本測(cè)試函數(shù)并與其余四種智能算法進(jìn)行比較，ISSA能有效提高算法的收斂精度，且提高整個(gè)搜索過(guò)程的搜索速度與穩(wěn)定性。