多目標進化算法(MOEA)概述

多目標進化算法系列

多目標進化算法(MOEA)概述

多目標優化-測試問題及其Pareto前沿

多目標進化算法詳述-MOEA/D與NSGA2優劣比較

多目標進化算法-約束問題的處理方法

基于C#的多目標進化算法平臺MOEAPlat實現

MOEAD中聚合函數等高線分析

MOEAD中一種使解更均勻分布的聚合函數介紹

---

對于大多數多目標優化問題，其各個目標往往是相互沖突的，因此不可能使得所有的目標同時達到最優，而是一組各個目標值所折衷的解集，稱之為Pareto最優集。以下為一些基本定義(以最小化優化問題為例)：

Definition 1: 多目標優化問題(multi-objective optimization problem(MOP))
F ( x ) = ( f 1 ( x ) , . . . , f m ( x ) ) s . t . x ∈ Ω F(x)=(f_1(x),...,f_m(x))\\ s.t. \; x\in \Omega F(x)=(f1?(x),...,fm?(x))s.t.x∈Ω

Definition 2: Pareto支配(Pareto Dominance)
x支配y,記為 x ? \prec ? y ，當且僅當 ? i ∈ { 1 , 2 , . . . , m } \forall {i} \in \{1,2,...,m\} ?i∈{1,2,...,m}, f i ( x ) ≤ f i f_i(x) \leq f_i fi?(x)≤fi?(y), 且 ? j ∈ { 1 , 2 , . . . , m } \exists {j} \in \{1,2,...,m\} ?j∈{1,2,...,m}, s.t. f j ( x ) < f j ( y ) \; f_j(x)<f_j(y) fj?(x)<fj?(y) 。

Definition 3: Pareto最優解(Pareto Optimal Solution)
如果一個解 x ? x^* x? 被稱之為Pareto optimal solution， 當且僅當 x ? x^* x? 不被其他的解支配。

Definition 4: Pareto 集(Pareto Set)
一個MOP，對于一組給定的最優解集，如果這個集合中的解是相互非支配的，也即兩兩不是支配關系，那么則稱這個解集為Pareto Set 。

Definition 5: Pareto 前沿(Pareto Front)
Pareto Set 中每個解對應的目標值向量組成的集合稱之為Pareto Front, 簡稱為PF

Definition 6：近似集(Approximation Set)
一般來說，準確的Pareto Set是很難得到的，其近似集相比來說容易得到，因此一般我們只需用一定數量的Approximation Set 來表示PS 。

Definition 7： 近似前沿(Approximation Front)
Approximation Set 中每個解對應的目標值向量組成的集合稱之為Approximation Front 。

目前來說，由于多目標問題的復雜性，傳統的數學方法不能取得較為理想的結果，而進化算法在多目標優化問題上得到了很廣泛的應用，通過種群的不斷進化迭代，進化算法能得到一個Approximation Set，那么我們如何來評價得到的Approximation Set的優劣呢，以下為兩方面的評價標準。
Definition 7：收斂性(Convergence)
Approximation Front 與 PF 的貼近程度。

Definition 8: 分布性(Distribution)
描述Approximation Front 在PF 的分布情況，包括多樣性(Diversity)和均勻性(Uniformity)。

具體來說，常用的兩個指標分別是IGD(Inverted Generational Distance) 和 HV(Hypervolume)。其中，IGD需要知道PF數據，且其具體計算為每個PF中的點到其最近的Approximation Front中的點的距離之和的均值。同時，需注意，這兩種方法都能同時度量解的分布性和收斂性。

現在來講講主流的多目標進化算法。
從進化算法的角度來講，目前已有遺傳算法(GA)，粒子群算法(PSO)，蟻群算法(ACO)等一系列算法用來解決多目標優化問題，但用的比較多的還是遺傳算法，粒子群算法也有。
從多目標問題本身來說，主要分類如下：

• 基于Pareto支配關系
• 基于分解的方法
• 基于Indicator方法

先來介紹下基于遺傳算法的多目標優化算法的一些基本參數：
種群大小：每次迭代都需保證種群大小是一致的，且其大小應由初始化設定。
交叉概率：用于衡量兩個個體交叉的概率。
突變率：交叉產生的解發生突變的概率。
標準的遺傳算法每次迭代都會將上一代的個體丟棄，雖然這符合自然規律，但對于遺傳算法來說，這樣效果不是特別好，因此，精英保留策略將上一代個體和當前個體混合競爭產生下一代，這種機制能較好的保留精英個體。
基于Pareto支配關系
最經典的方法是NSGA-II，該方法由Kalyanmoy Deb等人于2002年提出(A Fast and Elitist Multiobjective Genetic Algorithm:
NSGA-II)，該方法主要包括快速非支配排序，將每次交叉突變產生的解和前一代的解合并，然后利用非支配排序分層，其偽代碼如下：

---

快速非支配排序算法流程
輸入：父代子代個體構成的種群 P P P
FOR each p ∈ P p\in P p∈P
\quad S p = ? S_p=\varnothing Sp?=?
\quad n p = 0 n_p=0 np?=0
\quad FOR each q ∈ P q\in P q∈P
\qquad IF p ? q p\prec q p?q
\quad \qquad S p = S p ? { q } S_p=S_p\bigcup \{q\} Sp?=Sp??{q}
\qquad ELSEIF q ? p q\prec p q?p
\quad \qquad n p = n p + 1 n_p=n_p+1 np?=np?+1
\qquad ENDIF
\quad ENDFOR
\quad IF n p = = 0 n_p==0 np?==0
\qquad p r a n k = 1 p_{rank}=1 prank?=1
\qquad F 1 = F 1 ? { p } F_1=F_1\bigcup \{p\} F1?=F1??{p}
\quad ENDIF
ENDFOR
i = 1 i=1 i=1
WHILE F i ≠ ? F_i\neq \varnothing Fi??=?
\quad Q = ? Q=\varnothing Q=?
\quad FOR each p ∈ F i p\in F_i p∈Fi?
\qquad FOR each q ∈ S p q\in S_p q∈Sp?
\quad \qquad n q = n q ? 1 n_q=n_q-1 nq?=nq??1
\quad \qquad IF n q = = 0 nq==0 nq==0
\qquad \qquad q r a n k = i + 1 q_{rank}=i+1 qrank?=i+1
\qquad \qquad Q = Q ? { q } Q=Q\bigcup \{q\} Q=Q?{q}
\quad \qquad ENDIF
\qquad ENDFOR
\quad ENDFOR
\quad i = i + 1 i=i+1 i=i+1
\quad F i = Q F_i=Q Fi?=Q
ENDWHILE
輸出： F 1 , F 2 , . . . , F i F_1,F_2,...,F_i F1?,F2?,...,Fi?

---

再就是把每層相加直到超過種群個體，也即滿足 l = a r g m i n l ∑ i = 1 l > N l=argmin_l{\sum_{i=1}^{l}}>N l=argminl?∑i=1l?>N 并且有 ∑ i = 1 l ? 1 < N \sum_{i=1}^{l-1}<N ∑i=1l?1?<N， 再在第 l l l層基于擁擠距離來選擇解，擁擠距離偽代碼如下：

---

擁擠距離計算方法
輸入：第 i i i層的解 R t = F l Rt=F_l Rt=Fl?
r = ∣ R t ∣ r=|Rt| r=∣Rt∣
for each j j j,set R t [ j ] d i s t a n c e = 0 Rt[j]_{distance}=0 Rt[j]distance?=0
FOR each objective m m m
\quad R t = s o r t ( R t , m ) Rt=sort(Rt,m) Rt=sort(Rt,m)
\quad R t [ 1 ] d i s t a n c e = R t [ r ] d i s t a n c e = ∞ Rt[1]_{distance}=Rt[r]_{distance}=\infty Rt[1]distance?=Rt[r]distance?=∞
\quad FOR j = 2 : ( r ? 1 ) j=2:(r-1) j=2:(r?1)
\qquad R t [ j ] d i s t a n c e = R t [ j ] d i s t a n c e + ( R t [ j + 1 ] . m ? R t [ j ? 1 ] . m ) / ( f m m a x ? f m m i n ) Rt[j]_{distance}=Rt[j]_{distance}+(Rt[j+1].m-Rt[j-1].m)/(f_m^{max}-f_m^{min}) Rt[j]distance?=Rt[j]distance?+(Rt[j+1].m?Rt[j?1].m)/(fmmax??fmmin?)
\quad ENDFOR
ENDFOR

---

具體來說，NSGA-II使用快速非支配排序來保證收斂性，并且利用擁擠距離來保證分布性。特別說下，在迭代后期，大多數解都是非支配的，也即大多數解都在第一層。
當然，隨著NSGA-II的提出，很多基于此的算法如雨后春筍般大量涌現，特別是在處理高維多目標優化問題時這種想法得到很多的應用，如VaEA，RVEA，NSGA-III等。
同時，SPEA2也是基于Pareto支配關系的一種較為流行的算法(SPEA2: Improving the Strength Pareto Evolutionary Algorithm)，該算法使用一個外部保存集來保存較為優秀的解，同時，對每一個解，利用其支配的解的數量和基于KNN的鄰近解的距離來給每一個解打分，得分越小的解更優。

基于分解的方法
該方法第一次系統地被提出是在2007年由Qingfu Zhang等人提出(MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition)，該方法將MOP分解為多個子問題，這樣就可以優化每個子問題來求解一個MOP。一般而言，基于分解的方法首先需要得到一組均勻分布的參照向量來指導選擇操作。在此，有必要說說產生參照向量的方法。目前對于低維多目標優化問題，常用方法為Das and Dennis于1998年提出的systematic approach(Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems).
對于每個參照向量，其指導選擇的過程需要比較解的優劣，這就需要用到一些標量函數來定量衡量一個解對于這個參照向量的適應度值。常用的標量函數包括：

• Weighted Sum Approach
• Tchebycheff Approach
• penalty-based boundary intersection (PBI) approach

Weighted Sum Approach
m i n g w s ( x ∣ λ ) = ∑ i = 1 m λ i f i ( x ) min \; g^{ws}(x|\lambda)=\sum_{i=1}^m\lambda_if_i(x) mingws(x∣λ)=∑i=1m?λi?fi?(x)
其中 λ \lambda λ是參照向量，其運行機理如下圖：

這里需要注意，標準的Weighted Sum Approach不能處理非凸問題，因為由上圖可知，對于非凸問題，每個參照向量的垂線與其前沿不可能相切。對于這個問題，Rui Wang等人與2016年提出相對應的改進(Localized weighted sum method for many-objective optimization)，主要是約束替換范圍。

Tchebycheff Approach
m i n g t e ( x ∣ λ , z ? ) = m a x { λ i ( f i ( x ) ? z i ? ) } min\; g^{te}(x|\lambda,z^*)=max\; \{\lambda_i (f_i(x) - z_i^*)\} mingte(x∣λ,z?)=max{λi?(fi?(x)?zi??)}
其中 λ \lambda λ是參照向量，其運行機理如下圖：

標準的Tchebycheff Approach得到的解不均勻，為此Yutao Qi等人于2014年提出一種解決方法(MOEA/D with Adaptive Weight Adjustment)， λ ? = ( 1 λ 1 ∑ i = 1 m 1 λ i , . . . . , 1 λ m ∑ i = 1 m 1 λ i ) \lambda^* =(\frac{\frac{1}{\lambda_1}}{\sum_{i=1}^m\frac{1}{\lambda_i}},....,\frac{\frac{1}{\lambda_m}}{\sum_{i=1}^m\frac{1}{\lambda_i}}) λ?=(∑i=1m?λi?1?λ1?1??,....,∑i=1m?λi?1?λm?1??),通過這個參照向量的轉換即可得到分布均勻的解。

penalty-based boundary intersection (PBI) approach
m i n g p b i ( x ∣ λ , z ? ) = d 1 + θ d 2 min\; g^{pbi}(x|\lambda,z^*)=d_1+\theta d_2 mingpbi(x∣λ,z?)=d1?+θd2?

其中 d 1 d_1 d1?， d 2 d_2 d2?如上圖所示。一般來說， θ = 5 \theta = 5 θ=5是比較常用的，Yuan Yuan等人提出的 θ ? D E A \theta -DEA θ?DEA算法對 θ \theta θ的取值有較為詳細的討論(A New Dominance Relation-Based Evolutionary Algorithm for Many-Objective Optimization)。
基于分解的進化方法框架如下：

---

MOEA/D算法流程

N N N個均勻分布的權重向量： λ 1 , λ 2 , . . . , λ N \lambda_1,\lambda_2,...,\lambda_N λ1?,λ2?,...,λN? // N N N 是種群大小
P 0 P_0 P0?：隨機初始化的種群
z ? z^* z?：初始化的理想點
T T T：每個權重向量的鄰居的個數
B ( i ) = ( i 1 , i 2 , . . . , i T ) B(i)=(i_1,i_2,...,i_T) B(i)=(i1?,i2?,...,iT?)是第 i i i個權重向量的 T T T個鄰居的編號
t = 0 t = 0 t=0
WHILE t < M a x I t e r a t i o n t < MaxIteration t<MaxIteration
\quad FOR( i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N)
\qquad 構造新解：從 B ( i ) B(i) B(i)中隨機選擇兩個索引 k , l k,l k,l，再基于 x k , x l x^k,x^l xk,xl生成新解 y y y
\qquad 更新 z ? z^* z?：對于 j = 1 , 2 , . . . , m j=1,2,...,m j=1,2,...,m,如果 z j ? < f ) j ( y ) z_j^*<f)j(y) zj??<f)j(y)，則用 f j ( y ) f_j(y) fj?(y)取代 z j ? z_j^* zj??
\qquad 更新近鄰解：對于每一個 j ∈ B ( i ) j\in B(i) j∈B(i)，如果 g ( y ∣ λ j , z ? ) ≤ g ( x j ∣ λ j , z ? ) g(y|\lambda_j,z^*)\leq g(x^j|\lambda_j,z^*) g(y∣λj?,z?)≤g(xj∣λj?,z?)，那么則用解 y y y取代 x j x^j xj
\quad ENDFOR
\quad t = t + 1 t = t + 1 t=t+1
ENDWHILE
輸出結果

---

基于Indicator方法
相比于IGD指標，Hypervolume更容易用來作為一個測度在種群進化過程中用來選擇個體,如IBEA[8]以及其快速計算HV的HypE[9]，因為IGD需要知道真實的Pareto Front數據，而這對于一個未知多目標優化問題是相當困難的，但有些算法是用當前的非支配解來近似Pareto Front，如AR-MOEA[10]。

至于具體的多目標進化算法后續將會詳細介紹。

ps：文獻[12]是我的碩士論文，里面有較為詳細的綜述類的描述，對多個經典算法以及一些遺傳操作都有介紹，還有衡量指標也是。

QQ交流群：399652146

參考文獻
[1] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, Apr. 2002
[2] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” in Proc. Evol. Methods Design Optim. Control Appl. Ind. Prob., Athens, Greece, 2002, pp. 95–100.
[3] Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation, 11(6):712–731, 2007.
[4] Yutao Qi, Xiaoliang Ma, Fang Liu, Licheng Jiao, Jianyong Sun, and Jianshe Wu. MOEA/D with adaptive weight adjustment. Evolutionary computation, 22(2):231–264, 2014.
[5] Kalyanmoy Deb and Himanshu Jain. An evolutionary many objective optimization algorithm using reference- point-based nondominated sorting approach, part i: Solving problems with box constraints. IEEE Trans. Evolutionary Computation, 18(4):577–601, 2014.
[6] Yuan Yuan, Hua Xu, Bo Wang, and Xin Yao. A new dominance relation-based evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation, 20(1):16–37, 2016.
[7] Indraneel Das and John E Dennis. Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 8(3):631–657, 1998
[8] E. Zitzler and S. Kunzli, "Indicator-based selection in multiob- jective search,"in Proceedings of the 8th International Conference on Parallel Problem Solving from Nature, 2004, pp. 832–842.
[9] J. Bader and E. Zitzler, “HypE: An algorithm for fast hypervolume-based many-objective optimization,” Evolutionary Computation, vol. 19, no. 1, pp. 45–76, 2011.
[10] Tian Y, Cheng R, Zhang X, et al. An Indicator Based Multi-Objective Evolutionary Algorithm with Reference Point Adaptation for Better Versatility[J]. IEEE Transactions on Evolutionary Computation, 2017, PP(99):1-1.
[11] 張作峰. 基于分解的多目標進化算法研究[D]. 湘潭大學, 2013.
[12] 基于分解思想的多目標進化算法研究. 湖南大學, 2018