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

(貴州大學(xué)現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴陽(yáng) 550025)

0 引言

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

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

1 相關(guān)知識(shí)

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

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

minimize:f(x),x∈D

(1)

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

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

(2)

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

解x到第j個(gè)約束的距離定義為：

(3)

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

(4)

1.2 廣義反向?qū)W習(xí)算法

廣義反向?qū)W習(xí)[8]概念定義如下:

(5)

xi,j=rand(aj,bj)

(6)

廣義反向?qū)W習(xí)算法能有效地利用反向解的資源，擴(kuò)大搜索方向，提高搜索效率。在進(jìn)化過(guò)程中約束了種群的搜索空間，加快了算法收斂速度和效率。

初始化階段偽代碼如下：

算法1 初始化階段的廣義反向?qū)W習(xí)(GOBL)策略(1)隨機(jī)產(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#若超出邊界,則重新隨機(jī)生成;(6) P1i,j=rand(aj,bj) endif endfor endfor

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

進(jìn)化時(shí)偽代碼如下:

算法2 進(jìn)化階段的廣義反向?qū)W習(xí)(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個(gè)個(gè)體。

1.3 自適應(yīng)權(quán)衡模型機(jī)制

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

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

ffitness(xi)=G(xi)

(7)

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

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

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

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

(8)

個(gè)體xi的目標(biāo)函數(shù)值f(xi)根據(jù)下式進(jìn)行轉(zhuǎn)換：

(9)

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

接著，將目標(biāo)函數(shù)值f(xi)標(biāo)準(zhǔn)化

(10)

將違約值G(xi)標(biāo)準(zhǔn)化

(11)

則個(gè)體最終適應(yīng)值為

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

(12)

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

ffitness(xi)=f(xi)

(13)

2 改進(jìn)差分進(jìn)化算法

2.1 改進(jìn)的個(gè)體選擇機(jī)制

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

個(gè)體選擇機(jī)制偽代碼如下：

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

2.2 差分變異

2.2.1 個(gè)體排序及概率計(jì)算

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

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

(14)

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

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

(15)

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

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

圖1 不同模型下的概率計(jì)算

2.2.2 自適應(yīng)變異策略

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

(16)

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

2.2.3 改進(jìn)的自適應(yīng)縮放因子及交叉因子設(shè)計(jì)

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

F=F0×2λ

Cr=0.5×(1+rand)

(17)

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

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

變異偽代碼如下:

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

3 算法步驟

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

本文算法步驟如下:

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

4 算法測(cè)試與分析

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

4.1 參數(shù)設(shè)置

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

4.2 若干改進(jìn)策略對(duì)于算法性能影響分析

為了驗(yàn)證個(gè)體排序?qū)λ惴ㄊ諗克俣鹊挠绊懀脺y(cè)試函數(shù)g01和g08分別執(zhí)行GOBL-RDE和GOBL-DE(個(gè)體不作排序處理)算法驗(yàn)證個(gè)體排序的有效性，比較結(jié)果如圖2所示，其中實(shí)線表示GOBL-DE算法，虛線表示GOBL-RDE算法。由圖2知虛線收斂速度更快，因此可以認(rèn)為利用優(yōu)秀個(gè)體資源可加快算法收斂。

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

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

(a)g03收斂圖

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

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

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

5 結(jié)論

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