2018-05-06 15:12:33 qithon 阅读数 6756
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    30466 人正在学习 去看看 张中强

多目标进化算法系列

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

现实世界中的多目标优化问题往往包含不等式约束和等式约束,对于这类带约束条件的多目标优化问题,需要使用有别于无约束优化问题的处理方法。下面首先给出带约束条件的多目标优化问题的的定义:
Definition : 约束多目标优化问题

F(x)=(f1(x),...,fm(x))                    s.t.xi(L)xixi(U),  i=1,2,...,n  gj(x)0,  j=1,2,...,J                      hk(x)=0,  k=1,2,...,K                     \begin{matrix} F(x)=(f_1(x),...,f_m(x))\;\;\;\;\;\;\;\;\;\;\\ s.t.\qquad\qquad\qquad\qquad\qquad\qquad \\ x_i^{(L)}\leq x_i \leq x_i^{(U)},\; i=1,2,...,n\;\\ g_j(x)\leq 0,\;j=1,2,...,J\;\;\;\;\;\;\;\;\;\;\;\\ h_k(x)=0,\;k=1,2,...,K\;\;\;\;\;\;\;\;\;\;\\ \end{matrix}

在这个定义式中,为了描述方便,将所有的不等式约束都转换为了g(x)0g(x)\leq 0的形式。其中mm为目标函数的个数,nn为决策变量的个数,JJ为不等式约束条件的个数,KK为等式约束条件的个数,xi(L)x_i^{(L)}xi(U)x_i^{(U)}分别为第ii个决策变量xix_i的下限和上限值。

针对这类带约束条件的优化问题,使用无约束多目标进化算法处理的方法显然是不可行的,为了解决这类约束多目标优化问题,针对基于Pareto支配关系的算法,主要使用带约束的支配关系(constrained-dominance)来处理,而对于基于分解的算法,则使用新的替换策略来更新解。

为了详细说明上述两种方法,现介绍几个重要的概念。

对于一个解xx,若其满足约束条件,则称该解为可行解(feasible solution),若不满足,则称之为不可行解(infeasible solution)。

对于不可行解,如何描述其违反约束的程度呢,一般使用约束违反值(constraint violation value),该值用来定量描述一个解违反约束条件的程度。对于一个解xx,其值可如下表达

CV(x)=i=1Jgj(x)+k=1Khk(x)CV(x)=\sum_{i=1}^J{\langle g_j(x) \rangle} + \sum_{k=1}^K{|h_k(x)|}

其中α\langle \alpha \rangle表示若α0\alpha\leq 0,则α=0\langle \alpha \rangle =0,否则α=α\langle \alpha \rangle = |\alpha|。显然,对于一个解,其CV值越小,说明该解越优。同时,对于一个可行解,其CV值为0,对于不可行解,其CV值则大于0。

下面介绍约束支配关系,对于任意两个解x,yx,yxx约束支配yy的条件满足以下条件的任一项即可:

  1. xx是可行解,而yy是不可行解;
  2. x,yx,y都不是可行解,但CV(x)<CV(y)CV(x)<CV(y)
  3. x,yx,y都是可行解,且xx Pareto支配 yy

以上便是约束支配关系的描述,对于一个带约束的多目标优化问题,便可直接将该支配关系应用到基于Pareto支配关系的多目标进化算法中,如NSGA-II,NSGA-III等,同时,对于无约束多目标优化问题,该支配关系显然也是有效的。

下面介绍基于分解的算法处理约束多目标优化问题中的替换策略。假设yy是新生成的子代解,选择一个邻居解xx来确定是否用解yy替换解xx,满足以下条件的任一项则替换之:

  1. xx是不可行解,yy是可行解;
  2. x,yx,y都不是可行解,但CV(x)>CV(y)CV(x)>CV(y)
  3. x,yx,y都是可行解,但解yy的聚合函数值更小

该替换策略可直接用到MOEA/D或其他基于分解思想的多目标进化算法中来处理约束多目标优化问题。

以上便是目前约束多目标优化问题处理的一些常用方法。

QQ交流群:399652146

参考:

  1. Deb K, Pratap A, Meyarivan T. Constrained Test Problems for Multi-objective Evolutionary Optimization[C]// Evolutionary Multi-Criterion Optimization, First International Conference, EMO 2001, Zurich, Switzerland, March 7-9, 2001, Proceedings. 2001:284–298.
  2. Jain H, Deb K. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4):602-622.
  3. Li K, Deb K, Zhang Q, et al. An Evolutionary Many-Objective Optimization Algorithm Based on Dominance and Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(5):694-716.
2018-10-05 12:35:25 qithon 阅读数 1277
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    30466 人正在学习 去看看 张中强

多目标进化算法系列

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

MOEAPlat简介
github地址:https://github.com/qshzhang/MOEAs

基于C#实现,展示的结果包括近似Pareto前沿,具体的Pareto前沿数据,IGD值的变化曲线等,当然这些都是高度可定制化的。

目前只提供了基于遗传算法的多目标进化算法,交叉方式已提供SBX和DE两种,变异方式为多项式突变。同时,该平台已实现MOEA/D,NSGA2,NSGA3,MOEA/DD,BiGE,IBEA,MOEA/D-M2M,MOEA/D-NBI,MOEA/D-TPN,NSGA-MPBI,RVEA,SPEA2,SPEA/R,TDEA,VaEA等算法。

对于多目标优化问题,已实现无约束的多目标优化问题,包括ZDT系列,DTLZ系列,WFG系列,MOP系列,UF系列,以及复杂前沿的多目标优化问题,如F1-F6等问题,而对于约束问题,实现了CTP1,OSY,SRN,TNK等,放在Constrained MOP目录下。

愿景
希望能共同维护,将已实现算法或自己的算法实现提交到该项目,同时,对于该平台不合理的设计以及代码也可以修改,特别是对于三维多目标优化问题,其前沿数据还不能可视化显示。

QQ交流群:399652146

2017-06-06 16:54:59 qithon 阅读数 38140
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    30466 人正在学习 去看看 张中强

多目标进化算法系列

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

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

Definition 1: 多目标优化问题(multi-objective optimization problem(MOP))
F(x)=(f1(x),...,fm(x))s.t.  xΩF(x)=(f_1(x),...,f_m(x))\\ s.t. \; x\in \Omega

Definition 2: Pareto支配(Pareto Dominance)
x支配y,记为 x \prec y ,当且仅当i{1,2,...,m}\forall {i} \in \{1,2,...,m\},fi(x)fif_i(x) \leq f_i(y), 且j{1,2,...,m}\exists {j} \in \{1,2,...,m\}, s.t.   fj(x)<fj(y)\; f_j(x)<f_j(y)

Definition 3: Pareto最优解(Pareto Optimal Solution)
如果一个解xx^* 被称之为Pareto optimal solution, 当且仅当 xx^* 不被其他的解支配。

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),该方法主要包括快速非支配排序,将每次交叉突变产生的解和前一代的解合并,然后利用非支配排序分层,其伪代码如下:


快速非支配排序算法流程
输入:父代子代个体构成的种群PP
FOR each pPp\in P
\quad Sp=S_p=\varnothing
\quad np=0n_p=0
\quad FOR each qPq\in P
\qquad IF pqp\prec q
\quad\qquad Sp=Sp{q}S_p=S_p\bigcup \{q\}
\qquad ELSEIF qpq\prec p
\quad \qquad np=np+1n_p=n_p+1
\qquad ENDIF
\quad ENDFOR
\quad IF np==0n_p==0
\qquad prank=1p_{rank}=1
\qquad F1=F1{p}F_1=F_1\bigcup \{p\}
\quad ENDIF
ENDFOR
i=1i=1
WHILE FiF_i\neq \varnothing
\quad Q=Q=\varnothing
\quad FOR each pFip\in F_i
\qquad FOR each qSpq\in S_p
\quad \qquad nq=nq1n_q=n_q-1
\quad \qquad IF nq==0nq==0
\qquad \qquad qrank=i+1q_{rank}=i+1
\qquad \qquad Q=Q{q}Q=Q\bigcup \{q\}
\quad \qquad ENDIF
\qquad ENDFOR
\quad ENDFOR
\quad i=i+1i=i+1
\quad Fi=QF_i=Q
ENDWHILE
输出:F1,F2,...,FiF_1,F_2,...,F_i


再就是把每层相加直到超过种群个体,也即满足l=argminli=1l>Nl=argmin_l{\sum_{i=1}^{l}}>N 并且有 i=1l1<N\sum_{i=1}^{l-1}<N, 再在第ll层基于拥挤距离来选择解,拥挤距离伪代码如下:


拥挤距离计算方法
输入:ii层的解Rt=FlRt=F_l
r=Rtr=|Rt|
for each jj,set Rt[j]distance=0Rt[j]_{distance}=0
FOR each objective mm
\quad Rt=sort(Rt,m)Rt=sort(Rt,m)
\quad Rt[1]distance=Rt[r]distance=Rt[1]_{distance}=Rt[r]_{distance}=\infty
\quad FOR j=2:(r1)j=2:(r-1)
\qquad Rt[j]distance=Rt[j]distance+(Rt[j+1].mRt[j1].m)/(fmmaxfmmin)Rt[j]_{distance}=Rt[j]_{distance}+(Rt[j+1].m-Rt[j-1].m)/(f_m^{max}-f_m^{min})
\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
min  gws(xλ)=i=1mλifi(x)min \; g^{ws}(x|\lambda)=\sum_{i=1}^m\lambda_if_i(x)
其中λ\lambda是参照向量,其运行机理如下图:

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

Tchebycheff Approach
min  gte(xλ,z)=max  {λi(fi(x)zi)}min\; g^{te}(x|\lambda,z^*)=max\; \{\lambda_i (f_i(x) - z_i^*)\}
其中λ\lambda是参照向量,其运行机理如下图:

标准的Tchebycheff Approach得到的解不均匀,为此Yutao Qi等人于2014年提出一种解决方法(MOEA/D with Adaptive Weight Adjustment),λ=(1λ1i=1m1λi,....,1λmi=1m1λ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}}),通过这个参照向量的转换即可得到分布均匀的解。

penalty-based boundary intersection (PBI) approach
min  gpbi(xλ,z)=d1+θd2min\; g^{pbi}(x|\lambda,z^*)=d_1+\theta d_2

其中d1d_1d2d_2如上图所示。一般来说,θ=5\theta = 5是比较常用的,Yuan Yuan等人提出的θDEA\theta -DEA算法对θ\theta的取值有较为详细的讨论(A New Dominance Relation-Based Evolutionary Algorithm for Many-Objective Optimization)。
基于分解的进化方法框架如下:


MOEA/D算法流程

NN个均匀分布的权重向量:λ1,λ2,...,λN\lambda_1,\lambda_2,...,\lambda_N // NN 是种群大小
P0P_0:随机初始化的种群
zz^*:初始化的理想点
TT:每个权重向量的邻居的个数
B(i)=(i1,i2,...,iT)B(i)=(i_1,i_2,...,i_T)是第ii个权重向量的TT个邻居的编号
t=0t = 0
WHILE t<MaxIterationt < MaxIteration
\quad FOR(i=1,2,...,Ni=1,2,...,N)
\qquad构造新解:B(i)B(i)中随机选择两个索引k,lk,l,再基于xk,xlx^k,x^l生成新解yy
\qquad更新zz^*对于j=1,2,...,mj=1,2,...,m,如果zj<f)j(y)z_j^*<f)j(y),则用fj(y)f_j(y)取代zjz_j^*
\qquad更新近邻解:对于每一个jB(i)j\in B(i),如果g(yλj,z)g(xjλj,z)g(y|\lambda_j,z^*)\leq g(x^j|\lambda_j,z^*),那么则用解yy取代xjx^j
\quad ENDFOR
\quadt=t+1t = 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

2016-09-10 11:29:02 ouyang______ 阅读数 227
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    30466 人正在学习 去看看 张中强

                                     基本概念

EA(evolutionary algorithm) 进化算法

MOEA(多目标进化算法)(multi-objective evolutionary algorithm)

MOGA(多目标遗产算法)(multi-objective genetic algorithm)

EMOO(进化多目标优化)(evolutionary multi-objective optimization)

MOEA包括:NSGA-||、NPGA、SPEA2等

决策向量空间

目标向量空间

支配关系

目标函数的适应度

选择算子:适应值计较选择、Boltzmann选择、排序选择、联赛选择

 

 

          单目标选法

选择方法:roulette wheel赌选择法、随机遍历抽样法、截断选择法、锦标赛选择法。

 

 

算法实现:

首先参数一个初始化种群P,通过二元锦标赛选择,交叉和变异产生一个子代种群Q。

 

 

Pareto最优边界:

2018-03-24 14:57:31 qithon 阅读数 8330
  • Java经典算法讲解

    在面试中,算法题目是必须的,通过算法能够看出一个程序员的编程思维,考察对复杂问题的设计与分析能力,对问题的严谨性都能够体现出来。一个算法的好坏,直接影响一个方法调用的性能,进而影响软件的整体性能。算法是学习所有编程语言的基础,在Java的学习过程中首先也会选择以算法起步,本次课程重点讲解Java开发中常用的基本算法。

    30466 人正在学习 去看看 张中强

多目标进化算法系列

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

NSGA-II由Kalyanmoy Deb等人于2002年在文章"A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II"中提出,是对1994年提出的NSGA的改进,相比于NSGA,NSGA2的改进主要两点:

  1. 提出一种快速非支配排序,使得Pareto支配排序的时间复杂度由O(N3)O(N^3)优化到O(N2)O(N^2)
  2. 提出一种拥挤距离来衡量解的分布性,并基于此选择种群中的合适的个体

NSGA-II的提出,为多目标进化算法的一大进步,特别是其基于Pareto支配关系的框架被后来许多算法采用,如NSGA-III,VaEA等。同时,NSGA-II对于低维多目标优化问题效果是不错的,但是对于高维多目标优化问题,其首先面对的便是由于其基于Pareto支配关系所导致的选择压力过小的问题,其次,便是拥挤距离在高维空间不适用,计算复杂度也比较高。

MOEA/D由张青富老师等人于2007年在文章"MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition"中提出。MOEA/D将一个多目标优化问题转换为多个标量子问题,且每一个子问题由一个均匀分布的权重向量构成,对于每生成一个新解,则基于聚合函数对该子问题附近的解进行替换。MOEA/D的优时如下:

  1. 收敛更快,计算复杂度低;
  2. 对于比较简单的PF,由于指导进化的权重向量是均匀分布的,因此MOEA/D所得到的解分布比较均匀

MOEA/D的提出为多目标进化算法提供了一种新的解决方案,基于MOEA/D的算法随后遍地开花,MOEA/DD,MOEA/D-STM,MOEA/D-SAS等。标准的MOEA/D对于低维简单PF的多目标优化问题效果是很好的,但对于复杂PF的问题,其分布性将会大打折扣,同时,对于高维多目标优化问题,其分布性也不能得到保证,效果也比较差。

下面比较两种算法的优劣:

  1. 从低维多目标优化问题(2-,3-目标)看:
    低维情况也要分两种情况考虑,一种是简单的PF的MOP,一种是复杂PF的MOP。
    首先来看简单的PF的情况。以2维的DTLZ1为例,下面两张图分别是NSGA-II和MOEA/D得到的2维DTLZ1的散点图。

NSGA-II
MOEA/D
很显然,对于2维DTLZ1,MOEA/D无论在均匀度上面,还是收敛性上面都优于NSGA-II。
下面再看复杂PF的情况,在此以有long tail 和 sharp peak的PF的F1为例,下面两张图就是NSGA-II和MOEA/D得到的近似解的散点图。

NSGA-II
MOEA/D
不难看出,对于F1来说,NSGA-II的效果是优于MOEA/D的,这主要是因为MOEA/D基于均匀分布的权重向量来指导进化的进行,但对于这类复杂PF的MOP,单位超平面上分布均匀的权重向量并不能保证解的均匀分布性。
3. 从高维看
NSGA-II 首先存在选择压力过小的问题 再就是拥挤距离的计算及其复杂
MOEA/D 在高维情况下分布性也不是很好

但总的来看,不管低维还是高维,MOEA/D比NSGA-II的速度快很多。

QQ交流群:399652146

没有更多推荐了,返回首页