基于反向?qū)W習(xí)和可行性準(zhǔn)則交叉的約束差分進(jìn)化算法

段 偉 徐 斌

(上海工程技術(shù)大學(xué)機(jī)械與汽車工程學(xué)院 上海 201620)

Crossover operator Engineering application

0 引 言

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

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

(4)

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

(5)

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

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

(6)

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

(7)

1.3 Deb準(zhǔn)則

Deb準(zhǔn)則是應(yīng)用最廣泛的約束處理方法之一，與其他方法相比，Deb準(zhǔn)則不需要定義額外參數(shù)，只需根據(jù)問題的目標(biāo)函數(shù)和約束違反值就篩選出絕對優(yōu)秀的目標(biāo)個體。對于給定的兩個個體xi和ui，當(dāng)滿足下列條件之一時，稱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 改進(jìn)的約束差分進(jìn)化算法

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

2.1 基于反向?qū)W習(xí)的種群初始化

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

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

2. Fori=1 toN

3. Forj=1 toD

5. End for

//反向?qū)W習(xí)的初始個體

7. End for

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

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

2.2 基于反向?qū)W習(xí)的邊界處理

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

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

(8)

3 可行性準(zhǔn)則交叉算子

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

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

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中挑選出適應(yīng)值小的N個個體更新種群X。

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

4 實驗驗證與工程應(yīng)用

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

4.1 與基本的DE算法DE/rand/1進(jìn)行比較

將DEOC算法與基本的DE算法進(jìn)行比較，兩種算法參數(shù)設(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算法和改進(jìn)DEOC算法在求解g01、g02、g04、g05、g08和g13等6個函數(shù)的收斂曲線。

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

4.2 與其他改進(jìn)約束算法比較

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

表1 算法運行結(jié)果比較

續(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ù)中的最好值均達(dá)到最優(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算法進(jìn)行比較時，DEOC算法在對g01、g03、g05、g11和g13問題優(yōu)化結(jié)果明顯優(yōu)秀，并且根據(jù)問題的特性，可以認(rèn)為DEOC算法在處理含有等式的約束優(yōu)化問題時，效果優(yōu)異于MED+HJ算法。因此，DEOC算法具有較高的收斂精度和穩(wěn)定性，并且該算法是有效的。

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

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

4.4 焊接梁優(yōu)化

焊接梁的成本計算問題是驗證約束算法有效性的常用模型，圖5是焊接梁的三維模型示意圖，根據(jù)文獻(xiàn)[18]，得到焊接梁成本問題的目標(biāo)函數(shù)式(12)和約束函數(shù)式(13)，基于DEOC算法對該模型進(jìn)行優(yōu)化，并與其他兩種先進(jìn)的約束優(yōu)化算法MOCoDE[19]和CPSO[20]進(jìn)行對比，對比結(jié)果如表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)化結(jié)果的最小值、平均值和最大值均為當(dāng)前所得的最優(yōu)解，在最大值和方差比較中均優(yōu)于其他兩種算法，表明本文提出的約束差分進(jìn)化算法DEOC具有更好的實際工程應(yīng)用效果。

5 結(jié) 語

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