王 偉, 何東之

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

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

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

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

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

1 基本的GWO算法

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

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

(1)

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

(2)

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

A=2ar1-a

(3)

C=2r2

(4)

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

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

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個灰狼的位置。

2 改進的GWO算法

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

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

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

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

(12)

其中:k=t/T,t為當(dāng)前迭代次數(shù),T為算法的總迭代次數(shù);為了保證a的取值范圍不變,aini、afin分別為2、0;μ∈[-1,1]為隨機因子,用于改變原有的平滑曲線。

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

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

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

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

(13)

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

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

2.3 NGGWO的算法流程

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

圖1 NGGWO算法流程

3 數(shù)值實驗與分析

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

在實驗中選用的測試函數(shù)見表1所列。

表1 測試函數(shù)

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

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

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

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

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

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

表2 30維度的實驗結(jié)果

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

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

表3 60維度的實驗結(jié)果

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

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

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

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

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

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

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

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

3.3 新算法與其他GWO改進算法差異性分析

為了更好地驗證NGGWO算法性能,本文引入3種較新的GWO改進算法來進行算法的性能分析,分別是IGWO[15]、EGWO[16]、TGWO[17]。測試函數(shù)的問題維度設(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ù)據(jù)見表4所列。表4中,pF為通過Friedman檢驗的到的p值;R為對實驗數(shù)據(jù)以秩的形式升序排序后所得到的平均排名;pB為通過Bonferroni檢驗得到的p值。

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

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

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

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

表4 4個競爭算法的實驗結(jié)果

4 結(jié) 論

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