王 偉, 何東之

(北京工業(yè)大學(xué) 信息學(xué)部,北京 100124)

隨著科技的發(fā)展與計(jì)算領(lǐng)域的深入研究,生活中出現(xiàn)了許多復(fù)雜的優(yōu)化問(wèn)題。受一些生物種群活動(dòng)的啟發(fā),研究人員提出了一系列群智能算法,為解決復(fù)雜的優(yōu)化問(wèn)題提供了新的解決方案[1]。這些算法因其具有計(jì)算方法簡(jiǎn)單、運(yùn)算速度快,并且可用于解決各類(lèi)優(yōu)化問(wèn)題而受到人們的關(guān)注,目前已提出的群智能算法包括:蟻群優(yōu)化(ant colony optimization, ACO)算法[2]、粒子群優(yōu)化(particle swarm optimization,PSO)算法[3]、差分進(jìn)化(differential evolution,DE)算法[4]和人工蜂群(artificial bee colnony,ABC)算法[5]等。

文獻(xiàn)[6]提出了灰狼優(yōu)化(grey wolf optimization,GWO)算法。GWO模擬了灰狼的種群活動(dòng),具有與其他群智能算法相同的特點(diǎn),如原理簡(jiǎn)單、算法參數(shù)少、局部搜索能力強(qiáng)等。但與其他群智能算法不同的是,該算法考慮了種群中的社會(huì)階層,更大程度上模仿了生物種群所具有的特性。目前,GWO已成功應(yīng)用于經(jīng)濟(jì)調(diào)度[7]、組合優(yōu)化[8]、特征選擇[9]、分類(lèi)[10]、聚類(lèi)[11]等領(lǐng)域的優(yōu)化問(wèn)題。此外,GWO的多目標(biāo)優(yōu)化[12]及其應(yīng)用[13-14]也取得了一定的研究成果。

但是,基本的GWO算法除了具有許多優(yōu)點(diǎn)外,還存在收斂速度慢、局部停滯不前的缺點(diǎn)。文獻(xiàn)[15]為提高GWO算法在解決多峰值的高維度問(wèn)題時(shí)的搜索精度和收斂速度, 引入了隨機(jī)調(diào)整的收斂因子;文獻(xiàn)[16]發(fā)現(xiàn)GWO算法對(duì)搜索空間中的坐標(biāo)原點(diǎn)具有傾向性,提出了一種對(duì)坐標(biāo)原點(diǎn)不敏感、可以動(dòng)態(tài)調(diào)整的增強(qiáng)型灰狼優(yōu)化算法;文獻(xiàn)[17]提出錦標(biāo)賽法、比例法和普遍抽樣法等5種改進(jìn)的選擇策略來(lái)優(yōu)化GWO算法。

針對(duì)算法容易陷入局部最優(yōu)和后期收斂速度慢的問(wèn)題,本文提出了一種改進(jìn)的基于非線(xiàn)性控制因子和遺傳變異的GWO算法(grey wolf optimization algorithm based on the nonlinear control factor and genetic variation,NGGWO)。首先提出一種非線(xiàn)性策略來(lái)替代原有的線(xiàn)性策略，即基于余弦函數(shù)的非線(xiàn)性收斂方法,提高算法的探索能力；其次將變異策略引入算法用來(lái)改進(jìn)算法容易陷入局部最優(yōu)的問(wèn)題。

1 基本的GWO算法

在GWO算法中,提出使用α、β、δ3種最優(yōu)解來(lái)模仿狼群社會(huì)中的首領(lǐng),其他解被認(rèn)為是ω。其中,α為適應(yīng)度值最好的解決方案,其次是β,最后是δ。GWO算法通過(guò)下式來(lái)建立包圍機(jī)制的數(shù)學(xué)建模,即

X(t+1)=Xp(t)-AD

(1)

D=|CXp(t)-X(t)|

(2)

其中:t為當(dāng)前迭代次數(shù);Xp(t)為獵物的位置;X(t)為灰狼個(gè)體的位置;A、C為隨機(jī)系數(shù)。A、C計(jì)算公式為:

A=2ar1-a

(3)

C=2r2

(4)

其中:a在迭代過(guò)程中從2到0線(xiàn)性遞減;r1、r2為[0,1]之間的隨機(jī)數(shù)。

為實(shí)現(xiàn)狼群圍捕機(jī)制的數(shù)學(xué)模型,算法中通過(guò)α、β、δ的位置來(lái)更新其他個(gè)體的位置,即

Dα=|C1Xα-Xi|

(5)

Dβ=|C2Xβ-Xi|

(6)

Dδ=|C3Xδ-Xi|

(7)

X1=Xα-A1Dα

(8)

X2=Xβ-A2Dβ

(9)

X3=Xδ-A3Dδ

(10)

Xi(t+1)=(X1+X2+X3)/3

(11)

其中:Xα、Xβ、Xδ分別為α、β、δ的位置;Xi為當(dāng)前迭代中的第i個(gè)灰狼的位置。

2 改進(jìn)的GWO算法

2.1 基于余弦函數(shù)的非線(xiàn)性收斂策略

群智能算法普遍存在對(duì)探索與開(kāi)發(fā)的平衡問(wèn)題。探索是算法在求解空間內(nèi)尋找最優(yōu)解的能力;開(kāi)發(fā)是算法根據(jù)現(xiàn)有結(jié)果進(jìn)一步尋優(yōu)的能力。當(dāng)然,每種群智能算法都有用于平衡探索與開(kāi)發(fā)能力的控制因子。在GWO算法中,當(dāng)|A|>1時(shí),具有較強(qiáng)的探索能力;當(dāng)|A|≤1時(shí),具有較強(qiáng)的開(kāi)發(fā)能力。因此,根據(jù)(3)式可以看出,控制因子a有著平衡探索與開(kāi)發(fā)能力的作用。

在基本的GWO算法中,控制因子a隨著迭代次數(shù)的增加從2線(xiàn)性遞減到0。但是在現(xiàn)實(shí)問(wèn)題中,若沒(méi)有進(jìn)行更為全面的探索,則可能使算法陷入局部最優(yōu),甚至?xí)霈F(xiàn)過(guò)早收斂的情況。因此,為了增加算法的探索能力,本文提出一種基于余弦的非線(xiàn)性策略對(duì)a進(jìn)行改進(jìn),計(jì)算公式為:

a=(aini-afin)cos(kπ/2)+μ

(12)

其中:k=t/T,t為當(dāng)前迭代次數(shù),T為算法的總迭代次數(shù);為了保證a的取值范圍不變,aini、afin分別為2、0;μ∈[-1,1]為隨機(jī)因子,用于改變?cè)械钠交€(xiàn)。

2.2 基于遺傳變異的搜索策略

在基本的GWO算法中,狼群中的3個(gè)最優(yōu)個(gè)體的位置確定后,它們將引領(lǐng)狼群進(jìn)行下一次的搜索行動(dòng)。但是,如果算法已經(jīng)陷入局部最優(yōu),那么隨著迭代次數(shù)的增加,其他個(gè)體將會(huì)向局部最優(yōu)靠攏,將導(dǎo)致算法求得的結(jié)果是局部最優(yōu)而非全局最優(yōu)。因此,提出一個(gè)可以有效幫助GWO算法跳出局部最優(yōu)的改進(jìn)策略尤為重要。

本文為了提高算法避免局部最優(yōu)的能力,在遺傳算法中的變異策略的啟發(fā)下,提出了通過(guò)變異策略改進(jìn)GWO算法的搜索策略,采用Logistic混沌映射的思想來(lái)產(chǎn)生變異個(gè)體,計(jì)算公式如下:

Xi=μXi-1(1-Xi-1)

(13)

其中:Xi為混沌變量X的第i維變量;μ∈[0,4]。為保證X混沌的特性,一般將μ設(shè)定為趨近于4的值。

在根據(jù)混沌變量X得到變異個(gè)體后,將其與原個(gè)體比較,最終保留具有更優(yōu)解決方案的個(gè)體。(13)式主要是根據(jù)Logistic混沌映射的特性來(lái)幫助算法產(chǎn)生具有不可預(yù)測(cè)的變異體。假如算法正處于局部最優(yōu)的困境中,但變異體具有更優(yōu)方案,這將有助于算法走出極值區(qū)域,并且可以幫助算法避免過(guò)早收斂。

2.3 NGGWO的算法流程

將非線(xiàn)性控制策略與新的搜索策略相結(jié)合,本文提出NGGWO,算法流程如圖1所示。NGGWO算法初始化種群的時(shí)間復(fù)雜度為O(N),更新最優(yōu)個(gè)體需要的迭代時(shí)間為O(T),變異次數(shù)為O(m)。因此NGGWO的時(shí)間復(fù)雜度為O(T)。

圖1 NGGWO算法流程

3 數(shù)值實(shí)驗(yàn)與分析

3.1 測(cè)試函數(shù)與參數(shù)設(shè)置

在實(shí)驗(yàn)中選用的測(cè)試函數(shù)見(jiàn)表1所列。

表1 測(cè)試函數(shù)

表1中各個(gè)測(cè)試函數(shù)的最優(yōu)值均為0?；鶞?zhǔn)測(cè)試函數(shù)主要分為單峰值(F1～F8)和多峰值(F9～F18)2組。

單峰值函數(shù)有且僅有1個(gè)最優(yōu)值,不存在多個(gè)極值,適合檢測(cè)算法的局部搜索能力,也就是開(kāi)發(fā)能力。與此相反,多峰值函數(shù)具有多個(gè)局部最優(yōu)解,便于檢測(cè)算法的全局探索能力和避免局部最優(yōu)的能力。為了保證實(shí)驗(yàn)的公平性,統(tǒng)一設(shè)定GWO與NGGWO的共有參數(shù)。

與實(shí)驗(yàn)內(nèi)容相關(guān)的GWO代碼均在Matlab R2014a中進(jìn)行編碼,所有實(shí)驗(yàn)都是在同一臺(tái)電腦上完成,該電腦的配置為:Windows10 系統(tǒng)、Intel(R) Core(TM) i5-8300H CPU @ 2.30 GHz 、8.00 GB內(nèi)存。

3.2 新算法與基本GWO算法的差異性分析

實(shí)驗(yàn)的問(wèn)題維度分別設(shè)置為30、60,其他參數(shù)一致。對(duì)每個(gè)測(cè)試函數(shù)計(jì)算30次,2組測(cè)試實(shí)驗(yàn)結(jié)果見(jiàn)表2、表3所列。表2、表3中展示了計(jì)算結(jié)果的均值(Mean)和方差(Std),數(shù)據(jù)格式是Mean (Std);pW表示通過(guò)Wilcoxon檢驗(yàn)得到的p值。

何謂小說(shuō)家？畢飛宇有個(gè)有趣的說(shuō)法，他說(shuō)小說(shuō)家就是身體倍兒棒的人，他的眼力好，旁人能看厘米，他能看毫米；旁人能聽(tīng)十米，他能聽(tīng)一里；旁人能辨五味，他能辨千滋百味。他說(shuō)的是莫言，是作家那超人的感受力。不過(guò)，黃金明并不是莫言式的作家，他不是那種用身體寫(xiě)作的人，他是用思想寫(xiě)作的小說(shuō)家。他沒(méi)有用耳目口鼻讓世界變得五光十色、五味雜陳萬(wàn)花筒般旋轉(zhuǎn)起來(lái)，但他始終探索一種必須用宏大的思想坐標(biāo)和敏銳的心智結(jié)構(gòu)才能理解的先鋒性十足的智性小說(shuō)。

表2 30維度的實(shí)驗(yàn)結(jié)果

從表2可以看出,在問(wèn)題維度為30時(shí),2個(gè)算法均在函數(shù)F15上取得了最優(yōu)值。此外,GWO算法在函數(shù)F12上也取得了較好的值。但是,在所有測(cè)試函數(shù)中,NGGWO算法僅在函數(shù)F12的計(jì)算結(jié)果上處于劣勢(shì)。

從表3可以看出,在問(wèn)題維度為60時(shí),GWO算法僅在函數(shù)F12上取得了較好的結(jié)果。在其他測(cè)試函數(shù)上,NGGWO的計(jì)算精度優(yōu)于GWO。

表3 60維度的實(shí)驗(yàn)結(jié)果

為了客觀地檢驗(yàn)NGGWO算法與GWO算法的性能差異,采用Wilcoxon符號(hào)秩檢驗(yàn)方法來(lái)檢驗(yàn)2個(gè)算法在不同維度上是否具有明顯的差異,并在表2、表3的最后列出了計(jì)算結(jié)果。

從表2、表2可以看出,根據(jù)2組實(shí)驗(yàn)結(jié)果得到的pW值分別為0.002 3和0.001 4。2種情況的pW值都小于5%的顯著性水平。這意味著NGGWO與GWO算法的性能具有顯著性的差異。因此,在求解精度上,NGGWO算法優(yōu)于GWO算法。

除了算法的計(jì)算精度,算法的收斂能力也是算法的性能表現(xiàn)。單峰值測(cè)試函數(shù)和多峰值測(cè)試函數(shù)的收斂曲線(xiàn)如圖2、圖3所示。為了更好地區(qū)分不同維度下算法的曲線(xiàn),以虛線(xiàn)表示問(wèn)題維度為30時(shí)的收斂曲線(xiàn),以實(shí)線(xiàn)代表維度為60時(shí)的收斂曲線(xiàn)。

從圖2可以看出,相比于GWO算法,NGGWO算法在整個(gè)算法迭代過(guò)程的早期所得到的計(jì)算精度較低,而在迭代后期曲線(xiàn)會(huì)呈直線(xiàn)趨勢(shì)快速下降并且比GWO的精度更高。其主要原因是受到NGGWO算法中的非線(xiàn)性控制參數(shù)a的影響。在算法迭代前期,控制參數(shù)a提高了算法早期的全局探索能力,種群中的個(gè)體沒(méi)有聚集在最優(yōu)解的周?chē)?。在后?NGGWO中的控制參數(shù)a慢慢變小,所有個(gè)體開(kāi)始向最優(yōu)解靠攏,從而加快了算法的收斂。

圖2 NGGWO與GWO在單峰值函數(shù)上的求值曲線(xiàn)

圖3 NGGWO與GWO在多峰值函數(shù)上的求值曲線(xiàn)

從圖3可以看出,多峰值測(cè)試函數(shù)在曲線(xiàn)收斂的情況與單峰值測(cè)試函數(shù)類(lèi)似。在迭代早期,NGGWO算法的收斂效果一般沒(méi)有初始的GWO效果好，在迭代后期加快了收斂,并取得較好的結(jié)果。

值得注意的是,測(cè)試函數(shù)F9、F11和F14的曲線(xiàn)圖上可以看出,GWO的求值曲線(xiàn)很快趨近于水平,NGGWO算法有效地避免了算法過(guò)早收斂的情況,并取得了更精確的結(jié)果。其主要原因是NGGWO算法增加了算法對(duì)于局部停滯的改進(jìn)方案,驗(yàn)證了文中提出的非線(xiàn)性控制參數(shù)策略與變異策略的有效性。

3.3 新算法與其他GWO改進(jìn)算法差異性分析

為了更好地驗(yàn)證NGGWO算法性能,本文引入3種較新的GWO改進(jìn)算法來(lái)進(jìn)行算法的性能分析,分別是IGWO[15]、EGWO[16]、TGWO[17]。測(cè)試函數(shù)的問(wèn)題維度設(shè)置為30,其他參數(shù)不變。此外,EGWO所特有的權(quán)重系數(shù)分別設(shè)置為ω1=0.5,ω2=0.3,ω3=0.2其中,ω1為α的權(quán)重系數(shù);ω2、ω3分別為β、δ的權(quán)重系數(shù)。實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表4所列。表4中,pF為通過(guò)Friedman檢驗(yàn)的到的p值;R為對(duì)實(shí)驗(yàn)數(shù)據(jù)以秩的形式升序排序后所得到的平均排名;pB為通過(guò)Bonferroni檢驗(yàn)得到的p值。

從表4可以看出,NGGWO算法在18個(gè)測(cè)試函數(shù)上的結(jié)果最好。在其他3個(gè)改進(jìn)的算法中,相比于NGGWO算法,只有TGWO算法在測(cè)試函數(shù)F3～F5和F11～F13的實(shí)驗(yàn)結(jié)果上具有一定的競(jìng)爭(zhēng)力。而IGWO與EGWO算法在所有測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果都與NGGWO算法的結(jié)果相差甚多。

為了更好地檢驗(yàn)NGGWO算法與其他算法的性能差距,本文進(jìn)行了2組一對(duì)多形式的非參數(shù)比較檢驗(yàn),校驗(yàn)后的數(shù)據(jù)也見(jiàn)表4所列。通過(guò)Friedman檢驗(yàn)用來(lái)比較4個(gè)算法之間是否具有顯著性差異。

從表4可以看出,pF遠(yuǎn)小于5%的顯著性水平。這意味著4個(gè)算法的性能完全不同。為了更好地檢驗(yàn)它們之間的差異,采用Bonferroni檢驗(yàn)進(jìn)行事后檢驗(yàn),它主要是根據(jù)競(jìng)爭(zhēng)算法之間排名來(lái)校正檢驗(yàn)結(jié)果。

根據(jù)R的數(shù)據(jù)可以看出,NGGWO的排名高于其他3個(gè)算法,并且3組pB的值都小于5%的顯著性水平,這意味著NGGWO分別與其他3個(gè)算法之間具有顯著的差異。

表4 4個(gè)競(jìng)爭(zhēng)算法的實(shí)驗(yàn)結(jié)果

4 結(jié) 論

本文提出了一種改進(jìn)的灰狼優(yōu)化算法,其改進(jìn)主要包括2個(gè)部分:首先提出了一種非線(xiàn)性控制參數(shù)a,用于平衡算法的探索和開(kāi)發(fā)能力;其次提出了一種基于遺傳變異的搜索策略,用于幫助算法解決局部停滯問(wèn)題。通過(guò)2組實(shí)驗(yàn)分別將新算法與GWO、IGWO、EGWO、TGWO進(jìn)行比較。第1組實(shí)驗(yàn)分析了NGGWO算法與GWO算法在計(jì)算精度上的差異,并通過(guò)曲線(xiàn)圖更直觀地展示了2個(gè)算法的迭代過(guò)程。第2組實(shí)驗(yàn)將NGGWO與IGWO、EGWO、TGWO算法進(jìn)行性能差異性評(píng)估。實(shí)驗(yàn)結(jié)果表明:相比于GWO算法,本文提出的NGGWO算法能夠更好地解決局部停滯問(wèn)題,算法的計(jì)算精度更高;相比于其他3個(gè)改進(jìn)的競(jìng)爭(zhēng)算法,NGGWO算法的計(jì)算精度也具有顯著的優(yōu)勢(shì)。