改進的差分進化算法在約束優(yōu)化問題中的應用*

白 歡，袁慶霓，王 鑫，孫睿彤，衣君輝，施輝城

(貴州大學現(xiàn)代制造技術教育部重點實驗室，貴陽 550025)

0 引言

約束優(yōu)化類問題在現(xiàn)實生活中無處不在，然而求解該類問題的算法卻很少。與無約束類問題不同，約束類問題求解的關鍵是最優(yōu)解必須滿足所有的約束條件，約束條件的限制不僅使得可行區(qū)域變小、搜索空間變得復雜，而且約束條件也難以處理，大大地增加了求解的難度。因此，目前對約束類問題的研究，絕大多數(shù)研究者采用的是約束處理技術。李智勇等[1]詳細地綜述了約束優(yōu)化問題的求解方法和常用的約束處理技術。

在進化算法中，差分進化(DE)算法具有結構簡單、參數(shù)少、收斂性好和搜索能力強的特點[2-3]，因此，很多研究者將DE算法與約束處理技術結合來求解約束優(yōu)化問題。劉若辰等[4]提出一種改進的自適應約束差分進化算法，但是該算法對個體的評價側重于個體是否違反約束條件，在后期搜尋最優(yōu)解時精度不高，這是因為種群中保持適當?shù)牟豢尚袀€體數(shù)量有助于提高收斂性[1]，同時也是找到全局最優(yōu)解的關鍵。TOSCANO等[5]提出在變異過程中父代向量采用隨機排序法，提高了種群多樣性，但是收斂速度較慢。WANG等[6]將廣義反向學習策略用于生產(chǎn)初始種群，有效地利用了反向解的信息，然而在后代的進化過程中沒有使用該策略，未能有效利用其優(yōu)勢。吳文海等[7]對文獻[6]的不足作了改進，但是對于進化過程中縮放因子的選取未能體現(xiàn)出對多樣性和最優(yōu)解的保護。受文獻[4-7]的啟發(fā)，本文提出一種改進的差分進化算法(GOBL-RDE)來求解約束優(yōu)化問題。利用廣義反向學習算法生成反向種群并在后期進化過程中約束種群的搜索空間，加快算法收斂速度；對于變異操作為固定值的缺點，根據(jù)可行率自適應采用兩種變異策略，并設計了自適應交叉因子和縮放因子，有效地利用了“優(yōu)秀”個體資源，提高了種群的多樣性；在選擇操作中，將常用的“貪婪”選擇作了改變，通過將變異前的種群與變異后的種群混合，經(jīng)排序后選擇不同的Np個個體作為新種群。通過與其他幾種約束進化算法進行比較，實驗證明在處理約束類問題時，GOBL-RDE算法在最優(yōu)解上收斂精度更高，收斂速度更快。

1 相關知識

1.1 約束優(yōu)化問題

約束優(yōu)化問題中，約束條件有等式、不等式及邊界約束等形式，可按照以下方式做出定義：

minimize:f(x),x∈D

(1)

其中，x=(x1,x2,…,xn)∈D?Rn為n維決策空間;f:D→R為目標函數(shù);gj(x)≤0表示不等式約束;hj(x)=0表示等式約束;p、q分別表示不等式和等式約束的個數(shù);ui和li分別為xi的上、下界。處理等式約束時，通常將其轉化為相應的不等式約束：

|hj(x)|-δ≤0,j∈{p+1,…,q}

(2)

式中，δ為正容忍因子，本文取值為0.000 1。

解x到第j個約束的距離定義為：

(3)

則解x到可行域的距離定義為約束違反程度G(x)，可表示為：

(4)

1.2 廣義反向學習算法

廣義反向學習[8]概念定義如下:

(5)

xi,j=rand(aj,bj)

(6)

廣義反向學習算法能有效地利用反向解的資源，擴大搜索方向，提高搜索效率。在進化過程中約束了種群的搜索空間，加快了算法收斂速度和效率。

初始化階段偽代碼如下：

算法1 初始化階段的廣義反向學習(GOBL)策略(1)隨機產(chǎn)生初始化種群P0;#種群數(shù)量為Np;(2)for i=1:Np(3) for j=1:n(4) P1i,j=k×(aj+bj)-P0i,j(5) ifP1i,jbjthen#若超出邊界,則重新隨機生成;(6) P1i,j=rand(aj,bj) endif endfor endfor

在P0和新種群P1中擇優(yōu)選取Np個個體。

進化時偽代碼如下:

算法2 進化階段的廣義反向學習(GOBL)策略(1)ifrand(0,1)max(P0ij,t)then(6) P1ij,t=rand(min(P0ij,t),max(P0ij,t)) endif endfor endfor(7)執(zhí)行算法3; endif

在Pt和新種群P1中擇優(yōu)選取Np個個體。

1.3 自適應權衡模型機制

在處理約束類問題時難免會出現(xiàn)不滿足條件的個體，為了更好的處理約束條件對適應值的影響，自適應權衡模型(ATM)機制[9]是將種群劃分為：不可行、半可行和可行狀態(tài)，并分別計算其適應值。

在不可行狀態(tài)下，個體均不滿足約束條件，使用個體的違約值代替適應值。

ffitness(xi)=G(xi)

(7)

在半可行狀態(tài)下，有一部分個體滿足約束條件，使用適應值轉換(AFT)策略[10]來執(zhí)行轉換。

AFT策略是根據(jù)個體是否滿足約束條件分為集合Z1和Z2，其中Z1、Z2分別表示滿足和不滿足約束條件的個體序號。

Z1={i|G(xi)=0,i=1,…,N}

Z2={i|G(xi)>0,i=1,…,N}

(8)

個體xi的目標函數(shù)值f(xi)根據(jù)下式進行轉換：

(9)

式中，φ為可行率，f(xbest)、f(xworst)分別為Z1中最好和最差的個體序號。

接著，將目標函數(shù)值f(xi)標準化

(10)

將違約值G(xi)標準化

(11)

則個體最終適應值為

ffinal(xi)=fnor(xi)+Gnor(xi),i∈(1,…,N)

(12)

在可行狀態(tài)下，個體均滿足約束條件。使用個體目標函數(shù)值代表其適應值。

ffitness(xi)=f(xi)

(13)

2 改進差分進化算法

2.1 改進的個體選擇機制

利用GOBL策略獲得原種群及反向新種群，此時需篩選出較優(yōu)的Np個個體，而傳統(tǒng)的DE算法在選擇操作時是將種群中父代向量的每個個體與新種群中對應的個體逐個進行適應值比較，保存適應值較優(yōu)的個體，在這種篩選機制下可能會出現(xiàn)兩個適應值都較優(yōu)秀的個體進行比較，但是也會出現(xiàn)兩個適應值都較差的個體進行比較，那么此時必然會有一個適應值較差的個體被保留，這無疑會影響進化速度，而且容易陷入局部最優(yōu)[11]，因此本文設計一種改進的選擇機制來加快進化速度。具體操作如下：首先將父代種群與新種群合并，然后計算其適應值并作排序處理，最后選擇較優(yōu)的Np個不同的個體。

個體選擇機制偽代碼如下：

算法3 個體選擇機制(1)執(zhí)行ATM機制計算個體適應值;(2)根據(jù)適應值對個體進行排序;(3)選取靠前的Np個個體。

2.2 差分變異

2.2.1 個體排序及概率計算

在差分變異過程中，為了利用種群中“優(yōu)秀”個體的資源，對個體適應值由優(yōu)到差進行排序[12]，個體xi的排序值由下式表示:

Ri=N-i,i=1,2,…,N

(14)

式中，N表示種群中個體的數(shù)量(本文N=50)，i為第i個個體在種群中的排序值。

個體排序后需要將個體被選擇的概率計算出來。約束優(yōu)化問題中，為了更好地體現(xiàn)個體間的支配關系，根據(jù)可行率分別選擇模型計算，本文采用以下公式進行概率Pi計算[13]：

(15)

式中，i=1,2,…,N,λ=0.5或2。λ值的選取直接影響了參與變異的個體，從而影響最優(yōu)解的搜索范圍。

如圖1所示，R1、R2為種群中排序后的兩個個體，其兩個個體在模型一(λ=2)下的選擇概率分別為p1、p2,在模型二(λ=0.5)下的選擇概率分別為p3、p4，由圖1知，p2-p1>p4-p3，且兩者差值較大，這表明模型一下個體間的支配關系比模型二更加顯著。進化初期，滿足約束條件的個體較少，該階段的主要目的是使不可行個體滿足約束條件，增加可行個體的數(shù)量，因此采用模型一能充分利用“優(yōu)秀”個體資源加快搜索速度。當種群處于可行狀態(tài)下時，若仍然用模型一，那么一些表現(xiàn)稍差的個體被選中的概率大大降低，同時被選中參與變異的個體的數(shù)量也會減少，容易陷入局部最優(yōu)，降低種群多樣性，故采用模型二效果更好。

圖1 不同模型下的概率計算

2.2.2 自適應變異策略

DE/rand/2策略在進化后期搜索中效率低，收斂速度慢，而DE/best/2策略收斂性好，但是難以維持種群的多樣性[14]。為了同時具備以上兩者優(yōu)點，本文采用自適應變異策略，方法如下：

(16)

式中，xi,t、xr1,t、xr2,t、xr3,t、xr4,t為第t代中不同的個體;vi,t為變異后產(chǎn)生的試驗向量;xgbest為進化過程中適應值最優(yōu)個體;F為縮放因子，F(xiàn)∈(0,2);rand為隨機數(shù),rand∈(0,1);φ為可行率。進化初期，可行個體數(shù)量少，因此φ值較小，DE/best/2被選擇的概率較大，即利用最“優(yōu)秀”的個體資源引領其他參與變異的個體向該個體進行學習，加快了收斂速度。進化后期，可行個體數(shù)量多，因此φ值較大，DE/rand/2被選擇的概率大，保證了種群的多樣性。若變異生成的個體超出邊界范圍，則在其允許范圍內(nèi)再次隨機初始化。

2.2.3 改進的自適應縮放因子及交叉因子設計

在DE算法中，參數(shù)縮放因子F和交叉因子Cr對算法的尋優(yōu)能力有直接的影響，為了避免算法中參數(shù)固定，本文使用自適應縮放因子F和自適應交叉因子Cr。具體計算如下：

F=F0×2λ

Cr=0.5×(1+rand)

(17)

式中，Generations表示迭代次數(shù)的最大值;t表示當前迭代次數(shù);F0為常數(shù)，F(xiàn)0∈(0,1);rand為隨機數(shù)，rand∈(0,1)。通過測試發(fā)現(xiàn)，當常數(shù)F0取值較小時，算法的收斂速度較慢，最優(yōu)解搜索能力較差；當常數(shù)F0取值較大時，盡管收斂速度得到了改善，但是最優(yōu)解搜索能力仍然較差；通過實驗發(fā)現(xiàn)當常數(shù)F0=0.5時算法的整體性能最佳。

在進化初期，大部分個體有較差的適應值，由式(17)知，F(xiàn)具有較大數(shù)值，擴大了搜索空間，減少了對個體信息的利用，保持了種群的多樣性。隨著迭代次數(shù)逐漸增加，F(xiàn)取值逐漸減小，直到后期收斂于常數(shù)F0，這有利于保持種群中的“優(yōu)秀”個體資源，防止其遭受破壞并增大了尋到最優(yōu)解的幾率。交叉因子Cr采用隨機函數(shù)生成，其平均值為0.75。具體算法如下：

變異偽代碼如下:

算法4 變異偽代碼(1)根據(jù)適應值對個體Ri進行排序;(2)按照種群所處狀態(tài)選擇相對應的概率計算模型;(3)計算種群中每個個體的被選擇的概率Pi;(4)根據(jù)選擇概率選擇4個不同的個體;(5)按式(17)計算縮放因子F和交叉因子Cr;(6)按式(16)生成vi,t。

3 算法步驟

結合上述內(nèi)容，本文GOBL-RDE算法步驟如下：

本文算法步驟如下:

算法5 本文算法(GOBL-RDE)步驟(1)設置相關參數(shù);(2)執(zhí)行算法1和算法2生成初始種群;(3)執(zhí)行算法3選擇個體;(4)執(zhí)行算法4生成vi,j;(5)執(zhí)行算法3選擇個體;(6)執(zhí)行算法2;(7)判斷是否達到精度要求或最大迭代次數(shù),若是,則結束;否則跳轉到步驟(4)。

4 算法測試與分析

為測試算法性能，采用經(jīng)典的約束測試函數(shù)[15]中的13個函數(shù)進行驗證。分析GOBL算法的有效性，并與εRDE[16]、GOBL-ACDE[7]和ATMES[10]三種算法在最優(yōu)值、平均值、最差值以及標準差等指標進行比較。

4.1 參數(shù)設置

廣義反向學習算法中，k值能影響反向個體資源，Jr表示進化時執(zhí)行廣義反向學習算法的概率，在整個GOBL-RDE算法框架中k和Jr值的選取會影響算法的性能，為了使得算法簡單，本文將其設為固定值，本文算法中k取0.2，Jr取0.8，最大迭代次數(shù)為2000，其余參數(shù)采用自適應設計。

4.2 若干改進策略對于算法性能影響分析

為了驗證個體排序對算法收斂速度的影響，利用測試函數(shù)g01和g08分別執(zhí)行GOBL-RDE和GOBL-DE(個體不作排序處理)算法驗證個體排序的有效性，比較結果如圖2所示，其中實線表示GOBL-DE算法，虛線表示GOBL-RDE算法。由圖2知虛線收斂速度更快，因此可以認為利用優(yōu)秀個體資源可加快算法收斂。

(a)g01收斂圖 (b)g08收斂圖

為了驗證GOBL對算法收斂速度的影響，分別將測試函數(shù)g03、g06、g09利用GOBL-RDE與RDE(進化階段不使用GOBL算法)算法進行比較，迭代次數(shù)為2000次，三個函數(shù)的收斂結果如圖3所示，其中實線表示RDE算法，虛線表示GOBL-RDE算法。由圖3可知，g03和g06兩種算法最終結果收斂到同一值，但是虛線的速度更快，而g09兩種算法收斂值接近，但是虛線的收斂速度和精度更高，因此可以認為GOBL算法加快了收斂速度。

(a)g03收斂圖

為了驗證算法的收斂精度，將GOBL-RDE算法與GOBL-ACDE、εRDE和ATMES幾種約束優(yōu)化算法進行比較，算法比較結果如表1所示，表中加粗的表示較優(yōu)的值。

表1 GOBL-RDE與GOBL-ACDE、εRDE和ATMES算法比較

由表1可以看出，在函數(shù)g02、g03、g05、g08、g11測試中，GOBL-RDE算法的前三項指標均優(yōu)于其它算法，而其中就有三個函數(shù)(g03、g05和g11)均包括等式約束，這說明GOBL-RDE算法在處理含有等式約束時效果比較好。對于像g02這種可行區(qū)域非常大的函數(shù)，進化時種群直接進入可行狀態(tài)，因此可以忽略上述4種算法在約束處理機制上的差別，只需要考慮算法在最優(yōu)值處尋優(yōu)的搜索能力，從表1知，只有GOBL-RDE和GOBL-ACDE兩種算法尋到最優(yōu)值，其余算法均未尋到，但是在其他三項指標方面，GOBL-ACDE算法結果略差于GOBL-RDE算法，因此可以認為GOBL-RDE算法的尋優(yōu)能力較好。在約束條件比較多(5個及以上)的情況下，這類函數(shù)對約束條件的處理是找到最優(yōu)解的關鍵，本文中有函數(shù)g01、g04、g05、g07和g10，雖然GOBL-RDE在函數(shù)g04的三項指標稍差于GOBL-ACDE，但是在g05、g07、g10上，GOBL-RDE算法每個尋優(yōu)指標均優(yōu)于其余算法，因此可以認為GOBL-RDE算法在約束處理機制方面是較優(yōu)的。與εRDE相比，GOBL-RDE只在g03和g06兩項結果表現(xiàn)稍差，這說明GOBL-RDE比εRDE有更好的尋優(yōu)精度。與GOBL-ACDE相比，雖然GOBL-RDE和GOBL-ACDE基本在13個測試函數(shù)均可達到全局最優(yōu)，但是GOBL-ACDE在函數(shù)g02、g03、g06、g08、g11上各項指標表現(xiàn)稍差。與ATMES相比，GOBL-RDE除了在函數(shù)g04、g06上表現(xiàn)稍差，在其它函數(shù)上三種指標均優(yōu)于ATMES算法。GOBL-RDE在13個測試函數(shù)中標準差較小，這說明穩(wěn)定性表現(xiàn)較好，因此可以認為GOBL-RDE尋優(yōu)性能更好。

5 結論

本文提出一種改進的差分進化算法用于求解約束優(yōu)化問題，算法利用GOBL算法產(chǎn)生反向種群提高了搜索效率。改進了變異策略單一的缺點，并通過參數(shù)自適應方式選擇變異策略，改進了縮放因子，有效地利用了“優(yōu)秀”個體資源，降低了陷入局部最優(yōu)的幾率，保持了種群的多樣性；在選擇操作中，對傳統(tǒng)的“貪婪”機制作了改進，并充分利用反向解資源，加快了收斂速度。通過與幾種約束算法進行比較，結果證明在處理約束類問題時，本文提出的算法有較高的收斂精度，而且收斂速度較快。