求解約束優(yōu)化問題的動態(tài)目標(biāo)遷移差分進(jìn)化算法＊

劉俊梅 馬永剛 高岳林

（中國礦業(yè)大學(xué)銀川學(xué)院基礎(chǔ)部數(shù)學(xué)教研室1） 銀川 750011）（北方民族大學(xué)信息與系統(tǒng)科學(xué)研究所2） 銀川 750021）

0 引 言

考慮以下約束優(yōu)化問題（constrained optimization problems，COPs）：

式中：gi（x），hj（x），i＝1，2，…，m；j＝1，2，…，n是Rn上有的連續(xù)實(shí)函數(shù).設(shè)Ω＝｛x：≤xd≤，d＝1，2，…，n｝，F(xiàn)是問題（1）的可行域.

約束優(yōu)化問題廣泛存在于許多領(lǐng)域，如貨物分配、股票分析等.然而處理約束條件是求解約束優(yōu)化問題的關(guān)鍵，目前，處理約束優(yōu)化問題的主要方法是罰函數(shù)方法，懲罰函數(shù)不足之處，是很難找到適當(dāng)?shù)膽土P因子.為了克服此缺點(diǎn)，K.Deb等人［1－2］利用遺傳算法競爭選擇策略，引入了不需要懲罰因子而直接比較個體優(yōu)劣的方法，但是該方法搜索能力不強(qiáng)，Liu Bo［3］提出的協(xié)同進(jìn)化差分進(jìn)化算法（CODE）.

近年來，除了罰函數(shù)法，一些新穎的技術(shù)也被融入到進(jìn)化算法中用來處理約束，Runarsson和Yao［4］提出了一種隨機(jī)排序法來處理約束技術(shù)（SR），M.M.Efren［5］等提出的簡單可行基規(guī)則差分進(jìn)化（CHDE），Lu和Chen［6］提出了自適應(yīng)速度改進(jìn)的粒子群優(yōu)化算法求解約束優(yōu)化問題，采用動態(tài)多目標(biāo)方法處理約束.

以上這些方法均提出了可行解優(yōu)于不可行解的規(guī)則，它沒有充分考慮到約束邊界周圍的個體，對于這類問題，位于最優(yōu)解附近的不可行解對于尋找最優(yōu)解是很有幫助的.

針對形如式（1）的非線性約束優(yōu)化問題，提出了一種改進(jìn)的差分進(jìn)化算法.該算法在初始化中加入遷移操作，采用動態(tài)雙目標(biāo)的約束處理方法，將其轉(zhuǎn)化為無約束雙目標(biāo)優(yōu)化問題，當(dāng)個體的違反約束度在容忍度以外時，通過違反約束度函數(shù)更新個體，當(dāng)個體的違反約束度在容忍度以內(nèi)時，通過原目標(biāo)函數(shù)更新個體，在每次迭代中保留一部分性能較優(yōu)的不可行個體，擴(kuò)大了個體的搜索范圍，增強(qiáng)了算法尋優(yōu)效果.

1 遷移初始化及基本差分進(jìn)化算法的改進(jìn)

1.1 遷移初始化

在基本差分進(jìn)化算法［7］中，初始化過程是隨機(jī)的，隨機(jī)過程大多可以保證初始種群分布均勻，但對個體的質(zhì)量不能保證，種群中有一部分個體遠(yuǎn)離可行域.如果初始種群較好，將有助于提高算法的效率和求解質(zhì)量.

本文采取初始化遷移操作，對隨機(jī)產(chǎn)生的個體按照一定的約束違反度進(jìn)行選擇，將遠(yuǎn)離可行域的個體向可行域方向遷移，以此提高個體的質(zhì)量.

定義約束違反度函數(shù)

顯然，φ（x）是所有違反約束的和，φ（x）≥0，并且φ（x）＝0當(dāng)且僅當(dāng)x∈F.

根據(jù)式（2）計算初始種群P0中每個個體的約束違反度，將約束違反度小于等于δ1的個體放入種群P1，否則，將個體放入種群P2，然后將種群P2中的個體進(jìn)行遷移操作，遷移操作公式如下

式中：α為常數(shù)，本文取α＝0.6；R為隨機(jī)選擇的種群P1中的個體；S為種群P2中的個體，用新產(chǎn)生的個體X替換個體S。按照式（4）將種群P2中每個個體進(jìn)行替換，然后將種群P1和P2合并為一個種群，這樣就可以提高種群中個體的質(zhì)量，根據(jù)需要可以連續(xù)進(jìn)行L次以上的種群遷移操作，本文取L＝5，每進(jìn)行一次種群遷移操作，違反約束容忍度變?yōu)樵瓉淼?.1倍.

1.2 基本差分進(jìn)化算法的改進(jìn)

1.2.1 變異操作 DE最基本的變異成分是父代的差分矢量，種群中每個矢量對父代兩個不同的個體根據(jù)式（5）產(chǎn)生變異個體，變異操作的方程為

1.2.2 交叉操作 DE利用交叉操作以保持種群的多樣性.將個體與xm進(jìn)行交叉操作，產(chǎn)生試驗個體vi.為保證個體的進(jìn)化，首先通過隨機(jī)選擇，使得vi至少有一位由xm貢獻(xiàn)，而對于其他位，可利用交叉概率因子CR，決定vi中那位由xm貢獻(xiàn)，那位由貢獻(xiàn).交叉操作的方程為

式中：rand（）為［0，1］之間的均勻分布的隨機(jī)數(shù)；交叉概率因子CR∈［0，1］.

針對基本DE算法中參數(shù)取固定值容易陷入局部極值的問題，本文采用隨迭代次數(shù)線性遞增的交叉概率因子，更新公式為

式中：t為當(dāng)前迭代次數(shù)；Tmax為最大迭代次數(shù)；參數(shù)CRmin，CRmax表示交叉概率因子的下界和上界，該交叉概率能良好的平衡全局搜索能力和局部搜索能力.

1.2.3 選擇操作 基本DE算法采用“貪婪”的搜索策略，經(jīng)過變異與交叉操作后生成的試驗個體vi與進(jìn)行競爭，只有當(dāng)vi的適應(yīng)度值較更優(yōu)時才被選作子代，否則，直接將作為子代.這種選擇策略也是一種精英保留策略，考慮到約束優(yōu)化問題的非線性約束條件，算法將對這種選擇策略進(jìn)行修正.

對于vi和的競爭，種群最優(yōu)個體xbest的進(jìn)化，本文依據(jù)違反約束度函數(shù)和原目標(biāo)函數(shù)進(jìn)行選擇操作，當(dāng)個體的違反約束度在容忍度以外時，通過違反約束度函數(shù)更新個體，當(dāng)個體的違反約束度在容忍度以內(nèi)時，通過原目標(biāo)函數(shù)更新個體，具體操作見算法1.

2 求解約束優(yōu)化問題的動態(tài)目標(biāo)遷移差分進(jìn)化算法

2.1 約束處理技術(shù)

本文采取動態(tài)目標(biāo)的處理方法，它的主要思想是將約束違反度函數(shù)作為優(yōu)化的第一個目標(biāo)，將目標(biāo)函數(shù)作為第二個目標(biāo)進(jìn)行優(yōu)化.

因此求解約束優(yōu)化問題（COPs）就可以轉(zhuǎn)化為無約束雙目標(biāo)優(yōu)化問題

本文設(shè)置一個閥值δ2≥0，使得φ（x）≤δ2時，就開始優(yōu)化f（x）.如果個體x在可行域的外面，（即φ（x）＞δ2），則個體以φ（x）為其優(yōu)化目標(biāo)，否則，個體以目標(biāo)函數(shù)f（x）進(jìn)行優(yōu)化.更新個體xi和全局最優(yōu)個體xbest的具體流程（記為算法1）如下.

式中：Tmax為最大迭代次數(shù)；δ2的初始值取為10－5.

2.2 違反簡單邊界約束的處理技術(shù)

在某些情況下，xi新產(chǎn)生的試驗向量vi會逃離簡單邊界約束，就會給算法帶來不必要的計算.為此，如果某個試驗向量逃離簡單邊界用舊個體xi和邊界）的平均值來取代試驗向量［8］.

2.3 改進(jìn)差分進(jìn)化算法（DOMDE）

步驟1 （初始化設(shè)置）確定種群的大小N，搜索空間的維數(shù)n，收縮因子F，交叉概率R的上下界，初始化約束違反容忍度δ1，初始化閥值δ2，最大迭代次數(shù)Tmax，遷移初始化總代數(shù)L，設(shè)置當(dāng)前迭代代數(shù)t＝1.

步驟2 遷移初始化

1）按照式（3）隨機(jī)產(chǎn)生N個n維向量.

2）由式（2）計算粒子群的約束違反度，如果φ（xi）≤δ1，將第i個個體加入到種群P1，否則，加

步驟3 若A＝ ｛x｜φ（x）≤δ2｝≠Φ，取初始全局最優(yōu)位置xbest＝arg，否則xbest＝入到種群P2，然后對P2中的每個個體按照式（4）進(jìn)行遷移操作，最后將種群P1和種群P2合并為種群P，直到進(jìn)行L次種群遷移操作為止.

步驟4 根據(jù)式（5）、（6）、（7）產(chǎn)生試驗向量，如果試驗向量的某一分量xid（t）（d＝1，2，…，n）越出邊界，則按式（10）對其分量重新賦值.

步驟5 根據(jù)算法1（見3.1）更新每個個體和全局最優(yōu)個體.

步驟6 讓t＝t＋1，返回到步驟3，直到達(dá)到設(shè)定的最大迭代次數(shù)停止.

3 數(shù)值實(shí)驗及分析

為了驗證本文算法（DOMDE）的有效性，選取6個測試函數(shù)［9］進(jìn)行試驗，將試驗的結(jié)果與已有的結(jié)果進(jìn)行比較.這些測試函數(shù)被認(rèn)為是用進(jìn)化算法很難優(yōu)化的復(fù)雜函數(shù)，這些測試函數(shù)的主要特性如表1所列.在表1中，ρ＝｜F｜／｜S｜是估計可行域占整個搜索空間的比率，｜F｜表示可行解的個數(shù)，｜S｜表示整個搜索空間隨機(jī)產(chǎn)生解的個數(shù)，在實(shí)驗中｜S｜＝1000 000.其中LI，NI，LE，NE分別表示約束優(yōu)化問題約束條件中線性不等式、非線性不等式、線性等式、非線性等式的個數(shù).

表1 6個測試函數(shù)的主要性質(zhì)

數(shù)值實(shí)驗在Matlab7.8中進(jìn)行，在計算中，群體規(guī)模 N＝10n，F(xiàn)＝0.6，CRmin＝0.1，CRmax＝0.9，初始化的約束違反度容忍度δ1在問題g04，g09中取為1，在g03中取為5，在g06中取為4 000，在g08中取為8，初始閥值δ2均取為10－5，最大迭代次數(shù)Tmax＝1 000，根據(jù)試驗問題g01中沒有進(jìn)行遷移初始化操作，其余5個問題中遷移初始化進(jìn)化代數(shù)L取為5.每個測試函數(shù)在相同的條件下獨(dú)立運(yùn)行20次，函數(shù)的最優(yōu)值（記為Opt）以及20次實(shí)驗的最好結(jié)果（記為Best）、中間值（記為Median）、最優(yōu)值平均值（記為Mean）、最差結(jié)果（記為Worst）以及標(biāo)準(zhǔn)差（記為Std）見表2.

表2 測試函數(shù)運(yùn)行結(jié)果的比較表

問題g03是極大化問題，利用－f（x）將其轉(zhuǎn)化為極小化問題.由表2可見，DOMDE算法對于大多數(shù)優(yōu)化問題基本上都找到了最優(yōu)解，并且標(biāo)準(zhǔn)差也比較小.問題g01有2個局部極小－13.000和－12.453 125，20次獨(dú)立實(shí)驗算法都跳出這兩個局部極小點(diǎn).對于6個測試函數(shù)，DOMDE算法也基本上達(dá)到了較為滿意的結(jié)果，新算法（DOMDE）與HM結(jié)果的比較見表3.

表3 新算法（DOMDE）與HM［9］結(jié)果的比較表

由表3可見，DOMDE算法不僅從20次運(yùn)行的最好值，平均最好值，還是最差值，都比HM算法的尋優(yōu)性能好，并且對于復(fù)雜的、利用進(jìn)化算法難優(yōu)化的g06問題，HM算法沒有好的計算結(jié)果，而新算法DOMDE也基本上達(dá)到了最優(yōu)解.

4 結(jié)束語

本文給出了一種求解約束優(yōu)化問題的動態(tài)目標(biāo)遷移差分進(jìn)化算法（DOMDE）.針對隨機(jī)初始化種群個體的質(zhì)量不高，有許多個體可能遠(yuǎn)離可行域，采用遷移初始化提高初始種群的質(zhì)量.將基本差分進(jìn)化算法的選擇操作進(jìn)行修正，采用動態(tài)目標(biāo)的處理約束方法來更新種群個體和全局個體，當(dāng)個體的違反約束度在容忍度以外時，通過違反約束度函數(shù)更新個體，當(dāng)個體的違反約束度在容忍度以內(nèi)時，通過原目標(biāo)函數(shù)更新個體.給出一種特殊的違反簡單邊界約束的處理技術(shù)，提高算法的尋優(yōu)能力.將DOMDE算法的測試數(shù)值與目前已知的最優(yōu)數(shù)值以及HM隨機(jī)性方法得到的數(shù)值結(jié)果進(jìn)行對比，顯示出DOMDE算法的有效性，通用性和穩(wěn)健性，是一種有潛力的全局優(yōu)化算法.

［1］沈文勝，熊方方.混合型非線性規(guī)劃的 MATLAB實(shí)現(xiàn)方法［J］.武漢理工大學(xué)：交通科學(xué)與工程版，2011，35（2）：413－416.

［2］DEB K，AGRAWAL S.A niched－penalty approach for constraint handling in genetic algorithm［C］／／Proc of the Icennga－99，Portorz，1999：234－239.

［3］LIU Bo，HAN Nan，ZHANG Xuejun.A co－evolutionary differential algorithm for constrained optimization［C］／／3th International Conference on Natural Computation（ICNC 2007），China，Haikou，2007：51－57.

［4］RUNARSSON T P，YAO X.Stochastic ranking for constrained evolutionary optimization［J］.IEEE Trans Evol Comput，2000，4（3）：284－294.

［5］EFREN M M，CARLOS A，COELLO C，et al.Simple feasibility rules and differential evolution for constrained optimization［C］／／3th Mexican International Conference on Artificial Intelligence（MICAI 2004），Mexico City，MX，2004：707－716.

［6］LU Haiyan，CHEN Weiqi.Self－adaptive velocity particle swarm optimization for solving constrained optimization problems［J］.Journal of Global Optimization，2008，41（3）：427－445.

［7］STORN R，PRICE K.Differential evolution－a simple and efficient adaptive scheme for global optimization over continuous spaces［R］.Berkley：Technical Report International Computer Science Institute，1995.

［8］KARIN Z，RAINER L.Constrained single－objective optimization using differential evolution［C］／／Proceedings of the Congress on Evolutionary Computation 2006（CEC′2006）.Vancouver，Canada，2006：927－934.

［9］KOZIEL S，MICHALEWICZ Z.Evolutionary algorithms，homomorphous mapping，and constrained parameter optimization［J］.Evolutionary Computation，1999，7（1）：19－44.