融合精英學(xué)習(xí)與多項(xiàng)式變異的改進(jìn)麻雀算法

歐陽城添,劉裕嘉,朱東林

(江西理工大學(xué),江西 贛州 341000)

1 引言

群體智能優(yōu)化算法主要是通過觀察大自然中各種生物的群體覓食行為而發(fā)明的啟發(fā)式算法。許多新型的群智能優(yōu)化算法相繼被提出,如:蟻群算法(Ant Colony Optimization,ACO),蝙蝠算法(Bat Algorithm,BA),蜻蜓算法(Dragonfly Algorithm,DA),鯨魚優(yōu)化算法(Whale Optimization algorithm,WOA),麻雀搜索算法(Sparrow Search Algortihm,SSA)等等。其中的麻雀搜索算法(SSA)是薛建凱等[1]在2020年首次提出的一種新型群體智能優(yōu)化算法。麻雀搜索算法相較于其它算法有較好的優(yōu)化效果[2],但在搜索過程中依舊存在效率較低和容易陷入局部最優(yōu)的問題。

為對群體智能優(yōu)化算法在搜索過程中的問題進(jìn)行改善,許多學(xué)者都提出了自己的改善方案:康朝海等[3]提出一種基于精英高斯學(xué)習(xí)的改進(jìn)魚群粒子群混合算法,利用魚群算法中較好的全局搜索能力和粒子群算法中較強(qiáng)的局部搜索能力的特點(diǎn),在搜索初期利用魚群算法來取得最佳群體,在迭代后期使用粒子群算法進(jìn)行精確搜索,并在最后階段采用改進(jìn)的精英高斯學(xué)習(xí)策略,進(jìn)一步優(yōu)化最后結(jié)果的精度。楊萬里等[4]提出一種基于Logistic映射的新型混沌簡化PSO算法,引入混沌理論使慣性權(quán)重具有混沌搜索能力,同時(shí)使學(xué)習(xí)因子隨尋優(yōu)過程呈正弦函數(shù)變化,降低算法陷入局部最優(yōu)的概率。黃清寶等[5]提出一種基于余弦控制因子和多項(xiàng)式變異的鯨魚優(yōu)化算法,利用余弦曲線和慣性權(quán)值優(yōu)化控制參數(shù),初期減緩收斂來增強(qiáng)全局搜索能力,后期加快收斂速度來優(yōu)化搜索精度,并在最優(yōu)鯨魚位置上采用多項(xiàng)式變異,來使算法增加跳出局部極值的概率。卜冠南等[6]采用一種隨迭代分組數(shù)減少策略方法,使蟻群算法增加全局搜索能力,提高求解路徑規(guī)劃性能。Wang W C等[7]引入柯西變異算子,避免螢火蟲算法陷入局部最優(yōu),提高了全局搜尋能力。劉景森等[8]引入混沌映射和隨機(jī)交叉策略,優(yōu)化樽海鞘群算法的全局搜索性能,并將其應(yīng)用于工程優(yōu)化問題。

上述文獻(xiàn)的改進(jìn)方法,在一定程度上降低了算法陷入局部最優(yōu)的概率,但在搜索過程中依然存在較大的隨機(jī)性,實(shí)驗(yàn)結(jié)果并不總能滿足優(yōu)化預(yù)期。因此,在此基礎(chǔ)之上,本文提出了融合精英學(xué)習(xí)與多項(xiàng)式變異的改進(jìn)麻雀算法。在初始化階段,利用維度空間均勻初始化種群,優(yōu)化種群分布,提高初期搜索效率;然后在發(fā)現(xiàn)者搜索階段,引入精英學(xué)習(xí)策略,擴(kuò)大搜索范圍,提高算法的開拓能力;最后在采用多項(xiàng)式變異對麻雀搜索算法中的最佳位置進(jìn)行更新,降低算法陷入局部最優(yōu)解的概率,增強(qiáng)尋優(yōu)性能。通過8個(gè)基準(zhǔn)函數(shù)的仿真,驗(yàn)證了上述方法的有效性。

2 麻雀搜索算法

在麻雀種群整個(gè)覓食過程中,自發(fā)地形成兩種行為方式,一個(gè)為發(fā)現(xiàn)者,另一個(gè)為加入者。發(fā)現(xiàn)者的作用主要是引導(dǎo)種群發(fā)現(xiàn)覓食區(qū)域和具體方向,而加入者一般是在發(fā)現(xiàn)者的指引下獲取食物。為了更大地提高自己的捕食概率,部分加入者會(huì)會(huì)對發(fā)現(xiàn)者進(jìn)行監(jiān)視而方便與其爭奪食物或者圍繞其周圍進(jìn)行覓食。當(dāng)整個(gè)麻雀種群受到捕食者威脅時(shí),會(huì)進(jìn)行反捕食行為。

在SSA中,發(fā)現(xiàn)者會(huì)優(yōu)先獲得食物并比發(fā)現(xiàn)者獲得更大的覓食范圍。發(fā)現(xiàn)者一般占到種群的10%～20%,在每次迭代時(shí)位置更新公式如下

(1)

式中:t代表當(dāng)前迭代次數(shù);T為最大的迭代次數(shù);Xi,j表示第i個(gè)麻雀在第j維中的位置信息。α∈(0,1]是一個(gè)隨機(jī)數(shù);Q是服從正態(tài)分布的隨機(jī)數(shù);L表示一個(gè)元素全為1的矩陣,大小為1×d,;R2∈[0,1]和ST∈[0.5,1]分別表示預(yù)警值和安全值。當(dāng)R2

除了發(fā)現(xiàn)者,剩余的麻雀均作為加入者,并根據(jù)下式進(jìn)行位置更新

(2)

式中:Xworst表示目前所在的全局最劣位置;Xp表示目前狀態(tài)下發(fā)現(xiàn)者所處的最優(yōu)位置;A表示一個(gè)1×d的矩陣,其中每個(gè)元素隨機(jī)賦值為1或-1,并且A*=AT(AAT)-1。當(dāng)i>n/2時(shí),表示由于適應(yīng)度較低,第i個(gè)加入者沒有獲取食物,處于非常饑餓的狀態(tài),所以需要飛往其它地方覓食來獲取更高的能量。

當(dāng)發(fā)現(xiàn)危險(xiǎn)時(shí),麻雀群會(huì)進(jìn)行反捕食行為,其位置更新如下

(3)

式中:β表示步長控制參數(shù),是服從均值為0,方差為1的正態(tài)分布隨機(jī)數(shù);K∈[-1,1]是一個(gè)隨機(jī)數(shù),表示麻雀移動(dòng)的方向,同時(shí)也是步長控制參數(shù);e設(shè)置為一個(gè)最小常數(shù),來防止出現(xiàn)分母為0的情況;fi表示第i只麻雀的適應(yīng)度值,fg和fw分別是當(dāng)前種群的最優(yōu)和最差適應(yīng)度值。當(dāng)fi>fg時(shí),表明此麻雀位于種群的邊緣,極容易受到捕食者襲擊;當(dāng)fi=fg時(shí),表明種群中間的麻雀意識(shí)到捕食者的威脅,需要和其它麻雀一起抱團(tuán)來減少被捕食的風(fēng)險(xiǎn)。

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

3.1 均勻初始化

麻雀搜索算法在開始初始化過程中有較大的隨機(jī)性,這將使得一部分的麻雀個(gè)體距離過近,空間上分布不均,從而將降低算法初期搜索效率。對此,本文將利用維度空間均勻初始化的方案來開始初始化麻雀種群。均勻初始化相對于Logistic混沌映射初始化和Tent映射初始化過程[9],所用時(shí)間更少并且約束條件更簡單,種群分布更為均勻,并在算法初期的搜索效率也有進(jìn)一步提升。以下為操作過程:

1)依據(jù)種群個(gè)體數(shù)目,種群個(gè)體在子空間中的密度系數(shù)ρ以及在每個(gè)維度分量的上限Xmax與下限Xmin,將麻雀種群所處的整個(gè)空間平均分成M個(gè)子空間。

2)在各個(gè)獨(dú)立的子空間中,按任意概率產(chǎn)生出N個(gè)種群個(gè)體,根據(jù)

(4)

3)終初始種群由M×N個(gè)種群個(gè)體所構(gòu)成,種群初始化過程就此結(jié)束。

3.2 精英學(xué)習(xí)策略

麻雀種群中的發(fā)現(xiàn)者引導(dǎo)著種群的搜索方向和范圍,所以發(fā)現(xiàn)者的搜索策略也直接影響了算法的尋優(yōu)結(jié)果。在發(fā)現(xiàn)者搜索過程中,麻雀搜索算法自身的缺陷將有一定幾率限制種群的覓食范圍,致使最終落入局部極值的結(jié)果。

精英學(xué)習(xí)策略的目的是生成適應(yīng)度高精英個(gè)體,獲取精英解的位置,提高算法的尋優(yōu)能力。本文做了一些改進(jìn),該策略的形成是受遺傳算法和環(huán)形拓?fù)浣Y(jié)構(gòu)所啟發(fā),將遺傳算法中的精英選擇操作[10]和環(huán)形拓?fù)浞椒ㄏ嘟Y(jié)合,更多的篩選出引導(dǎo)能力較強(qiáng)的精英個(gè)體。

環(huán)形拓?fù)浣Y(jié)構(gòu)方程如下

qi,j=rj·xmi1,j+(1-rj)·xmi2,j

(5)

引入的精英學(xué)習(xí)策略有效的擴(kuò)展了發(fā)現(xiàn)者的搜索范圍并優(yōu)化了搜索路徑,進(jìn)一步增大了麻雀種群的覓食空間,增強(qiáng)了算法的全局探索能力和局部尋優(yōu)能力,避免了陷入局部極值的困擾。

3.3 多項(xiàng)式變異

在智能優(yōu)化算法的迭代過程中常容易陷入局部最優(yōu),而引入變異來降低算法陷入局部最優(yōu)解的概率是一種行之有效的方法。在算法中加入變異算子有兩點(diǎn)優(yōu)勢,首先,在迭代后期可以提高算法的求解速度;其次,也可以繼續(xù)保持解的多樣性。多項(xiàng)式變異[11]一般常被用于多目標(biāo)函數(shù)優(yōu)化,因?yàn)閱文繕?biāo)優(yōu)化也可以看作多目標(biāo)優(yōu)化的一種特別的情形,所以單目標(biāo)優(yōu)化也可以采用多項(xiàng)式變異進(jìn)行操作。據(jù)此,本文引入多項(xiàng)式變異對麻雀搜索算法中的最佳個(gè)體位置進(jìn)行優(yōu)化選擇

多項(xiàng)式變異算子方程式如下

vk+1=vk+δ×(uk-lk)

(6)

其中

(7)

u代表[0,1]內(nèi)的任意數(shù),分布指數(shù)為ηm,δ1=(vk-lk)/(uk-lk),δ2=(uk-vk)/(uk-lk),vk是初始最佳個(gè)體位置,vk+1是進(jìn)行變異操作后的最佳個(gè)體位置,uk是位置上限,lk是位置下限。

在圖書館創(chuàng)客空間運(yùn)動(dòng)如火如荼開展的熱潮中，學(xué)者們對創(chuàng)客空間建設(shè)的必要性進(jìn)行了探討，主要分為兩種觀點(diǎn)，一種觀點(diǎn)認(rèn)為建設(shè)創(chuàng)客空間非常必要，但也有學(xué)者從不同角度提出冷思考。

引入多項(xiàng)式變異算子,對麻雀最優(yōu)位置進(jìn)行更新變異,提高了算法跳出局部極值的概率,在搜索后期也進(jìn)一步加快了算法收斂速度,增強(qiáng)了搜索效率。

3.4 改進(jìn)的麻雀搜索算法流程

本文提出的融合精英學(xué)習(xí)與多項(xiàng)式變異的改進(jìn)麻雀算法,首先通過維度空間均勻初始化種群,均勻麻雀種群密度,提高初期搜索效率,接著采用精英學(xué)習(xí)策略,拓展發(fā)現(xiàn)者的搜索范圍,增強(qiáng)算法的全局尋優(yōu)能力,最后在麻雀最優(yōu)位置引入多項(xiàng)式變異算子,進(jìn)一步降低算法陷入局部最優(yōu)解的概率,增強(qiáng)算法尋優(yōu)性能。通過多策略的引入有效的改進(jìn)了算法搜索能力的不足,在搜索效率和可靠性上有進(jìn)一步增強(qiáng),同時(shí)也提高了獲得全局最優(yōu)解的概率。具體步驟如下:

1)種群初始化。對種群數(shù)目,迭代次數(shù)和上下界進(jìn)行初步設(shè)置。

2)通過維度空間均勻初始化種群,使麻雀位置重新進(jìn)行分布。

3)計(jì)算各只麻雀的適應(yīng)度值,找出當(dāng)前最優(yōu)適應(yīng)度值和最差適應(yīng)度值,以及相對應(yīng)的位置。

4)從適應(yīng)度值較優(yōu)的麻雀中,選取部分麻雀作為發(fā)現(xiàn)者,按照式(5)更新位置。

5)余下麻雀作為跟隨者,按照式(2)更新位置。

6)從麻雀中隨機(jī)選擇部分麻雀作為警戒者,按照式(3)更新位置。

7)選擇多項(xiàng)式變異對當(dāng)前最優(yōu)解進(jìn)行擾動(dòng),產(chǎn)生新解并進(jìn)行對比,選取最優(yōu)位置。

8)判斷是否達(dá)到結(jié)束條件,若是,則進(jìn)行下一步,否則跳轉(zhuǎn)步驟2)。

9)程序結(jié)束,輸出最優(yōu)結(jié)果。

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

4.1 參數(shù)及環(huán)境設(shè)置

本文采用了8個(gè)標(biāo)準(zhǔn)測試函數(shù)來對ISSA算法的改進(jìn)效果來進(jìn)行分析驗(yàn)證,為進(jìn)一步檢驗(yàn)改進(jìn)后的具體效果,加入了混沌麻雀搜索優(yōu)化算法(CSSA)[12],原麻雀搜索算法(SSA),粒子群算法(PSO)與灰狼算法(GWO)進(jìn)行對比實(shí)驗(yàn)。為了兼顧公平與效率,根據(jù)以往經(jīng)驗(yàn),所有算法的種群規(guī)模都設(shè)置為20,種群迭代次數(shù)為200。各個(gè)基準(zhǔn)測試函數(shù)如表1。前6個(gè)函數(shù)維度設(shè)為30,單峰函數(shù)為F1-F4,多峰函數(shù)為F5-F6,剩余2個(gè)函數(shù)為不同定維函數(shù)。每個(gè)算法獨(dú)立運(yùn)行30次,計(jì)算出各算法的最優(yōu)值、平均值、標(biāo)準(zhǔn)差。三項(xiàng)指標(biāo)用來檢驗(yàn)算法的尋優(yōu)能力、尋優(yōu)速度及穩(wěn)定性。算法優(yōu)化對比實(shí)驗(yàn)結(jié)果如表2。

表1 測試函數(shù)表

4.2 結(jié)果分析

從表2的測試結(jié)果可以看出,相較于原算法,改進(jìn)算法的尋優(yōu)效果有顯著性地提升,更容易找到最優(yōu)解且求解效率更高。在前四個(gè)單峰測試函數(shù)中,ISSA算法地各個(gè)指標(biāo)都相對很好,對比于其它算法在求解速度和精度上都有很好地效果,且更容易找到最優(yōu)解;在中間兩個(gè)多峰測試函數(shù)中,ISSA算法在F5函數(shù)上的表現(xiàn)有些許提升,在F6函數(shù)上提升效果更為明顯,說明改進(jìn)算法還是有一定的優(yōu)化效果和穩(wěn)定性。在最后兩個(gè)定維測試函數(shù)中,ISSA算法在各方面的表現(xiàn)都比較突出,能更快更好的找到全局最優(yōu)解,驗(yàn)證了改進(jìn)的有效性。綜合數(shù)據(jù)來看,CSSA算法的具有一定的改進(jìn)效果,后面還有優(yōu)化空間;PSO的指標(biāo)數(shù)據(jù)不太穩(wěn)定,尋優(yōu)速度較慢;GWO尋優(yōu)速度較快,但尋優(yōu)精度極差,易陷入局部最優(yōu)。由此可以看出,維度空間均勻初始化提升了算法初始的求解效率,精英學(xué)習(xí)策略和多項(xiàng)式變異的引入使得算法在擺脫局部極值的問題上有很好的改進(jìn)效果。

4.3 算法收斂曲線對比分析

為了清楚的表現(xiàn)出各個(gè)算法在不同測試函數(shù)的收斂效果,根據(jù)生成數(shù)據(jù)繪制了相關(guān)的算法收斂曲線。如圖1所示,一共有8個(gè)基準(zhǔn)測試函數(shù)的收斂曲線圖,坐標(biāo)中的橫軸和縱軸分別表示迭代次數(shù)和適應(yīng)度函數(shù)值。

圖1 各算法收斂效果對比圖

從對比圖中可以看出,ISSA算法的收斂效果對比較為明顯,在原有算法的基礎(chǔ)上很大的提升,相比于其它算法,在收斂速度和穩(wěn)定性上也具有很好的效果,更容易跳出局部極值的困擾?？梢钥闯?改進(jìn)方法的引入具有良好的優(yōu)化效果,以上數(shù)據(jù)也進(jìn)一步驗(yàn)證了改進(jìn)方案的有效性。

4.4 Wilcoxon秩和檢驗(yàn)

僅憑最優(yōu)值,平均值和標(biāo)準(zhǔn)差這三個(gè)指標(biāo)不足以體現(xiàn)出ISSA算法與其它算法的優(yōu)勢,為兼具公平性,本文采用Wilcoxon秩檢驗(yàn)的方法對于改進(jìn)算法進(jìn)行合理性評估。為了驗(yàn)證ISSA算法與其它算法是否具有顯著的差異性,在P=0.05時(shí)對結(jié)果進(jìn)行檢驗(yàn)。如果P<0.05,可以認(rèn)定為拒絕原假設(shè),說明所對比的兩種算法具有顯著的差異性;如果P>0.05,就可以認(rèn)定為接受其原假設(shè),說明所對比的兩種算法沒有顯著的差異性,也就是代表兩種算法的優(yōu)化效果相當(dāng),這里用N/A表示。具體結(jié)果如表3所示。

表3 Wilcoxon秩和檢驗(yàn)P值

通過表3可以得知,ISSA算法與其它對比算法之間確實(shí)具有顯著的差異性,也同時(shí)體現(xiàn)了改進(jìn)算法的先進(jìn)性。

4.5 策略有效性檢驗(yàn)

為了更直觀的展示改進(jìn)算法的優(yōu)化效果,分析檢驗(yàn)策略的有效性,根據(jù)實(shí)驗(yàn)數(shù)據(jù)繪制了算法個(gè)體位置分布圖。經(jīng)過綜合考慮,本文選用了F1測試函數(shù)對原算法和改進(jìn)算法進(jìn)行對比。圖2和圖3分別為SSA算法和ISSA算法的個(gè)體位置分布圖。

圖2 SSA算法個(gè)體分布圖

圖3 ISSA算法個(gè)體分布圖

從圖2可以看出,原算法的個(gè)體位置分布比較分散,個(gè)體收斂速度較慢,在個(gè)體尋優(yōu)過程中不能快速有效的找到最優(yōu)位置,尋優(yōu)性能有待提升。

對比于圖2,圖3中改進(jìn)算法的優(yōu)化效果有明顯提升。相比于原算法,改進(jìn)算法的個(gè)體位置分布比較集中,個(gè)體收斂速度加快,說明所采用的維度空間初始化操作確實(shí)加快了種群的搜索效率,節(jié)約了時(shí)間。在個(gè)體尋優(yōu)過程中,改進(jìn)算法很快的找到了個(gè)體的最優(yōu)位置,同時(shí)多數(shù)集中在最優(yōu)區(qū)域,表明精英學(xué)習(xí)策略的有效性,也證明了多項(xiàng)式變異確實(shí)有效的提高了獲得最優(yōu)解的概率,增強(qiáng)了算法的性能。

4 結(jié)束語

智能算法的優(yōu)化問題是算法研究的一大熱點(diǎn),在對麻雀搜索算法的研究中,為改善SSA算法的搜索效率和解決易陷入局部最優(yōu)的問題,本文提出了融合精英學(xué)習(xí)與多項(xiàng)式變異的改進(jìn)麻雀算法。首先,該算法利用了維度空間對種群進(jìn)行均勻初始化,平衡了種群分布密度,提高了初期搜索效率;接著,通過引入精英學(xué)習(xí)策略改進(jìn)了發(fā)現(xiàn)者的搜索方式,有效地提升了算法的全局搜索能力,使得搜索范圍更加廣闊;最后,多項(xiàng)式變異的引入對最優(yōu)位置進(jìn)行了選擇性優(yōu)化,提高了種群跳出局部最優(yōu)的概率,增強(qiáng)了算法的尋優(yōu)性能。通過算法性能測試分析可知,通過采用以上策略,有效地改善了麻雀搜索算法的搜索效率并且在一定程度上提高了算法的全局尋優(yōu)能力,最終也進(jìn)一步驗(yàn)證了ISSA算法的優(yōu)化效果。在后面的研究中,將重點(diǎn)關(guān)注于把改進(jìn)算法應(yīng)用到工程實(shí)踐中,發(fā)揮智能算法的優(yōu)點(diǎn)。