處理帶約束的多目標優(yōu)化進化算法1

1、處理帶約束的多目標優(yōu)化進化算法王躍宣'，劉連臣'，牟盛靜2，吳澄'(1.涓華大學自動化系，國家CIMS匸程技術研究中心.北京100084:2.高性能計算研究所,新加坡117528)#摘婆：紆對當前對求解多0標優(yōu)化的遺傳算法中主 要考慮如何處理相5沖突的多個目標間的優(yōu)化,而 很少考慮對約束條件的處理的問題,提出一種求解 帶約束的多目標優(yōu)化遺傳算法,利用鄰域比較與存 檔操作遺傳算法處理多個相圮沖突的II標Z間的優(yōu) 化、利用不可疔度選擇操作處理約束條件和選用約 束匸導廉理指導進化過程選擇操作；面向多目標約 柬優(yōu)化算法的兩類難點問題,列舉了 2個典型何題 進行仿貞計畀研究，仿頁

2、結果表明該克法能較大概 率的獲得炙I I標約束優(yōu)化間懸的町仃Bareto垠優(yōu)解。 關鍵字：務H標優(yōu)化：約束：Pareto 優(yōu)解：鄰域比 較與存檔操作:不可行度選擇;約束主導康* 中圖分類號：TP313. 13Constrained multi-objectiveoptimization evolutionary algorithmWANG Yuexuan1, LIU Lianchen1. MUShengjing2. WU Cheng1(1. National CIMS Engineering Research Center,Department of Automation, Tsinghua

3、Uni versit y,Beijing 100084. China;2. Institute of High Performance Computing,Singapore 117528)Abstract:Genetic algorithms for constraintnuilti-ohjective optimization prohlems mainly fociK on optimizing the conflicting multiple objectives but constraint conditions have been seldom considered so far.

4、 In this paper, a new genetic algorithm is proposed, in which neighbortiood comparing and archiving are utilized to the genetic algorithm to smooth the conflicting objectives. Infeasibility degree selection is used to handle constraints Constraint domain principle is also applied to guide the evolut

5、ionary process For the two kinds of difficult problems in constrained multi-objective optimization, two classical problems are computed by the algorithm. Simulation results show that the proposal can find feasible Pareto solutions in a big probability.Key Words: Multi-objective optimization, constni

6、ined, evolutionar)r algorithm Pareto optimal solution, neighborhood and archive operation. Infeasibility degree selection, constrained dominated principle近年來，人吊:基j:遺傳算法的多目標優(yōu) 化方法被逐步引起重視卩®。但目前求解多口 標優(yōu)化的遺傳算法主耍考慮相互沖突的多目 標間的優(yōu)化而很少考慮約束條件5 0而約束 處理是匸程優(yōu)化問題中一個關鍵部分，因此 燈必婆建立一個仃效的方法求解-般的約束 多目標優(yōu)化問題。Michalewicz

7、181對當前基T* 進化算法的各種處理約束方法做了一個全而 綜述。其中罰丙數(shù)方法在實際問題中得到了 垠廣泛的應用。但一般罰隨數(shù)方法處理約束 條件的性能很人程度上依賴罰系數(shù)的設置。 為解決這個問題，很多研究者捉出新的改進 方法修叫其中Mu等提出一個在一定程度 上類似于模擬退火技術的遺傳口決求解約束 優(yōu)化問題，算法通過不可行度 infeasibility degree, IFD)選擇操作將不可行解分為對接 受的和不可接受的解。隨著進化過程，町接 受的不對行解逐步接近可行域。這里，將種 群屮的不町行解進行分類的觀點可肖接用在 同時處理可能的Pareto垠優(yōu)解集。本文在Mu等提出的基丁鄰域和存檔 操作

8、進化算法(neighborhood and archive genetic algorithm. NAGA)處理無約束的多目 標優(yōu)化問題的基礎上，進一步做了改進并提 出能處理各類約束條件的多口標優(yōu)化算法 (infeasibility degree based neighborhood and archive genetic algorithm. IFDNAGA)» 多 H 標優(yōu)化部分沿用NAGA方法，采用IFD方法 處理各類約束條件，并引入約束主導原理指 導進化選擇過程。故后用2個典型的數(shù)值例 子對IFDNAGA算法的性能進行仿真測試， 結果表明該算法能獲得可行的Pareto授優(yōu) 收

9、稿日期：2004-014)2 資助項目：國家“九七三”項目(2OO2CB312202) 作者簡介：王躍宣(1975)，女(漢，浙江，博 士后通訊聯(lián)系人：昊澄，院七，E-mail： wuc解。1鄰域和存檔操作遺傳算法1.1 處理約束的不町行度選擇為了在多冃標優(yōu)化問題中區(qū)分不町行解 與町行解，Deb等人在非被主導排序算法 （NSGA-II）屮定義了一個約束主導原理Pi： 一個解?？煞Q為約束主導另一個解當且 僅當下列條件滿足，1）解兀是町行解而解形不是可行解；2）解兀與廠都不是町行解，但解X,的總體 約束沖突值小于解廠；3）解兀與心都是町行解且兀主導®。Deb等何山采用這個原理來處理基丁遺

10、 傳算法的多冃標優(yōu)化問題屮的約束條件，并 由實例證明該原理在指導群體進化并收斂到 可行的Pareto最優(yōu)解前沿中的有效性。為了定帚的得到問題屮每個解的約朿沖 突程度，或者不町行程度，定義一個解兀的 不可ff度（IFD）為該解的所有沖突的約束值 的平方和：0（x,） = 2JminO.g（£）F + £|心（兀），（1）坯中：g/（兀）、九（兀）分別是優(yōu)化問題的不等 式約束（人于或等于）和等式約束，丿和”分 別是不等式約束式的個數(shù)和總約束式的個 數(shù)。這里不町行度可認為是解兀到町行域的 距離，兀離町行域越遠，不町行度越人，反 Z越?。寒斬榭尚薪鈺r，不可行度為零。為了逐步增大滿

11、足約束要求的壓力，使 進化搜索由整個解空間逐步向著町行域中的 Pareto Iti優(yōu)解靠近。酋先定義不町行度閥值: （S0川=7* £旅兀）"財1 I冋丿其中："為退火因子,隨著迭代進行,T由 匚變化到7；#。S葉為種群規(guī)模不可行度 閥值是一個逐步減小的退火因子與當前種群 的平均不可行度值的乘積。在每步進化中, 根據每一個候選解的不町行度與閥值的比較 來決定這個解是被接受還是被拒絕。當一個不町行解的不町行度大丁 不可行 發(fā)閥值，該解被拒絕，沓則該不町行解被接 受并進入卜一代遺傳算法操作。為保證種群 規(guī)模不變,被拒絕的解由當前代中可行度最 小的解等量取代。1.2 鄰

12、域和存檔操作的藝日標優(yōu)化方法甚于進化算法的多冃標約束優(yōu)化方法的 主要仃:務包括：在種群中識別可行的Pareto Id優(yōu)解，保證算法收斂到町彳亍的Pareto厳優(yōu) 前沿，以及將獲得的Pareto最優(yōu)解均勻分布 在 Pareto 前沿上根據Pareto ii優(yōu)解的定義，Mu等“麻丁 鄰域比較法建立了從群體中識別Pareto最優(yōu) 解的坷級識別法。肖先是識別局部Pareto 優(yōu)解步驟，通過比較候選解所有目標值在其 鄰域內的單調性，得到判別Pares最優(yōu)解的 必要條件。如果一個候選解的所有冃標值在 其鄰域內變化時是單調增加或者是單調減 小，則該候選解可認為是一個IK Pareto解并 被舍棄。否則，如果

13、在具鄰域內，候選解的 部分II標值單調增加而另有部分II標值單調 減小，則該候選解作為局部卄被主導解保附。 第步識別步驟是針對第一步講別得到的対 部非被主導解進行的。通過対每個局部罪被 主導解的所有目標值與存檔中的所冇Pareto 最優(yōu)解的所有冃標值進行比較。判斷局部非 被主導解是否在整個搜索解空間屮都是罪被 主導的，也就是Pareto最優(yōu)解的過程。在多冃標優(yōu)化問題中，維持Pareto最優(yōu) 解在Pareto前沿的均勻分布是另-個關鍵的 步驟.Mu割I提出了一個簡單而有效的維持 Pareto最優(yōu)解均勻分布的方法；鄰域排擠法, 并采川了存檔操作來心儲宙鄰域識別法獲得 的Pareto最優(yōu)解。排擠法是

14、通過比較由鄰域 識別法得到的新的Pareto最優(yōu)解與存檔中的 Pareto最優(yōu)解，舍棄與存檔屮的解的距離過 小的候選解。每個存檔屮的Pareto E優(yōu)解都 由一個小的區(qū)間_£.卄&表示，這兩個邊界 值被認為是該解的鄰域。適應值分配過程是通過對新的Pareto最 優(yōu)解賦以人的數(shù)值而対其他被舍棄的解賦以 小的數(shù)值來實現(xiàn)的。在適應值分配步驟中引 入了正則化Euclidean距離。1.3 IFDNAGA 算法IFDNAGA算法的其他部分采用改進的 精英遺傳算法（elitist GA）,算法流程如F：1）初始化。初始化進化群體，設置垠人迭 代次數(shù)K max和其他通用遺傳算法參 數(shù)：群體

15、規(guī)模、交叉概率、變異概率。 設置存檔人小以和鄰域人小d，平均不 可行度（閥值）系數(shù)匚沏和Gd；2）計算當前種群所有個體的不可行度IFD 和群體的不町行度閥值，完成不町行度 選擇操作；3）應用鄰域識別法從完成不可行度選擇操 作的群體中計算并比較個體解和直鄰域 解的所們4標函數(shù)，從屮獲得 固eto報 優(yōu)解：4）執(zhí)行鄰域排擠法，根據所得解Z間的差 距排擠晅舍的內reto最優(yōu)解，繪后將新 feretofi優(yōu)解存檔；5）根據約朿主導原理對處理后的群體進行 適應度賦值；6）如果迭代次數(shù)人最人次數(shù)K max或者 存檔中的F&reto最優(yōu)解個數(shù)人丁或等 于以，則停止；7）執(zhí)行選擇、交叉和變異操作以產生

16、卜 - 代種群。同時保留父代中最好的個體。8）計算新的群體中所有個體的不町行度 IFD和種群的不可行度閥值,執(zhí)行不可 行度選擇操作，產生新的群體：9）向用鄰域識別法從新種群中獲得Ffereto 瑕優(yōu)解：10）將新識別的 內reto最優(yōu)解與存檔中的 fereto最優(yōu)解Z間執(zhí)行鄰域排擠操作， 赧后將未被排擠的內reto址優(yōu)解“檔;11）根擁約束丄導原理刈處理后的卅體進行 適應度賦值。12）返回步驟6） °遺傳算法采用實數(shù)編碼法，苴他通用操 作算子：選擇算子，交叉算子和變異算子分 別釆用輪盤賭法、算術交義法和鄰域變異法 91O2數(shù)值測試例子采用IFDNAGA對2個不同復雜程度的 女目標約束

17、優(yōu)化問題進行數(shù)值求解。測試例 了的選擇是根據多口標約束優(yōu)化算法的兩類 難點問題而設計的山）：1）算法在接近Parelo址優(yōu)前沿處的搜索性 能：2）算法在胳個搜索空間的收斂性。所選例子使用IFDNAGA時釆用的算法 參數(shù)為：群體規(guī)模為100,交叉概率為0.9, 變異概率為0.1,變異幅度為Upp=13問, 最人進化次數(shù)為500,存檔體枳以為500, 鄰域范曲d為O.OOOl1群體的平均不可行 度1FD （閥值）系數(shù)幾如和匚加分別是0.8 和3。例1Minimize fl（x）= x2, Minimize /,（x）= u-2）2» Subject to x2-2.5.v+1.5>

18、0 ,-io<x< io.（3）例1的無約束情況已由很多研究者進行 了求解釗。這里增加了約束條件用以測試算 法在整個解空間中搜索可行區(qū)域的性能圖 1和圖2分別給出了兩個日標函數(shù)対決策變 量和兩個目標函數(shù)之間的Pareto最優(yōu)解和 Pareto前沿。計算結果說明町行的Pareto最 優(yōu)解處在范陽0 < X < 1 和 1.5<x<2, ifljXjh'Z 的垠優(yōu)口標函數(shù)值范也是0 </,< 1和 I < /; < 4 ,以及 2.25 S £ S 4 和 0 S 厶 S 0.25。 所得到的町行Pareto最優(yōu)解在Pa

19、reto詢沿形 成均勻分布。圖1例1的可行Pareto最優(yōu)解分布圖2例1的可行最優(yōu)目標函數(shù)例 2 15,11,1Minimize y;(x)=比，Minimize f2(x)x2,Subject to xf +- 1 - 0.1cos(16arctan0 x2(召-05卩+(勺-0.5)2 S05 ；0<Xj< OS 七 S;r (4)tia4圖3例2的可行最優(yōu)目標函數(shù)圖3給出了例2的町行Pares前沿以及 Pareto最優(yōu)解在前沿的分布?？尚蠵areto前 沿包括3個不連接的部分，IFDNAGA成功 搜索到這3個町行Pareto址優(yōu)解區(qū)域。3結論本文捉出了一個處理帯約束的多目標優(yōu)

20、 化的冇效算法IFDNAGA,利用遺傳算法的 群體并行搜索性能，采用不町行度選杼操作 來處理約束條件，將不町行解分為町接受的 和不町接受的兩類，并將町接受的不町行解 和町行解進行鄰域和存檔操作以獲取K+的 Pareto最優(yōu)解。通過2個典型的帯約束 標優(yōu)化問題的成功求解，證明IFDNAGA能 很好地求得所有町行Pareto M優(yōu)解，并使得 其在町彳亍Pareto前沿形成均勻分布。這個新 方法將在實際工程優(yōu)化問題應用屮被逐步得 到重視。參考文獻(References)1 MU Shengjing* SU Hongyc. WANG Yuexuan. et al. An efficient evolu

21、tionary multi-objective optimization algorithmA. Proceedings of the IEEE Congress on Evolulionary Computation (CEC2OO3) C. Canberra: IEEE Prcss. 2003. 914-920.|2 Schaffer J D. Multiple objective optimization with vector evaluated genetic algorithms A. Proceedings of the First International Conferenc

22、e on Genetic AlgorithmsC. Lawrence Erlbaunr IEEEPress. 1985.93-1003 Fonseca C M, Fleming P J. An overview of evolutionary algorithms in multiobjective optiniizationR|. Sheffield: Department of Automatic Control and Systems Engineering, University of Sheffield. 1994.4 Srinivas N , Deb K. Multiobjecti

23、ve optimizationusing nondominated sorting in genetic algorithms |J. Evolulionary Computation 1994. 2(3):221-248.|5 Veldhuizen DAV. Multiobjective evolutionary algorithms: classificatio n. analyses and new innovations |D. Air Force Institute of Technology Air University. 1999.|6 Zitzler E. Deb K. Tluele L Comparison of Multiobjcctive Evolutionary Algorithms: Empirical ResultsJ|. Evolutionary* Computation. 2000. 8(2): 173-195.7J Deb K. Pratap A. Meyarivan T. Constrained test problems for multi-objective evolulionary optimizationR. KanGAL report ,20000