基于反向學習和可行性準則交叉的約束差分進化算法

段 偉 徐 斌

(上海工程技術大學機械與汽車工程學院 上海 201620)

Crossover operator Engineering application

0 引 言

差分進化算法(Differential Evolution, DE)是一種新興的進化搜索算法[1]，具有結構簡單、魯棒性強、參數(shù)少等特點，在全局優(yōu)化過程中得到廣泛的應用。但是實際的工程優(yōu)化設計問題通常包含各種復雜約束，傳統(tǒng)的DE算法在求解這類問題時存在一定的局限性，通常需要加入額外的約束處理技術。常用的約束處理技術主要包括懲罰函數(shù)法、可行性法則和多目標優(yōu)化方法等[2]。王慶賀等[3]對約束多目標問題中進化個體對各個目標的影響動態(tài)變化進行了分析，提出了基于各分目標懲罰函數(shù)，合理地動態(tài)分配目標函數(shù)值，提高種群個體對目標值影響的準確性；Deb[4]利用約束違反度值描述約束程度并參與到個體適應度值的比較中，綜合考慮影響種群個體大小的條件，挑選出滿足條件的子代種群，確定種群的進化方向；Gong等[5]提出了一種基于Pareto占優(yōu)準則的多目標約束處理方法，將被子代個體Pareto支配的父代個體用子代個體替代，并采用e-dominance對儲備的非支配個體進行更新歸檔。

反向學習[6]是通過對稱點找到數(shù)值對應的鏡像點，有利于實現(xiàn)隨機點的均布，文獻[7-10]將反向學習方法應用于算法中，擴大了種群的搜索范圍，避免無效搜索。因此本文利用反向學習進行種群初始化，并對進化后的個體進行反向邊界處理；同時在Wang等[11]的啟發(fā)下，對Deb約束處理后的目標個體和實驗個體加設可行性算子，并進一步進行交叉處理，提出一種基于反向學習和可行性準則交叉的約束差分進化算法(DEOC) 。為了驗證DEOC算法的性能，采用13個標準測試函數(shù)進行仿真實驗，并將其應用于蝸輪齒圈和焊接梁優(yōu)化問題中，驗證DEOC算法的有效性。

1 基本理論

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

約束優(yōu)化的基本形式為：

minf(x)x∈Ω

(1)

s.t.gt(x)≤0,t= 1,2,…,q

ht(x) = 0,t=q+ 1,q+ 2,…,m

式中:x=(x1,x2,…,xD)是一個D維的向量個體；f(x)為目標函數(shù)，gt(x)是第t個非等式約束條件；ht(x)是第t-q個等式約束條件。一般將等式約束變形成不等式約束形式：

|ht(x)|-δ≤0t∈{q+1,q+2,…,m}

(2)

式中：δ為一個正的容忍值，一般取10-4。一個解x的約束違反值為：

(3)

G(x)的大小反映個體x違反約束條件的程度。

1.2 差分進化算法

(4)

1) 變異操作是差分進化算法的主要操作，它決定了算法種群的進化方向，最為常用的變異策略為：

(5)

式中：xr1、xr2、xr3表示選擇種群中三個互異個體；F∈[0,1]為縮放因子。

2) 交叉操作：利用式(5)得到的變異后個體v與x執(zhí)行二項式交叉操作，生成新個體:

(6)

式中：CR∈[0,1]為交叉率；jrand表示[1,D]中的一個隨機整數(shù)。

(7)

1.3 Deb準則

Deb準則是應用最廣泛的約束處理方法之一，與其他方法相比，Deb準則不需要定義額外參數(shù)，只需根據(jù)問題的目標函數(shù)和約束違反值就篩選出絕對優(yōu)秀的目標個體。對于給定的兩個個體xi和ui，當滿足下列條件之一時，稱ui比xi好：

1)G(xi)=0且G(ui)=0，并且f(ui)

2)G(xi)>0且G(ui)=0。

3)G(xi)>0且G(ui)>0，并且G(ui)

2 改進的約束差分進化算法

本文提出DEOC算法著重解決約束優(yōu)化問題，基于反向學習方法對初始種群和進化種群的邊界選擇進行進一步優(yōu)化，擴大算法的搜索范圍，同時在Deb準則中加入交叉算子，儲備滿足快速收斂的失效個體。通過進一步交叉進化，優(yōu)秀的失效個體重新歸位到種群，最終提高算法的收斂速度和穩(wěn)定性。

2.1 基于反向學習的種群初始化

基本的差分進化算法的初始種群是模仿生物進化的方法，通過隨機的方式產(chǎn)生的，這樣產(chǎn)生的隨機數(shù)就有可能出現(xiàn)局部化，造成初始種群個體相似，初始的搜索范圍狹小，從而進化提前停滯，導致算法所搜尋的優(yōu)秀個體無法代表整個搜索域。而通過對隨機產(chǎn)生的初始種群進行反向學習后，提高了初始生物個體分布的均勻性，防止初始種群聚集在某一區(qū)域，提高了初始種群的質量。DEOC算法產(chǎn)生初始種群的偽代碼如下：

1. 通過式(4)產(chǎn)生初始種群X(0)。

2. Fori=1 toN

3. Forj=1 toD

5. End for

//反向學習的初始個體

7. End for

//X(0)為初始種群，X^(0)為反向種群，W為混合種群

9.從W中挑選N個適應值小的個體更新種群X(0)。

2.2 基于反向學習的邊界處理

在處理約束問題時，變異交叉后的個體ui易跳出初始邊界 [xmin,j,xmax,j]，造成種群有效個體減少，降低算法的收斂速度并易使算法陷入局部最優(yōu)。所以要對跳出邊界的個體uλ及時糾正，常用的邊界處理的方法是用u^λ=xmin,j+rand[0,1]×(xmax,j-xmin,j)代替失效個體uλ，但是利用這種方法產(chǎn)生的u^λ失去了變異交叉對種群個體的進化影響。

為了保留算法變異交叉操作對跳出邊界個體的影響性，本文學習反向學習精英選擇策略[12]對于處理變異交叉后的中間群體的方法，采用式(8)所示的反向邊界處理并吸收的方法，調(diào)整個體uλ中基因ui,j大小，使uλ跳回邊界區(qū)域內(nèi)，同時該方法又可以增加有效個體的多樣性，保證算法的全局搜索能力。

(8)

3 可行性準則交叉算子

本文發(fā)現(xiàn)Deb準則沒有完全發(fā)掘不可行域中個體的能力，沒有利用可行個體和與之對應變異交叉后個體的關系，即沒有保留個體在進化過程中的進化能力。為了保證種群個體都具有更強的學習能力，提出一種基于可行性準則交叉算子，充分挖掘部分不可行解攜帶的信息。如圖1所示，當ui滿足G(xi)<0，G(ui)>0，并且f(ui)

誤除個體hi具有更小的目標函數(shù)，更接近最優(yōu)解的特點。由圖1可以發(fā)現(xiàn)hi和xi的直線方向上可能會產(chǎn)生適應度函數(shù)更小的個體，因此對hi和xi進行交叉處理，產(chǎn)生下一代個體zi，選取zi=[0,1]×(hi+xi)，將zi儲存在Z中。根據(jù)適應度值評估種群Z與X，并更新種群X?；诳尚行詼蕜t交叉算子的偽代碼如下：

1.Z=?;

2. Fori=1 toN

3. ifG(xi)=0&G(ui)>0&f(ui)

4.hi=ui;zi=rand[0,1]×(hi+xi);Z=Z∪zi；

5. End if

6. End for

7.P=Z∪X;

8. 從P中挑選出適應值小的N個個體更新種群X。

將上述3部分改進內(nèi)容融入基本差分進化算法，得到改進的DEOC算法，迭代過程如圖2所示。

4 實驗驗證與工程應用

為了驗證DEOC算法的有效性，選取了13個標準約束優(yōu)化測試函數(shù)進行實驗仿真[13]。這13個測試函數(shù)的目標函數(shù)包含線性和非線性方程，其中g01、g04、g07、g11和g12五個測試函數(shù)的目標函數(shù)為二次方程。約束函數(shù)包含線性不等式約束、非線性等式和不等式約束，其中g03，g05、g11和g13四個測試函數(shù)中含有等式和不等式約束。另外，為了進一步驗證DEOC算法在實際工程中的有效性，將其用于蝸輪齒圈和焊接梁優(yōu)化設計問題。

4.1 與基本的DE算法DE/rand/1進行比較

將DEOC算法與基本的DE算法進行比較，兩種算法參數(shù)設置如下：N=40，F(xiàn)=0.8，CR=0.9，運行30次，最大評估次數(shù)為240 000次。兩種算法在求解g03、g06、g07、g09、g10、g11、g12這7個問題時，差別不明顯，因此，圖3給出了基本DE算法和改進DEOC算法在求解g01、g02、g04、g05、g08和g13等6個函數(shù)的收斂曲線。

可以看出，DEOC算法與基本的DE算法相比，在收斂速度和收斂精度上都有很大的優(yōu)勢。在對g01和g02函數(shù)進行評價時，DEOC算法的收斂方向選擇更加精確。在對g04函數(shù)進行評價時，DEOC算法在800代左右完成問題優(yōu)化，速度超過基本DE算法。在對g05、g08和g13函數(shù)進行評價時，DEOC算法的收斂精度具有很高的優(yōu)勢，其中g05和g13是含有等式約束的優(yōu)化問題。相對于基本DE算法，DEOC算法快速找到約束域并且快速向可行域最優(yōu)點靠攏。所以，DEOC算法是有效的，并且具有更高的魯棒性和斂速度。

4.2 與其他改進約束算法比較

將DEOC算法與SaCDE[14]、新型ICA[15]、PJAD-CDE[16]和MDE+HJ[17]四種約束算法進行比較。其中SaCDE基于雙進化策略的差分進化算法，同時對進化種群中較差個體進行改造，使種群的整體目標函數(shù)更快速優(yōu)化。新型ICA將種群個體賦予國家發(fā)展思想，通過國內(nèi)改革和國外殖民的競爭戰(zhàn)略思想，使各個小國家向最優(yōu)解發(fā)展。PJAD-CDE采用多種進化策略，并對縮放因子F和變異算子CR進行動態(tài)調(diào)整。MDE+HJ基于文化基因算法，通過利用變量增量、階躍縮減因子和終止準則激勵最優(yōu)解進化。表1給出了五種算法的最好值、平均值和方差值。需要注意的是，表1中給出的SaCDE、新型ICA、PJAD-CDE和MDE+HJ算法實驗結果由各算法對應文獻得到，部分數(shù)據(jù)由參考文獻中數(shù)據(jù)四舍五入得到，其中：SaCDE最大評估次數(shù)為500 000次。新型ICA和PJAD-CDE算法最大評估次數(shù)均為240 000次。MDE+HJ算法的最大評估次數(shù)為125 000次。

表1 算法運行結果比較

續(xù)表1

觀察表1統(tǒng)計值，相對于SaCDE和新型ICA，DEOC在最好值、平均值和方差都表現(xiàn)出較高的優(yōu)勢，尤其在g07、g09、g12測試函數(shù)的方差值，DEOC明顯優(yōu)于其他兩種算法，表明DEOC具有較高的魯棒性；在最好值的搜索中，除g11遜色于SaCDE和新型ICA外，DEOC在其余測試函數(shù)中的最好值均達到最優(yōu)解。相對于PJAD-CDE算法，在對g13函數(shù)實驗時，DEOC算法相比于PJAD-CDE算法表現(xiàn)較差，但兩種算法在對其余函數(shù)求解時，最好解和平均值均取得很好的成績，并且DEOC算法在g02、g04、g07、g09和g10的方差表現(xiàn)出色，所以DEOC算法與PJAD-CDE算法不相上下并且具有較高的穩(wěn)定性。在與MED+HJ算法進行比較時，DEOC算法在對g01、g03、g05、g11和g13問題優(yōu)化結果明顯優(yōu)秀，并且根據(jù)問題的特性，可以認為DEOC算法在處理含有等式的約束優(yōu)化問題時，效果優(yōu)異于MED+HJ算法。因此，DEOC算法具有較高的收斂精度和穩(wěn)定性，并且該算法是有效的。

4.3 蝸輪齒圈優(yōu)化

蝸輪蝸桿減速器可以多齒嚙合、傳動穩(wěn)定，并且具有良好的自鎖能力，所以在機械傳動中應用廣泛，為保證減速器具有良好的減磨抗振性能，蝸輪常用鑄錫青銅和鑄鋁青銅等貴重的軟質材料，提高減速器的柔性。通過優(yōu)化蝸輪蝸桿參數(shù)，可以有效地減小蝸輪齒圈體積，減少貴重金屬的使用量，以達到減少成本的效果。本文以某電梯拽引機的普通圓柱蝸輪蝸桿減速器的蝸輪齒圈體積為優(yōu)化對象，圖4給出蝸輪的二維模型示意圖，已知P1=7 kW，n1=1 400 r/min，i=20，K=1.2，[σH]=220 Mpa，蝸輪加工材料為鑄錫青銅ZCuSn10Pb1。在滿足表面接觸疲勞強度和剛度的條件下，利用DEOC對蝸輪齒圈進行優(yōu)化，根據(jù)目標函數(shù)和約束條件建立式(9)-式(11)的優(yōu)化數(shù)學模型。其中式(11)為參數(shù)的取值，且[z1,m,q]=[x1,x2,x3]，z1為蝸桿頭數(shù)，m為蝸輪模數(shù)，q為蝸桿的直徑系數(shù)。優(yōu)化結果如表2所示。

minf(X)=V(z1,q,m)=

(9)

L′3-[y]≤0

(10)

式中：E為彈性模量；I為蝸桿截面的慣性矩。

2≤x1≤4,3≤x2≤5,5≤x3≤16

(11)

可以看出，基于DEOC優(yōu)化的蝸輪齒圈體積約是常規(guī)設計方法的51.10%，對優(yōu)化后的結果進行圓整處理，圓整體積約是常規(guī)設計方法的70.34%，因此，DEOC優(yōu)化方法大大降低了貴重金屬的成本支出。

4.4 焊接梁優(yōu)化

焊接梁的成本計算問題是驗證約束算法有效性的常用模型，圖5是焊接梁的三維模型示意圖，根據(jù)文獻[18]，得到焊接梁成本問題的目標函數(shù)式(12)和約束函數(shù)式(13)，基于DEOC算法對該模型進行優(yōu)化，并與其他兩種先進的約束優(yōu)化算法MOCoDE[19]和CPSO[20]進行對比，對比結果如表3所示。

minf(X) = 1.104 71x12x2+

0.048 11x3x4(14.0+x2)

(12)

s.t.g1(X)=τ(X)-τmax≤0g2(X)=σ(X)-σmax≤0g3(X)=x1-x4≤0g4(X)=0.104 71x12+0.048 11x3x4· (14.0 +x22)-5.0≤0g5(X)=0.125-x1≤0g6(X)=δ(X)-δmax≤0g7(X)=P-Pc(X)≤0

(13)

可以看出，在對焊接梁成本的優(yōu)化中，DEOC優(yōu)化結果的最小值、平均值和最大值均為當前所得的最優(yōu)解，在最大值和方差比較中均優(yōu)于其他兩種算法，表明本文提出的約束差分進化算法DEOC具有更好的實際工程應用效果。

5 結 語

本文提出一種基于反向學習和可行性準則交叉的約束差分進化算法，采用反向學習對種群初始化和邊界選擇進行處理，有效地提升種群多樣性，同時在Deb準則中加入可行性判斷條件，對滿足可行性準則的個體再次進行交叉處理，可行解進行二次開發(fā)利用，提高算法的收斂速度和穩(wěn)定性。將改進算法應用于蝸輪齒圈和焊接梁優(yōu)化問題中，顯示出DEOC算法在實際工程中應用的有效性。