多目标进化算法(MOEA)概述

多目标进化算法系列

多目标进化算法(MOEA)概述多目标优化-测试问题及其Pareto前沿多目标进化算法详述-MOEA/D与NSGA2优劣比较多目标进化算法-约束问题的处理方法基于C#的多目标进化算法平SEO靠我台MOEAPlat实现MOEAD中聚合函数等高线分析MOEAD中一种使解更均匀分布的聚合函数介绍

对于大多数多目标优化问题，其各个目标往往是相互冲突的，因此不可能使得所有的目标同时达到最优，而是一组各个SEO靠我目标值所折衷的解集，称之为Pareto最优集。以下为一些基本定义(以最小化优化问题为例)：

Definition 1: 多目标优化问题(multi-objective optimization probSEO靠我lem(MOP))F ( x ) = ( f 1 ( x ) , . . . , f m ( x ) ) s . t . x ∈ Ω F(x)=(f_1(x),...,f_m(x))\\ s.t. \SEO靠我; x\in \Omega F(x)=(f1​(x),...,fm​(x))s.t.x∈Ω

Definition 2: Pareto支配(Pareto Dominance) x支配y,记为 x≺ \precSEO靠我 ≺y，当且仅当 ∀ i ∈ { 1 , 2 , . . . , m } \forall {i} \in \{1,2,...,m\} ∀i∈{1,2,...,m}, f i ( x ) ≤ f i fSEO靠我_i(x) \leq f_i fi​(x)≤fi​(y), 且 ∃ j ∈ { 1 , 2 , . . . , m } \exists {j} \in \{1,2,...,m\} ∃j∈{1,2,..SEO靠我.,m}, s.t. f j ( x ) < f j ( y ) \; f_j(x)<f_j(y) fj​(x)<fj​(y) 。

Definition 3: Pareto最优解(Pareto OptiSEO靠我mal Solution) 如果一个解 x ∗ x^* x∗ 被称之为Pareto optimal solution， 当且仅当 x ∗ x^* x∗ 不被其他的解支配。

Definition 4: PaSEO靠我reto 集(Pareto Set) 一个MOP，对于一组给定的最优解集，如果这个集合中的解是相互非支配的，也即两两不是支配关系，那么则称这个解集为Pareto Set 。

Definition 5: PSEO靠我areto 前沿(Pareto Front) Pareto Set 中每个解对应的目标值向量组成的集合称之为Pareto Front, 简称为PF

Definition 6：近似集(ApproximatiSEO靠我on Set) 一般来说，准确的Pareto Set是很难得到的，其近似集相比来说容易得到，因此一般我们只需用一定数量的Approximation Set 来表示PS 。

Definition 7： 近似SEO靠我前沿(Approximation Front) Approximation Set 中每个解对应的目标值向量组成的集合称之为Approximation Front 。

目前来说，由于多目标问题的复杂性，传SEO靠我统的数学方法不能取得较为理想的结果，而进化算法在多目标优化问题上得到了很广泛的应用，通过种群的不断进化迭代，进化算法能得到一个Approximation Set，那么我们如何来评价得到的ApproxiSEO靠我mation Set的优劣呢，以下为两方面的评价标准。

Definition 7：收敛性(Convergence) Approximation Front 与 PF 的贴近程度。

Definition 8:SEO靠我 分布性(Distribution) 描述Approximation Front 在PF 的分布情况，包括多样性(Diversity)和均匀性(Uniformity)。

具体来说，常用的两个指标分别是IGSEO靠我D(Inverted Generational Distance) 和 HV(Hypervolume)。其中，IGD需要知道PF数据，且其具体计算为每个PF中的点到其最近的Approximation SEO靠我Front中的点的距离之和的均值。同时，需注意，这两种方法都能同时度量解的分布性和收敛性。

现在来讲讲主流的多目标进化算法。

从进化算法的角度来讲，目前已有遗传算法(GA)，粒子群算法(PSO)，蚁群算法SEO靠我(ACO)等一系列算法用来解决多目标优化问题，但用的比较多的还是遗传算法，粒子群算法也有。

从多目标问题本身来说，主要分类如下： 基于Pareto支配关系基于分解的方法基于Indicator方法

先来介绍下SEO靠我基于遗传算法的多目标优化算法的一些基本参数：

种群大小：每次迭代都需保证种群大小是一致的，且其大小应由初始化设定。

交叉概率：用于衡量两个个体交叉的概率。

突变率：交叉产生的解发生突变的概率。

标准的遗传算法SEO靠我每次迭代都会将上一代的个体丢弃，虽然这符合自然规律，但对于遗传算法来说，这样效果不是特别好，因此，精英保留策略将上一代个体和当前个体混合竞争产生下一代，这种机制能较好的保留精英个体。

基于Pareto支SEO靠我配关系

最经典的方法是NSGA-II，该方法由Kalyanmoy Deb等人于2002年提出(A Fast and Elitist Multiobjective Genetic Algorithm:

NSSEO靠我GA-II)，该方法主要包括快速非支配排序，将每次交叉突变产生的解和前一代的解合并，然后利用非支配排序分层，其伪代码如下：

快速非支配排序算法流程 输入：

父代子代个体构成的种群 P P P

FOR eachSEO靠我 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\SEO靠我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}

\SEO靠我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 ENDFOSEO靠我R

\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_SEO靠我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​​=SEO靠我∅

\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 SEO靠我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 \qquaSEO靠我d 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}

\quadSEO靠我 \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

输出SEO靠我： F 1 , F 2 , . . . , F i F_1,F_2,...,F_i F1​,F2​,...,Fi​

再就是把每层相加直到超过种群个体，也即满足 l = a r g m i n l ∑ i SEO靠我= 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 ∑SEO靠我i=1l−1​<N， 再在第 l l l层基于拥挤距离来选择解，拥挤距离伪代码如下：

拥挤距离计算方法 输入：

第 i i i层的解 R t = F l Rt=F_l Rt=Fl​

r = ∣ R t ∣ rSEO靠我=|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 SEO靠我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 sSEO靠我 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​=RSEO靠我t[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 tSEO靠我 [ 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]SEO靠我_{distance}=Rt[j]_{distance}+(Rt[j+1].m-Rt[j-1].m)/(f_m^{max}-f_m^{min}) Rt[j]distance​=Rt[j]distancSEO靠我e​+(Rt[j+1].m−Rt[j−1].m)/(fmmax​−fmmin​)

\quad ENDFOR

ENDFOR

具体来说，NSGA-II使用快速非支配排序来保证收敛性，并且利用拥挤距离来保证分布性SEO靠我。特别说下，在迭代后期，大多数解都是非支配的，也即大多数解都在第一层。

当然，随着NSGA-II的提出，很多基于此的算法如雨后春笋般大量涌现，特别是在处理高维多目标优化问题时这种想法得到很多的应用，如VSEO靠我aEA，RVEA，NSGA-III等。

同时，SPEA2也是基于Pareto支配关系的一种较为流行的算法(SPEA2: Improving the Strength Pareto EvolutionarSEO靠我y Algorithm)，该算法使用一个外部保存集来保存较为优秀的解，同时，对每一个解，利用其支配的解的数量和基于KNN的邻近解的距离来给每一个解打分，得分越小的解更优。

基于分解的方法

该方法第一次系统SEO靠我地被提出是在2007年由Qingfu Zhang等人提出(MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition)SEO靠我，该方法将MOP分解为多个子问题，这样就可以优化每个子问题来求解一个MOP。一般而言，基于分解的方法首先需要得到一组均匀分布的参照向量来指导选择操作。在此，有必要说说产生参照向量的方法。目前对于低维多SEO靠我目标优化问题，常用方法为Das and Dennis于1998年提出的systematic approach(Normal-boundary intersection: A new method foSEO靠我r generating the pareto surface in nonlinear multicriteria optimization problems).

对于每个参照向量，其指导选择的过程需SEO靠我要比较解的优劣，这就需要用到一些标量函数来定量衡量一个解对于这个参照向量的适应度值。常用的标量函数包括：Weighted Sum ApproachTchebycheff ApproachpenaltySEO靠我-based boundary intersection (PBI) approach

Weighted Sum Approach

m i n g w s ( x ∣ λ ) = ∑ i = 1 m λ SEO靠我i f i ( x ) min \; g^{ws}(x|\lambda)=\sum_{i=1}^m\lambda_if_i(x) mingws(x∣λ)=∑i=1m​λi​fi​(x)

其中 λ \laSEO靠我mbda λ是参照向量，其运行机理如下图：

这里需要注意，标准的Weighted Sum Approach不能处理非凸问题，因为由上图可知，对于非凸问题，每个参照向量的垂线与其前沿不可能相切。对于这个问SEO靠我题，Rui Wang等人与2016年提出相对应的改进(Localized weighted sum method for many-objective optimization)，主要是约束替换范围。SEO靠我

Tchebycheff Approach

m i n g t e ( x ∣ λ , z ∗ ) = m a x { λ i ( f i ( x ) − z i ∗ ) } min\; g^{te}(xSEO靠我|\lambda,z^*)=max\; \{\lambda_i (f_i(x) - z_i^*)\} mingte(x∣λ,z∗)=max{λi​(fi​(x)−zi∗​)}

其中 λ \lambda SEO靠我λ是参照向量，其运行机理如下图：

标准的Tchebycheff Approach得到的解不均匀，为此Yutao Qi等人于2014年提出一种解决方法(MOEA/D with Adaptive WeighSEO靠我t Adjustment)， λ ∗ = ( 1 λ 1 ∑ i = 1 m 1 λ i , . . . . , 1 λ m ∑ i = 1 m 1 λ i ) \lambda^* =(\frac{\SEO靠我frac{1}{\lambda_1}}{\sum_{i=1}^m\frac{1}{\lambda_i}},....,\frac{\frac{1}{\lambda_m}}{\sum_{i=1}^m\frSEO靠我ac{1}{\lambda_i}}) λ∗=(∑i=1m​λi​1​λ1​1​​,....,∑i=1m​λi​1​λm​1​​),通过这个参照向量的转换即可得到分布均匀的解。

penalty-basedSEO靠我 boundary intersection (PBI) approachm i n g p b i ( x ∣ λ , z ∗ ) = d 1 + θ d 2 min\; g^{pbi}(x|\laSEO靠我mbda,z^*)=d_1+\theta d_2 mingpbi(x∣λ,z∗)=d1​+θd2​

其中 d 1 d_1 d1​， d 2 d_2 d2​如上图所示。一般来说， θ = 5 \thetaSEO靠我 = 5 θ=5是比较常用的，Yuan Yuan等人提出的 θ − D E A \theta -DEA θ−DEA算法对 θ \theta θ的取值有较为详细的讨论(A New Dominance RSEO靠我elation-Based Evolutionary Algorithm for Many-Objective Optimization)。

基于分解的进化方法框架如下：

MOEA/D算法流程

N N N个SEO靠我均匀分布的权重向量： λ 1 , λ 2 , . . . , λ N \lambda_1,\lambda_2,...,\lambda_N λ1​,λ2​,...,λN​ // N N N 是种群大小

PSEO靠我 0 P_0 P0​：随机初始化的种群

z ∗ z^* z∗：初始化的理想点

T T T：每个权重向量的邻居的个数

B ( i ) = ( i 1 , i 2 , . . . , i T ) B(i)=(iSEO靠我_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 eSEO靠我 r a t i o n t < MaxIteration t

\quad FOR( i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N)

\qquad 构造新解：

从SEO靠我 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∗：

对SEO靠我于 j = 1 , 2 , . . . , m j=1,2,...,m j=1,2,...,m,如果 z j ∗ < f ) j ( y ) z_j^*

\qquad 更新近邻解：

对于每一个 j ∈ B SEO靠我( 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|\SEO靠我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 + 1SEO靠我 t=t+1

ENDWHILE

输出结果

基于Indicator方法相比于IGD指标，Hypervolume更容易用来作为一个测度在种群进化过程中用来选择个体,如IBEA[8]以及其快速计算HV的HypE[SEO靠我9]，因为IGD需要知道真实的Pareto Front数据，而这对于一个未知多目标优化问题是相当困难的，但有些算法是用当前的非支配解来近似Pareto Front，如AR-MOEA[10]。

至于具体的SEO靠我多目标进化算法后续将会详细介绍。

ps：文献[12]是我的硕士论文，里面有较为详细的综述类的描述，对多个经典算法以及一些遗传操作都有介绍，还有衡量指标也是。

QQ交流群：399652146

参考文献

[1] SEO靠我K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithSEO靠我m: NSGA-II,” IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, Apr. 2002

[2] E. Zitzler, M. LaumSEO靠我anns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” in Proc. Evol. MSEO靠我ethods Design Optim. Control Appl. Ind. Prob., Athens, Greece, 2002, pp. 95–100.

[3] Qingfu Zhang andSEO靠我 Hui Li. Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions oSEO靠我n evolutionary computation, 11(6):712–731, 2007.

[4] Yutao Qi, Xiaoliang Ma, Fang Liu, Licheng Jiao, SEO靠我Jianyong Sun, and Jianshe Wu. MOEA/D with adaptive weight adjustment. Evolutionary computation, 22(2SEO靠我):231–264, 2014.

[5] Kalyanmoy Deb and Himanshu Jain. An evolutionary many objective optimization algSEO靠我orithm using reference- point-based nondominated sorting approach, part i: Solving problems with boxSEO靠我 constraints. IEEE Trans. Evolutionary Computation, 18(4):577–601, 2014.

[6] Yuan Yuan, Hua Xu, Bo WaSEO靠我ng, and Xin Yao. A new dominance relation-based evolutionary algorithm for many-objective optimizatiSEO靠我on. IEEE Transactions on Evolutionary Computation, 20(1):16–37, 2016.

[7] Indraneel Das and John E DeSEO靠我nnis. Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multSEO靠我icriteria optimization problems. SIAM Journal on Optimization, 8(3):631–657, 1998

[8] E. Zitzler and SEO靠我S. Kunzli, "Indicator-based selection in multiob- jective search,"in Proceedings of the 8th InternatSEO靠我ional Conference on Parallel Problem Solving from Nature, 2004, pp. 832–842.

[9] J. Bader and E. ZitzSEO靠我ler, “HypE: An algorithm for fast hypervolume-based many-objective optimization,” Evolutionary CompuSEO靠我tation, vol. 19, no. 1, pp. 45–76, 2011.

[10] Tian Y, Cheng R, Zhang X, et al. An Indicator Based MulSEO靠我ti-Objective Evolutionary Algorithm with Reference Point Adaptation for Better Versatility[J]. IEEE SEO靠我Transactions on Evolutionary Computation, 2017, PP(99):1-1.

[11] 张作峰. 基于分解的多目标进化算法研究[D]. 湘潭大学, 2013.

[SEO靠我12] 基于分解思想的多目标进化算法研究. 湖南大学, 2018