基于醉漢漫步和反向學習的灰狼優(yōu)化算法*

劉 煉,付紹昌,黃輝先

(湘潭大學自動化與電子信息學院,湖南 湘潭 411105)

1 引言

高維函數優(yōu)化問題在理論研究和實際生產過程中具有很重要的應用價值，許多問題可通過數學建模轉換為最優(yōu)問題，如物流配送路徑優(yōu)化的研究[1]、高鐵動態(tài)調度方法問題[2]和多分類孿生支持向量機參數優(yōu)化問題[3]。高維復雜函數優(yōu)化通常是指維度超過100維的函數優(yōu)化問題，而隨著維度的增加，問題的局部最優(yōu)值也會增加，其計算復雜度也會呈指數級增長[4]，解決問題的難度也隨之加大。

近年來隨著群體智能SI(Swarm Intelligence)算法的興起，遺傳算法GA(Genetic Algorithm)、粒子群優(yōu)化PSO( Particle Swarm Optimization)算法和人工蜂群ABC(Artificial Bee Colony)算法等相繼被提出。郭佳等[5]提出一種優(yōu)化的馬爾可夫鏈人工蜂群算法，通過馬爾可夫鏈對第一階段產生的解空間進行重構，減少了人工蜂群算法的隨機性，同時避免了因依賴某一最優(yōu)值導致的算法早熟。馮璋等[6]提出一種二維主成分分析法與主成分分析法結合與改進灰狼優(yōu)化算法共同優(yōu)化支持向量機的人臉識別方法，以減少提取特征的維度和提取時間,從而縮短了支持向量機所需的識別時間，為了提高灰狼優(yōu)化算法的全局搜索能力,引用精英反向學習策略初始化種群。在光伏大規(guī)模故障系統(tǒng)中，標記數難以記錄，Huang等[7]提出了一種結合人工蜂群算法和半監(jiān)督極限學習機的新算法來解決該問題。隨著社會的進步，問題復雜程度不斷增加，為進一步檢測算法的綜合能力，近幾年研究人員提出了更復雜的測試函數，如CEC(Congress on Evolutionary Computation)2013、CEC2014等。以上學者所提出的改進算法無論在全局收斂性還是求解精度方面都待提高，同時算法尋優(yōu)只針對標準測試函數，對復雜測試函數效果不佳。

灰狼優(yōu)化GWO(Grey Wolf Optimizer)算法是Mirjalili等[8]在2014 年提出的一種群體智能優(yōu)化算法。GWO概念清晰，具有結構簡單、計算時間復雜度低、易于實現和局部尋優(yōu)能力強等特性，擁有良好的全局搜索和局部搜索切換機制，得到了諸多國內外研究者的認可。Teng等[9]提出了一種結合粒子群優(yōu)化算法的灰狼優(yōu)化算法PSO_GWO，利用非線性控制參數來平衡算法的搜索能力，提高算法的收斂速度。Pan等[10]將種群狼分成幾個獨立的群體，提出了一種并行灰狼優(yōu)化算法。Mittal等[11]通過控制參數a協調算法的探索和開發(fā)能力,提出了一種改進的灰狼優(yōu)化算法MGWO(Modified GWO)。柳長安等[12]設計了一種靜態(tài)平均和動態(tài)加權平均混合的位置更新策略，并使用非線性遞減函數改進灰狼優(yōu)化算法距離控制參數。GWO 算法雖然得到了許多改進,但針對高維復雜函數問題的研究仍不多見。龍文等[13,14]對高維復雜函數優(yōu)化問題進行了研究，但其收斂精度不是很高，且在近幾年提出的復雜測試函數上效果不明顯。為增強算法綜合尋優(yōu)能力，同時兼顧對標準測試函數和復雜測試函數的尋優(yōu)效果，本文將醉漢漫步、反向學習與灰狼優(yōu)化算法相結合，提出一種改進灰狼優(yōu)化算法DGWO(Drunkard Grey Wolf Optimizer)。算法主要改進策略為：

(1)為增加局部搜索和全局搜索能力，對種群中精英個體采用醉漢漫步策略進行更新。

(2)為避免陷入局部最優(yōu)，對種群中α、β、δ與當前種群中適應度值最差的3匹狼進行反向學習，重新計算適應度值并與本身比較排序，將3匹最好的狼隨機保留在狼群中，以增加種群多樣性，增加跳出局部最優(yōu)的概率。

(3)為平衡局部搜索能力和全局搜索能力，種群迭代過程中，更新時參數A、C采用標量系數[15]和矢量系數，各為迭代次數的一半。

實驗測試，該改進算法應用于高維測試函數與復雜函數時在精度和收斂速度上有明顯的優(yōu)勢，可應用于兩級運算放大器參數設計中。

2 基本灰狼優(yōu)化算法

GWO算法是受大自然中狼群狩獵捕食的啟發(fā)而提出來的，其中α狼為當代種群中最靠近獵物的狼，β狼和δ狼為第2和第3靠近獵物的狼，ω狼則為種群中其它狼。在狼群搜捕獵物時ω狼受α、β、δ狼的引導朝3匹狼的方向前進，以實時更新自身的位置，并靠近獵物。根據狼群狩獵時所建立的數學模型如式(1)～式(4)所示：

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

(1)

A=2·a·r1-a

(2)

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

(3)

C=2·r2

(4)

其中，t為當前迭代次數;Xp(t)為獵物位置;A為收斂因子，其值控制著ω狼是接近還是逃離領導狼，當A的絕對值大于1時狼群將逃離領導狼，此時ω狼會放棄此時可能有獵物的區(qū)域，去探索更多的區(qū)域；D為包圍步長；r1和r2是隨機向量，其分量取值為[0,1];a隨著整個迭代過程的進行從2到0逐漸線性減小,a={a,a,…,a}是由a構造出的向量，其維度與r1維度相同;C為擺動因子。

狼群個體在包圍獵物時的數學模型如式(5)～式(11)所示，式(5)～式(10)用于計算狼群個體與α、β、δ狼的距離，式(11)用于計算新的狼群個體位置:

Dα=|C1·Xα-X(t)|

(5)

Dβ=|C2·Xβ-X(t)|

(6)

Dδ=|C3·Xδ-X(t)|

(7)

X1(t)=Xα-A1×Dα

(8)

X2(t)=Xβ-A2×Dβ

(9)

X3(t)=Xδ-A3×Dδ

(10)

X(t+1)=[X1(t)+X2(t)+X3(t)]/3

(11)

其中，Xα、Xβ和Xδ分別表示α、β和δ的位置，Dα、Dβ和Dδ分別表示狼群個體到α、β和δ的距離，A1～A3，C1～C3分別表示通過式(2)和式(4)生成的隨機數。

基本GWO 算法的偽代碼如算法1 所示。

算法1基本GWO算法

輸入：種群規(guī)模N，迭代次數t，最大迭代次數Maxit。

輸出：Xα。

1：在搜索空間中隨機生成N匹初始狼；

2：根據式(3)和式(4)計算參數A、a和C的值;

3：依次計算適應度值f(Xi),i=1,2,3,…,N;

4：將狼按適應度值升序排序，取前3分別標記為Xα、Xβ和Xδ，令并t=0;

5：whilet

6：fori=1 toNdo

7： 根據式(8)～式(11)更新第i匹灰狼的位置;

8：endfor

9： 根據式(3)和式(4)更新參數A和C的值;

10： 重新計算適應度值f(Xi),i=1,2,3,…,N;

11： 更新Xα、Xβ和Xδ的值;

12：t=t+1;

13：endwhile

14:returnXα

3 改進的灰狼優(yōu)化算法DGWO

3.1 醉漢漫步模型

隨機漫步(Random Walk)[16]思想最早由Pearson在1905年提出的，它是一種不規(guī)則的變動形式，變動過程中的每一步都是隨機的。隨機漫步的思想是,從隨機點出發(fā)進行隨機跳躍但會遍歷整個圖。隨機漫步已在眾多領域得到應用。Gupta等[17]提出一種新穎的隨機漫步灰狼優(yōu)化算法，并證明可解決連續(xù)優(yōu)化問題，而且可以解決實際生活優(yōu)化問題。隨機漫步可大致分為3種：馬爾可夫鏈[18]、醉漢走路(Drunkard Walk)[19]和萊維飛行(Lévy Flight)[20]。本文采用基本的醉漢漫步模型，該模型在初始化時產生一組隨機數，如式(12)所示：

Di=(r3*2-1)*π

(12)

其中,r3∈[0,1]，π為圓周率。

如式(13)～式(17)所示進行三角變換：

newx=step×sin(Di)+oldx

(13)

Drβ=newx·(Xβ-Xα)

(14)

Drδ=newx·(Xδ-Xα)

(15)

X(t+1)=a×Drβ+Xβ

(16)

oldx=newx

(17)

X(t+1)=a×Di+Xα

(18)

其中,step為醉漢步長，步長可固定也可變化，小步長促使在當前子代附近展開搜索，而足夠大的步長有助于探索新的有希望或未探索的搜索區(qū)域，本文中step固定為2。

本文根據式(13)～式(17)更新β狼和δ狼。根據式(18)更新α狼，醉漢漫步具有強大的隨機性，方向具有不確定性，精英狼處于當前狼群最優(yōu)位置，故精英狼漫步增強了精英狼的局部搜索能力，在優(yōu)化復雜函數時效果明顯。

3.2 反向學習策略

反向學習策略[21]是由Tizhoosh于2005 年提出的一種智能計算方法，廣泛應用于各種算法優(yōu)化中，以提高算法搜索性能。利用反向學習策略的有效性，張新明等[22]提出一種最優(yōu)最差反向學習策略，實驗結果表明最優(yōu)最差反向學習策略比一般反向學習策略更有效。反向學習的主要思想是在同一空間中對當前解進行反向求解，設xj是某一對象n維空間的一個當前解，x*為反向解，則x*通過式(19)進行求解,且x1,x2,…,xn∈R，xj∈(aj,bj),aj與bj分別代表搜索空間上下限。

x*=aj+bj-xj

(19)

狼群中α、β、δ狼與最差的狼的信息是當前狼群所積累的知識和經驗的代表。在本文改進的灰狼優(yōu)化算法DGWO中，α、β、δ狼均為精英個體，在求α、β、δ狼的反向解的同時將狼群中適應度最差的3匹狼進行反向求解，并重新計算6個反向解的適應度值且進行排序，用排序后前3的反向解隨機替換種群中的個體，以增加種群的多樣性，擴大搜索范圍。為了協調算法的勘探和開采能力, 引入反向學習策略。由精英反向學習策略可知, 將反向解與當前解同時保留，可增強下一代群體中種群的多樣性, 能增加算法跳出局部最優(yōu)的概率；另一方面,反向解又保留了當前種群中精英個體的有益搜索信息，可以加快算法的收斂速度。

3.3 算法步驟

綜上所述,改進灰狼優(yōu)化(DGWO) 算法的步驟如下所示：

步驟1算法參數設置：種群規(guī)模N，最大迭代次數Maxit。

步驟2隨機生成初始種群，計算每個個體的適應度值并排序，將前3個最優(yōu)個體的位置依次保存為Xα、Xβ、Xδ。

步驟3根據式(5)～式(11)更新灰狼位置信息,更新A，a，C的值。

步驟4根據式(12)～式(18)更新α、β、δ狼。

步驟5根據式(19) 進行反向學習。

步驟6重復步驟3～步驟5直到達到最大迭代次數，輸出α狼位置，算法終止。

4 實驗及數值分析

4.1 測試函數

本節(jié)采用國際通用的10個標準測試函數驗證本文DGWO算法的有效性，并將其應用于模擬集成電路參數設計問題。為了驗證該改進算法求解高維函數的有效性，本文還選取了10個高維測試函數進行實驗，并將測試結果與PSO、GWO-CS和GWO的測試結果進行對比。10個標準測試函數如表1所示，表中n表示維度，Fmin表示全局最優(yōu)解的值。

4.2 基本GWO算法與DGWO算法對比

為了保證公平性，算法進行對比時采用相同的參數初始化設置，其中求解高維測試函數時種群規(guī)模N=50，最大迭代次數Maxit=1000。在GWO中，參數a的初始值為2。每種算法獨立運行30 次，記錄尋優(yōu)的最優(yōu)值、最優(yōu)值位置、平均值以及標準差。所有測試均在Intel(R) Core(TM)i5-4590 CPU、6 GB內存、3.30 GHz的計算機上進行，利用Matlab 2017a編寫程序。采用DGWO對表1中10個測試函數進行求解，并與基本GWO進行對比。

Table 1 10 standard test functions表1 10個標準測試函數

由表2可看到，改進后DGWO算法與基本GWO算法相比有明顯改進，其中f1、f2、f3、f4、f5、f7、f8、f9的收斂精度有了明顯提高，且尋到了f1、f2、f3、f7、f8、f9的全局最優(yōu)解，標準差達到零，其仿真結果顯示了DGWO算法改進策略的有效性。

表3給出了DGWO與3種對比算法(PSO、GWO和GWO-CS)對表1中10個可變維測試函數在100維、500維和1 000維中各自的尋優(yōu)結果對比,其中種群規(guī)模N=30,最大迭代次數Maxit=500,算法獨立運行20次。通過分析表3可以得知全部測試函數取得最優(yōu)值，在100維、500維和1 000維的情況下函數f1、f2、f3、f7、f9均達到理論最小值0，函數f8達到理論最小值8.88e-16。

Table 2 Results comparison of 10 standard test functions between GWO algorithm and DGWO algorithm表2 GWO算法與DGWO算法對10個標準測試函數結果對比

Table 3 Optimization results of PSO,GWO,GWO-CS,DGWO algorithms on high-dimensional function 表3 PSO、GWO、GWO-CS、DGWO 在高維測試函數上的尋優(yōu)結果

在其它函數的尋優(yōu)精度上，與3個對比算法相比均具有優(yōu)勢。隨著維度的增大，3種算法的尋優(yōu)精度明顯下降，但本文DGWO算法在測試函數尋優(yōu)結果中均具有優(yōu)勢，且標準差同樣具有優(yōu)勢?？傮w來說,本文提出的DGWO算法在100維、500維、1 000維的測試函數上相對于GWO、PSO和GWO-CS算法尋優(yōu)結果更優(yōu)。

由表3可知，DGWO與GWO、PSO、GWO-CS相比在100維、500維以及1 000維時均取得了較優(yōu)的結果，PSO算法均未收斂，GWO在100維時(f1、f2、f3、f6、f7和f8)收斂，在500維和1 000維時只有部分收斂，由此可見GWO算法在高維函數尋優(yōu)方面還有提升空間。

為了更直觀地比較4種算法的收斂精度與收斂速度，圖1給出函數f1、f2、f5、f7、f8、f9的適應度進化曲線圖進行對比。從圖1中可看出，與PSO、GWO、GWO-CS算法相比，DGWO算法尋優(yōu)效果更好，精度更高，收斂速度也快。

從圖1中f2、f5、f8的適應度進化曲線可以看出，在迭代過程中算法收斂速度較快，體現出改進算法在陷入局部最優(yōu)時具有良好的機制跳出局部最優(yōu)，找到全局最優(yōu)解。

為進一步驗證本文提出的改進算法的有效性，本文使用10個CEC2013[23]測試函數作為尋優(yōu)對象，測試函數中包含單峰函數(f11、f12)、多峰函數(f13～f16)及組合函數(f17～f20)。各算法尋優(yōu)參數設定如下：維度為10，種群規(guī)模N=50，最大迭代次數Maxit=1000，算法獨立運行30次，測試函數如表4所示，尋優(yōu)結果如表5所示。

Figure 1 Fitness curves of 4 algorithms on 6 functions圖1 4種算法在6個標準測試函數上的適應度進化曲線

Table 4 CEC2013 test functions

由表5可知,與GWO、PSO、GWO-CS相比，DGWO在f11～f20上均具有優(yōu)勢，平均值均取得最優(yōu)，大部分標準差取得最優(yōu)。在單峰函數(f11)上取得全局優(yōu)解，且標準差較小，可以看出該改進算法在復雜單峰函數上較對比算法具有明顯優(yōu)勢，在多峰函數(f13～f16)上均取得最優(yōu)，對于函數f13和f16改進效果顯著，明顯提高了收斂精度，在組合函數(f17～f20)上測試算法性能時，DGWO同樣均取得最優(yōu)，且相較于GWO、PSO和GWO-CS具有明顯的效果，f17、f19、f20平均值有大幅度提高。由以上的比較結果可知，DGWO在求解大部分函數時具有優(yōu)勢，不僅僅在高維測試標準函數上，而且在復雜測試函數上同樣具有優(yōu)勢，進一步驗證了DGWO算法的有效性。

4.3 計算復雜度

評價元啟發(fā)式算法有效性的一個指標為計算時間復雜度。計算時間復雜度越低的算法，可以用越少的計算力來完成相同的求解任務。在最壞的情況下，DGWO與GWO、GWO-CS的計算時間復雜度如下所示：

在初始化階段，DGWO與GWO、GWO-CS的時間復雜度相同。種群初始化時的時間復雜度為O(N),其中N為種群大小。參數a、A和C的初始化時間復雜度為O(3)，領導者的產生過程的時間復雜度為O(3N)。

Table 5 Optimization results of 4 algorithms on CEC201310 test functions表5 4種算法在CEC201310測試函數上的尋優(yōu)結果

每種算法的主要計算步驟都在 while 循環(huán)中。在 GWO中，種群位置更新的時間復雜度為O(N)；在假設每個測試函數的時間復雜度為O(1)的前提下，種群適應度計算的時間復雜度為O(N)；參數更新、領導者更新過程的時間復雜度分別為O(3)和O(3N)。綜上所述，while 循環(huán)的時間復雜度為O((5N+3)·T)，其中T是最大迭代次數。GWO 的總計算時間復雜度為O(T·N)。

在GWO_CS中種群位置更新的時間復雜度為O(N)；杜鵑搜索復雜度為O(3N)，種群重新更新計算復雜度為O(N)。部分參數更新計算復雜度為O(10)，領導者更新過程的時間復雜度為O(3N)。綜上所述，while 循環(huán)的時間復雜度為O((8N+10)·T)，其中T是 最大迭代次數。GWO_CS 的總計算時間復雜度為O(T·N)。

因此，考慮最壞情況下，3種灰狼優(yōu)化算法的計算時間復雜度相同。

5 在兩級運算放大器設計中的應用

隨著模擬集成電路(IC)的拓撲結構變得越來越復雜，模擬電路設計自動化面臨更多更嚴峻的挑戰(zhàn)。模擬集成電路的參數設計可以通過建立數學模型轉化為一個優(yōu)化問題，在保證增益、轉換速率、單位增益和帶寬等設計指標的前提下獲得最優(yōu)解，大大縮短設計時間，提高電路的綜合性能。本文以L50G CMOS工藝下兩級無緩沖運算放大器的增益優(yōu)化設計為例[24,25]檢驗DGWO算法的實用性。該放大器的電路如圖2所示。

Figure 2 Standard two-stage operational amplifier圖2 標準兩級運算放大器

該問題的數學模型如下所示：

considerX=[x1,x2,…,x10]=[S1,…,S8,I6,Cc]

minf(X)=EAv/Av=EAv/(20 lg(2gm1gm6/(x9I6(λ2+λ4)(λ6+λ7))))

s.tg1(X)=EUGB/UGB=EUGB/(gm1/(x10+A2Cgd6))≤1

g2(X)=ESR/SR=ESR/(x9/x10)≤1

g4(X)=EPSRR+/PSRR+=EPSRR+/(20 lg(2gm1gm6/(x9λ6I6(λ2+λ4))))≤1

g5(X)=EPSRR-/PSSR-=EPSRR-/(20 lg(2gm1gm6/(x9λ7I6(λ2+λ4))))≤1

g6(X)=Pdiss/EPdiss=(VDD-VSS)(2x9+

I6)/1000/EPdiss≤1

g7(X)=10gm2/gm6≤1

g8(X)=0.122CL/x10≤1

g9(X)=10UGB/P3≤1

h1(X)=x1-x2=0,h2(X)=x3-x4=0

wheregm1=gm2= (K′nx1x9)0.5

gm3=gm4= (K′px3x9)0.5

gm6=gm4x6/x4

A2=gm6/(I6(λ6+λ7))

Cgd6=CGDOP·x6·L

P3=gm3/(4/3·COXx3L2)

Rangex1,x2,…,x8∈[1,50],x9∈(0,30],x10∈(0,10]

其中，λ2,λ4，λ6和λ7分別代表晶體管m2,m4,m6和m7的溝道調制系數。

在DGWO的基礎上，引入非平穩(wěn)多級分配罰函數約束處理方法[26]對模擬電路進行優(yōu)化設計。

表6給出了對該運算放大器性能指標設計要求，模型中，EAv,EUGB,ESR和ETA分別表示增益、帶寬、擺率和版圖面積的期望值，λ為晶體管的溝道調制系數，CGDOP為PMOS的柵漏重疊電容，K′n和K′p分別為NMOS和PMOS的本征導電因子。PSRR+和PSRR-為正電源抑制比和低頻負電源抑制比。

Table 6 Standard two-stage operational amplifier design characteristics requirements表6 標準兩級運算放大器設計特性要求

分別設置EAv，EUGB，ESR，ETA，EPSSR+，EPSSR-，EPdiss，CL，L為50 dB，5 MHz，10 V/μs，400 μm2，60 dB，60 dB，2 mW，10 pF，2 μm,表7給出了4種算對標準兩級運算放大器低頻增益的優(yōu)化結果，經過5 000次迭代,每種算法獨立運行20次。由表7可知，PSO算法在5 000次迭代后找不到可行解，DGWO算法的均值結果明顯優(yōu)于其它3種算法,驗證了DGWO在工程應用中的有效性。

Table 7 Standard two-stage operational amplifier low-frequency gain optimization results表7 標準兩級運算放大器低頻增益優(yōu)化結果

6 結束語

本文對基本灰狼優(yōu)化算法進行了改進，將反向學習和醉漢漫步融入其中，提出了DGWO算法。精英反向學習策略提高了種群多樣性，擴大了搜索范圍，醉漢漫步機制在提高灰狼優(yōu)化算法收斂速度的同時，也提高了算法的收斂精度。本文在10個高維標準測試函數及CEC2013部分測試函數上對DGWO進行了仿真實驗，結果表明,與PSO、GWO和GWO-CS 算法相比,DGWO算法在大部分函數上獲得了較高的尋優(yōu)精度，能有效處理高維函數及復雜函數優(yōu)化問題，在單峰函數中具有良好的局部尋優(yōu)效果，在多峰函數與組合函數中又體現出全局搜索能力得到加強。在開環(huán)低頻增益優(yōu)化問題中，與其它3種群體智能算法相比，DGWO算法在對比實驗中具有優(yōu)勢，驗證了該算法的有效性。