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

李道軍，李廷鋒，盧青波

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

0 引言

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

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

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

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

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

1 基本差分進化算法

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

差分進化算法的進化過程如下所述。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 災變策略

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

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

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

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

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

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

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

Step 3.2：交叉操作；

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

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

Step 5：輸出結果。

3 仿真與分析

為檢測MIDE算法的性能，設置種群大小為100，將整數(shù)變量變異算子中的縮放因子設置為RandInt（0，3），即取0～3中的隨機整數(shù)，將連續(xù)變量的縮放因子設置為0.5，將交叉率設置為0.1，將災變因子設置為0.01，每個問題獨立運行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。

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

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

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

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

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

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

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

DDESPF與HDDESPF獲得的f2（x）的最優(yōu)解為：x*=（81，33，30，45，36），函數(shù)最優(yōu)值為f2（x）min=-30512.45。MIDE算法進化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的結果比較。其中，MIDE算法結果采用文獻[7]中算法設置。從表4中數(shù)據(jù)可以看出，MIDE算法在相同設置下，獲得的最優(yōu)解要優(yōu)于其余2種算法，且算法能穩(wěn)定收斂。圖3給出了3種算法求解f2（x）時的收斂曲線比較。從圖3中可以看出，MIDE在進化400代左右收斂到最優(yōu)點，其收斂速度要快于MIHDE與CLSDE算法。

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

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

4 結論

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

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