多目標進化算法|基於網格約束分解方法

近期，南京航空航天大學蔡昕燁副教授，汕頭大學範衠教授和香港城市大學張青富教授關於網格約束分解的多目標進化算法研究取得了新進展，相關成果發表在國際頂級期刊《IEEE Transaction on Evolutionary Computation》上。

基於分解的多目標進化算法（MOEA/D）將一個多目標優化問題分解為一組單目標優化的子問題，並以相互協作的多點搜索方式同時求解它們。然而，常用的分解方法，如加權和（WS）切比雪夫（TCH）和懲罰值邊界交叉法（PBI）來源於基於單點搜索的數學規劃，它們可能不太適合基於種群的多目標進化算法。

   圖1  TCH或CDG分解方法對具有不同形狀PF問題的求解效果

首先，常用的分解方法對Pareto前沿（PF）的形狀特別敏感。例如，使用TCH分解方法在求解具有非常凹PF的問題時，可近似出比較均勻的解集；但是對於具有凸形前沿時，TCH分解方法得到解集的多樣性並不理想，如圖1(a)所示。當多目標優化問題在不同目標上的規模有顯著差距時，TCH分解方法也不能得到理想的解集，如圖1(b)所示。

其次，在使用上述常用分解方法時，一個解可能會作為最優解關聯到多個子問題，從而導致解集多樣性的丟失。設第個子問題的解是，定義這個解的改進區域為在第個子問題上解比好，如圖2(a)-2(c)的陰影部分所示。對於第個子問題，位於改進區域中的解都比好，從而會替換掉，進而會導致解集多樣性的丟失。由圖2(a)-2(c)可以看出，傳統的分解方法（WS，TCH和PBI）中一個解的改進區域過大，對解集多樣性保持以及多點協作搜索不利。

圖2 不同分解方法下解的改進區域

為了解決上述兩個問題，本章提出了一種網格約束分解方法(Constrained Decomposition with Grids, CDG)。CDG中的每個子問題都是一個帶約束的單目標優化問題：當優化某個目標時，則對其餘的目標設置上下界約束。如果使用網格系統均勻地進行約束分解，那麼每個解的改進區域將會是一個細長的區域，如圖2(d)所示，這非常有利於在優化過程中種群的多樣性保持以及有效的多點協作搜索。此外，由於使用網格進行均勻的約束分解，CDG對PF形狀具有較好的魯棒性，如圖1(c) - (d)所示。

基於CDG，本文進一步提出了一種網格約束分解的多目標進化算法（CDG-MOEA）。CDG-MOEA與7個算法在15個測試問題上的性能對比驗證了其有效性。

 

 

相關論文及原始碼可以在作者個人主頁下載：http://xinyecai.github.io/

 

論文信息：

Title: A Constrained Decomposition Approach with Grids for Evolutionary Multiobjective Optimization

Authors: Xinye Cai, Zhiwei Mei, Zhun Fan, and Qingfu Zhang

Source: IEEE Transaction on Evolutionary Computation

DOI: 10.1109/TEVC.2017.2744674

Online date: August 2017 (Early Access)

全文連結：https://ieeexplore.ieee.org/document/8016633/