1、n 當前文檔修改密碼：8362839用于約束多目標優化問題的雙群體差分進化算法孟紅云1 張小華2 劉三陽1(1.西安電子科技大學 應用數學系，西安，710071；2.西安電子科技大學 智能信息處理研究所，西安，710071)摘 要：首先給出一種改進的差分進化算法，然后提出一種基于雙群體搜索機制的求解約束多目標優化問題的差分進化算法該算法同時使用兩個群體，其中一個用于保存搜索過程中找到的可行解，另一個用于記錄在搜索過程中得到的部分具有某些優良特性的不可行解，避免了構造罰函數和直接刪除不可行解此外，將本文算法、NSGA-和SPEA的時間復雜度進行比較表明，NSGA-最優，本文算法與SPEA相當.對

2、經典測試函數的仿真結果表明，與NSGA-相比較，本文算法在均勻性及逼近性方面均具有一定的優勢.關鍵字： 差分進化算法；約束優化問題；多目標優化問題； 中圖分類號：TP181 引言達爾文的自然選擇機理和個體的學習能力推動進化算法的出現和發展，用進化算法求解優化問題已成為一個研究的熱點1-3但目前研究最多的卻是無約束優化問題然而，在科學研究和工程實踐中，許多實際問題最終都歸結為求解一個帶有約束條件的函數優化問題，因此研究基于進化算法求解約束優化問題是非常有必要的不失一般性，以最小化問題為例，約束優化問題（Constrained Optimization Problem，）可定義如下： （1）其中為

3、目標函數，稱為約束條件，稱為維決策向量將滿足所有約束條件的解空間稱為(1)的可行域特別的，當時，(1)為單目標優化問題；當時，（1）為多目標優化問題為第個不等式約束，是第個等式約束另一方面，對于等式約束可通過容許誤差（也稱容忍度）將它轉化為兩個不等式約束： （2）故在以后討論問題時，僅考慮帶不等式約束的優化問題進一步，如果使得不等式約束，則稱約束在處是積極的在搜索空間中，滿足約束條件的決策變量稱為可行解，否則稱為不可行解定義1（全局最優解）是的全局最優解，是指且不劣于可行域內任意解所對應的目標函數，表示為 對于單目標優化問題，等價為，而對于多目標優化問題是指不存在，使得Pareto優于 目前，

4、進化算法用于無約束優化問題的文獻居多，與之比較，對約束優化問題的研究相對較少4-6。文7對當前基于進化算法的各種約束處理方法進行了較為詳細的綜述.對于約束優化問題的約束處理方法基本上分為兩類：基于罰函數的約束處理技術和基于多目標優化技術的約束處理技術由于罰函數法在使用中不需要約束函數和目標函數的解析性質，因此經常被應用于約束優化問題，但該類方法對罰因子有很強的依賴性，需要根據具體問題平衡罰函數與目標函數為了避免復雜罰函數的構造，Verdegay等8將進化算法中的競爭選擇用于約束處理，并在比較兩個解的性能時提出了三個準則,但他的第三個準則可行解優于不可行解這一準則合理性不強 .然而該文的這一準則

5、卻為進化算法求解約束優化問題提供了新思路，獲得了良好效果.因為在現實中存在一大類約束優化問題，其最優解位于約束邊界上或附近，對于這類問題，在最優解附近的不可行解的適應值很可能優于位于可行域內部的大部分可行解的適應值，因此無論從適應值本身還是從最優解的相對位置考慮，這樣的不可行解對找到最優解都是很有幫助的，故如何有效利用搜索過程中的部分具有較好性質的不可行解是解決此類問題的難點之一基于以上考慮，本文擬給出一種求解約束多目標優化問題的基于雙群體機制的差分進化算法，并對文中算法的時間復雜度與NSGA-9和SPEA10進行比較，最后用實驗仿真說明文中算法的可行性及有效性2 用于約束優化的雙群體差分進化

6、算法2.1 差分進化算法差分進化算法是一類簡單而有效的進化算法，已被成功應用于求解無約束單目標和多目標優化問題 11-14該算法在整個運行過程中保持群體的規模不變，它也有類似于遺傳算法的變異、交叉和選擇等操作，其中變異操作定義如下： (3)其中,為從進化群體中隨機選取的互不相同的三個個體，為位于區間中的參數(3)式表示從種群中隨機取出的兩個個體的差，經參數放大或縮小后被加到第三個個體上，以構成新的個體為了增加群體的多樣性，交叉操作被引入差分進化算法，具體操作如下：針對父代個體的每一分量，產生位于區間中的隨機數，根據與參數的大小關系確定是否用替換，以得到新的個體，其中如果新個體優于父代個體，則用

7、來替換，否則保持不變在差分進化算法中，選擇操作采取的是貪婪策略，即只有當產生的子代個體優于父代個體時才被保留，否則，父代個體被保留至下一代 大量研究與實驗發現差分進化算法在維護群體的多樣性及搜索能力方面功能較強，但收斂速度相對較慢，因此本文擬給出一種改進的差分進化算法用于多目標優化問題，仿真實驗表明，改進的差分進化算法在不破壞原有算法維護群體多樣性的前提下，可改善差分進化算法的收斂速度2.2 基于雙群體的差分進化算法2.2.1 基本概念以下僅討論帶不等式約束的多目標優化問題 （4）定義2.1 稱為（4）的不可行解，是指至少存在一個，滿足定義2.2 違反約束的強度，即約束違反度函數定義為，本文取

8、定義2.3 違反約束的數目，其中定義2.4 不可行解優于不可行解，是指的約束向量Pareto優于的約束向量2.2.2 基本思想由上一節分析可知，在搜索過程中遇到的不可行解不能簡單丟掉因此，在設計算法時不但要考慮算法的收斂速度，而且還必須保證群體中可行解的優勢地位；另一方面，對于多目標優化問題，維持搜索群體的多樣性與考慮群體的收斂速度是同等重要的基于此考慮，本節采用基于雙群體的差分進化算法求解約束多目標優化問題，其中群體用來保存搜索過程中遇到的可行解，用來保存搜索過程中遇到的占優不可行解，同時具有較強的記憶功能，可記憶中每一個體搜索到的最優可行解和整個群體到目前為止搜索到的最優可行解，分別記為和

9、，其中表示個體對自身的思考和認知，表示個體間的信息交流，這一點和PSO算法類似與此同時，我們還通過一種改進的差分進化算法產生新的群體，在產生新群體的過程中，群體中的部分個體參與了個體再生，并通過新生成的個體更新、和為了避免性能較優的不可行解被刪除，本文擬采用雙群體搜索機制，其中群體用于記錄可行解，群體 記錄不可行解，分別為群體與的規模，滿足，和分別為群體中每一個個體搜索到最優可行解和群體迄今為止搜索到最優可行解2.2.3 改進的差分進化算法為了維護群體的多樣性和收斂性，同時有效的利用已搜索到的不可行解的某些優良特性，下面給出一種改進的差分進化算法，并通過以下兩種方式產生新的個體方法1： 其中，

10、方法2：其中，方法1的目的在于通過向最優個體學習，改善算法的收斂速度方法2的主要目的在于和不可行個體進行信息交流，共享不可行解的一些優良特性，增加群體的多樣性在具體操作過程中，首先用改進的差分進化算法產生新的個體，然后針對父代個體的每一個分量，產生位于區間中的隨機數，根據與參數的大小關系確定是否用來替換，得到新的個體如果是可行解，而且的規模小于給定規模，則可直接將插入；如果插入后的群體的規模大于給定規模，首先兩兩比較中的個體，如果存在兩個個體，滿足Pareto優于，則將個體刪除，如果不存在，也就是說集合中任意兩個個體所對應的目標向量都不可比較，則計算中任意兩個個體間的距離，隨機刪除距離最小的兩

11、個個體中的一個如果是不可行解，而且的規模小于給定規模，則可直接將插入群體中；如果等于給定規模閾值，計算插入后的群體中任意兩個個體的約束向量，如果存在兩個個體，滿足約束向量Pareto優于約束向量，則刪除；如果不存在，則刪除滿足的個體經過以上操作，群體和的規模不會大于給定規模閾值最后利用新生成的群體更新最優個體集合和，群體的更新方法和SPEA算法中外部群體的更新方法相同，而的更新方法如下：如果新生成的可行解Pareto優于對應的局部最優解，則用替換，否則不予替換2.3算法的基本流程綜上所述，基于雙群體的差分進化算法的約束處理技術的流程可表示如下：step1. 隨機生成個個體，判斷每一個體的可行性

12、，然后根據個體可行性將其插入到對應的群體或中；并初始化和及參數和step2. 判斷搜索是否結束，如果結束，轉向step5，否則轉向step3.step3. 生成隨機數，如果，根據方法1，生成新的個體；否則，根據方法2生成新的個體，如果是可行解，將插入到中；否則插入到中，反復執行直到生成個可行解step4. 根據新生成的群體更新最優個體集和，轉向step2step5. 輸出最優解集3 算法分析3.1 算法的性能衡量約束優化問題的算法性能的衡量可分為兩部分，一部分為最終獲得的最優解的性能的衡量，如通過GD15來度量最優群體的逼近性，SP16來衡量最優解的分布均勻性，或通過計算目標函數的次數衡量算法

13、的復雜度和算法的收斂速度另一部分是針對約束優化問題來衡量群體的多樣性，Koziel & Michalewicz17給出一種多樣性度量準則，其定義如下： （5） 其中表示每一次搜索過程中生成的可行解的數目，為所生成的所有個體的數目相應地，為了衡量群體中的不可行解違反約束的強度，可采用約束違反度函數的均值來度量： （6）其中表示集合所包含元素的數目然而在實際問題中，決策者往往只對某一范圍的最優解感興趣，故下邊只評價本文算法對標準測試函數最終獲得的最優解集的逼近性與均勻性，并與NSGA-進行比較3.2 算法的時間復雜性分析我們僅考慮種群規模對算法時間復雜度的影響，設可行群體的規模為，不可行群

14、體的規模為，群體的規模為，群體的最大規模為，則文中算法迭代一次的時間復雜度可計算如下：算法中重組和變異操作的時間復雜度為；判斷進化群體中個體可行性所需時間復雜度為；更新群體、和的時間復雜度分別為、和；計算群體和的適應度所需時間復雜度為；用于更新最優群體的時間復雜度最差為；保持最優群體和進化群體多樣性的時間復雜度最差為； 則算法迭代一次所需的時間復雜度最差為+ （7）上述復雜度可簡化為 （8）設為所有種群的規模，令，則本文算法的時間復雜度< （9）NSGA- 9和SPEA 10是多目標進化算中兩個最具有代表性的優秀算法，這兩個算法的時間復雜度最差分別為和，其中分別為進化種群規模和外部種群集

15、的規模因而，SPEA和本文算法的時間復雜度最差為，這比NSGA-的時間復雜度稍高一些，但接下來的實驗結果告訴我們，本文算法的均勻性及逼近性卻明顯優于NSGA-事實上，SPEA和本文算法的時間復雜度主要用于環境選擇（Environmental selection）上，如果文中對采取NSGA-中的多樣性保持策略，則本文算法的復雜度將降至4 實驗結果與分析（1） 測試函數與參數設置為了驗證本文給出算法的可行性，我們采用Deb18建議的用來測試約束多目標優化算法性能的四個常見的測試函數來檢驗本文算法的性能可行解集合的規模，不可行解集合的規模初始化時，隨機生成個體的數目，參數，為位于區間中的一致隨機數D

16、eb給出的測試函數可用統一的解析表示，即其中， 測試函數選取不同的參數時，所構造的測試函數性質不同，可行解和不可行解的分布也不同，最終導致全局Pareto最優解集的不同其中通過控制參數的大小，可以控制Pareto前端不連續的段數，越大段數越多；而較小參數可以使得每一不連續Pareto前端僅包含一個Pareto點；參數調節連續可行域到Pareto前端的點的距離，越大距離越遠，其作用在于調節問題求解的難度；參數的作用在于改變分段Pareto前端之間的分布特性，當=1時，Pareto前端為均勻分布；當時， Pareto前端向較大的方向移動；當時，則Pareto前端向較大的方向移動基于以上分析我們選取

17、不同的參數構造4個常用的測試函數檢驗本節算法的性能，這些測試函數的參數取值具體如下圖4.1測試函數 CTP1在目標空間示意圖 圖4.2測試函數CTP2在目標空間示意圖圖4.3測試函數 CTP3在目標空間示意圖 圖4.4測試函數CTP4在目標空間示意圖測試函數CTP1：，可行解、不可行解、全局Pareto前端分布如圖4.1所示測試函數CTP2： ，可行解、不可行解、全局Pareto前端分布如圖4.2所示測試函數CTP3：，可行解、不可行解、全局Pareto前端分布如圖4.3所示測試函數CTP4：，可行解、不可行解、全局Pareto前端分布如圖4.4所示（2）實驗結果與分析在相同的測試函數和目標函

18、數計算次數下，將本文算法和經典的NSGA-II算法進行比較，并將各自算法獨立運行30次，然后統計兩種算法所得Pareto最優解集的均勻性（Spacing，SP）與逼近性（Generational distance, GD）的最好、最差、均值、方差和中間值，以此作為衡量算法性能的標準由于真實Pareto最優集是未知的，故我們將兩種算法所得的60個近似Pareto最優解集之并集的Pareto濾集作為真實Pareto最優解集的逼近，其中測試函數CTP1，CTP2，CTP3的函數值計算次數為10200，而CTP4的函數值計算次數為610014這里，集合的Pareto濾集定義為. 圖4.5、4.6、4.

19、7、4.8為從30次運行中隨機選擇的一次運行結果，從實驗曲線可以看到本文算法求出的Pareto Front在逼近性方面要優于NSGA-II圖4.5測試函數CTP1的Pareto Front 圖 4.6 測試函數CTP2的Pareto Front 圖4.7測試函數CTP3的Pareto Front 圖4.8測試函數CTP4的Pareto Front為了進一步定量的評價兩種算法的逼近性與均勻性，表4.1，4.2，4.3，4.4給出了兩種算法對上述四個測試函數的SP，GD的統計結果，從表中數據容易看出，在解集的逼近性和均勻性方面本文算法對四個測試函數的標準方差都明顯小于經典的NSGA-II算法，這說

20、表4.1 測試函數CTP1評價準則的統計結果bestworstavgmedianStd.Dev.SPNSGA-II0.42850.71790. 57490.56940.1842Proposed0.51870.61380. 57050.56840.1043GDNSGA-II0.00050.00210. 00170.00150.0013Proposed9.821e-055.367e-042.0625e-0042.636e-040.0003表4.2 測試函數CTP2評價準則的統計結果bestworstavgmedianStd.Dev.SPNSGA-II0.32750.41210. 39240.373

21、20.2157Proposed0.26890.33510.29650.29740.0813GDNSGA-II0.00080.00170.0010.00130.0011Proposed1.547e-051.784e-042.306e-78.033e-050.0001表4.3 測試函數CTP3評價準則的統計結果bestworstavgmedianStd.Dev.SPNSGA-II0.52190.74510.36990.37910.2312Proposed0.51870.61380.29650.28340.1813GDNSGA-II0.00050.00210.00120.00130.0013Prop

22、osed9.821e-055.367e-048.0325e-0052.636e-040.0002表4.4 測試函數CTP4評價準則的統計結果bestworstavgmedianStd.Dev.SPNSGA-II0.27530.56340.34900.35760.1278Proposed0.22450.52860.34260.33810.1138GDNSGA-II0.00110.00360.00230.00230.0030Proposed1.3232e-83.371e-74.6452e-85.173e-80.0001明本文的算法性能更穩定另一方面，上述定量的度量結果也表明在搜索過程中適當的運用性

23、能較優的不可行解的信息不僅有助于保持群體的多樣性，而且增強了算法的搜索功能，并在一定程度上起到了維持解集的均勻性的作用5 結論本文借助粒子群算法的基本思想給出了一種改進的差分進化算法，在適當的利用部分優良不可行個體的基礎上，提出了用于約束多目標優化問題的雙群體差分進化算法該算法中的兩個群體分別用于記錄進化過程中的可行解及部分性能較優的不可行解，其優點在于可以充分利用每次迭代產生的子代個體的信息此外，還對文中算法的時間復雜度與NSGA-和SPEA進行比較.經典測試函數的數值仿真結果表明，本文算法無論在解集的逼近性及均勻性方面都優于NSGA-II算法，這表明文中提出的基于雙群體的差分進化算法可用于

24、求解帶約束的多目標優化問題方面有一定的優勢正如“沒有免費的午餐定理”19所指出的，任何一種算法不可能在所有的性能方面占盡優勢，雖然本文算法在求解約束多目標優化問題方面具有一定的優勢，但計算量要稍高于NSGA-II。接下來我們的研究將致力于如何降低算法的時間復雜度及本文算法的實際應用。參考文獻1. Mitsuo Gen and Runwei Cheng, Genetic algorithms & Engineering Design. John Wiley & Sons, Inc, New York,1997.2. Fred Glover, Heuristics for Inte

25、ger programming using surrogate constraints. Decision Sciences,1977，8(1):156-166;3. David E.Goldberg, Genetic in search, optimization and machine learning. Addison-Wesley Publishing Co.,Reading,Massachusetts,1989.4. Wang Yuexuan, Liu Lianchen, etc,. Constrained Multiobjective Optimization Evolutiona

26、ry Algorithm. Journal of Tsinghua Univ(Sci & Tech),2005,45(1),103-106.(王躍宣，劉連臣等. 處理帶約束的多目標優化進化算法. 清華大學學報（自然科學版），2005，45（1），103-106) .5. Zhang Yongde, Huang Shabai. On Ant Colony Algorithm for Solving Multiobjective Optimization Problems. Control and Decision. 2004,20(2),170-174. （張勇德，黃莎白. 多目標優化問

27、題的蟻群算法研究. 控制與決策，2005，20（2），170-174.）6. Gao Yugen, Cheng Feng,etc,. A New Improved Genetic Algorithms Based on Converting Infeasible Individuals into Feasible Ones and Its Property Analysis. Acta Electronica Sinica，2006，34（4），638-641. (高玉根，程峰，王燦，王國彪. 基于違約解轉化法的遺傳算法及其性能分析. 電子學報，2006，34（4），638-641).7. C

28、arlos A. Coello Coello. Theoretical and Numerical Constraint-Handling Techniques used with Evolutionary Algorithms: A Survey of the State of the Art, Computer Methods in Applied Mechanics and Engineering, Vol. 191, No. 11-12, pp. 1245-1287, January 2002.8. Fernando Jiménez and José L. Verd

29、egay. Evolutionary techniques for constrained optimization problems. In Hans-Jürgen Zimmermann, editor, 7th European Congress on Intelligent Techniques and Soft Computing (EUFIT'99), Aachen, Germany, 1999. Verlag Mainz. ISBN 3-89653-808-X.9. Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and

30、T. Meyarivan. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 2002, 6(2), 182-197.10. Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Trans. On Evolu

31、tionary Computation,1999,3(4),257-271.11. Storn，R. and K. Price(1995). Differential evolution: a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical Report TR-95-012, International Computer Science Institute, Berkeley.12. Yung-Chien Lin, Kao-Shing Hwang, an

32、d Feng-Sheng Wang. Hybrid Differential Evolution with Multiplier Updating Method for Nonlinear Constrained Optimization Problems. CEC'2002, volume 1, pages 872-877, Piscataway, New Jersey, May 2002.13. Abbass, H., Sarker, R. and Newton, C. PDE: A Pareto-frontier Differential Evolution Appro

33、ach for Multi-objective Optimization Problems. Proceedings of the Congress on EC 2001(CEC2001),vol.2, IEEE Service Center, Piscataway, New Jersey,971-978.14. Li Bing-yu, Xiao Yun-shi, Wu Qi-di. Hybrid algorithm based on particle swarm optimization for solving constrained optimization problems. Contr

34、ol and Decision, 2004, 19(7), 804-807.(李炳宇，蕭蘊詩，吳啟迪一種基于粒子群算法求解約束優化問題的混合算法，控制與決策，2004,19(7), 804-807) .15. D.A.Van Veldhuizen and G.B. lamont. Multiobjective Evolutionary Algorithm Research : A history and analysis. Dept. Elec.Comput.Eng.,Graduate School of Eng., Air Force Inst.Technol.,Wright-Patters

35、on AFB, OH.Tech.Rep.TR-98-03,1998.16. J. Schott. Fault tolerant design using single and multicriteria genetic algorithm optimization. Masters thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology,1995.17. S.Koziel and Michalewicz. Evolutionary algorithms, homomorp

36、hous Mapping, and constrained parameter optimization. Evolutionary Computation, 1996,7(1):19-44. 18. Kalyanmoy Deb, Amrit Pratap, and T. Meyarivan. Constrained Test Problems for Multi-objective Evolutionary Optimization. In: Proceedings of the 1st International Conference on Evolutionary Multi-Crite

37、rion Optimization, Zurich, Switzerland, 2001, Springer-Verlag, 284-29819. Wolpert D.H., Macready W.G. No free lunch theorems for search. Santa Fe,NM: Santa Fe Institute. Technical Report: SFI-TR-05-010, 1995. A Differential Evolution Based on double Populations for Constrained Multi-objective Optimi

38、zation ProblemMENG Hong-yun1, ZHANG Xiao-hua 2, LIU San-yang1(1. Dept. of Applied Math., Xidian University, Xian 710071, China；2. Institute of Intelligent Information Processing, Xidian University, Xian, 710071)Abstract: An improved differential evolution approach is given first, and a new algorithm

39、 based on double Populations for Constrained Multi-objective Optimization Problem (CMOP) is presented. In the proposed algorithm, two populations are adopted, one is for the feasible solutions found during the evolution, and the other is for infeasible solutions with better performance which are all

40、owed to participate in the evolution with the advantage of avoiding difficulties such as constructing penalty function and deleting infeasible solutions directly. In addition, the time complexity of the proposed algorithm, NSGA-and SPEA are compared, which show the best is NSGA-, followed by SPEA an

41、d our algorithm simultaneously. The experiments on benchmarks indicate that our algorithm is superior to NSGA-in the measure of GD and SP. Keywords: Differential Evolution; Constrained Optimization Problem; multi-objective optimization problem;BackgroundConstrained optimization, both for nonlinear p

42、rogramming and multi-objective optimization, is a very important problem and has a variety of applications in engineering, management, mathematics and other fields. A common way to constrained optimization problem is to deal with constraints by penalty function, with the disadvantage and difficulty in choosing the penalty factors. In this paper, the authors propose a differentia