無約束優(yōu)化問題的差分進(jìn)化算法求解

洪云飛 （長江大學(xué)期刊社；信息與數(shù)學(xué)學(xué)院，湖北 荊州434023）

陳 忠 （長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州434023）

差分進(jìn)化算法 （Differential Evolution，DE）是一種基于群體差異的啟發(fā)式隨機(jī)搜索算法［1］。差分進(jìn)化算法具有全局優(yōu)化性能好，結(jié)構(gòu)簡單和易于實(shí)現(xiàn)的特點(diǎn)，在函數(shù)優(yōu)化［2－3］、多目標(biāo)優(yōu)化［4］、背包問題［5－6］、系統(tǒng)辨識［7－8］等方面得到廣泛應(yīng)用。下面，筆者利用差分進(jìn)化算法求解無約束優(yōu)化問題。

1 約束優(yōu)化問題的數(shù)學(xué)描述

不失一般性，以最小化問題為例，無約束優(yōu)化問題可描述為：

其中，S＝ ｛x∈Rn｜li≤xi≤ui，i＝1，2，…，n｝為問題的可行域。

2 差分進(jìn)化算法的構(gòu)成要素

1）編碼方法 使用差分進(jìn)化算法求解一個問題之前，需要選擇一種編碼方法。編碼就是將實(shí)際問題的解用一種便于算法操作的形式來描述。根據(jù)問題的具體情況，可以靈活選擇編碼方式。如對于排序問題可采取順序編碼，對于背包問題可以采取0－1編碼。對于實(shí)優(yōu)化問題，一般可以直接使用實(shí)數(shù)編碼，編碼的每一位就是解的相應(yīng)維的取值。筆者選擇實(shí)數(shù)編碼作為算法實(shí)現(xiàn)的編碼方式。

2）適應(yīng)度函數(shù)的構(gòu)造 類似于遺傳算法，差分進(jìn)化算法的適應(yīng)度函數(shù)也是用來對搜索狀態(tài)進(jìn)行評價(jià)的。一般情況下，將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)是最直接也是最容易理解的做法。當(dāng)然，對目標(biāo)函數(shù)的任何變形都可以作為適應(yīng)度函數(shù)，只要這個變形是嚴(yán)格單調(diào)的。筆者直接把目標(biāo)函數(shù)作為適應(yīng)度函數(shù)。

3）種群規(guī)模 種群規(guī)模NP是一個整型參數(shù)。當(dāng)NP很小的時(shí)候，由于無法保證種群的多樣性，算法容易陷入局部最優(yōu)解。然而，種群規(guī)模過大將導(dǎo)致計(jì)算時(shí)間大幅增加，降低算法的執(zhí)行效率。并且當(dāng)種群規(guī)模增長到一定水平時(shí)，繼續(xù)增加種群規(guī)模將不再有顯著作用。因此，針對不同的具體問題，需要設(shè)置合適的種群規(guī)模算法才能達(dá)到較好的搜索性能。

4）初始解的獲得 差分進(jìn)化算法可以隨機(jī)給出初始解，也可以事先使用其他算法給出一個較好的初始解。由于差分進(jìn)化算法主要是基于個體之間的差異推動群體進(jìn)化，因此初始解的好壞對算法的搜索性能有較大影響。尤其是一些帶有復(fù)雜約束的優(yōu)化問題，隨機(jī)給出的初始解很可能是不可行的，甚至通過多步搜索也很難找到一個可行解，這個時(shí)候應(yīng)該針對特定的復(fù)雜約束，采用啟發(fā)式方法或其他方法找到可行解作為初始解。筆者以標(biāo)準(zhǔn)測試函數(shù)檢測算法性能時(shí)采用隨機(jī)方式生成初始解。

5）進(jìn)化操作 差分進(jìn)化算法的基本進(jìn)化操作包括變異、交叉和選擇。算法在優(yōu)化迭代過程中，采用規(guī)模為NP的D維向量（i＝1，2，…，NP）作為第g代的種群，在搜索空間中進(jìn)行尋優(yōu)，其中NP為種群規(guī)模，D為解空間維數(shù)。

式中，CR為交叉概率，范圍在0～1之間；rand（）為0～1范圍內(nèi)生成的隨機(jī)數(shù)；jrand為1～D之間隨機(jī)選取的整數(shù)隨機(jī)量。

式中，f（·）為適應(yīng)度函數(shù)。

6）停止準(zhǔn)則 一般使用最大迭代次數(shù)或可以接受的滿意解作為停止準(zhǔn)則。筆者選擇最大迭代次數(shù)作為算法停止的控制參數(shù)。

3 差分進(jìn)化算法步驟和流程

差分進(jìn)化算法執(zhí)行的步驟如下：

Step1 初始化。根據(jù)具體問題初始化種群。

Step2 判斷是否滿足停止條件。如果滿足，輸出結(jié)果，算法停止；否則繼續(xù)一下步驟。

Step3 執(zhí)行變異操作。從父代群體中隨機(jī)選取3個個體，按照式 （2）執(zhí)行變異操作，得到變異個體；

Step4 執(zhí)行交叉操作。對變異個體按式 （3）執(zhí)行交叉操作，得到交叉?zhèn)€體；

Step5 執(zhí)行選擇操作。計(jì)算交叉?zhèn)€體的適應(yīng)值，并與原個體進(jìn)行比較，依據(jù)貪婪選擇原則執(zhí)行選擇操作，返回Step2；

差分進(jìn)化算法的執(zhí)行流程如圖1所示。

圖1 差分進(jìn)化算法流程

4 數(shù)值試驗(yàn)

通過標(biāo)準(zhǔn)測試函數(shù)來分析差分進(jìn)化算法在求解數(shù)值優(yōu)化問題時(shí)的尋優(yōu)性能。筆者選取的標(biāo)準(zhǔn)測試函數(shù)如下：

對于待求解問題本身來說，問題維度是影響計(jì)算規(guī)模的關(guān)鍵因素。對于求解算法而言，控制參數(shù)是影響算法性能的關(guān)鍵因素。在差分進(jìn)化算法中，有3個主要控制參數(shù)：種群規(guī)模NP、變異操作中差分向量的縮放因子F以及交叉操作中的交叉因子CR。因此，筆者首先通過上述標(biāo)準(zhǔn)測試函數(shù)對差分進(jìn)化算法的計(jì)算性能進(jìn)行初步檢驗(yàn)，同時(shí)分析不同控制參數(shù)對差分進(jìn)化算法計(jì)算性能的影響，從而獲取比較合適的控制參數(shù)設(shè)置范圍，并以此為基礎(chǔ)展開后續(xù)并行差分進(jìn)化算法的研究和測試工作。

較大的種群規(guī)模，一方面可以容納更多的不同個體，為種群多樣性提供了可能；另一方面增加了需要進(jìn)行評價(jià)計(jì)算的個體數(shù)量，也就意味著算法尋優(yōu)的時(shí)間必然要增加。因此，不能簡單地說種群規(guī)模的變化對算法求解性能影響的利弊，而需要進(jìn)行大量模擬計(jì)算，把種群規(guī)模控制在一個合理的范圍內(nèi)，既保證差分進(jìn)化算法有足夠的特征各異的進(jìn)化個體，又兼顧算法的求解耗時(shí)。

將問題維度固定為30，迭代次數(shù)為1000，縮放因子F固定為0.6，交叉因子CR固定為0.8，在不同種群規(guī)模情況下以差分進(jìn)化算法對上述5個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行模擬計(jì)算，模擬計(jì)算結(jié)果如表1所示。

表1 不同種群規(guī)模下測試函數(shù)的模擬計(jì)算結(jié)果

由表1可見，當(dāng)問題維度為30時(shí)，隨著種群規(guī)模的增加，差分進(jìn)化算法尋優(yōu)得到的結(jié)果逐漸向全局最優(yōu)點(diǎn)靠近，但是當(dāng)種群規(guī)模超過200左右時(shí)，算法的尋優(yōu)結(jié)果并沒有繼續(xù)呈現(xiàn)較強(qiáng)的向全局最優(yōu)點(diǎn)逼近的趨勢，反而呈現(xiàn)出一種震蕩或回退的趨勢，如圖2所示。該現(xiàn)象說明，在問題維度一定的情況下，種群規(guī)模超過某個閾值后，繼續(xù)增加種群規(guī)模未必能夠帶來尋優(yōu)性能的增加。但是可以預(yù)見的是，其計(jì)算耗時(shí)必然會隨著種群規(guī)模的擴(kuò)大而迅速增加。

圖2 適應(yīng)值與種群規(guī)模的關(guān)系

［1］Storn R，Price K.Differential evolution－A simple heuristic for global optimization over continuous spaces ［J］.Journal of Global Optimization，1997，11 （4）：341－359.

［2］Ali M M.Differential evolution with preferential crossover ［J］.European Journal of Operations Research，2007，181 （3）：1137－1147.

［3］Noman N，Iba H.Accelerating differential evolution using an adaptive local search ［J］.IEEE Trans on Evolutionary Computation，2008，12 （1）：107－125.

［4］Iorio A W，Li X D.Solving rotated multi－objective optimization problems using differential evolution ［A］.Proceeding of the 17th Australian joint conference on advances in artificial intelligence ［C］.Cairns，Australia，2004：861－872.

［5］Chen Peng，Li Jian，Liu Zhiming.Solving 0－1knapsack problems by a discrete binary version of differential Evolution ［A］.Proceeding of the 2nd International Symposium on Intelligent Information Technology Application ［C］.Shanghai，China，2008，II：513－516.

［5］Wang Ling，F(xiàn)u Xiping，Mao Yunfei，et al.A novel modified binary differential evolution algorithm and its applications ［J］.Neuron computing，2012，98 （5）：55－75.

［7］Peng Bo，Liu Bo，Zhang Fuyi，et al.differential evolution algorithm based parameter estimation for chaotic systems［J］.Chaos，Solutions and Fractals，2009，39 （5）：2110－2118.

［8］Zhang Rui，Song Shiji，Wu Cheng.A hybrid differential evolution algorithm for job shop scheduling problems with expected total tardiness criterion ［J］.Applied Soft Computing，2013，13 （3）：1448－1458.