求解約束優化問題的動態目標遷移差分進化算法＊

劉俊梅 馬永剛 高岳林

（中國礦業大學銀川學院基礎部數學教研室1） 銀川 750011）（北方民族大學信息與系統科學研究所2） 銀川 750021）

0 引 言

考慮以下約束優化問題（constrained optimization problems，COPs）：

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

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

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

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

針對形如式（1）的非線性約束優化問題，提出了一種改進的差分進化算法.該算法在初始化中加入遷移操作，采用動態雙目標的約束處理方法，將其轉化為無約束雙目標優化問題，當個體的違反約束度在容忍度以外時，通過違反約束度函數更新個體，當個體的違反約束度在容忍度以內時，通過原目標函數更新個體，在每次迭代中保留一部分性能較優的不可行個體，擴大了個體的搜索范圍，增強了算法尋優效果.

1 遷移初始化及基本差分進化算法的改進

1.1 遷移初始化

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

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

定義約束違反度函數

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

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

式中：α為常數，本文取α＝0.6；R為隨機選擇的種群P1中的個體；S為種群P2中的個體，用新產生的個體X替換個體S。按照式（4）將種群P2中每個個體進行替換，然后將種群P1和P2合并為一個種群，這樣就可以提高種群中個體的質量，根據需要可以連續進行L次以上的種群遷移操作，本文取L＝5，每進行一次種群遷移操作，違反約束容忍度變為原來的0.1倍.

1.2 基本差分進化算法的改進

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

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

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

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

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

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

對于vi和的競爭，種群最優個體xbest的進化，本文依據違反約束度函數和原目標函數進行選擇操作，當個體的違反約束度在容忍度以外時，通過違反約束度函數更新個體，當個體的違反約束度在容忍度以內時，通過原目標函數更新個體，具體操作見算法1.

2 求解約束優化問題的動態目標遷移差分進化算法

2.1 約束處理技術

本文采取動態目標的處理方法，它的主要思想是將約束違反度函數作為優化的第一個目標，將目標函數作為第二個目標進行優化.

因此求解約束優化問題（COPs）就可以轉化為無約束雙目標優化問題

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

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

2.2 違反簡單邊界約束的處理技術

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

2.3 改進差分進化算法（DOMDE）

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

步驟2 遷移初始化

1）按照式（3）隨機產生N個n維向量.

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

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

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

步驟5 根據算法1（見3.1）更新每個個體和全局最優個體.

步驟6 讓t＝t＋1，返回到步驟3，直到達到設定的最大迭代次數停止.

3 數值實驗及分析

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

表1 6個測試函數的主要性質

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

表2 測試函數運行結果的比較表

問題g03是極大化問題，利用－f（x）將其轉化為極小化問題.由表2可見，DOMDE算法對于大多數優化問題基本上都找到了最優解，并且標準差也比較小.問題g01有2個局部極小－13.000和－12.453 125，20次獨立實驗算法都跳出這兩個局部極小點.對于6個測試函數，DOMDE算法也基本上達到了較為滿意的結果，新算法（DOMDE）與HM結果的比較見表3.

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

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

4 結束語

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

［1］沈文勝，熊方方.混合型非線性規劃的 MATLAB實現方法［J］.武漢理工大學：交通科學與工程版，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.