Handling Constrained Multiobjective Optimization Problems With Constraints in Both the Decision and Objective Spaces
1.摘要
在真實世界中，帶有決策和目标限制的多目标優化問題常常都同時出現。但以前的人工CMOPS從來沒有同時考慮過決策和目标限制。是以，本文設計了一個同時帶有決策和目标限制的人造的多目标優化問題集，取名為DOC。
另外，本文還提出了一個簡單且高效的處理DOC或也可用于其他CMOPS的方法，取名為TOP。最後本文通過實驗證明了TOP算法的有效性。
2.介紹
這部分文章對CMOP和本文研究内容做了基本介紹，這裡隻對重點問題做介紹。
①一個CMOP可以簡單描述為以下形式：
其中F(x)是目标函數集，g(x)是不等式限制，h(x)是等式限制，x是決策變量。
②現實生活中，大部分限制是決策限制。文章提供了個小例子差別目标限制和決策限制，比如我們去買車，我們的目标函數是舒适度和價格。我們希望價格cost<50k，這個就構成了目标限制，這很容易在目标空間中描述。另外，我們希望座位seat>5,生産國=德國，可以發現這兩個限制卻不能在目标空間描述出來，這兩個實際就是決策限制。
③DOC中涉及到等式限制，目前很少的人工CMOPS考慮到了等式限制
④TOP算法分成兩步。第一步：利用權重的方法将CMOP轉換為一個單目标問題，進行優化。第二步：直接使用現有的CMOEAs對第一步優化結果進行進一步優化，注意此時優化的是個帶限制的多目标優化原問題。
3.相關工作
這部分文章介紹了CMOPs裡面涉及的一些基本定義，以及對目前人工CMOPs和CMOEAs做了介紹。
A.基本定義
1）Pareto Dominance:假設有兩個決策向量，Xu和Xv。當Xu得到的所有目标函數的值都小于Xv求出的，我們稱Xu支配Xv。
2）Feasible Region:滿足所有限制條件的空間即為可行域。我們用下面的公式描述限制的違反程度。
其中，CVi(x)為第i個目标函數的違反程度。
3）Pareto Optimal Solution:對于一個決策向量Xu，如果找不到比起更優的Xv向量，則稱Xu是一個最優的解決方案
4）Pareto Optimal Set:Pareto 最優集，由多個最優決策向量組成的最優解決方案集合
5) Pareto Front:Pareto 前沿，Pareto 最優集在目标空間的圖像
B.目前的人工CMOPs的介紹
目前的人工CMOPs主要分如下兩種：
- 第一種：在多目标優化問題中隻考慮了目标限制。比如CTPs, DAS-CMOPs, 和 NCTPs.
- 第二種：在多目标優化問題中隻單獨考慮決策和目标限制。比如CFs.
C.目前的CMOEAs的介紹
目前的CMOEAs算法大緻分成以下3類：
- 基于支配的方法，包括NSGA-II-CDP,IDEA
- 基于分解的方法，包括CMOEAD，MOEA/D-CDP
- 基于名額的方法
而主流的為前兩種,是以這裡不讨論基于名額的方法：
基于支配的方法
NSGA-II-CDP
原文：A fast and elitist multiobjective genetic algorithm: NSGA-II。
該算法是NSGA-II的延伸，其中CDP指加入了限制支配原理。具體的說，任何可行的個人都支配任何不可行的個體，對于兩個不可行個體，最好是限制違反較小的個體。
IDEA
原文：Infeasibility Driven Evolutionary Algorithm (IDEA) for Engineering Design Optimization
該算法進化過程中顯式地保持了一小部分不可行的解決方案。 認為不可行解的存在有利于IDEA從可行區域和不可行區域搜尋帕累托最優解。
Adaptive tradeoff model
原文：A comparative study of constraint-handling techniques in evolutionary constrained multiobjective optimization
自适應權衡模型根據目前種群的可行性比例将整個進化過程分為三種情況。 這三種情況是：1)不可行情況；2)半可行情況；3)可行情況。 在不同的情況下，設計了不同的限制處理技術來處理限制。
A CMOEA based on an adaptive penalty function and a distance measure
原文：Constraint handling in multiobjective evolutionary optimization
該算法不僅可以在可行區域内搜尋帕累托最優解，而且可以利用不可行個體提供的重要資訊，具有更好的目标函數值和較低的限制違反。
Blended ranking to cross infeasible regions in constrained multiobjective problems注：标題即原文
該算法可以跨越目标空間的不可行區域，找到真正的限制帕累托前沿。 該算法的主要思想是将個體在目标空間中的秩與其在限制空間中的秩相混合。
An evoltionary algorithm for constrained multi-objective optimization
提出了一種CMOEA，其中帕累托優勢概念與限制處理技術和多樣性機制相結合。
New constraint handling method for multi-objective and multi-constraint evolutionary optimization
提出了一種新的基于帕累托最優性的限制處理技術。
Constrained Pareto simulated annealing for constrained multi-objective optimization 和 Constrained multiobjective optimization algorithm based on immune system model
分别采用模拟退火和免疫系統模型求解CMOP。
A corner point-based algorithm to solve constrained
multi-objective optimization problems 和 Differential evolution mutation operators for constrained multi-objective optimization
采用差分進化(DE)來應對CMOP。
A modified objective function method with feasible-guiding strategy to solve constrained multiobjective optimization problems
引入了一種改進的目标函數方法來引導優勢度檢驗，并采用了一種可行的指導政策來修複不可行的個體。 認識到單一限制處理技術的局限性。
Constrained multi-objective optimization algorithm with an ensemble of constraint handling methods
提出了一種新的CMOEA，它利用限制處理技術的集合來求解CMOP。
基于分解的方法
CMOEAD
原文：An adaptive constraint handling approach embedded MOEA/D
提出了一種基于分解的CMOEA，稱為CMOEAD，通過添加一種新的限制處理技術，可以看作是MOEA/D的擴充。 在這種限制處理技術中，根據限制類型、可行空間的大小和搜尋結果自适應地調整違規門檻值。 這種限制處理技術的目的是增加選擇壓力，并使不可行的解決方案的違規小于确定的門檻值，得到可行解。
MOEA/D-CDP
原文:A study of two penalty-parameterless constraint handling techniques in the framework of MOEA/D
随機排序和CDP的擴充/修改版本是在MOEA/D架構下實作的。 實驗結果表明，CDP比随機排序更有效。
An improved epsilon constraint handling method embedded in MOEA/D for constrained multi-objective optimization problems
将改進的epsilon限制處理技術應用于MOEA/D，其中epsilon水準根據目前人群中的可行性比率動态調整。
Push and pull search for solving constrained multi-objective optimization problems
一個推拉搜尋(PPS)架構被嵌入到MOEA/D中，以解決CMOPs。 在PPS中，搜尋過程分為兩個不同的階段：1)推送階段和2)拉動階段。 在推送階段，忽略了限制，旨在跨越無限制帕累托前沿前面的不可行區域。 然後在拉階段，考慮限制，并采用改進的epsilon限制技術将在推階段得到的解拉向可行的和非主導的區域。
MOEA/D with angle-based constrained dominance principle for constrained multi-objective optimization problems
一種名為基于角度的限制優勢原理的限制處理技術被納入到MOEA/D中，用于求解CMOP。
4.DOC
DOC中包含了9個執行個體，即DOC1-DOC9，其中m代表目标函數個數，D代表決策變量的個數，NOC代表目标限制，NDC代表決策限制，NIC代表不等式限制，NEC代表等式限制，Feasibility Ratio代表得到可行解的機率.
5.TOP
TOP算法分成兩步。
第一步：利用權重的方法将CMOPs轉換為一個簡單的單目标問題，進行優化。我們需要注意的是：
- 設計一個合理的權重向量将問題轉換為單目标函數
- 限制處理方式為a.如果Xu和Xv都是可行解時，取目标函數的導數更小的 b.當一個可行一個不可行時取可行的 c.當都不可行時，取限制違反程度小的
- 本文采用了DE進行搜尋
- 停止條件：a.可行解的比例超過三分之一 b.計算所有可行個體的所有目标函數的歸一化結果之和，取其max和min，若max-min<0.2. 則停止
第二步：直接使用現有的CMOEAs對第一步優化結果進行進一步優化，注意此時優化的是個帶限制的多目标優化原問題。
6.實驗
實驗名額
- FR：可行率
- IGD:越小越好
- HV：越大越好
參數設定
- 種群大小：對于2目标問題設定成100，3目标問題設定成300。這裡參考了MOEA/D: A multiobjective evolutionary algorithm based on decomposition提供的建議
- 使用了二進制交叉和多項式變異，交叉機率設為1.0，變異機率設為1/D，D為決策變量個數
- 獨立運作數和終止條件：所有算法在每個執行個體上獨立運作20次，當兩個目标CMOP和三個目标CMOP分别達到200，000和400，000個适應度評估時終止。
- 算法參數設定：為了確定比較公平，NSGA-II-CDP、IDEA、CMOEAD和MOEA/D-CDP的其他參數設定與它們的原始論文相同，并且在ToP架構下保持不變。
本文對比了使用TOP的 NSGA-II-CDP 和IDEA 算法和沒使用TOP的，這兩個進化算法都是基于支配的方式，結果如下圖。
本文對比了使用TOP的 CMOEAD 和 MOEA/D-CDP 算法和沒使用TOP的，這兩個進化算法都是基于分解的方式，結果如下圖。
另外，文章還對比了使用DE後TOP的表現。