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

崔建弘，林海霞，呂曉華，張衛娟

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

0 引 言

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

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

1 灰狼優化算法GWO

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

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

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

(1)

(2)

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

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

(3)

(4)

(5)

收斂因子a定義為

a=2-2×t/Tmax

(6)

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

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

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

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

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

(4)whilet

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

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

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

(8)t=t+1

(9)end while

(10)返回α狼為最優解

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

2 改進灰狼優化算法：CODEGWO

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

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

(7)

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

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

(8)

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

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

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

(9)

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

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

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

(10)

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

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

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

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

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

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

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

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

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

(11)

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

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

(12)

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

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

(13)

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

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

(14)

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

2.3 個體擾動機制

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

(15)

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

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

X=X×Dop

(16)

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

圖1 CODEGWO算法的完整執行流程

3 實驗分析

3.1 實驗環境搭建

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

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

3.2 實驗結果分析

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

表1 標準測試函數

表2 算法的尋優結果

表2(續)

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

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

4 結束語

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

圖2 算法的收斂曲線

表3 不同改進思路的影響