混沌映射與精英高斯擾動的非線性灰狼優化算法

蔡 娟

(廣州科技職業技術大學 信息工程學院，廣東 廣州 510550)

0 引 言

灰狼群體擁有嚴格的社會等級層次關系。頂端為群體領導者，稱α狼，負責關于捕獵、休憩等活動的決策制定。第二層為β狼，可以協助α狼決策制定和其它群體活動。β狼的地位僅次于α狼，其主要職責是α狼與其它低等級狼群的橋梁，負責傳送指令并反饋信息。第三層為δ狼，職責是偵查和放哨，聽從于α狼和β狼。最低層為ω狼，數量最多，可平衡種群內個體間的關系。受這種等級機制和灰狼種群捕食行為的啟發，著名學者Mirjalili提出了一種新型群體智能算法-灰狼優化算法(grey wolf optimization，GWO)[1]。GWO算法依賴參數少、模型簡單，尋優性能更好，比粒子群算法PSO、差分進化算法DE等具有更好的求解精度和穩定性，已廣泛應用于求解最優特征子集[2]、多機電力系統[3]、作業車間調度[4]、WSN節點部署[5]、機器人路徑規劃[6]和圖像分割[7]等領域。然而，傳統GWO依然存在對初始種群分布的依賴、易于陷入局部最優及面對多峰函數優化時難以協調開發與勘探能力的不足。

針對灰狼優化算法的不足，文獻[8]通過個體變異對位置進行更新，利用5種非線性控制參數設計了改進算法。文獻[9]提出基于精英對立學習與混沌擾動融合的混合灰狼優化算法HGWO，可以有效求解高維函數優化問題。文獻[10]結合混沌映射與Cauchy變異策略，改善了初始種群結構及開發與搜索能力均衡。文獻[11,12]均針對收斂因子做了非線性調整，并驗證了策略的有效性，但改進程度比較局部。文獻[13]融合差分進化和GWO，利用差分進化的個體變異和遺傳機制對位置更新進行擾動，有效提升了收斂速度和尋優精度。

以上改進思路雖然可以在某一方面對灰狼優化過程做出相應改進，但在收斂速度、局部開發和全局勘探過程的均衡以及如何避免陷入局部最優、提升尋優精度等綜合性能方面仍然具有較多不足。為了進一步提高灰狼優化算法的尋優精度和收斂速度，本文的主要工作如下：①設計基于混沌Tent映射與對立學習機制的灰狼種群初始化方法，保證初始種群中較優個體的同時，使個體盡可能均勻分布于搜索空間內；②設計非線性收斂因子控制策略，有效均衡局部開發和全局勘探；③引入精英個體高斯擾動機制，在頭狼選取上進行高斯擾動，使算法跳出局部最優。

1 灰狼優化算法GWO

灰狼捕獵由3步構成：追蹤接近獵物→追捕包圍迫使獵物停止→攻擊獵物。

(1)灰狼社會分級

將當前狼群中適應度最高的灰狼個體(即問題解)視為α狼，第二高的灰狼視為β狼，第三高的灰狼視為δ狼，剩余候選者全部視為ω狼。GWO算法中，灰狼的捕獵行為(問題優化過程)由α、β、δ這3頭狼指揮，ω狼跟隨α、β、δ這3頭狼作位置更新。

(2)包圍獵物

捕獵過程中，灰狼包圍獵物的數學模型為

D=|C·Xp(t)-X(t)|

(1)

X(t+1)=Xp(t)-A·D

(2)

式中：t為迭代數，A、C為系數，Xp為獵物位置矢量，X為搜索灰狼位置矢量。式(1)為灰狼與獵物間的距離，式(2)為灰狼位置更新公式。同時

A=2a·rand1-a

(3)

C=2·rand2

(4)

其中，rand1和rand2表示區間[0,1]內的隨機數，作用是增強灰狼搜索移動的隨機性和個體多樣性，a表示收斂系數，定義為與迭代相關的線性關系式

a=2-2t/Tmax

(5)

其中，Tmax表示算法的最大迭代次數。可以看出，收斂系數a會隨著算法迭代線性地從2遞減為0。

(3)狩獵

灰狼捕食過程中，狩獵由α狼指揮，β狼和δ狼參與。對于抽象的搜索空間，灰狼種群通常無法判斷獵物的準確位置(最優解)。為了模擬狩獵行為，可假設α狼、β狼和δ狼已知獵物位置。此時，可保存當前最優的3個解，迫使ω狼依據3個最優解的指導進行位置更新。因此，灰狼狩獵的數學模型為

Dα=|C1·Xα-X|

(6)

Dβ=|C2·Xβ-X|

(7)

Dδ=|C3·Xδ-X|

(8)

其中，Dα、Dβ和Dδ分別為灰狼個體與α、β和δ的間距，Xα、Xβ和Xδ為α、β和δ的當前位置，X為灰狼個體的當前位置

X1=Xα-A1·Dα

(9)

X2=Xβ-A2·Dβ

(10)

X3=Xδ-A3·Dδ

(11)

(12)

其中，式(9)、式(10)、式(11)分別定義了灰狼個體朝α狼、β狼和δ狼前進的步長和方向，式(12)定義灰狼個體最終的更新位置。同時，wi為α狼、β狼和δ狼的權重系數，定義為

(13)

為了模擬灰狼接近獵物的過程，可以逐步減小收斂系數a的取值。相應地，A的波動范圍也將隨著a的取值而降低。換言之，迭代過程中a從2遞減至0時，A將在區間[-2a,2a]內作隨機變化。當A處于[-1,1]時，灰狼的下一位置是當前位置和獵物位置間的任意位置。此外，灰狼主要通過α狼、β狼和δ狼的位置搜索獵物。灰狼之間相互分離搜索獵物，并逐步靠近并攻擊獵物。為了在數學模型上建立灰狼間的分散模型，可以利用大于1或小于-1的A迫使灰狼與獵物背離，使GWO算法具備全局搜索能力。

式(4)表明，C為[0,2]內的隨機值。C相當于灰狼位置對獵物影響的權重。若C>1，表明定義灰狼與獵物間的距離時權重較大；若C<1，表明定義灰狼與獵物間的距離時權重較小。該參數有助于為灰狼優化算法引入更加隨機的行為，便于隨機化的空間搜索并避免局部最優。同時，與參數A相比，C不是線性遞減的，這樣在整個迭代過程中，算法可以提供決策空間中的全局搜索機制。

圖1是灰狼優化算法GWO的完整執行流程。

圖1 傳統GWO算法的流程

2 改進灰狼優化算法CEOGWO

2.1 基于混沌Tent映射與對立學習機制的種群初始化機制

通常智能群體算法的求解過程始于初始種群。初始種群的結構對算法的收斂速度和尋優精度具有重要影響。傳統的GWO算法由于無法借鑒任意先驗知識，以全隨機化方式生成初始種群，但這無法保證初始種群在空間中的均勻分布。

混沌序列呈現規律性、隨機性和遍歷性等特點。與完全隨機化相比，融合混沌的灰狼初始種群具有更好的多樣性。混沌主要通過[0,1]間的映射關系產生混沌序列，再將其轉換至種群個體空間。混沌有很多種，Logistic映射利用最為普遍。但Logistic映射遍歷性較差，對初始參數較敏感，映射點在邊緣位置密度高，中間區域密度較低。而Tent映射比Logistic映射均勻性更好。但Tent映射的混沌序列又存在小周期、不確定周期點的不足。綜合考慮，結合完全隨機化特點，CEOGWO算法將傳統Tent混沌映射中添加隨機變量r/N，得到Tent映射為

(14)

式中：i為種群規模，i=1,2,…,N，j為混沌序號，j=1,2,…,d，r為隨機數，r∈[0,1]，μ為混沌參數，μ∈[0,2]，μ值越大，混沌性能越優。通過式(14)，可得到混沌值di,j， 再將其映射至種群搜索空間，即

xi,j=lbj,min+yi,j×(ubj,max-lbj,min)

(15)

式中： [lbj,min,ubj,max] 為灰狼位置xi,j的上下限范圍。

群體智能算法都是在初始種群結構基礎上尋優的，不斷通過貪婪選擇策略，改善種群個體，尋找全局最優。算法性能與初始種群個體與目標最優的距離直接相關。若隨機初始種群本身離全局最優距離較遠，灰狼尋優可能無法完成。研究結果表明，對立學習機制可以通過同步考慮當前解及其對立解改善候選解的質量，加快算法收斂。因此，在式(14)的混沌Tent映射生成的初始種群基礎上，CEOGWO算法進一步將其對立解也考慮在初始種群中，優化初始種群構成。以下介紹對立學習相關概念。

令x∈[l,u]， 其對立數x’為x’=u+l-x。 令Xi=(xi1,xi2,…,xid) 為d維空間內的候選解，且 (xi1,xi2,…,xid)∈X，xi∈[li,ui]，i=1,2,…,d。 則Xi的對立點為X’i=(x’i1,x’i2,…,x’id)，x’i=ui+li-xi。

令Xi=(xi1,xi2,…,xid) 為d維空間內的候選解，且xi∈[li,ui]，i=1,2,…,d。f(X) 為適應度函數。候選解X’i=(x’i1,x’i2,…,x’id) 為Xi=(xi1,xi2,…,xid) 的對立點。若f(X’i)≥f(Xi) (若適應度值越大，性能越優)，則可以選擇候選解X’i替換Xi；否則，保留Xi。此時，候選解和對立候選解都考慮在初始種群中。

綜上，CEOGWO算法的初始化過程為：

(1)在搜索空間中以式(14)、式(15)表達的混沌Tent映射機制初始化N個灰狼個體，作為初選初始種群IP；

(2)基于對立數與對立點的定義，生成初選初始種群IP中所有灰狼個體的對立位置，將對立位置構成的種群定義為OP；

(3)對比種群IP中原始位置與種群OP中對立點位置的適應度，保留適應度更大的灰狼個體在初始種群中，得到最終的初始灰狼種群FIP，種群規模保持不變，依然為N。

2.2 基于非線性的收斂因子控制機制

灰狼優化算法中，收斂因子a的作用是控制算法的局部開發和全局勘探能力。局部開發強調已知信息對區域精細搜索，決定算法收斂速度；全局勘探則旨在讓灰狼個體搜索更廣闊的搜索空間，避免搜索過程陷入局部最優解，決定算法尋優能力。收斂因子的均衡控制決定了算法收斂速度和尋優精度。根據前文，參數A決定了算法的局部開發和全局勘探能力，而參數A又由收斂因子a決定。由a的計算公式可知，a將隨著迭代次數的增加線性地由2遞減為0。對于灰狼優化算法而言，迭代初期較大a值可以增大灰狼搜索步長，搜索更廣闊的空間，避免尋優過程早熟并過快收斂；迭代后期較小a值可以減小灰狼搜索步長，提升局部精細開發能力，加快算法收斂。然而，兩種搜索類型并不是完全線性切換的，收斂系數的線性遞減并不能實際體現灰狼的復雜搜索過程，尤其出現多峰值情形時，易于陷入局部最優。研究結果表明，非線性的收斂因子控制可以使灰狼獲得更好的尋優性能。本文在CEOGWO算法中設計了以下非線性收斂因子控制機制

(16)

式中：收斂因子a隨當前迭代數t發生變化，afinal為a終值，aini為a初值，Tmax為最大迭代數，ξ>0為非線性調整系數。

根據式(16)可知，在算法迭代初期，收斂因子a衰減較慢，可保持相對較大值，也使得搜索步長相對較大，利于全局搜索；迭代后期收斂因子衰減加快，搜索步長減小，利于提升搜索精度。這種非線性收斂因子控制機制可以有效協調GWO算法的局部開發和全局勘探能力，切換具備自適應性。

2.3 基于精英個體的高斯擾動機制

由灰狼尋優過程可知，搜索過程由當前灰狼種群中適應度最優的3頭灰狼α狼、β狼和δ狼引領。在搜索過程的末期，所有灰狼向決策層的3個頭狼附近區域逼近，此時會缺失群體多樣性，收斂速度明顯變慢或停滯，最終陷入局部最優。為此，CEOGWO算法引入高斯擾動機制，在α狼、β狼和δ狼3個精英個體的選取上利用高斯擾動進行位置更新，使算法搜索跳出局部最優，擴大灰狼的搜索范圍，勘探新的搜索區域。

令d維空間內灰狼種群中適應度最優的3個精英個體分別為Xα=(xα,1,xα,2,…,xα,d)、Xβ=(xβ,1,xβ,2,…,xβ,d) 和Xδ=(xδ,1,xδ,2,…,xδ,d)， 將其位置更新方式定義為

Xbest′(t)=Xbest(t)×(1+τ×G(σ))

(17)

式中：best=α、β、δ，Xbest′(t) 表示經過高斯擾動的精英灰狼個體位置，Xbest(t)表示原始α狼、β狼和δ狼的位置，G(σ)表示服從高斯分布的隨機分布，t為當前迭代次數，τ為擾動強度，且0≤τ≤1，定義為

(18)

式中：N代表灰狼種群規模。

因此，α狼、β狼和δ狼的位置更新方式為

(19)

利用高斯擾動對當前的α狼、β狼和δ狼的選擇進行擾動變異，可以增強3個頭狼跳出局部最優的概率，避免種群向著錯誤的引導方向移動，提升尋優效率。

2.4 算法步驟

CEOGWO算法的執行步驟如下：

步驟1 算法參數初始化，包括種群規模N、收斂因子初值aini和終值afinal、算法最大迭代次數Tmax、非線性調整系數ξ、擾動強度τ。

步驟2 利用2.1節的混沌Tent映射與對立學習機制生成初始化種群，表示為 {X1,X2,…,XN}，N為種群規模。

步驟3 計算所有灰狼個體適應度值 {f(X1),f(X2),…,f(XN)}。 根據適應度對灰狼作降序排列，選擇最優的前3個灰狼保存為種群的α狼、β狼和δ狼，對應位置分別為Xα、Xβ和Xδ。

步驟4 利用2.2節的非線性收斂因子控制機制更新參數a，并相應更新A和C。

步驟5 根據式(12)更新當前種群中每頭灰狼的位置，重新計算灰狼種群所有個體的適應度，選擇適應度最優的3個個體，利用2.3節的精英個體高斯擾動機制，得到新的α狼、β狼和δ狼。

步驟6 終止判斷。若運行次數小于Tmax，返回步驟3執行；否則，返回α狼作為問題最優解。

圖2是CEOGWO算法的完整執行流程。

圖2 CEOGWO算法的執行框架

3 數值仿真分析

3.1 實驗環境

搭建數值仿真環境以驗證本文的CEOGWO算法的有效性。選取最為常用的8個標準測試函數進行數值仿真，相關屬性見表1。測試函數中，單峰值函數f1(x)～f4(x) 可測試尋優精度，多峰值函數f5(x)～f8(x) 可測試全局尋優能力和收斂速度。對于連續多峰值函數，隨著函數維度遞增，其局部極值點會呈現指數級增長。表2給出改進灰狼優化算法的相關參數配置情況。仿真實驗執行環境為Intel酷睿 CPU 3.0 G，內存8 GB，OS為Windows 10，仿真軟件為Matlab 7.1。選取文獻[9]的混合灰狼優化算法HGWO、文獻[10]的非線性參數控制灰狼優化算法NGWO和文獻[13]的基于差分進化的灰狼優化算法DEGWO進行性能對比研究，加上本文算法CEOGWO，一共4種算法進行數值仿真。

3.2 實驗結果分析

實驗一：表3測試了低維度(D=30)和高維度(D=100，500)設置下算法的尋優結果。從結果可以看到，本文的CEOGWO算法在大多數基準的測試下均可以收斂到最優值，說明算法針對單峰函數和多峰函數時具有很好的穩定性和魯棒性。即使部分基準函數測試下沒有得到最優值，依然可以得到非常接近的值，同時也是相對其它幾種算法的全局最優解。此處，從所得到的平均值和標準方差值來看，CEOGWO算法在多數標準測試函數中也得到了更好的表現，這說明算法中所采用的混沌Tent映射、對收斂因子的非線性控制以及對于精英個體的高斯擾動是有效可行的。對比算法HGWO、NGWO和DEGWO雖然分別從不同的切入點對傳統灰狼優化作了改時，但其全面性能方面不如CEOGWO算法。總體來說，CEOGWO算法的尋優成功率普遍優于對比算法，面對部分高維函數測試，對比算法尋優成功率較低，且出現為零的情形，說明改進的GWO的還需要進一步提升對于高維函數尋優的能力。

表1 基準測試函數

表2 CEOGWO算法的參數配置

表3 算法的尋優結果

表3(續)

圖3是維度取值50時測試函數的平均適應度收斂曲線。可以看到，CEOGWO算法在單峰值函數和多峰值函數情況下，達到收斂時的迭代次數相比另外3種算法會更少，算法收斂速度更快，尋優精度更高，這說明混沌Tent映射的種群初始化、收斂因子的非線性控制以及對于精英個體的高斯擾動機制在灰狼種群覓食過程中可以更好的引導灰狼的前進方向，在拓展搜索空間和避免局部最優的同時，有效均衡了局部開發與全局勘探進程，提升了尋優收斂速度。

實驗二：分析CEOGWO算法中的3種改進思路對于傳統GWO算法的改進情況，結果為20次模擬實驗的均值結果。依然利用表1中的8種基準函數時行測試，測試維度選取為30維。將僅利用混沌Tent映射與對立學習的種群初始化機制下的灰狼算法命名為CGWO算法，將僅利用非線性收斂因子控制機制的灰狼算法命名為NLGWO算法，將僅利用精英個體高斯擾動的灰狼算法命名為GGWO算法。灰狼算法的參數配置依然延用表2的參數，表4是數值仿真結果。從比較結果可以看出，對于初始種群的改進策略下的CGWO和對于收斂因子的改進策略下的NLGWO算法對于性能提升的改變略有局限，基于精英個體的高斯擾動策略下的GGWO算法可以得到更好的尋優性能和精度，在多數基準函數的測試下還是可以求解全局最優值的。前兩種算法性能較為相似，但其收斂速度受到一定影響，性能提升有限。灰狼優化算法中，精英個體引導灰狼種群的整體尋優方向，因此，GGWO算法中對于精英個體的位置更新擾動可以更好的引領種群的尋優進度，從而更快的收斂于全局最優解處。

實驗三：分析了非線性收斂因子對CEOGWO算法性能的影響。根據式(15)的定義可知，收斂因子的取值主要由其初值aini和終值afinal以及非線性調整系數ξ的取值決定。收斂因子決定了改進灰狼算法的局部開發與全局勘探的均衡能力，本部分將分別分析取不同的初終值對和非線性調整系數時算法尋優性能的變化。表5約出5對收斂因子初終值對下8個基準函數測試下的CEOGWO算法的性能表現。從結果可以看出，除了兩組基準函數的測試結果以外，其它6組測試結果表現比較穩定，在尋優精度和結果上表現并無很不差異，說明收斂因子初值與終值的選取對CEOGWO算法的性能不會產生較大的影響，這也說明了CEOGWO算法并沒有對個別參數產生較大依賴性。總體來看，收斂因子初值為2、終值為0時CEOGWO算法的尋優性能更好，該結論也符號線性收斂因子中該值的取值區間。表6測試了4組不同的非線性調整系數取值得到的性能表現。可以看到，在大多數基準函數測試下，CEOGWO算法的性能表現比較穩定，說明算法對該參數的依賴性依然不大，依然符合原本灰狼優化算法控制參數少的特征。

圖3 測試函數的尋優收斂曲線

表4 不同改進思路的影響

表5 收斂因子a取值的影響

表6 非線性調整系數 ξ 取值的影響

實驗四：觀察HGWO算法、NGWO算法、DEGWO算法及本文提出的CEOGWO算法在固定目標收斂精度同時，算法達到該尋優精度時所需要進行算法迭代次數和尋優成功率。尋優成功率表示計算成功次數與實驗求解次數之比，求解是否成功的判定標準為

(20)

式中：FA為實際求解最優解，FT為基準函數理論最優解。

表7是測試結果，函數維度為30，最大迭代數設置為400，取20次獨立運行的實驗結果均值進行比較。若達到最大迭代次算法運行結果仍然沒有達到所需的尋優精度，則將迭代次數定義為最大迭代次數。從表中結果可以看到，HGWO在前400次迭代中達到目標尋優精度的成功率比較低，說明HGWO算法在處理復雜優化問題時的尋優精度還有待提升。對于多峰值基準函數的尋優問題，DEGWO算法的尋優成功率平均高于70%，說明該算法處理多峰函數優化時性能表現較好。NGWO算法的尋優成功率基本接近于100%，說明非線性的收斂系數的設計還是能夠有效均衡灰狼群體的全局搜索和局部開發能力的，對于灰狼尋優性能提升是行之有效的。本文的CEOGWO算法的尋優成功率不僅穩定在100%，且其得到目標尋優精度時所需要的迭代次數也小于3種對比，說明處理復雜優化問題時，算法具備很好的穩定性，能夠有效提升尋優精度和收斂速度。

表7 不同算法的尋優成功率及收斂迭代數

4 結束語

提出一種基于混沌Tent映射與精英高斯擾動的非線性灰狼優化算法。該算法在求解復雜優化問題全局最優解時，可以提供更好的尋優精度和收斂速度，主要體現在：基于混沌Tent映射與對立學習機制，以更加均勻的分布實現了種群初始化過程；基于一種非線性的收斂因子控制方法均衡了種群個體的局部開發和全局勘探；基于精英個體的高斯擾動實現了灰狼位置更新，跳出了局部最優。通過標準函數的測試證實了算法是有效且可行的。進一步的研究工作可以嘗試利用改進算法求解具體的工程設計和數據挖掘分析問題，以求驗證算法在求解實際問題上的可行性。