用于約束多目標優(yōu)化問題的雙群體差分進化算法

1、用于約束多目標優(yōu)化問題的雙群體差分進化算法孟紅云1 張小華2 劉三陽1(1.西安電子科技大學(xué) 應(yīng)用數(shù)學(xué)系，西安，710071；2.西安電電子科技技大學(xué) 智能信信息處理理研究所所，西安安，71100771)摘 要：首先給給出一種種改進的的差分進進化算法法，然后后提出一一種基于于雙群體體搜索機機制的求求解約束束多目標標優(yōu)化問問題的差分進進化算法法該算法同時時使用兩兩個群體體，其中中一個用用于保存存搜索過過程中找找到的可可行解，另另一個用用于記錄錄在搜索索過程中中得到的的部分具具有某些些優(yōu)良特特性的不不可行解解，避免免了構(gòu)造造罰函數(shù)數(shù)和直接接刪除不不可行解解此外，將將本文算算法、NSGGA-和SPP

2、EA的的時間復(fù)復(fù)雜度進進行比較較表明，NSGGA-最優(yōu)，本本文算法法與SPPEA相相當(dāng).對經(jīng)典典測試函函數(shù)的仿仿真結(jié)果果表明，與NSSGA-相比較較，本文文算法在在均勻性性及逼近近性方面面均具有一一定的優(yōu)優(yōu)勢.關(guān)鍵字： 差分進進化算法法；約束束優(yōu)化問問題；多多目標優(yōu)優(yōu)化問題題； 中圖分類號號：TPP181 引言達爾文的自自然選擇擇機理和和個體的的學(xué)習(xí)能能力推動動進化算算法的出出現(xiàn)和發(fā)發(fā)展，用用進化算算法求解解優(yōu)化問問題已成成為一個個研究的的熱點1-33但目目前研究究最多的的卻是無無約束優(yōu)優(yōu)化問題題然而而，在科科學(xué)研究究和工程程實踐中中，許多多實際問問題最終終都歸結(jié)結(jié)為求解解一個帶帶有約束束條件

3、的的函數(shù)優(yōu)優(yōu)化問題題，因此此研究基基于進化化算法求求解約束束優(yōu)化問問題是非非常有必必要的不失一一般性，以以最小化化問題為為例，約約束優(yōu)化化問題（Connstrrainned OOptiimizzatiion Proobleem，）可定義義如下： （1）其中為目標標函數(shù)，稱為約束條件，稱為維決策向量將滿足所有約束條件的解空間稱為(1)的可行域特別的，當(dāng)時，(1)為單目標優(yōu)化問題；當(dāng)時，（1）為多目標優(yōu)化問題為第個不等式約束，是第個等式約束另一方面，對于等式約束可通過容許誤差（也稱容忍度）將它轉(zhuǎn)化為兩個不等式約束： （2）故在以后討討論問題題時，僅僅考慮帶帶不等式式約束的的優(yōu)化問問題進進一步，如如

4、果使得得不等式式約束，則則稱約束束在處是積積極的在搜索索空間中中，滿足足約束條條件的決決策變量量稱為可可行解，否否則稱為為不可行行解定義1（全全局最優(yōu)優(yōu)解）是的全局局最優(yōu)解解，是指指且不劣于于可行域域內(nèi)任意意解所對對應(yīng)的目目標函數(shù)數(shù)，表示示為 對于單單目標優(yōu)優(yōu)化問題題，等價價為，而而對于多多目標優(yōu)優(yōu)化問題題是指不不存在，使使得Paaretto優(yōu)于于 目前，進化化算法用用于無約約束優(yōu)化化問題的的文獻居居多，與之比比較，對對約束優(yōu)優(yōu)化問題題的研究相相對較少少4-66。文7對當(dāng)前前基于進進化算法法的各種種約束處處理方法法進行了了較為詳詳細的綜綜述.對于約約束優(yōu)化化問題的的約束處處理方法法基本上上分為

5、兩兩類：基基于罰函函數(shù)的約約束處理理技術(shù)和和基于多多目標優(yōu)優(yōu)化技術(shù)術(shù)的約束束處理技技術(shù)由由于罰函函數(shù)法在在使用中中不需要要約束函函數(shù)和目目標函數(shù)數(shù)的解析析性質(zhì)，因因此經(jīng)常常被應(yīng)用用于約束束優(yōu)化問問題，但該類方法法對罰因因子有很很強的依依賴性，需需要根據(jù)據(jù)具體問問題平衡衡罰函數(shù)數(shù)與目標標函數(shù)為了避避免復(fù)雜雜罰函數(shù)數(shù)的構(gòu)造造，Veerdeegayy等8將進化化算法中中的競爭爭選擇用用于約束束處理，并在比較兩個解的性能時提出了三個準則,但他的第三個準則可行解優(yōu)于不可行解這一準則合理性不強 .然而該文的這一準則卻為進化算法求解約束優(yōu)化問題提供了新思路，獲得了良好效果.因為在現(xiàn)實實中存在在一大類類約束優(yōu)

6、優(yōu)化問題題，其最最優(yōu)解位位于約束束邊界上上或附近近，對于于這類問問題，在在最優(yōu)解解附近的的不可行行解的適適應(yīng)值很很可能優(yōu)優(yōu)于位于于可行域域內(nèi)部的的大部分分可行解解的適應(yīng)應(yīng)值，因因此無論論從適應(yīng)應(yīng)值本身身還是從從最優(yōu)解解的相對對位置考考慮，這這樣的不不可行解解對找到到最優(yōu)解解都是很很有幫助助的，故故如何有有效利用用搜索過過程中的的部分具具有較好好性質(zhì)的的不可行行解是解解決此類類問題的的難點之之一基基于以上上考慮，本本文擬給出一一種求解解約束多目目標優(yōu)化化問題的的基于雙雙群體機機制的差差分進化化算法，并并對文中中算法的的時間復(fù)復(fù)雜度與與NSGGA-9和SPPEA10進行比比較，最最后用實實驗仿真真

7、說明文文中算法法的可行行性及有有效性2 用于約約束優(yōu)化化的雙群群體差分分進化算算法2.1 差差分進化化算法差分進化算算法是一一類簡單單而有效效的進化化算法，已已被成功功應(yīng)用于于求解無約約束單目目標和多多目標優(yōu)優(yōu)化問題題 11-14該算算法在整整個運行行過程中中保持群群體的規(guī)規(guī)模不變變，它也也有類似似于遺傳傳算法的的變異、交交叉和選選擇等操操作，其其中變異異操作定定義如下下： (3)其中,為從從進化群群體中隨隨機選取取的互不不相同的的三個個個體，為為位于區(qū)區(qū)間中的的參數(shù)(3)式表表示從種種群中隨隨機取出出的兩個個個體的的差，經(jīng)經(jīng)參數(shù)放放大或縮縮小后被被加到第第三個個個體上，以以構(gòu)成新新的個體體為

8、了了增加群群體的多多樣性，交交叉操作作被引入入差分進進化算法法，具體體操作如如下：針對父代個個體的每每一分量量，產(chǎn)生生位于區(qū)區(qū)間中的的隨機數(shù)數(shù)，根據(jù)據(jù)與參數(shù)數(shù)的大小小關(guān)系確確定是否否用替換換，以得到新新的個體體，其中如果果新個體體優(yōu)于父代代個體，則則用來替替換，否否則保持持不變在差分分進化算算法中，選選擇操作作采取的的是貪婪婪策略，即即只有當(dāng)當(dāng)產(chǎn)生的的子代個個體優(yōu)于于父代個個體時才才被保留留，否則則，父代個個體被保保留至下下一代 大大量研究究與實驗驗發(fā)現(xiàn)差差分進化化算法在在維護群群體的多多樣性及及搜索能能力方面面功能較較強，但但收斂速速度相對對較慢，因因此本文文擬給出一一種改進進的差分分進化算

9、算法用于于多目標標優(yōu)化問問題，仿真實驗表明明，改進進的差分分進化算算法在不不破壞原有算算法維護護群體多多樣性的的前提下下，可改改善差分分進化算算法的收收斂速度度2.2 基基于雙群群體的差差分進化化算法2.2.11 基本概概念以下僅討論論帶不等等式約束束的多目目標優(yōu)化化問題 （44）定義2.11 稱為（44）的不不可行解解，是指指至少存存在一個個，滿足足定義2.22 違反約約束的強強度，即即約束違違反度函函數(shù)定義義為，本本文取定義2.33 違反約約束的數(shù)數(shù)目，其其中定義2.44 不可行行解優(yōu)于于不可行行解，是是指的約約束向量量Parretoo優(yōu)于的的約束向向量2.2.22 基本思思想由上一節(jié)分分

10、析可知知，在搜搜索過程程中遇到到的不可可行解不不能簡單單丟掉因此，在在設(shè)計算算法時不不但要考考慮算法法的收斂斂速度，而而且還必必須保證證群體中中可行解解的優(yōu)勢勢地位；另一方方面，對對于多目目標優(yōu)化化問題，維持搜索群體的多樣性與考慮群體的收斂速度是同等重要的基于此考慮，本節(jié)采用基于雙群體的差分進化算法求解約束多目標優(yōu)化問題，其中群體用來保存搜索過程中遇到的可行解，用來保存搜索過程中遇到的占優(yōu)不可行解，同時具有較強的記憶功能，可記憶中每一個體搜索到的最優(yōu)可行解和整個群體到目前為止搜索到的最優(yōu)可行解，分別記為和，其中表示個體對自身的思考和認知，表示個體間的信息交流，這一點和PSO算法類似與此同時，我

11、們還通過一種改進的差分進化算法產(chǎn)生新的群體，在產(chǎn)生新群體的過程中，群體中的部分個體參與了個體再生，并通過新生成的個體更新、和為了避免性性能較優(yōu)優(yōu)的不可可行解被被刪除，本本文擬采用雙群群體搜索索機制，其中群體用于記錄可行解，群體 記錄不可行解，分別為群體與的規(guī)模，滿足，和分別為群體中每一個個體搜索到最優(yōu)可行解和群體迄今為止搜索到最優(yōu)可行解2.2.33 改進的的差分進進化算法法為了維護群群體的多多樣性和和收斂性性，同時時有效的的利用已已搜索到到的不可可行解的的某些優(yōu)優(yōu)良特性性，下面面給出一一種改進進的差分分進化算算法，并并通過以以下兩種種方式產(chǎn)產(chǎn)生新的的個體方法1： 其中，方法2：其中，方法1的目

12、目的在于于通過向向最優(yōu)個個體學(xué)習(xí)習(xí)，改善善算法的的收斂速速度方方法2的的主要目目的在于于和不可可行個體體進行信信息交流流，共享享不可行行解的一一些優(yōu)良良特性，增加群體的多樣性在具體操作過程中，首先用改進的差分進化算法產(chǎn)生新的個體，然后針對父代個體的每一個分量，產(chǎn)生位于區(qū)間中的隨機數(shù)，根據(jù)與參數(shù)的大小關(guān)系確定是否用來替換，得到新的個體如果是可行行解，而而且的規(guī)規(guī)模小于于給定規(guī)規(guī)模，則則可直接接將插入入；如果果插入后后的群體體的規(guī)模模大于給給定規(guī)模模，首先先兩兩比比較中的的個體，如如果存在在兩個個個體，滿滿足Paaretto優(yōu)于于，則將將個體刪刪除，如如果不存存在，也也就是說說集合中中任意兩兩個個

13、體體所對應(yīng)應(yīng)的目標標向量都都不可比比較，則則計算中中任意兩兩個個體體間的距距離，隨隨機刪除除距離最最小的兩兩個個體體中的一一個如果是不可可行解，而而且的規(guī)規(guī)模小于于給定規(guī)規(guī)模，則則可直接接將插入入群體中中；如果果等于給給定規(guī)模模閾值，計計算插入入后的群群體中任任意兩個個個體的的約束向向量，如如果存在在兩個個個體，滿滿足約束束向量PPareeto優(yōu)優(yōu)于約束束向量，則則刪除；如果不不存在，則則刪除滿滿足的個個體經(jīng)過以上操操作，群群體和的規(guī)模模不會大大于給定定規(guī)模閾閾值最最后利用用新生成成的群體體更新最最優(yōu)個體體集合和和，群體體的更新新方法和和SPEEA算法法中外部部群體的的更新方方法相同同，而的的

14、更新方方法如下下：如果果新生成成的可行行解Paaretto優(yōu)于于對應(yīng)的的局部最最優(yōu)解，則則用替換換，否則則不予替替換2.3算法法的基本本流程綜上所述，基基于雙群群體的差差分進化化算法的的約束處處理技術(shù)術(shù)的流程程可表示示如下：隨機生成個個個體，判判斷每一一個體的的可行性性，然后后根據(jù)個個體可行行性將其插入入到對應(yīng)應(yīng)的群體體或中；并并初始化化和及參數(shù)數(shù)和判斷搜索是是否結(jié)束束，如果果結(jié)束，轉(zhuǎn)轉(zhuǎn)向sttep55，否則則轉(zhuǎn)向sstepp3.生成隨機數(shù)數(shù)，如果果，根據(jù)據(jù)方法11，生成成新的個個體；否否則，根根據(jù)方法法2生成新的個個體，如如果是可可行解，將將插入到到中；否否則插入入到中，反反復(fù)執(zhí)行行直到生生

15、成個可行解根據(jù)新生成成的群體體更新最最優(yōu)個體體集和，轉(zhuǎn)向向stepp2step55. 輸出最最優(yōu)解集集3 算法分分析3.1 算算法的性性能衡量量約束優(yōu)化問問題的算法性性能的衡衡量可分分為兩部部分，一一部分為為最終獲獲得的最最優(yōu)解的的性能的的衡量，如如通過GGD15來度量量最優(yōu)群群體的逼逼近性，SP16來衡量最優(yōu)解的分布均勻性，或通過計算目標函數(shù)的次數(shù)衡量算法的復(fù)雜度和算法的收斂速度另一部分是針對約束優(yōu)化問題來衡量群體的多樣性，Koziel & Michalewicz17給出一種多樣性度量準則，其定義如下： （5） 其中表示每每一次搜搜索過程程中生成成的可行行解的數(shù)數(shù)目，為為所生成成的所有有個體

16、的的數(shù)目相應(yīng)地地，為了了衡量群群體中的的不可行行解違反反約束的的強度，可可采用約約束違反反度函數(shù)數(shù)的均值值來度量量： （6）其中表示集集合所包包含元素素的數(shù)目目然而而在實際際問題中中，決策策者往往往只對某某一范圍圍的最優(yōu)優(yōu)解感興興趣，故故下邊只只評價本本文算法法對標準準測試函函數(shù)最終終獲得的的最優(yōu)解解集的逼逼近性與與均勻性性，并與與NSGGA-進行比比較3.2 算算法的時時間復(fù)雜雜性分析析我們僅考慮慮種群規(guī)規(guī)模對算算法時間間復(fù)雜度度的影響響，設(shè)可可行群體體的規(guī)模模為，不不可行群群體的規(guī)規(guī)模為，群群體的規(guī)規(guī)模為，群群體的最最大規(guī)模模為，則則文中算法法迭代一一次的時時間復(fù)雜雜度可計計算如下下：算法

17、法中重組組和變異異操作的的時間復(fù)復(fù)雜度為為；判斷斷進化群群體中個個體可行行性所需需時間復(fù)復(fù)雜度為；更新新群體、和的時間間復(fù)雜度度分別為為、和；計算群群體和的適應(yīng)應(yīng)度所需需時間復(fù)復(fù)雜度為為；用于更新新最優(yōu)群群體的時時間復(fù)雜雜度最差差為；保持持最優(yōu)群體體和進化化群體多多樣性的的時間復(fù)復(fù)雜度最最差為； 則算法迭代代一次所所需的時時間復(fù)雜雜度最差差為+ （7）上述復(fù)雜度度可簡化化為 （88）設(shè)為所有種種群的規(guī)規(guī)模，令令，則本本文算法法的時間間復(fù)雜度度 （99）NSGA- 9和SPPEA 10是多多目標進進化算中中兩個最最具有代代表性的的優(yōu)秀算算法，這兩個個算法的的時間復(fù)復(fù)雜度最最差分別別為和，其中中分

18、別為為進化種群群規(guī)模和和外部種種群集的的規(guī)模因而，SSPEAA和本文文算法的的時間復(fù)復(fù)雜度最最差為，這這比NSSGA-的時間間復(fù)雜度度稍高一一些，但但接下來來的實驗驗結(jié)果告告訴我們們，本文文算法的的均勻性性及逼近近性卻明明顯優(yōu)于于NSGGA-事實上上，SPPEA和和本文算算法的時時間復(fù)雜雜度主要要用于環(huán)環(huán)境選擇擇（Ennvirronmmenttal sellecttionn）上，如如果文中中對采取取NSGGA-中的多多樣性保保持策略略，則本本文算法法的復(fù)雜雜度將降至4 實驗結(jié)結(jié)果與分分析（1） 測測試函數(shù)數(shù)與參數(shù)數(shù)設(shè)置為了驗證本本文給出算算法的可可行性，我我們采用用Debb18建議的的用來測測

19、試約束束多目標標優(yōu)化算算法性能能的四個個常見的的測試函函數(shù)來檢檢驗本文文算法的的性能可行解解集合的的規(guī)模，不不可行解解集合的的規(guī)模初始化化時，隨隨機生成成個體的的數(shù)目，參參數(shù)，為位于于區(qū)間中中的一致致隨機數(shù)數(shù)Deeb給出出的測試試函數(shù)可可用統(tǒng)一一的解析析表示，即即其中， 測試函函數(shù)選取取不同的的參數(shù)時時，所構(gòu)構(gòu)造的測測試函數(shù)數(shù)性質(zhì)不不同，可可行解和和不可行行解的分分布也不不同，最最終導(dǎo)致致全局PPareeto最最優(yōu)解集集的不同同其中中通過控控制參數(shù)數(shù)的大小小，可以以控制PPareeto前前端不連連續(xù)的段段數(shù)，越越大段數(shù)數(shù)越多；而較小小參數(shù)可可以使得得每一不不連續(xù)PPareeto前前端僅包包含一

20、個個Parretoo點；參參數(shù)調(diào)節(jié)節(jié)連續(xù)可可行域到到Parretoo前端的的點的距距離，越越大距離離越遠，其其作用在在于調(diào)節(jié)節(jié)問題求求解的難難度；參參數(shù)的作作用在于于改變分分段Paaretto前端端之間的的分布特特性，當(dāng)當(dāng)=1時時，Paaretto前端端為均勻勻分布；當(dāng)時， Parretoo前端向向較大的的方向移移動；當(dāng)當(dāng)時，則則Parretoo前端向向較大的的方向移移動基基于以上上分析我我們選取取不同的的參數(shù)構(gòu)構(gòu)造4個個常用的的測試函函數(shù)檢驗驗本節(jié)算算法的性性能，這這些測試試函數(shù)的的參數(shù)取取值具體體如下圖4.1測測試函數(shù)數(shù) CTTP1在在目標空空間示意意圖 圖4.2測測試函數(shù)數(shù)CTPP2在目

21、目標空間間示意圖圖圖4.3測測試函數(shù)數(shù) CTTP3在在目標空空間示意意圖 圖44.4測測試函數(shù)數(shù)CTPP4在目目標空間間示意圖圖測試函數(shù)CCTP11：，可行行解、不不可行解解、全局局Parretoo前端分分布如圖圖4.1所所示測試函數(shù)CCTP22： ，可行行解、不不可行解解、全局局Parretoo前端分分布如圖圖4.2所所示測試函數(shù)CCTP33：，可行行解、不不可行解解、全局局Parretoo前端分分布如圖圖4.3所所示測試函數(shù)CCTP44：，可行行解、不不可行解解、全局局Parretoo前端分分布如圖圖4.4所所示（2）實驗驗結(jié)果與與分析在相同的測測試函數(shù)數(shù)和目標標函數(shù)計計算次數(shù)數(shù)下，將將本

22、文算算法和經(jīng)經(jīng)典的NNSGAA-III算法進進行比較較，并將將各自算算法獨立立運行330次，然然后統(tǒng)計計兩種算算法所得得Parretoo最優(yōu)解解集的均均勻性（Spacing，SP）與逼近性（Generational distance, GD）的最好、最差、均值、方差和中間值，以此作為衡量算法性能的標準由于真實Pareto最優(yōu)集是未知的，故我們將兩種算法所得的60個近似Pareto最優(yōu)解集之并集的Pareto濾集作為真實Pareto最優(yōu)解集的逼近，其中測試函數(shù)CTP1，CTP2，CTP3的函數(shù)值計算次數(shù)為10200，而CTP4的函數(shù)值計算次數(shù)為610014這里，集合的Pareto濾集定義為. 圖

23、4.5、4.6、4.7、4.8為從30次運行中隨機選擇的一次運行結(jié)果，從實驗曲線可以看到本文算法求出的Pareto Front在逼近性方面要優(yōu)于NSGA-II圖4.5測測試函數(shù)數(shù)CTPP1的Parretoo Frrontt 圖 4.6 測試函函數(shù)CTTP2的的Parretoo Frrontt 圖4.7測測試函數(shù)數(shù)CTPP3的Parretoo Frrontt 圖圖4.8測試試函數(shù)CCTP44的Parretoo Frrontt為了進一步步定量的的評價兩兩種算法法的逼近近性與均均勻性，表4.1，4.2，4.3，4.4給出了兩種算法對上述述四個測測試函數(shù)數(shù)的SPP，GDD的統(tǒng)計計結(jié)果，從表中數(shù)據(jù)容易看

24、出，在解集的逼近性和均勻性方面本文算法對四個測試函數(shù)的標準方差都明顯小于經(jīng)典的NSGA-II算法，這說表4.1 測試函函數(shù)CTTP1評評價準則則的統(tǒng)計計結(jié)果bestworsttavgmediaanStd.DDev.SPNSGA-II0.428850.717790. 577490.569940.18442Propoosedd0.518870.613380. 577050.568840.10443GDNSGA-II0.000050.002210. 000170.001150.00113Propoosedd9.8211e-0055.3677e-0042.06225e-00442.6366e-0040

25、.00003表4.2 測試函函數(shù)CTTP2評評價準則則的統(tǒng)計計結(jié)果bestworsttavgmediaanStd.DDev.SPNSGA-II0.327750.412210. 399240.373320.21557Propoosedd0.268890.335510.296650.297740.08113GDNSGA-II0.000080.001170.00110.001130.00111Propoosedd1.5477e-0051.7844e-0042.3066e-778.0333e-0050.00001表4.3 測試函函數(shù)CTTP3評評價準則則的統(tǒng)計計結(jié)果bestworsttavgmedia

26、anStd.DDev.SPNSGA-II0.521190.745510.369990.379910.23112Propoosedd0.518870.613380.296650.283340.18113GDNSGA-II0.000050.002210.001120.001130.00113Propoosedd9.8211e-0055.3677e-0048.03225e-00552.6366e-0040.00002表4.4 測試函函數(shù)CTTP4評評價準則則的統(tǒng)計計結(jié)果bestworsttavgmediaanStd.DDev.SPNSGA-II0.275530.563340.349900.35776

27、0.12778Propoosedd0.224450.528860.342260.338810.11338GDNSGA-II0.001110.003360.002230.002230.00330Propoosedd1.32332e-83.3711e-774.64552e-85.1733e-80.00001明本文的算算法性能能更穩(wěn)定定另一方方面，上上述定量量的度量量結(jié)果也也表明在搜搜索過程程中適當(dāng)當(dāng)?shù)倪\用用性能較較優(yōu)的不不可行解解的信息息不僅有有助于保保持群體體的多樣樣性，而而且增強強了算法法的搜索索功能，并并在一定定程度上上起到了了維持解解集的均均勻性的的作用5 結(jié)論本文借助粒粒子群算算法的基基

28、本思想想給出了了一種改改進的差差分進化化算法，在適當(dāng)?shù)睦貌糠謨?yōu)良不可行個體的基礎(chǔ)上，提出了用于約束多目標優(yōu)化問題的雙群體差分進化算法該算法中的兩個群體分別用于記錄進化過程中的可行解及部分性能較優(yōu)的不可行解，其優(yōu)點在于可以充分利用每次迭代產(chǎn)生的子代個體的信息此外，還對文中算法的時間復(fù)雜度與NSGA-和SPEA進行比較.經(jīng)典測試函數(shù)的數(shù)值仿真結(jié)果表明，本文算法無論在解集的逼近性及均勻性方面都優(yōu)于NSGA-II算法，這表明文中提出的基于雙群體的差分進化算法可用于求解帶約束的多目標優(yōu)化問題方面有一定的優(yōu)勢正如“沒有有免費的的午餐定定理”19所指出出的，任何何一種算算法不可可能在所所有的性性能方面面占

29、盡優(yōu)優(yōu)勢，雖雖然本文文算法在在求解約約束多目目標優(yōu)化化問題方方面具有有一定的的優(yōu)勢，但但計算量量要稍高高于NSSGA-II。接接下來我我們的研研究將致致力于如何降降低算法法的時間間復(fù)雜度度及本文文算法的的實際應(yīng)用用。參考文獻Mitsuuo GGen andd Ruunweei CChenng, Gennetiic aalgooritthmss & Enggineeeriing Dessignn. Joohn Willey & SSonss, Incc, Neww Yoork,19997.Fred Glooverr, HHeurristticss foor IInteegerr prrogrra

30、mmmingg ussingg suurroogatte cconsstraaintts. Deccisiion Sciiencces,19777，88(1):1556-1166;Davidd E.Golldbeerg, Geenettic in seaarchh, opttimiizattionn annd mmachhinee leearnningg. Adddisoon-WWeslley Pubblisshinng CCo.,Reaadinng,MMasssachhuseettss,19989.Wang Yueexuaan, Liuu Liiancchenn, etcc,. CConss

31、traaineed MMulttiobbjecctivve OOptiimizzatiion Evooluttionnaryy Allgorrithhm. Jouurnaal oof TTsinnghuua UUnivv(Scci & Teech),20005,45(1),1033-1006.(王躍宣，劉劉連臣等等. 處處理帶約約束的多多目標優(yōu)優(yōu)化進化化算法. 清華華大學(xué)學(xué)學(xué)報（自自然科學(xué)學(xué)版），220055，455（1），1103-1066) .Zhangg Yoongdde, Huaang Shaabaii. OOn AAnt Collonyy Allgorrithhm ffor Soll

32、vinng MMulttiobbjecctivve OOptiimizzatiion Proobleems. Coontrrol andd Deecissionn. 20004,220(2),1770-1174. （張勇德，黃黃莎白. 多目目標優(yōu)化化問題的的蟻群算算法研究究. 控制制與決策策，20005，220（22），1170-1744.）Gao YYugeen, Cheeng Fenng,eetc,. AA Neew IImprroveed GGeneeticc Allgorrithhms Bassed on Connverrtinng IInfeeasiiblee Inndivviduu

33、alss innto Feaasibble Onees aand Itss Prropeertyy Annalyysiss. AActaa Ellecttronnica Siinicca，220066，344（4），6638-6411. (高玉根，程程峰，王王燦，王王國彪. 基于于違約解解轉(zhuǎn)化法法的遺傳傳算法及及其性能能分析. 電子子學(xué)報，220066，344（4），6638-6411).Carloos AA. CCoelllo Coeelloo. TTheooretticaal aand Nummeriicall Coonsttraiint-Hanndliing Tecchniiquees

34、uusedd wiith Evooluttionnaryy Allgorrithhms: A Surrveyy off thhe SStatte oof tthe Artt, CCompputeer MMethhodss inn Apppliied Mecchannicss annd EEngiineeerinng, Voll. 1191, Noo. 111-12, ppp. 112455-112877, JJanuuaryy 20002.Fernaandoo Jiimnnez andd Joos L. Verrdeggay. HYPERLINK http:/www.cs.cinvestav.

35、mx/constraint/papers/jimenez99.ps Evvoluutioonarry ttechhniqquess foor cconsstraaineed ooptiimizzatiion proobleems. Inn Haans-Jrrgenn Ziimmeermaann, edditoor, 7thh Euuroppeann Coongrresss onn Inntellliggentt Teechnniquues andd Sooft Commputtingg (EEUFIIT999), Aaacheen, Gerrmanny, 19999. Verrlagg Maa

36、inzz. IISBNN 3-896653-8088-X.Kalyaanmooy DDeb, Ammritt Prrataap, Sammeerr Aggarwwal, annd TT. MMeyaarivvan. A Fasst aand Eliitisst MMulttiobbjecctivve GGeneeticc Allgorrithhm: NSGGA-II, IEEEE Traansaactiionss onn Evvoluutioonarry CCompputaatioon, 20002, 6(22), 1822-1197.Eckarrt ZZitzzlerr annd LLoth

37、har Thiielee. MMulttiobbjecctivve eevollutiionaary alggoriithmms: A ccompparaativve ccasee sttudyy annd tthe strrenggth parretoo appprooachh. IIEEEE Trranss. OOn Evvoluutioonarry CCompputaatioon,119999,3(4),2577-2771.Stornn，R. annd KK. PPricce(119955). Diffferrenttiall evvoluutioon: a ssimpple andd

38、effficciennt aadapptivve sscheeme forr gllobaal ooptiimizzatiion oveer cconttinuuouss sppacees. Tecchniicall Reeporrt TTR-995-0012, Innterrnattionnal Commputter Sciiencce IInsttituute, Beerkeeleyy.Yung-Chiien Linn, KKao-Shiing Hwaang, annd FFengg-Shhengg Waang. Hyybriid DDifffereentiial Evooluttionn

39、 wiith Mulltipplieer UUpdaatinng MMethhod forr Noonliineaar CConsstraaineed OOptiimizzatiion Proobleems. CEEC220022, vvoluume1, pagges 8722-8777, Pisscattawaay, Neww Jeerseey, Mayy 20002.Abbasss, H., Saarkeer, R. andd Neewtoon, C. PDEE: AA Paaretto-ffronntieer DDifffereentiial Evooluttionn Appprooac

40、hh foor MMultti-oobjeectiive Opttimiizattionn Prrobllemss. PProcceeddinggs oof tthe Conngreess on EC 20001(CCEC20001),voll.2, IEEEE Serrvicce Cennterr, Piiscaatawway, Neew JJerssey,9711-9778.Li Biing-yu, Xiiao Yunn-shhi, Wu Qi-di. Hyybriid aalgooritthm bassed on parrticcle swaarm opttimiizattionn fo

41、or ssolvvingg coonsttraiinedd opptimmizaatioon pprobblemms. Conntrool aand Deccisiion, 20004, 199(7), 8044-8007.(李炳宇，蕭蕭蘊詩，吳吳啟迪一種基基于粒子子群算法法求解約約束優(yōu)化化問題的的混合算算法，控控制與決決策，220044,199(7), 8804-8077) .D.A.VVan Velldhuuizeen aand G.BB. llamoont. Muultiiobjjecttivee Evvoluutioonarry AAlgooritthm Ressearrch : AA

42、 hiistoory andd annalyysiss. DDeptt. EElecc.Coompuut.EEng.,Grraduuatee Scchoool oof EEng., AAir Forrce Insst.TTechhnoll.,WWrigght-Pattterrsonn AFFB, OH.Tecch.RRep.TR-98-03,19998.J. Scchottt. Faaultt toolerrantt deesiggn uusinng ssinggle andd muultiicriiterria gennetiic aalgooritthm opttimiizattionn.

43、 MMastters tthessis, Deeparrtmeent of Aerronaautiics andd Asstroonauuticcs, Masssacchussettts IInsttituute of Tecchnoologgy,19995.S.Kozziell annd MMichhaleewiccz. Evooluttionnaryy allgorrithhms, hoomommorpphouus MMapppingg, aand connstrrainned parrameeterr opptimmizaatioon. Evooluttionnaryy Coompuut

44、attionn, 19996,7(11):119-444. Kalyaanmooy DDeb, Ammritt Prrataap, andd T. Meeyarrivaan. Connstrrainned Tesst PProbblemms ffor Mullti-objjecttivee Evvoluutioonarry OOptiimizzatiion. In: Prroceeediingss off thhe 11st Intternnatiionaal CConffereencee onn Evvoluutioonarry MMultti-CCritteriion Opttimiiza

45、ttionn, ZZuriich, Swwitzzerllandd, 220011, Spprinngerr-Veerlaag, 2884-2298Wolpeert D.HH., Maccreaady W.GG. No freee lluncch ttheooremms ffor seaarchh. SSantta FFe,NM: Sannta Fe Insstittutee. TTechhniccal Repportt: SSFI-TR-05-0100, 19995. A Diffferrenttiall Evvoluutioon BBaseed oon ddoubble Poppulaat

46、ioons forr Coonsttraiinedd Muultii-obbjecctivve OOptiimizzatiion ProobleemMENG Honng-yyun11, ZHANGG Xiiao-huaa 2, LIUU Sann-yanng1(1. DDeptt. of Appplieed MMathh., Xiddiann Uniiverrsitty, Xian 71000711, Chhinaa；2. Innstiitutte oof IInteelliigennt IInfoormaatioon PProccesssingg, Xiidiaan Uniiverrsitt

47、y, Xian, 71100771)Abstrractt: Ann immproovedd diiffeerenntiaal eevollutiion appproaach is givven firrst, annd aa neew aalgooritthm bassed on douublee Poopullatiionss foor CConsstraaineed MMultti-oobjeectiive Opttimiizattionn Prrobllem (CMMOP) is preesenntedd. IIn tthe proopossed alggoriithmm, ttwo p

48、oppulaatioons aree addoptted, onne iis ffor thee feeasiiblee sooluttionns ffounnd dduriing thee evvoluutioon, andd thhe ootheer iis ffor inffeassiblle ssoluutioons witth bbettter perrforrmannce whiich aree alllowwed to parrticcipaate in thee evvoluutioon wwithh thhe aadvaantaage of avooidiing difffi

49、cculttiess suuch as connstrructtingg peenallty funnctiion andd deelettingg innfeaasibble sollutiionss diirecctlyy. IIn aaddiitioon, thee tiime commpleexitty oof tthe proopossed alggoriithmm, NNSGAA-andd SPPEA aree coompaaredd, wwhicch sshoww thhe bbestt iss NSSGA-, ffollloweed bby SSPEAA annd oour a

50、lggoriithmm siimulltanneouuslyy. Thee exxperrimeentss onn beenchhmarrks inddicaate thaat oour alggoriithmm iss suuperriorr too NSSGA-in thee meeasuure of GD andd SPP. Keywoordss: DDifffereentiial Evooluttionn; Connstrrainned Opttimiizattionn Prrobllem; muultii-obbjecctivve opttimiizattionn prrobllem

51、;BackggrouundConsttraiinedd opptimmizaatioon, botth ffor nonnlinnearr prrogrrammmingg annd mmulti-objjecttivee opptimmizaatioon, is a vveryy immporrtannt pprobblemm annd hhas a vvariietyy off apppliicattionns iin eengiineeerinng, mannageemennt, matthemmatiics andd ottherr fiieldds. A ccommmon wayy t

52、oo coonsttraiinedd opptimmizaatioon pprobblemm iss too deeal witth cconsstraaintts bby ppenaaltyy fuuncttionn, wwithh thhe ddisaadvaantaage andd diiffiicullty in chooosiing thee peenallty facctorrs. In thiis ppapeer, thee auuthoors prooposse aa difffereentiial evollutiion baseed oon ddoubble popuulattionns ffor consstraaine