基于自適應e截斷策略的約束多目標優化算法

畢曉君　張　磊（哈爾濱工程大學信息與通信工程學院哈爾濱150001）

?

基于自適應e截斷策略的約束多目標優化算法

畢曉君張磊*
（哈爾濱工程大學信息與通信工程學院哈爾濱150001）

為提高約束多目標優化問題所求解集的分布性和收斂性，該文提出基于自適應ε截斷策略的約束多目標優化算法。首先，自適應ε截斷選擇策略能夠保留Pareto最優解和約束違反度及目標函數值均較優的不可行解，不僅提高了種群多樣性，而且能夠較好地兼顧多樣性和收斂性；其次，為增強算法的局部開發能力，在變異操作和交叉操作之后進行指數變異；最后，改進的擁擠密度估計方式只選擇一部分Pareto最優解和距離較近的個體參與計算，不僅更加準確地反映解集的分布性，而且降低了計算量。通過在標準測試問題（CTP系列）上與其他4種優秀算法的對比結果可以得出，該算法所求解集的分布性和收斂性均得到一定提高，而且相較于對比算法在求解性能上具備一定的優勢。

約束多目標優化；約束處理技術；ε截斷；分布性；收斂性

1　引言

約束多目標優化問題（Constrained Multiob jective Optim ization Problems，CMOPs）是科學研究和工程實踐中最常見的問題之一，涉及到航空航天、網絡通信、機械設計、作業調度和決策科學等諸多領域［14］-。然而隨著目標個數的增加和約束條件的復雜，現有約束多目標優化算法已不能完全滿足應用的需求，算法的性能急需進一步提高。因此，約束多目標優化算法的研究具有重要的理論價值和實際意義。

文獻［5］在更新可行解集時隨機刪除歐氏距離最小的兩個個體中的一個，但會遺失邊界解，從而影響多樣性。同時在更新不可行解集時優先選擇約束違反度小的個體，但這樣的個體可能目標函數值較差，從而影響種群收斂速度；文獻［6］對可行解和不可行解分別構造不同的適應度函數，使得少量不可行解得到保留，從而擴大探索范圍。但由于缺少多樣性維持策略，所求解集的分布性欠佳；文獻［7］優先選擇位于稀疏區域的Pareto可行解進入下一代可行解集以及目標函數較優并且位于稀疏區域的不可行解進入下一代不可行解集，從而兼顧多樣性和收斂性，但算法收斂速度較慢；文獻［8］將目標函數、多樣性度量準則和約束違反度聚合成一個適應度函數，從而協調了精英選擇、多樣性和可行性之間的關系，但算法收斂精度不高；文獻［9］提出以可行解極小化目標函數值和不可行解極小化約束違反度為目標，并利用差分進化算法優良的多樣性能力進化種群，但可行解集與不可行解集的信息交流不夠，種群多樣性還需提高。文獻［10］將分解算法和隨機排序法以及Deb準則結合，但由于存在多個子問題對應同一個體的情況，嚴重影響了種群的多樣性。

綜上，約束多目標優化算法的核心在于如何兼顧多樣性和收斂性，具體涉及到目標函數與約束條件的平衡，可行解與不可行解的比較，全局探索和局部開發的協調等方面。但目前大多數優秀算法在多樣性和收斂性上很難達到充分的平衡。為此，本文提出基于自適應ε截斷策略的約束多目標優化算法。首先，提出的自適應ε截斷操作能夠有效協調可行解和不可行解，從而加強對搜索空間的探索范圍，并且在保證多樣性的同時又能兼顧收斂性；其次，在交叉和變異操作之后引入指數變異，進一步提高局部搜索能力，從而在一定程度上權衡全局探索和局部開發；最后，改進的擁擠密度估計方式能夠更加準確地評估種群的分布性，不僅提高進化效率而且更好地維持種群多樣性。

2　基于自適應e截斷的約束多目標優化算法

實驗研究表明，影響約束多目標優化算法性能的關鍵在于多樣性和收斂性的協調關系。因此本文算法不僅針對約束處理技術進行改進，而且還對進化操作以及多樣性維持方式進行改進，提出自適應ε截斷策略，引入指數變異，改進擁擠密度估計方法，從而獲得算法整體求解性能的改善。

2.1自適應e截斷策略

目前應用效果最好的約束處理技術為雙種群存儲［7］和ε約束［11］。雙種群存儲對可行解和不可行解分別存儲，能夠利用少量不可行解來提高種群多樣性。但由于在更新不可行解集時只是優先考慮約束違反度，使得種群中存在目標函數值較差的不可行解，進而影響收斂速度。ε約束最先用于解決約束單目標優化問題，在一定程度上協調了可行解和不可行解的關系，擴大了探索范圍。但其一對一的替換機制又會影響多樣性，因為被替換個體位于稀疏區域時，將會遺失部分搜索區域，所以ε約束在多樣性和收斂性上更加偏重后者。為此，在兩者基礎上提出ε截斷策略，充分協調多樣性和收斂性。

定義1ε截集：種群中所有滿足（）Gε≤X的個體X構成的集合稱為ε截集，記為ε≤P。

定義2ε截斷操作：將種群劃分為以約束違反度ε為界限的兩個種群（ε≤P和ε>P）的操作，稱為ε截斷操作。

ε設置如式（1）所示。

性質2當ε=0時，ε截斷策略與雙種群存儲性質相同，雙種群存儲是ε截斷的一個特例。

（1）ε截斷策略與雙種群存儲的比較：相同點：兩者均讓部分不可行解參與進化，從而提高種群多樣性；兩者都能避免可行解與不可行解的直接比較，事實上可行解與優秀不可行解很難定量比較。不同點：雙種群存儲是ε截斷策略在ε=0時的特例；兩者更新種群的機理不同，ε截斷策略會在進化種群中會保留少量優秀不可行解，而雙種群存儲通過單獨的不可行解集儲存不可行解，需要額外的存儲開支；ε截斷策略在進化前期時，ε值相對較大，種群中的不可行解能夠擴大對搜索空間的探索范圍，增強多樣性，同時保留的Pareto最優解又能保證收斂性。在進化后期ε相對較小并隨著進化迭代次數的增加逐漸趨于零，種群中會全部由可行解構成，此時更加注重的是種群的收斂性，所以ε截斷具有自適應性。

（2）ε截斷策略與ε約束的比較：相同點：兩者均能有效協調可行解和不可行解的關系，從而加強種群的多樣性。不同點：ε截斷能夠方便融合其他操作，如小生境和擁擠密度估計等，從而更好改善種群的分布性；ε約束是新生個體與舊個體一對一的比較，是基于單個個體的操作，雖然能夠加快收斂速度，但會影響種群的多樣性，而ε截斷是基于集合的操作并結合擁擠密度估計，所以能更好維護多樣性。

綜上，ε截斷策略通過自適應調整有效平衡了可行解與不可行解的關系，在進化前期保留Pareto最優解和一部分優秀不可行解，從而較好地兼顧了多樣性和收斂性，而在進化后期更加注重對可行域的開發能力，促使種群向Pareto前沿收斂。

2.2進化操作

本文采用文獻［12］的變異算子和交叉算子，分別如式（2）和式（3）所示。

研究表明，上述的變異算子和交叉算子對于維護種群的多樣性效果顯著。而為了加強局部搜索能力，本文以概率mp進行指數變異［13］，如式（4）所示。

其中，η為指數因子，rand（）·為［0，1］隨機數，jl和ju分別為決策空間j維的下界和上界。

2.3基于e截斷策略的精英選擇

經過2.2節的進化操作，會產生包含N個體的新生種群，進而將父代種群和新生種群合并，然后利用ε截斷操作，將合并種群一分為二成

接著從合并種群中選擇N個體作為下一代種群，共分3種情況。情況1則從中選擇N個體作為下一代種群；情況2：將ε≤P作為下一代種群；情況3:則從個體，并與合并作為下一代種群。

對于情況1，為了有效平衡多樣性和收斂性，應該選擇在目標空間上Pareto等級較高和擁擠密度較大的個體。首先利用快速非支配排序法［14］將分層為中選擇使得其總個體數量sN大于或等于N，如果sN N=，將然后選擇合適的前若干等級層作為下一代種群，如果sN N>，計算sF中所有個體的擁擠密度。接著選擇sF中擁擠密度最大的體，將其與合并作為下一代種群。值得注意的是，本文將sF中所有邊界解的擁擠密度定義為無窮大，以確保它們進入下一代，從而能夠加大對搜索空間的探索廣度。

擁擠密度計算方式［14］如式（6）所示。

其中，N為種群規模，，ijd表示個體iX到jX在目標空間上的歐氏距離。

由于式（6）考慮了其中一個個體到種群其他所有個體的距離，一方面計算量很大，另一方面處于Pareto等級較差等級，相對距離較遠的個體會對所要計算擁擠密度的個體會產生一定影響，從而不能準確反映種群的多樣性分布。為此，提出改進的擁擠密度公式，如式（7）所示。

式（7）中參與計算個體數量遠小于N，從而減少了計算量，并提高算法效率。同時，式（7）右邊第1項表示選擇距離較近的1T個體，從而避免距離較遠個體影響，而第2項表示選擇Pareto等級較優的2T個體，從而消除Pareto等級較差個體影響。所以改進的擁擠密度不僅能夠降低計算量，而且在計算個體的擁擠密度時能夠去除較遠個體和Pareto等級較差個體的影響，從而能夠準確反映個體的分布情況，并提高種群多樣性。

對于情況3，由于ε≤P中的個體數量較少，說明可行域相對較小，造成進化過程中搜索到的可行解較少，此時算法更應該偏重搜索可行解，故選擇約束違反度最小的個體，這樣能夠在一定程度上促使種群向可行域靠近。

2.4算法流程

為便于理解，給出本文算法的具體步驟。

步驟1初始化參數。包括最大進化代數maxG，種群規模N，縮放因子F，交叉因子CR，指數因子η，變異因子mp.；

步驟2在決策空間里隨機生成產生N個體，構成初始種群；

步驟3執行2.2節中進化操作，生成新生種群；

步驟4合并父代種群和新生種群，并計算合并種群所有個體的約束違反度和目標函數值；

步驟6執行2.3節中基于ε截斷的精英選擇操作，選擇N個體作為下一代種群；

步驟7判斷是否達到maxG，是則將種群中的Pareto最優解作為結果輸出，否則，轉到步驟3。

3　實驗及分析

為驗證本文算法在約束多目標優化問題上的求解性能，將其與目前性能優異的文獻［5］算法、文獻［6］算法、BB-MOPSO［7］，NSGA-2約束多目標優化算法［15］（以下簡稱NSGA-2）在通用標準測試函數CTP2-CTP7［6］上進行對比實驗，并采用GD［5］和SP［5］這兩種通用的評價指標測試算法的性能。其中，GD用于評價解集的收斂性，SP用于評價解集的分布性。實驗硬件環境為Intel Pentium，CPU:G 620，4 GB內存、主頻2.6 GHz的計算機，程序采用MATLAB R2010編寫。

由于CTP3和CTP4的真實Pareto最優解為多個離散點，CTP5的真實Pareto最優解為一段連續區域和多個離散點，再利用SP來度量分布性就不合適了。于是，將上述6個測試函數分為2組：CTP2，CTP6和CTP7記為第1組，CTP3，CTP4和CTP5記為第2組。第1組測試函數用SP來度量分布性以及用GD來度量收斂性，第2組測試函數用離散點個數來度量分布性以及用GD來度量收斂性。

3.1改進的擁擠密度估計的有效性驗證

為驗證改進擁擠密度估計的有效性，在本文算法基礎上，將原始擁擠密度估計方式（式（6））和改進擁擠密度估計方式（式（7））進行對比實驗，分別記為改進前和改進后。參數取值為N=100，Gmax= 3000，F=0.5，CR=0.9，η=20，pm=1/n。獨立運行次數為10次，實驗結果如表1～表3所示。

表1　第1組測試函數上改進前后的SP值

表2　第2組測試函數上改進前后的離散點個數

表3　 2組測試函數上改進前后的GD值

從表1可以看出，改進后的SP均值均優于改進前。特別在測試函數CTP5上，改進后的分布性有明顯的改善，表明改進的擁擠密度估計方法在種群多樣性維持上具有更好的性能；從表2可以看出，改進前后的離散點個數均取得較好的效果；從表3可以看出，在所有測試函數上，改進后的GD均值均優于改進前，特別在測試函數CTP2和CTP7上有明顯的提高，說明改進的擁擠密度估計方法對加強收斂性也有幫助。同時，改進后的標準差普遍較小，說明算法穩定性也得到增強。因此，改進的擁擠密度估計方法對提高多樣性起著重要作用，而多樣性的提高又能有效避免陷入局部搜索，為最終收斂到整個真實Pareto前沿提供保障。

3.2對比實驗及結果分析

為驗證本文算法的先進性，將其與優秀的NSGA-2，文獻［5］算法，BB-MOPSO和文獻［7］算法進行對比實驗，獨立運行為30次。為保證公平性，所有算法參數取值為種群規模N=100，最大迭代次數除此，本文算法其他參數取值對比實驗結果如表4～表6所示。

從表4可以看出，在測試函數CTP2和CTP6上，本文算法的SP均值優于其他4種算法，所求解集的分布性最優，說明在進化過程中較好地維持了種群多樣性。在測試函數CTP7上，NSGA-2的SP均值在5種算法中最優，略優于排名第2的本文算法。從表5可以看出，在測試函數CTP3上，文獻［5］算法、BB-MOPSO以及本文算法的離散點個數均值都為14，說明在30次獨立運行中都一致找到了所有的離散點。但文獻［5］算法的離散點個數均值只有9.90，表明由于多樣性維持不足導致遺失一部分Pareto解。在測試函數CTP4和CTP5上，本文算法均取得最優的結果，并且明顯優于其他4種算法，說明本文算法在進化中探索能力更強。綜上，本文算法在種群多樣性維護上具有明顯優勢，使得所求的解集分布性較好。

表4　 5種算法在第1組測試函數上的SP值

表5　 5種算法在第2組測試函數上的離散點個數

從表6可以看出，在測試函數CTP3，CTP4和CTP7上，本文算法獲得了最優的GD均值，表明所求得的解集更加逼近真實Pareto前沿。文獻［7］算法在測試函數CTP2和CTP6上，取得最優的GD均值，而在這兩個測試函數上，本文算法略劣于文獻［7］算法。在測試函數CTP5上，NSGA-2的GD均值最好，本文算法排名第2。但是NSGA-2的離散點個數均值和GD標準差都較差，說明NSGA-2的多樣性維持能力還需加強。以上實驗結果表明，本文算法在多樣性和收斂性上均具有一定的優勢。最后，本文算法的SP標準差和GD標準差在2組測試函數幾乎均為最優，表明本文算法的穩定性更好。

4　結束語

針對現有約束多目標優化算法在求解復雜約束多目標優化問題時解集分布性較差和收斂精度不高等問題，本文提出基于自適應ε截斷的約束多目標優化算法。首先，在雙種群存儲和ε約束的基礎上，提出ε截斷策略。通過自適應調整種群中的優秀不可行解的比例，有效協調可行解與不可行解的關系，從而兼顧多樣性和收斂性。其次，在變異和交叉操作后再次進行指數變異以增強對新生個體周圍區域的開發，進一步增強局部開發能力。最后，提出的擁擠密度估計方式通過選擇部分Pareto個體和距離較近的個體參與計算，能夠在改善解集的分布性的

表6　 5種算法在二組測試函數上的GD值

同時降低計算量。通過在CTP2-CTP7測試函數上進行測試，并與NSGA-2，文獻［5］算法，BB-MOPSO和文獻［7］算法進行對比實驗。實驗結果表明，本文算法所求解集的多樣性和收斂性均有較大的提高。下一步工作將針對約束高維目標優化算法及其在決策管理和工程優化中的應用進行展開，以獲得更高的社會價值和經濟價值。

［1］W EI H.Design exp loration of th ree-dim ensional transverse jet in a supersonic crossflow based on data m ining and mu lti-ob jective design optim ization app roaches［J］. International Journal of Hydrogen Energy，2014，39（8）: 3914-3925.doi:10.1016/j.ijhydene.2013.12.129.

［2］ABDELKHALEK O，KRICHEN S，and GUITOUNI A.A genetic algorithm based decision support system for the mu lti-ob jective node p lacement problem in next w ireless generation network［J］.Applied Soft Com puting，2015，33（8）: 278-291.doi:10.1016/j.asoc.2015.03.034.

［3］PARENTE M，CORTEZ P，and CORREIA A G.An evolutionary multi-ob jective optim ization system for earthworks［J］.Expert System swith Applications，2015，42（19）: 6674-6685.

［4］GRASSO R，COCOCCIONI M，MOURRE B，et al.A decision support system for optimal dep loyment of sonobuoy networks based on sea current forecasts and multi-ob jective evolutionary op tim ization［J］.Expert Systems with Applications，2013，40（10）:3886-3899.doi:10.1016/j.eswa. 2012.12.080.

［5］孟紅云，張小華，劉三陽.用于約束多目標優化問題的雙種群差分進化算法［J］.計算機學報，2008，31（2）:229-235. MENG Hongyun，ZHANG Xiaohua，and LIU Sanyang.A differential evolution based on double population for constrained multi-ob jective optim ization prob lem s［J］. Chinese Journal ofComputers，2008，31（2）:229-235.

［6］WOLDESENBET Y G，YEN G G，and TESSEMA B G. Constraint handling in multi-ob jective evolutionary optim ization［J］.IEEE Transactions on Evo lutionary Computation，2009，13（3）:514-525.doi:10.1109/TEVC. 2008.2009032.

［7］張勇，鞏敦衛，任永強，等.用于約束優化的簡潔多目標微粒群優化算法.電子學報，2011，39（6）:1437-1440.

ZHANG Yong，GONG Dunwei，REN Yongqiang，et al. Barebones mu lti-ob jective particle swarm optim izer for constrained optimization prob lem s［J］.Acta Electronica Sinica，2011，39（6）:1437-1440.

［8］LONG Q.A constraint handling technique for constrained multi-ob jective genetic algorithm［J］.Swarm and Evolutionary Computation，2014，15（4）:66-79.doi:10.1016/j. swevo.2013.12.002.

［9］GAO W F，YEN G G，and LIU S Y.A dual-population differential evolution w ith coevolution for constrained optim ization［J］.IEEE Transactions on Cybernetics，2015，45（5）:1094-1107.doi:10.1109/TCYB.2014.2345478.

［10］JAN M A and KHANUM R A.A study of two penalty-parameterless constraint handling techniques in theframework of MOEA/D［J］.Applied Soft Computing，2013，13（1）:128-148.doi:10.1016/j.asoc.2012.07.027.

［11］畢曉君，王玨，李博，等.基于動態遷移的ε約束生物地理學優化算法［J］.計算機研究與發展，2014，3（3）:580-589.

BI Xiaojun，WANG Jue，LIBo，et al.Anεconstrained biogeography-based optim ization w ith dynam ic m igration［J］Journal ofComputer Research and Development，2014，3（3）: 580-589.

［12］鄒德旋，高立群，段納.用修正的差分進化算法確定光電模型參數［J］.電子與信息學報，2014，36（10）:2521-2525.doi: 10.3724/SP.J.1146.2013.01858.

ZOU Dexuan，GAO Liqun，and DUAN Na.Determ ining the parametersof photovoltaicmodulesby amodified differential evolution algorithm［J］.Journal of Electron ics&Inform ation Technology，2014，36（10）:2521-2525.doi:10.3724/SP.J. 1146.2013.01858.

［13］TAN YY，JIAO YC，LI H，et al.Amodification to MOEA/D-DE for multi-ob jective optim ization problem s w ith com plicated Pareto sets［J］.Information Sciences，2012，213（23）:14-38.

［14］DEB Kand JAIN H.An evolutionary many-ob jective optim ization algorithm using reference-point-based nondom inated sorting approach，part I:solving problem s w ith box constraints［J］.IEEE Transactions on Evolutionary Computation，2014，18（4）:577-601.doi:10.1109/TEVC. 2013.2281535.

［15］DEB K，PRATAP A，AGARW AL S，et al.A fast and elitist multi-ob jective genetic algorithm:NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）: 182-197.

畢曉君：女，1964年生，教授，博士生導師，主要研究方向為智能信號處理、數字圖像處理、人工智能、機器學習等.

張磊：男，1987年生，博士生，研究方向為智能信號處理、約束多目標優化.

Constrained Multi-objective Optim ization Algorithm with Adap tivee Truncation Strategy

BIXiaojun ZHANG Lei
（College of Information and Communications Engineering，Harbin Engineering University，Harbin 150001，China）

To im prove distribution and convergence of the obtained solution set in constrained multi-ob jective op tim ization p rob lem s，this paper presents a constrained multi-ob jective op tim ization algorithm based on adaptive εtruncation strategy.Firstly，th rough the proposedεtruncation strategy，the Pareto optim al solutions and the in feasib le solutions with low constraint violation and good ob jective function values are retained to im prove diversity.Besides，both diversity and convergence are coordinated.Second ly，the exponential variation is added for further enhancing the local exploitation ability after mutation and crossover operation.Finally，the im proved crowding density estimation chooses a part of the Pareto optimal individuals and the near individuals to take part in the calcu lation，thus it not on ly assesses the distribution of the solution setmore accurately，bu t also reduces the com putational quantity.The com parative experim ent resu lts w ith another four excellent constrained multiob jective algorithm s on the standard constrained multi-ob jective op tim ization p rob lem s（CTP series）show that diversity and convergence of the proposed algorithm are imp roved，and it has certain advantages com pared with these algorithm s.

Constrained mu lti-ob jectiveoptim ization；Constraint hand ling technique；εtruncation；Distribution；Convergence

The National Natural Science Foundation of China（61175126）

TP18

A

1009-5896（2016）08-2047-07

10.11999/JEIT 151237

2015-11-05；改回日期：2016-03-17；網絡出版：2016-05-05

張磊zl12306124@163.com

國家自然科學基金資助項目（61175126）