個體擾動的混沌對立學習與差分進化灰狼算法

崔建弘，林海霞，呂曉華，張衛(wèi)娟

(河北工程技術(shù)學院 人工智能與大數(shù)據(jù)學院，河北 石家莊 050000)

0 引 言

受灰狼捕食行為的啟發(fā)，學者Mirjalili提出一種新型群體智能算法：灰狼優(yōu)化算法GWO[1]?；依莾?yōu)化算法參數(shù)依賴性更小、模型更簡單，尋優(yōu)性能更好。研究表明，該算法比粒子群算法PSO、差分進化算法DE、引力搜索算法GSA具有更好的求解精度和穩(wěn)定性，已廣泛應用于特征子集選取[2]、電力系統(tǒng)優(yōu)化[3]、作業(yè)車間調(diào)度[4]、WSN節(jié)點部署[5]、機器人路徑規(guī)劃[6]和圖像分割[7]等研究領(lǐng)域。然而，GWO算法的不足在于其性能受多個因素的影響，如：初始種群選取不當可能導致無法收斂至最優(yōu)解；全局搜索與局部開發(fā)會影響算法收斂速度，過多全局搜索可能導致無法找到最優(yōu)解，過多開發(fā)又可能使算法效率變低、陷入局部最優(yōu)。此外，種群多樣性是影響GWO性能的另一因素，若多樣性較差，表明個體會在小范圍內(nèi)密集匯聚，可能導致局部收斂；若多樣性較好，則表明個體在廣闊區(qū)域內(nèi)較為分散，又會導致算法收斂速度變慢。因此，該算法的優(yōu)化問題需要綜合考慮多因素影響。

相關(guān)研究中，文獻[8]利用萊維飛行策略對GWO進行改進，增強了全局搜索能力。文獻[9]利用指數(shù)衰減函數(shù)設計了改進算法MGWO，利用協(xié)同參數(shù)估計GWO的最優(yōu)參數(shù)值。文獻[10]引入非線性調(diào)節(jié)模塊控制GWO的參數(shù)，并利用對立學習進行種群初始化，但算法在高維度情形下無法收斂。文獻[11]設計了結(jié)合混沌與對立學習的混合GWO算法，分別利用混沌進行種群初始化，利用對立學習增強全局搜索。文獻[12]將粒子群優(yōu)化PSO與GWO進行結(jié)合，利用PSO進行初始種群選擇，GWO則進行位置更新。文獻[13]則利用鯨魚算法WOA改進了GWO的初始種群。文獻[14]利用布谷鳥搜索算法CS估算了GWO的最優(yōu)參數(shù)，但依然有早熟收斂的不足。文獻[15]設計增強灰狼算法EGWO，利用增強學習策略決定算法的最優(yōu)參數(shù)，然后利用神經(jīng)網(wǎng)絡將搜索代理的狀態(tài)轉(zhuǎn)換為行為規(guī)則，以增強搜索能力，但算法模型過于復雜。多樣性改進方面，現(xiàn)有方法的不足在于僅考慮了單個因素的改進，轉(zhuǎn)換參數(shù)過多，實現(xiàn)不便。本文將提出一種改進的GWO算法，具體改進思路是：引入混沌對立學習生成初始種群，提升初始解的質(zhì)量；引入差分進化的局部搜索機制，改善灰狼的局部開發(fā)與鄰近區(qū)域的搜索能力；引入個體擾動機制增加種群多樣性，改進灰狼的全局搜索能力。最后，通過實驗測試驗證改進算法的尋優(yōu)精度和收斂速度。

1 灰狼優(yōu)化算法GWO

GWO算法模擬的是群狼生活與捕食的行為，屬于面向種群的元啟發(fā)式算法。灰狼群體是一種典型的層次結(jié)構(gòu)模型。群體的領(lǐng)導者為α狼，即第一層次，負責制定整個種群的行為規(guī)則，如捕食、休眠等，所有其它個體必須服從規(guī)則。α狼捕食能力不一定最強，但是整個群體的管理者。第二層次為β狼，負責輔助α狼決策，并服從于α狼。β狼可以向更低層次的種群個體發(fā)布命令，并將反饋信息回傳至α狼。第三層次為δ狼，最低層次為ω狼，δ狼領(lǐng)導ω狼，但又服從于α狼和β狼。δ狼負責種群捕食過程中的邊界守衛(wèi)和種群保護工作?；依侨后w捕食行為分為3個階段：追蹤、包圍和攻擊。需要說明的是，由于灰狼群對于獵物的準確位置并沒有任何先驗知識，即無法準確認知獵物的位置，因此，整個種群中適應度最高的α狼將起到引領(lǐng)種群搜索食物源的作用。通過α狼的引領(lǐng)(以及β狼、δ狼的協(xié)作)，灰狼種群可以朝著最優(yōu)解(獵物位置)的方向逐步靠近，得到全局最優(yōu)解。

初始時，GWO以隨機位置生成初始的灰狼種群位置，α狼、β狼、δ狼則代表當前種群中的最優(yōu)、次優(yōu)及第三優(yōu)解，ω狼則代表剩余解。灰狼種群具備發(fā)現(xiàn)獵物并將獵物進行包圍的能力。以下對GWO的數(shù)學模型進行描述：

令Xp(t)代表當前迭代t時的獵物位置，X(t)為灰狼個體位置，則包圍過程如下

(1)

(2)

式中：r1、r2表示[0,1]內(nèi)的隨機數(shù)，C、A表示系數(shù)矢量，a表示收斂因子，隨迭代從2遞減至0。式(9)表明，灰狼會逐步減小與獵物間的距離，該距離由參數(shù)A、D決定，A逐步減小，而D本身即是與獵物的距離。因此，隨著GWO算法的迭代，灰狼會逐步接近并包圍獵物。

捕食過程中，α狼領(lǐng)導整個種群，β狼、δ狼從旁協(xié)助。通常獵物位置Xp(t)不可預知，但假設α狼、β狼、δ狼對獵物位置有著較為準確的判斷。通過維持α狼、β狼、δ狼的位置信息，低層次的狼群可以根據(jù)α狼、β狼、δ狼的位置信息進行位置更新，具體方式為

(3)

(4)

(5)

收斂因子a定義為

a=2-2×t/Tmax

(6)

式中：Tmax為算法的最大迭代次數(shù)，t為當前迭代次數(shù)。收斂因子會隨著迭代次數(shù)的遞增線性從2遞減至0，其作用是通過自身取值的變化協(xié)調(diào)算法的全局探索能力和局部開發(fā)能力。

式(2)表明，當 |A|<1時，通過減小a可以使灰狼接近獵物，模擬了對獵物的攻擊行為。如前所述，灰狼群體根據(jù)α狼、β狼、δ狼進行位置更新，參數(shù)A、C有助于算法避免局部最優(yōu)。當 |A|>1時，所有灰狼群將遠離當前獵物，尋找更好的獵物。GWO算法執(zhí)行步驟如下：

(1)初始化規(guī)模為N的灰狼種群X以及參數(shù)

(2)計算灰狼個體適應度

(3)按適應度最優(yōu)原則， 決定α狼、β狼、δ狼

(4)whilet

(5) 根據(jù)式(5)更新灰狼個體xi的位置，i=1,2,…,N

(6) 重新計算種群適應度

(7) 更新種群的α狼、β狼、δ狼位置

(8)t=t+1

(9)end while

(10)返回α狼為最優(yōu)解

注：步驟(2)需要計算灰狼個體的適應度，其公式化描述即為實驗分析中選取的基準函數(shù)F(x)，故在此外不作公式描述。

2 改進灰狼優(yōu)化算法：CODEGWO

2.1 融合混沌Tent映射與對立學習的種群初始化

混沌系統(tǒng)是一種非線性偽隨機確定性邊界系統(tǒng)，不具有周期性和收斂性，它的隨機性、對初始條件的敏感性、可遍歷性使其可以生成比隨機方式更好的初始種群。傳統(tǒng)的種群初始化是以均勻分布形式生成隨機序列，混沌序列則具有更好的指向性。常規(guī)混沌系統(tǒng)中，Tent比Logistic映射所生成的序列均勻性更好，改進算法首先利用Tent映射生成初始種群。映射表達式為

(7)

式中：i為種群規(guī)模，i=1,2,…,N，j為混沌序號，j=1,2,…,d，r為隨機數(shù)，且r∈[0,1]，μ為混沌參數(shù)，μ∈[0,2]。u的常規(guī)取值為0.7。首先根據(jù)式(7)計算d個混沌序列di,j， 再對混沌序列作逆映射，即可生成個體位置變量xi,j， 即

xi,j=lj+yi,j×(uj-lj)

(8)

式中： [lj,uj] 表示個體位置xi,j的搜索范圍。

對立學習可以計算一個解的對立解，然后比較兩個解的適應度為種群選取優(yōu)質(zhì)解，該方法可以進一步改進算法的收斂速度，尋找全局最優(yōu)。考慮x為 [l,u] 內(nèi)的一個實數(shù)，x∈[l,u]，l和u分別為問題的上下邊界，則x的對立數(shù)為x′=u+l-x。 矢量x∈RD的對立矢量x’∈RD定義為

x′j=uj+lj-xj,j=1,2,…,d

(9)

式中：lj和uj分別為元素xj∈x的下界和上界。生成對立矢量后，若在適應度上f(x′) 優(yōu)于f(x)， 則選擇對立解x′；否則，依然選擇原始解x。即：初始種群包含的是基于x和x′的最優(yōu)值生成的。

以混沌Tent映射代替均勻分布的初始種群隨機生成方式，利用以下等式結(jié)合混沌映射建立種群X

xi,j=li,j+yi,j×(ui,j-li,j),xi∈X,i=1,2,…,N,j=1,2,…,d

(10)

利用對立學習進一步改進混沌初始種群，計算混沌初始種群X及其對立種群X′的所有個體適應度，從兩個聯(lián)立的種群中選擇適應度最小的N個解作為灰狼優(yōu)化算法的初始種群。

基于混沌Tent映射與對立學習的定義，CODEGWO算法的種群初始化過程如下：

步驟1 在搜索空間中以混沌Tent映射機制初始化規(guī)模為N的灰狼個體位置，作為初始種群X；

步驟2 基于對立學習定義，生成初始種群X中所有灰狼個體位置的對立位置，將對立位置構(gòu)成的種群定義為X′；

步驟3 對比X中原始位置與X′中對立點位置的適應度，保留適應度更大的灰狼個體在初始種群中，得到最終的初始灰狼種群，種群規(guī)模依然為N。

2.2 基于差分進化的位置更新

差分進化是一種面向種群的隨機優(yōu)化方法，與其它進化算法類似，差分進化開始于包含若干目標個體的初始種群矢量，通過進化算子經(jīng)過若干次的種群迭代進化直到達到最大迭代數(shù)。引入變異算子、交叉算子和選擇算子對灰狼個體的位置更新進行改進。

(1)變異算子。變異算子表示如下

vi(t)=xr1(t)+w×(xr2(t)-xr3(t))

(11)

式中：v表示變異解，x表示當前種群中的解，t表示迭代數(shù)，下標r1、r2、r3表示3個[1,N]內(nèi)隨機選擇的相互獨立的整數(shù)，對應于3個不同的個體，w表示變異因子，用于控制兩個個體解之間的差分變化。

(2)交叉算子。個體變異后，利用交叉算子在目標矢量上可以進一步增加種群的多樣性。差分進化在xi和vi上利用交叉算子生成子代個體zi，具體表示為

(12)

式中：rand表示[0,1]間的隨機值，CR表示個體交叉概率。

(3)選擇算子。利用貪婪策略將父代個體與其子代個體進行比較，實現(xiàn)新個體的選擇，具體表示為

(13)

式中：f(z)為矢量z的適應度函數(shù)值。

利用選擇概率P決定灰狼個體是否依據(jù)差分進化策略進行位置。定義xi的選擇概率為其xi的適應度與種群總體適應度間的比例，表示為

(14)

根據(jù)選擇概率P，當前解xi將選擇使用傳統(tǒng)GWO算法或差分進化算法進行個體的位置更新。具體方法是：若P≥rand，rand為[0,1]內(nèi)的隨機數(shù)，則利用GWO算法對當前解xi進行位置更新，即式(3)～式(5)；若P

2.3 個體擾動機制

個體擾動可以增強GWO算法的全局搜索能力。將擾動算子Dop定義為

(15)

式中：Disi,j表示灰狼個體i和j之間的歐氏距離，j是個體i最近的鄰居個體，φ(a,b) 表示區(qū)間[a,b]間的均勻分布的隨機量。根據(jù)擾動算子的定義可知，當兩個灰狼個體相互較為接近時，Dop<1，這將導致灰狼向著初始點收斂。

為了維持灰狼種群的多樣性，在當前種群中利用擾動算子方式如下

X=X×Dop

(16)

改進GWO算法流程如圖1所示，將算法命名為CODEGWO。圖1最左側(cè)方框為種群初始化階段。進行相應參數(shù)初始化后，利用式(10)生成混沌種群X。然后，計算混沌種群X的對立種群X′，并計算種群規(guī)模為2N的所有灰狼個體適應度，選擇X與X′聯(lián)合種群中適應度最優(yōu)的N個個體作為初始種群。種群初始化后，進入圖1的中間方框，確定最優(yōu)的前3個灰狼個體α狼、β狼、δ狼。然后，利用式(14)計算選擇概率P，進入右側(cè)實線方框流程。首先判斷隨機量與選擇概率的大小關(guān)系，若隨機量較大，則執(zhí)行左側(cè)虛線方框中的傳統(tǒng)GWO位置更新機制，根據(jù)式(5)計算個體的新位置；若選擇概率較大，則執(zhí)行左側(cè)虛線方框中的差分進化位置更新機制，執(zhí)行差分進化的變異、交叉和選擇，得到新的個體位置。個體位置更新后，進入下方虛線方框中的個體擾動流程。首先根據(jù)式(15)計算擾動因子，然后根據(jù)式(16)進行個體擾動，提升全局搜索能力。最后，判定是否達到算法最大迭代次數(shù)，若達到，則輸出當前種群的全局最優(yōu)解，即α狼，結(jié)束算法執(zhí)行過程。

圖1 CODEGWO算法的完整執(zhí)行流程

3 實驗分析

3.1 實驗環(huán)境搭建

搭建數(shù)值仿真環(huán)境，以驗證本文算法的有效性。選取目前最為常用的8個標準測試函數(shù)進行數(shù)值仿真，函數(shù)相關(guān)屬性見表1。測試基準函數(shù)分為兩類，函數(shù)F1(x)～F4(x) 為單峰值函數(shù)，可用于評估算法的尋優(yōu)精度和收斂速度。此類函數(shù)在給定的搜索域內(nèi)僅有一個極值解。函數(shù)F5(x)～F8(x) 為多峰值函數(shù)，可用于評估算法避免局部最優(yōu)，到達全局最優(yōu)解的能力。對于連續(xù)多峰值函數(shù)，隨著函數(shù)維度遞增，其局部極值點會呈現(xiàn)指數(shù)級增長，且多峰值函數(shù)在搜索域內(nèi)擁有多個極值點。改進灰狼優(yōu)化算法CODEGWO的相關(guān)參數(shù)中，種群規(guī)模設置為40，算法最大迭代次數(shù)設置為400。仿真實驗執(zhí)行環(huán)境為Intel酷睿i7 CPU 3.0 G，內(nèi)存4 GB，操作系統(tǒng)為WIN10，仿真軟件為Matlab2017。

對比算法方面，選取文獻[9]的基于指數(shù)衰減函數(shù)的改進灰狼優(yōu)化算法MGWO、文獻[10]的非線性調(diào)節(jié)灰狼優(yōu)化算法NOGWO和文獻[16]的非線性收斂因子和動態(tài)權(quán)重策略下的改進灰狼優(yōu)化算法NDWGWO進行性能對比研究，以及本文提出的CODEGWO算法，一共4種算法進行數(shù)值仿真。

3.2 實驗結(jié)果分析

實驗一：表2測試了低維度D=30和高維度D=200/500環(huán)境下4種算法目標函數(shù)的尋優(yōu)結(jié)果。根據(jù)實驗結(jié)果，本文設計的CODEGWO算法在多數(shù)基準函數(shù)的測試下均可以收斂到最優(yōu)值，說明CODEGWO算法無論是對單峰函數(shù)的尋優(yōu)，還是多峰函數(shù)的尋優(yōu)，都擁有較好的穩(wěn)定性。在部分基準函數(shù)(如函數(shù)F4)的測試下并未達到最優(yōu)解，但已經(jīng)接近于最優(yōu)解，且相較于在種對比算法，其尋優(yōu)結(jié)果已經(jīng)是最優(yōu)的。此外，從目標函數(shù)的平均值Mean和標準方差值SD來看，CODEGWO算法在多數(shù)標準測試函數(shù)中也表現(xiàn)更好，說明算法中引入的混沌對立學習種群初始化、差分進化的局部搜索以及個體擾動增強種群多樣性機制是切實有效的。MGWO、NOGWO、NDWGWO這3種算法雖然分別從不同的切入點(種群初始化、個體位置更新、引入種群多樣性)對傳統(tǒng)灰狼優(yōu)化算法GWO進行了相應改進，但其在尋優(yōu)精度和收斂速度等全面性能方面不如CODEGWO算法?？傮w而言，CODEGWO算法的尋優(yōu)成功率普遍優(yōu)于對比算法，面對部分高維函數(shù)測試，對比算法尋優(yōu)成功率較低，說明對于GWO的改進還需要進一步提升對于高維函數(shù)的尋優(yōu)能力。

表1 標準測試函數(shù)

表2 算法的尋優(yōu)結(jié)果

表2(續(xù))

實驗二：圖2是目標函數(shù)維度取值為50時得到的平均適應度收斂曲線。根據(jù)結(jié)果，CODEGWO算法在單峰值函數(shù)和多峰值函數(shù)情況下，達到收斂時的迭代次數(shù)相比另外3種對比算法要更少，說明算法引入的混沌對立學習種群初始化、差分進化的局部搜索以及個體擾動增強種群多樣性機制在灰狼種群覓食過程中可以更好引導灰狼的前進方向，在拓展搜索空間和避免局部最優(yōu)解的同時，有效均衡了局部開發(fā)與全局搜索進程，提升了算法的尋優(yōu)收斂速度。

實驗三：本節(jié)實驗觀察從CODEGWO算法移除一種改進機制對于算法的性能影響。CODEGWO算法一共使用了4種改進機制，包括：在種群初始化中使用混沌Tent映射和對立學習機制、在個體位置更新方面使用差分進行機制以及使用個體擾動機制改善種群多樣性。移除一種改進機制后，保留其它3種改進機制在相應的灰狼優(yōu)化算法中，相應可以生成4種改進算法。第一種算法移除混沌Tent映射，僅利用對立學習生成初始種群，并在個體位置更新上使用差分進化，并做個體擾動，命名算法為R-Tent-GWO，R表示移除Remove。第二種算法移除對立學習機制，僅利用混沌Tent映射生成初始種群，在個體位置更新上使用差分進化，并做個體擾動，命名算法為R-OBL-GWO。第三種算法移除個體位置更新的差分進化機制，以混沌Tent映射和對立學習作種群初始化，利用傳統(tǒng)GWO的位置更新方法，并做個體擾動，命名算法為R-DE-GWO。第四種算法移除個體擾動機制，以混沌Tent映射和對立學習做種群初始化，在個體位置更新方面使用差分進行機制，不做個體擾動，算法命名為R-ID-GWO。表3是總計不同改進思路的5種算法在所有基準函數(shù)測試下得到的目標函數(shù)值的均值、標準差、計算時間以及尋優(yōu)成功率。從比較結(jié)果可以看出，種群初始化中利用的兩種策略性能總體較為接近，而對立學習機制更加能夠提升灰狼算法的尋優(yōu)能力，由于可以引入適應度更高的優(yōu)良個體在初始種群中。相對引入差分進化機制而言，移除個體擾動對于CODEGWO算法的影響更大，由于個體擾動機制可以增強種群多樣性，改進灰狼的全局搜索能力。總體來說，對于初始種群的改進可以大幅提升算法的尋優(yōu)精度，而在位置更新方式的差分進化機制以及個體擾動，則可以進一步加快算法的收斂速度，在避免局部最優(yōu)解上有進一步作用。對于算法的計算時間而言，在大多數(shù)基準函數(shù)中，未移除任一優(yōu)化機制的CODEGWO算法可以得到更高的計算效率，由于該算法的收斂速度更快，可以更快得到更高精度的最優(yōu)解。相對而言，在種群初始化中所作的優(yōu)化可以更好提升算法的尋優(yōu)效率，由于初始解中的優(yōu)良個體對于整個種群的進化方向擁有更好的指向性。差分進化和個體擾動機制對于計算效率的影響較為接近。

4 結(jié)束語

提出一種基于混沌對立學習和差分進化機制的改進灰狼優(yōu)化算法CODEGWO。具體地，引入混沌對立學習策略生成灰狼初始種群，提升初始解的質(zhì)量，加速算法收斂；引入差分進化的局部搜索機制，改善灰狼的局部開發(fā)與鄰近區(qū)域的搜索能力；引入個體擾動機制增加種群多樣性，改進灰狼的全局搜索能力。通過8種標準函數(shù)的測試結(jié)果表明，與同類算法相比，該算法可以有效提升尋優(yōu)精度和收斂速度，均衡改善灰狼優(yōu)化算法的性能。

圖2 算法的收斂曲線

表3 不同改進思路的影響