混合整數(shù)優(yōu)化問題的差分進(jìn)化算法研究

李道軍，李廷鋒，盧青波

（鄭州職業(yè)技術(shù)學(xué)院，鄭州 450121）

0 引言

在機(jī)械優(yōu)化設(shè)計問題中，經(jīng)常會遇到混合整數(shù)優(yōu)化問題，即在數(shù)學(xué)模型中同時存在連續(xù)設(shè)計變量和整型設(shè)計變量，例如：在設(shè)計圓柱齒輪減速器時，齒輪的齒數(shù)是整型設(shè)計變量，減速箱的寬度則是連續(xù)變量。這類問題在機(jī)械工程領(lǐng)域非常普遍，因此對于混合整數(shù)優(yōu)化問題的求解技術(shù)研究具有普遍的工程意義。

混合整數(shù)優(yōu)化問題的數(shù)學(xué)模型一般表示為：

對于上述模型，當(dāng)p=0時為一般的連續(xù)變量問題，當(dāng)p=D時為整數(shù)規(guī)劃問題，其余情況為混合整數(shù)優(yōu)化問題。

針對混合離散性優(yōu)化問題，陳立周[1]給出了一些頗為實用的求解方法。Appa等[2]對混合離散優(yōu)化問題的求解方法進(jìn)行了總結(jié)。連青惠等[3]對非均勻離散變量及連續(xù)變量的均勻離散化方法進(jìn)行了說明，分析了求解混合離散變量優(yōu)化問題的一般方法。軒華等[4]提出了混合離散變量優(yōu)化的灰色混沌復(fù)合遺傳算法。Sun等[5]基于可行規(guī)則提出了求解混合離散變量問題的改進(jìn)粒子群算法。文獻(xiàn)[6]～[11]提出了求解非線性混合整數(shù)非線性規(guī)劃問題的改進(jìn)差分進(jìn)化算法。車林仙等[12]提出了面向工程約束優(yōu)化的混合離散差分進(jìn)化算法。

以上研究利用不同的方法對混合離散性優(yōu)化問題的求解技術(shù)進(jìn)行了研究。其中，文獻(xiàn)[6]～[12]是基于差分進(jìn)化算法的研究，這些研究采用不同方法將差分進(jìn)化算法應(yīng)用到混合整數(shù)非線性優(yōu)化問題的求解中，但都未結(jié)合差分進(jìn)化算法特點(diǎn)為混合整數(shù)優(yōu)化問題設(shè)計通用的求解方法。本文將針對整數(shù)變量的特點(diǎn)，從差分進(jìn)化算法的變異算子入手，研究提出能夠單獨(dú)處理整數(shù)變量的變異算子，使差分進(jìn)化算法能夠直接對整數(shù)變量進(jìn)化，進(jìn)而提出混合整數(shù)優(yōu)化問題的差分進(jìn)化算法，并與已有幾種改進(jìn)算法進(jìn)行對比研究，驗證所提出方法的有效性。

1 基本差分進(jìn)化算法

差分進(jìn)化算法[13]的每個個體用一個實向量來表示，初始種群采用均勻分布的隨機(jī)數(shù)生成。令xi（g）代表第g代的第i個個體，則有

差分進(jìn)化算法的進(jìn)化過程如下所述。

1）初始化種群。在n維實數(shù)空間按式（3）隨機(jī)產(chǎn)生NP個個體：

式中，rand（0，1）為［0，1］上服從均勻分布的隨機(jī)數(shù)。

2）變異算子。變異算子是差分進(jìn)化算法的關(guān)鍵步驟，其過程為從當(dāng)前種群中隨機(jī)選擇3個不同個體xp1、xp2、xp3，且p1≠p2≠p3≠i，則有

式中，F(xiàn)為縮放因子。

3）交叉算子。交叉算子可增加種群的多樣性，其過程如式（5）所示：

式中：CR為交叉概率，CR∈［0，1］；jrand為［1，n］的隨機(jī)整數(shù)，這種交叉模式確保vij（g+1）中至少有1位來自hij（g）。

4）選擇算子。差分進(jìn)化算法采用的是“貪婪”選擇策略，由評價函數(shù)對向量vi（g+1）和向量xi（g）進(jìn)行比較，獲勝者保留。計算公式為：

反復(fù)執(zhí)行式（4）～式（6），直到達(dá)到算法預(yù)設(shè)的終止條件。

2 混合整數(shù)差分進(jìn)化算法

差分進(jìn)化算法的變異算子對候選解的產(chǎn)生起到至關(guān)重要的作用。對于混合整數(shù)問題，如何實現(xiàn)整數(shù)變量的進(jìn)化成為算法求解該類問題的關(guān)鍵。因此，本文針對整數(shù)類型變量設(shè)計專用的變異算子，以使整數(shù)變量能夠直接參與進(jìn)化。

2.1 整數(shù)變量的初始化

2.2 整數(shù)變量的變異算子

對于整數(shù)變量，為保證其變異后的結(jié)果仍為整數(shù)變量，這里首先對式（4）中的F約束為隨機(jī)整數(shù)RandInt（0，F(xiàn)max）。其中Fmax為最大整數(shù)取值。其次，為保證隨機(jī)性，對式（4）的求解結(jié)果進(jìn)行處理，具體的處理過程如表1所示。

表1 算法1的均勻離散變量變異算子偽代碼

2.3 災(zāi)變策略

采用差分進(jìn)化算法時，隨著進(jìn)化代數(shù)的增加，群體的差異度縮小，尤其是在變量取值較少的情況下，這種縮小會很快，從而使群體陷入局部最優(yōu)解。為減緩這種趨勢，提升算法的全局搜索能力，引入災(zāi)變因子DF，對群體中的個體進(jìn)行小概率淘汰，使群體中的個體在進(jìn)化中以一定的概率淘汰。這樣的操作保證了群體中有新個體的加入，達(dá)到提升群體多樣性的目的，從而提升算法的全局搜索能力。本文設(shè)置當(dāng)個體在選擇操作后，若父代個體未更新且滿足rand（0，1）＜DF，則對父代個體進(jìn)行重新初始化。

2.4 混合整數(shù)差分進(jìn)化算法流程

結(jié)合算法1與災(zāi)變操作，提出混合整數(shù)差分進(jìn)化算法（Mixed-Integer Differential Evolution，MIDE）。其算法流程如下所示。

Step 1：初始化算法參數(shù)；

Step 2：對整數(shù)變量與連續(xù)變量分別在其定義域內(nèi)隨機(jī)初始化；

Step 3：對每個個體執(zhí)行：

Step 3.1：變異操作，整數(shù)變量按算法1進(jìn)行，連續(xù)變量按標(biāo)準(zhǔn)DE算法執(zhí)行；

Step 3.2：交叉操作；

Step 3.3：選擇操作，若個體未進(jìn)行更新且滿足rand（0，1）＜DF，對該個體初始化；

Step 4：判斷是否達(dá)到收斂條件，否則轉(zhuǎn)Step 3繼續(xù)執(zhí)行；

Step 5：輸出結(jié)果。

3 仿真與分析

為檢測MIDE算法的性能，設(shè)置種群大小為100，將整數(shù)變量變異算子中的縮放因子設(shè)置為RandInt（0，3），即取0～3中的隨機(jī)整數(shù)，將連續(xù)變量的縮放因子設(shè)置為0.5，將交叉率設(shè)置為0.1，將災(zāi)變因子設(shè)置為0.01，每個問題獨(dú)立運(yùn)行50次。測試環(huán)境為：Intel CoreTMi5，8 GB RAM，Win7，VS2010。

本文采用Deb提出的可行規(guī)則方法[14]處理約束條件。

1）問題1。多項式優(yōu)化問題：

式中：-10≤xi≤10，且xi為整數(shù)（i=1，2，…，7）。

該問題的最優(yōu)解為x*=（2，2，0，4，0，1，2），函數(shù)最優(yōu)值為f1（x）min=700。

2）問題2。Himielblau約束優(yōu)化問題：

其中：

式中：78≤x1≤102，33≤x2≤45，27≤x3、x4、x5≤45，且所有變量取整數(shù)。

3）問題3。混合整數(shù)優(yōu)化多項式問題：

該問題的全局最優(yōu)解為：x*=（1，0，0，1，0.2，1.280624，1.954483），函數(shù)最優(yōu)值為f3（x）min=3.557463。

文獻(xiàn)[12]采用問題1與問題2測試HDDESPF算法處理整數(shù)規(guī)劃問題的能力。文獻(xiàn)[7]采用問題3測試算法處理混合整數(shù)優(yōu)化問題的能力。本文采用以上3個問題測試所提出的MIDE算法的性能。

表2給出了MIDE算法進(jìn)化500代的求解結(jié)果與其它算法的比較。從表2數(shù)據(jù)可以看出，MIDE算法與HDDESPF及DDESPF算法都能較好地求解該問題，但本文算法平均耗時最短。從圖1的收斂曲線可以看出，MIDE算法在進(jìn)化約125代（函數(shù)評價次數(shù)約為12 500次）后，獲得最優(yōu)值。

圖1 MIDE算法求解f1（x）的收斂曲線

表2 4種算法求解f1（x）的統(tǒng)計結(jié)果比較

表3給出了4種算法求解問題2的統(tǒng)計結(jié)果比較。從表3中數(shù)據(jù)可以看出，MIDE算法獲得了新的最優(yōu)值，且能完全收斂到該新的最優(yōu)解。圖2為MIDE算法求解f2（x）時的收斂曲線。從圖2中可以看出，MIDE算法在200代之前（即目標(biāo)函數(shù)的評價次數(shù)為20 000次）獲得了該問題的最優(yōu)解。

圖2 MIDE算法求解f2（x）的收斂曲線

表3 4種算法求解f2（x）的統(tǒng)計結(jié)果比較

DDESPF與HDDESPF獲得的f2（x）的最優(yōu)解為：x*=（81，33，30，45，36），函數(shù)最優(yōu)值為f2（x）min=-30512.45。MIDE算法進(jìn)化1000代的最優(yōu)解為x*=（78，33，30，45，37），函數(shù)最優(yōu)值為f2（x）min=-30649.40。其中約束條件的值為：g1（x）=91.9929，g2（x）=98.8939，g3（x）=20.0333。該解為可行解。

表4給出了3種算法求解問題3的結(jié)果比較。其中，MIDE算法結(jié)果采用文獻(xiàn)[7]中算法設(shè)置。從表4中數(shù)據(jù)可以看出，MIDE算法在相同設(shè)置下，獲得的最優(yōu)解要優(yōu)于其余2種算法，且算法能穩(wěn)定收斂。圖3給出了3種算法求解f2（x）時的收斂曲線比較。從圖3中可以看出，MIDE在進(jìn)化400代左右收斂到最優(yōu)點(diǎn)，其收斂速度要快于MIHDE與CLSDE算法。

圖3 3種算法求解f3（x）的收斂曲線

表4 3種算法求解f2（x）的統(tǒng)計結(jié)果比較

4 結(jié)論

本文結(jié)合混合整數(shù)優(yōu)化問題的特點(diǎn)，為差分進(jìn)化算法設(shè)計了整數(shù)變量的變異算子，進(jìn)而提出了混合整數(shù)差分進(jìn)化算法。與自適應(yīng)罰函數(shù)混合離散差分進(jìn)化算法（HDDESPF）及CLSDE算法進(jìn)行了試驗對比，結(jié)果表明：1）本文算法在運(yùn)行時間上要優(yōu)于HDDESPF算法，并在Himielblau約束優(yōu)化問題上獲取了比HDDESPF問題更優(yōu)的最優(yōu)解，且能穩(wěn)定收斂到該最優(yōu)解；2）在算法的收斂性及穩(wěn)定性上要優(yōu)于CLSDE算法；3）由于算法設(shè)計了整數(shù)變量的變異算子，使得進(jìn)化直接在整數(shù)域內(nèi)進(jìn)行，因此比應(yīng)用于整數(shù)規(guī)劃優(yōu)化問題求解更快，如背包問題。

MIDE的測試結(jié)果表明了其優(yōu)化性能，下一步將研究其在更廣泛領(lǐng)域（如0/1背包問題、旅行商問題、車間調(diào)度問題等）中的應(yīng)用。