改進(jìn)的麻雀搜索優(yōu)化算法及其應(yīng)用*

尹德鑫，張達(dá)敏，蔡朋宸，秦維娜

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

1 引言

近些年來，數(shù)值優(yōu)化經(jīng)常被用來處理工程中的一些復(fù)雜問題，群智能算法在數(shù)字優(yōu)化領(lǐng)域發(fā)揮著重要作用。當(dāng)前的主流群智能算法有：鯨魚優(yōu)化算法WOA(Whale Optimization Algorithm)[1]、灰狼優(yōu)化算法GWO(Grey Wolf Optimizer)[2]和蝗蟲優(yōu)化算法GOA(Grasshopper Optimization Algorithm)[3]等。麻雀搜索算法SSA(Sparrow Search Algorithm)是由Xue等[4]在2020年提出的一種新興群智能算法，具有求解精度高、收斂速度快和穩(wěn)定性好等優(yōu)點(diǎn)，但在面對多峰問題時(shí)仍然存在尋優(yōu)精度低、收斂速度慢和易陷于局部最優(yōu)等缺點(diǎn)。

對于改進(jìn)群智能優(yōu)化算法中種群多樣性不豐富、易陷于局部最優(yōu)和尋優(yōu)精度低等問題的研究工作有很多：文獻(xiàn)[5]通過改進(jìn)位置更新公式和非線性控制來增強(qiáng)灰狼優(yōu)化算法的尋優(yōu)精度；文獻(xiàn)[6]提出一種改進(jìn)的蝗蟲優(yōu)化算法，用高斯混沌映射來生成初始種群，增加種群多樣性；文獻(xiàn)[7]提出基于隨機(jī)替換和混合變異的蜻蜓算法，引入隨機(jī)策略來提高收斂速度；文獻(xiàn)[8]提出將粒子群優(yōu)化算法和差分算法混合，利用彼此的優(yōu)勢來避免過早收斂的問題；文獻(xiàn)[9]提出基于Levy飛行的鯨魚改進(jìn)算法，利用Levy飛行增加種群多樣性，防止過早收斂；文獻(xiàn)[10]提出一種基于動(dòng)態(tài)對立學(xué)習(xí)的競爭粒子群優(yōu)化算法，每次迭代隨機(jī)選擇2個(gè)粒子來進(jìn)行競爭，然后根據(jù)對立學(xué)習(xí)或者競爭學(xué)習(xí)來擴(kuò)大搜索范圍，使粒子群可以跳出局部最優(yōu)值，獲得更快的收斂速度。

以上改進(jìn)算法在一定程度上提高了全局搜索能力，避免了過早收斂。但是，通過深入研究算法發(fā)現(xiàn)仍存在尋優(yōu)精度不足，隨著搜索空間維度增加收斂速度變慢等問題。針對這些問題，本文提出一種改進(jìn)的麻雀搜索算法ISSA(Improved Sparrow Search Algorithm)，首先,將反向?qū)W習(xí)策略用于生成初始種群，豐富種群多樣性；然后，對步長控制參數(shù)進(jìn)行優(yōu)化，提高SSA的尋優(yōu)性能；最后，將Levy飛行引入到偵查預(yù)警麻雀位置更新公式中，加快收斂速度，避免局部最優(yōu)。

2 麻雀搜索算法

麻雀搜索算法的主要思想是通過模仿麻雀的覓食和反捕食行為，來進(jìn)行局部和全局搜索，麻雀覓食過程就是算法尋優(yōu)過程。SSA由3種類型的麻雀組成：發(fā)現(xiàn)者、加入者和偵察者。發(fā)現(xiàn)者通常擁有較高的適應(yīng)度值，負(fù)責(zé)為加入者提供覓食區(qū)域和方向；加入者為了得到更好的食物會(huì)一直跟隨發(fā)現(xiàn)者，同時(shí)監(jiān)視發(fā)現(xiàn)者并爭奪食物，以此保證他們的捕食率；當(dāng)偵察者發(fā)現(xiàn)捕食者后立即發(fā)出報(bào)警信號，全體麻雀做出反捕食行為[11]。

(1)發(fā)現(xiàn)者的位置更新公式如式(1)所示:

(1)

其中，t表示當(dāng)前迭代次數(shù)，T表示最大迭代次數(shù)，Xi,j(t)表示第i只麻雀在第j(1≤j≤d)維迭代次數(shù)為t時(shí)的位置信息，d為空間維度，α為[0,1]的隨機(jī)數(shù)，R2∈[0,1]表示預(yù)警值，ST∈[0.5,1]表示安全值，Q為服從正態(tài)分布的隨機(jī)數(shù)，L表示一個(gè)1×d的矩陣，其中內(nèi)部每個(gè)元素都為1。當(dāng)R2

(2)加入者的位置更新公式如式(2)所示：

(2)

其中，Xworst(t)表示當(dāng)前全局最差位置；Xpest(t)表示發(fā)現(xiàn)者占據(jù)的最佳位置；N為種群數(shù)量；A+=AT(AAT)-1，A表示一個(gè)內(nèi)部元素隨機(jī)分配為1或-1的1×d矩陣，AT為A的轉(zhuǎn)置。當(dāng)i>N/2時(shí)，表示適應(yīng)度值較差的第i只加入者處于饑餓狀態(tài)，它需要飛往其他方向?qū)ふ沂澄铩?/p>

(3)負(fù)責(zé)偵查的麻雀一般占種群的10%～20%，其位置更新公式如式(3)所示：

Xi,j(t+1)=

(3)

其中，Xbest(t)表示當(dāng)前全局最優(yōu)位置;β為服從均值為0，方差為1的正態(tài)分布隨機(jī)數(shù)的步長控制參數(shù);K∈[-1,1]表示麻雀運(yùn)動(dòng)方向，也是步長控制參數(shù);fi表示當(dāng)前麻雀的適應(yīng)度值;fg和fw分別表示當(dāng)前全局最優(yōu)值和最差值;e為一個(gè)常數(shù)，是為了避免分母為0。當(dāng)fi>fg時(shí)，表示麻雀處于種群的邊緣地段，易受到捕食者攻擊;當(dāng)fi=fg時(shí)，表示處于種群中間位置的麻雀意識到危險(xiǎn)，需要靠近其他麻雀來降低被捕食的概率。

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

3.1 反向?qū)W習(xí)策略

SSA中采用的是隨機(jī)生成初始種群，這樣生成的種群分布不均勻，導(dǎo)致種群多樣性不豐富，種群質(zhì)量不高，影響算法的收斂速度，因此本文改進(jìn)的麻雀搜索算法ISSA采用反向?qū)W習(xí)策略來解決這一問題。反向?qū)W習(xí)OBL(Opposition-Based Learning)策略是由Tizhoosh[12]提出的。該策略提出了對點(diǎn)的概念，用對立搜索代替了隨機(jī)搜索。利用反向?qū)W習(xí)策略生成種群的主要思想是：首先隨機(jī)生成初始種群，然后根據(jù)初始種群生成其反向種群，從中選擇較優(yōu)的種群作為下一代種群。反向?qū)W習(xí)策略會(huì)選擇更靠近最優(yōu)位置的個(gè)體作為種群的最初個(gè)體，這樣每個(gè)個(gè)體都離最優(yōu)解更近一步，以便提高種群中所有個(gè)體的收斂速度。此外，反向?qū)W習(xí)策略還可以通過搜索更多有效區(qū)域來提高群體的多樣性，增強(qiáng)算法的全局搜索能力。

(4)

其中，ub為搜索空間的上界，lb為搜索空間的下界,rand為[0,1]的隨機(jī)數(shù)。將隨機(jī)生成種群和反向種群合并為一個(gè)新的種群后，求新種群的適應(yīng)度函數(shù)，并將適應(yīng)度值按升序排列，取前N個(gè)最優(yōu)初始解作為新的麻雀初始種群。

3.2 步長因子動(dòng)態(tài)調(diào)整策略

在SSA中，式(3)中的步長控制參數(shù)β和K在平衡全局搜索能力與局部開發(fā)能力方面發(fā)揮了重要作用，但因?yàn)棣潞蚄都是隨機(jī)數(shù)，無法使麻雀充分探索空間，可能導(dǎo)致SSA陷入局部最優(yōu)。因此,需要對步長控制參數(shù)β和K進(jìn)行優(yōu)化，使較大的控制參數(shù)便于全局搜索，較小的控制參數(shù)促進(jìn)局部開發(fā)[13]。對步長控制參數(shù)β和K的改進(jìn)如式(5)和式(6)所示：

β=fitnessbest-(fitnessbest-

(5)

K=(fitnessbest-fitnessworst)·

(6)

其中，fitnessbest是最佳適應(yīng)度值，fitnessworst是最差適應(yīng)度值,T為最大迭代次數(shù)。從式(5)可知，改進(jìn)后的步長控制參數(shù)呈非線性遞增變化，因?yàn)樵赟SA的迭代早期階段，種群具有較高的多樣性，這意味著探索全局空間的能力較強(qiáng)而探索局部空間的能力較弱。因此，本文將控制參數(shù)的值設(shè)置為較小的值，以加強(qiáng)局部開發(fā)能力。在迭代后期當(dāng)所有麻雀都被當(dāng)前的全局最優(yōu)吸引，沒有足夠的搜索空間探索時(shí)，它們可能會(huì)過早收斂，因此將控制參數(shù)的值設(shè)置為較大的值，避免陷入局部最優(yōu)，有利于進(jìn)一步探索。從式(6)可知，步長因子K在迭代前期遞增后期快速減少，這有利于SSA在前期充分探索搜索空間，后期提高收斂速度。動(dòng)態(tài)調(diào)整步長控制參數(shù)可以平衡SSA全局搜索與局部開發(fā)能力,在提高尋優(yōu)精度的同時(shí)避免出現(xiàn)局部極值。

3.3 Levy飛行策略

Levy飛行[14]是一種非高斯隨機(jī)步態(tài)，步長服從重尾概率分布，其飛行特點(diǎn)為長時(shí)間進(jìn)行小步長隨機(jī)游走，偶爾會(huì)出現(xiàn)大步長[15]。從文獻(xiàn)[4]可知，標(biāo)準(zhǔn)SSA可能會(huì)陷入到局部極值，以致無法找到全局最優(yōu)解。在尋找最優(yōu)解過程中，Levy飛行不僅可以在短距離中進(jìn)行局部搜索，還可以在長距離中進(jìn)行全局搜索。因此，在搜索到最優(yōu)值附近時(shí)，Levy飛行能起到增強(qiáng)局部搜索能力的作用，有效解決了標(biāo)準(zhǔn)SSA可能陷入局部最優(yōu)的問題。本文將Levy飛行策略引入式(3)中的麻雀最優(yōu)位置，改進(jìn)后的SSA根據(jù)當(dāng)前位置與麻雀最優(yōu)位置的距離來進(jìn)行位置更新，這樣大大降低了麻雀陷入局部最優(yōu)的風(fēng)險(xiǎn)，而且仍然能充分執(zhí)行局部探索，改進(jìn)公式如式(7)所示：

(7)

其中，d為空間維度。Levy計(jì)算公式如式(8)和式(9)所示：

(8)

(9)

其中，Г為伽馬函數(shù)，θ為常數(shù)，r1和r2為[0,1]的隨機(jī)數(shù)。

3.4 ISSA偽代碼

ISSA的偽代碼如下所示：

1)設(shè)置種群數(shù)量為n、發(fā)現(xiàn)者數(shù)量為PD、偵察者數(shù)量為SD、預(yù)警值為R2、安全值為ST和最大迭代次數(shù)為T;

2)使用反向?qū)W習(xí)策略初始化種群;

3)計(jì)算每個(gè)麻雀的適應(yīng)度值，并找到當(dāng)前最佳個(gè)體和最差個(gè)體;

4)While(t

5)fori=1:PD

6) 根據(jù)式(1)更新麻雀位置

7)endfor

8)fori=(PD+1):n

9) 根據(jù)式(2)更新麻雀位置

10)endfor

11)forl=1:SD

12) 根據(jù)式(5)～式(7)更新麻雀位置;

13)endfor

14) 得到當(dāng)前更新位置;

15) 如果新的更新位置大于當(dāng)前更新位置，則更新它;

16)t=t+1;

17)endWhile

18)返回目標(biāo)函數(shù)值。

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

為了驗(yàn)證本文ISSA在求解優(yōu)化函數(shù)上的優(yōu)越性，對8個(gè)測試函數(shù)進(jìn)行仿真。表1為維度均是30的測試函數(shù)，F(xiàn)1～F4為單峰函數(shù)，F(xiàn)5～F8為多峰函數(shù)，單峰函數(shù)用于測試算法收斂速度，多峰函數(shù)因?yàn)橛卸鄠€(gè)局部最優(yōu)值，易使算法陷入局部極值，所以多峰函數(shù)用于測試算法的尋優(yōu)能力。

Table 1 Benchmark fuctions

4.1 算法對比分析

將ISSA獨(dú)立運(yùn)行30次求解的測試函數(shù)結(jié)果同SSA[4]、GOA[3]、GWO[2]和另一改進(jìn)麻雀搜索算法FSSA(F Sparrow Search Algorithm)[16]的結(jié)果相比。設(shè)置每種算法的共同參數(shù)最大迭代次數(shù)T=300，種群規(guī)模N=30。基于上述8個(gè)測試函數(shù)，將算法的最優(yōu)值、平均值和標(biāo)準(zhǔn)差作為評價(jià)指標(biāo)，仿真結(jié)果如表2所示。

從表2可以看出，對于單峰函數(shù)F1、F2、F3和F4，ISSA算法的求解精度都可以達(dá)到理想最優(yōu)值，尋優(yōu)性能明顯強(qiáng)于SSA、GOA、GWO和FSSA，且ISSA標(biāo)準(zhǔn)差都為0，說明ISSA的穩(wěn)定性也強(qiáng)于其他算法。對于多峰函數(shù)F5和F7，ISSA和SSA的求解精度最高，尋優(yōu)精度都達(dá)到了最優(yōu)值，且標(biāo)準(zhǔn)差為0，GOA性能最差，GWO次之；對于多峰函數(shù)F6和F8，從平均值可以看出，ISSA收斂精度最高，F(xiàn)SSA次之，GOA最差，從標(biāo)準(zhǔn)差來看，ISSA的穩(wěn)定性最高，這說明相比其他算法，ISSA具有更強(qiáng)的全局搜索能力、穩(wěn)定性和魯棒性。

圖1和圖2展示了單峰函數(shù)F3和F4的收斂曲線，圖3和圖4展示了多峰函數(shù)F7和F8的收斂曲線。從圖1可知，ISSA的收斂精度最高，F(xiàn)SSA次之，相較其他算法，ISSA最先收斂，并且尋優(yōu)精度達(dá)到了最優(yōu)值。從圖2可知，ISSA的收斂速度最快且它的尋優(yōu)效果也達(dá)到了理想狀態(tài)，這說明同其他算法相比，ISSA不僅有良好的全局搜索能力而且不易陷入局部最優(yōu)，平衡了全局探索能力與局部開發(fā)能力。從圖3可以看出，在相同尋優(yōu)精度下，相比SSA和FSSA，ISSA的收斂速度更快，這說明ISSA在一定程度上改善了SSA收斂速度上的缺陷。從圖4可以明顯看出，ISSA的尋優(yōu)精度明顯高于其他算法，這說明ISSA在求解多峰函數(shù)上規(guī)避了局部最優(yōu)的風(fēng)險(xiǎn)，提高了全局搜索的能力，增強(qiáng)了跳出局部最優(yōu)值的能力。

4.2 不同改進(jìn)策略對比

本節(jié)將ISSA與結(jié)合步長因子動(dòng)態(tài)調(diào)整策略的SSA1、結(jié)合Levy飛行策略的SSA2、融合反向?qū)W習(xí)策略的SSA3進(jìn)行對比,以驗(yàn)證不同改進(jìn)策略的有效性,實(shí)驗(yàn)結(jié)果如表3所示。由表3可知,ISSA對單峰函數(shù)尋優(yōu)時(shí),單峰函數(shù)F3和F4的3個(gè)性能評價(jià)指標(biāo)均達(dá)到了理想值,而對于多峰函數(shù)F7，ISSA和其他改進(jìn)算法的尋優(yōu)精度均達(dá)到理想值；ISSA對于多峰函數(shù)F8的尋優(yōu)精度雖沒有達(dá)到理想值，但比起標(biāo)準(zhǔn)SSA和其他改進(jìn)算法，ISSA也在一定程度上提高了尋優(yōu)精度。

Table 2 Test function simulation results

總的來說，SSA2和SSA3對F3和F4的有效性顯著，從3個(gè)評價(jià)指標(biāo)可看出，結(jié)合Levy飛行策略的更新策略和融合反向?qū)W習(xí)的策略可有效提高算法的尋優(yōu)能力;SSA1對單峰函數(shù)的尋優(yōu)結(jié)果是3種改進(jìn)策略算法中最差的，但其尋優(yōu)精度相比于SSA也得到了一定提升；SSA1和SSA3對于求解多峰函數(shù)F8的最優(yōu)值效果最好，但在標(biāo)準(zhǔn)差方面，不如SSA2算法穩(wěn)定，相比SSA，3種改進(jìn)算法在穩(wěn)定性和尋優(yōu)性上都得到了提升。表3的實(shí)驗(yàn)結(jié)果表明，在單峰函數(shù)和多峰函數(shù)中，融合3個(gè)改進(jìn)策略的ISSA能有效增加種群多樣性，提高算法尋優(yōu)精度。

4.3 Wilcoxon秩和檢驗(yàn)

Wilcoxon秩和檢驗(yàn)[17]是一種非參數(shù)統(tǒng)計(jì)檢驗(yàn)方法，本文用來判斷ISSA與其他算法是否有顯著性區(qū)別。本文將ISSA、SSA、GOA、GWO和FSSA均獨(dú)立運(yùn)行30次的平均值進(jìn)行秩和檢驗(yàn)，其結(jié)果如表4所示，其中P表示檢驗(yàn)結(jié)果，S表示顯著性判斷結(jié)果。當(dāng)P<0.05時(shí)，S顯示為“+”，表示ISSA的顯著性強(qiáng)于其他算法；當(dāng)P>0.05時(shí)，S顯示為“-”，表示ISSA的顯著性弱于其他算法；當(dāng)P=0.05時(shí),S顯示為“NaN”，表示無法進(jìn)行顯著性判斷。

從表4可以明顯看出，ISSA除了與SSA和FSSA在F5、F6和F7函數(shù)上無法進(jìn)行顯著性判斷外，對于其他算法不管是單峰函數(shù)還是多峰函數(shù)上的檢驗(yàn)結(jié)果，P值都遠(yuǎn)遠(yuǎn)小于0.05，且S都為+,這說明比起SSA、GOA、GWO和FSSA，ISSA具有顯著性優(yōu)勢。

Table 3 Test function comparison results

5 ISSA在認(rèn)知無線電中的應(yīng)用

隨著5G通信的普及，無線通信業(yè)務(wù)量大幅增加，頻譜資源的短缺和固定的頻譜分配方式導(dǎo)致頻譜利用率低和頻譜資源嚴(yán)重浪費(fèi)。因此，Joseph Mitola 博士提出用認(rèn)知無線電CR(Cognitive Ra-dio)[18]來解決頻譜利用率低的問題。本文針對大多數(shù)算法收斂速度不夠快，過于早熟，導(dǎo)致頻譜分配的系統(tǒng)效益不高和用戶間的公平性低等問題，提出用ISSA來優(yōu)化頻譜分配。將頻譜分配[19]映射到麻雀種群中每只麻雀的位置，算法迭代結(jié)果中的最優(yōu)種群解對應(yīng)于頻譜分配的系統(tǒng)效益和認(rèn)知用戶之間的公平性指數(shù)，其系統(tǒng)效益與公平性分別如式(10)和式(11)所示：

Table 4 Results of Wilcoxon

(10)

(11)

其中，sp,m∈{0,1}為無干擾分配矩陣的元素，當(dāng)sp,m=1時(shí)表示信道m(xù)可以被非授權(quán)用戶p占用;ep,m為效益矩陣的元素，表示某認(rèn)知用戶在信道上獲得的效益;P表示認(rèn)知用戶數(shù);M表示可用信道數(shù)。

為了驗(yàn)證ISSA在頻譜分配上的有效性，將ISSA與SSA[4]、蜘蛛猴算法SMO[20]和二進(jìn)制粒子群優(yōu)化算法BPSO[21]進(jìn)行對比。實(shí)驗(yàn)參數(shù)設(shè)置如下：網(wǎng)絡(luò)區(qū)域范圍為10×10;可用頻譜M=10;主用戶K=5;認(rèn)知用戶數(shù)P=10;傳送功率最大值和最小值分別為1 dB和4 dB;主用戶覆蓋半徑Dp=2。

為說明ISSA在不同網(wǎng)絡(luò)環(huán)境中均具有更好的優(yōu)化性能，在認(rèn)知用戶數(shù)與可用信道數(shù)都為10時(shí)，將4種算法在30種不同信道環(huán)境中進(jìn)行仿真，得到不同環(huán)境中的公平性，如圖5所示。從圖5可以看出，在不同的信道環(huán)境中，ISSA的公平性均大于SSA、SMO和BPSO算法的。

表5為4種算法在可用信道數(shù)和認(rèn)知用戶數(shù)相等的情況下，獨(dú)立運(yùn)行30次的系統(tǒng)總效益值，可以看出，ISSA的系統(tǒng)效益最高。總之，不管在公平性方面還是在系統(tǒng)總效益方面，ISSA都優(yōu)于SSA、SMO和BPSO，這說明了ISSA的有效性。

Table 5 System benefit comparison

6 結(jié)束語

麻雀算法作為一種新興群體智能算法，受到廣泛的關(guān)注。本文提出了一種改進(jìn)的麻雀搜索算法，使用反向?qū)W習(xí)策略來解決麻雀算法初始化種群時(shí)造成的種群分布不均勻問題，豐富了種群多樣性；為了更好地平衡SSA的探索能力和開發(fā)能力，對步長控制參數(shù)進(jìn)行優(yōu)化，同時(shí)對麻雀最優(yōu)位置引入飛行算子，提高了麻雀的收斂速度和尋優(yōu)精度。ISSA在8個(gè)單峰函數(shù)和多峰函數(shù)中進(jìn)行了測試，并進(jìn)行了秩和檢驗(yàn)分析，實(shí)驗(yàn)結(jié)果表明，ISSA的仿真結(jié)果更優(yōu)越，這說明ISSA具有很高的探索開發(fā)能力和穩(wěn)定性。此外，將ISSA應(yīng)用到認(rèn)知無線電頻譜分配優(yōu)化中，以系統(tǒng)總效益和認(rèn)知用戶公平性為評價(jià)指標(biāo)與SSA、SMO和BPSO進(jìn)行對比，結(jié)果表明，ISSA優(yōu)于其他算法，可獲得更高的網(wǎng)絡(luò)效益和公平性。