多目标进化算法详述-MOEA/D与NSGA2优劣比较

　

moea

多目标进化算法系列

1. 多目标进化算法(MOEA)概述
2. 多目标优化-测试问题及其Pareto前沿
3. 多目标进化算法详述-MOEA/D与NSGA2优劣比较
4. 多目标进化算法-约束问题的处理方法
5. 基于C#的多目标进化算法平台MOEAPlat实现

---

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

1. 提出一种快速非支配排序，使得Pareto支配排序的时间复杂度由$O\left(N^3\right)$O(N3)优化到$O\left(N^2\right)$O(N2)；
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的散点图。

很显然，对于2维DTLZ1，MOEA/D无论在均匀度上面，还是收敛性上面都优于NSGA-II。

下面再看复杂PF的情况，在此以有long tail 和 sharp peak的PF的F1为例，下面两张图就是NSGA-II和MOEA/D得到的近似解的散点图。

不难看出，对于F1来说，NSGA-II的效果是优于MOEA/D的，这主要是因为MOEA/D基于均匀分布的权重向量来指导进化的进行，但对于这类复杂PF的MOP，单位超平面上分布均匀的权重向量并不能保证解的均匀分布性。

3. 从高维看

NSGA-II 首先存在选择压力过小的问题 再就是拥挤距离的计算及其复杂

MOEA/D 在高维情况下分布性也不是很好

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

QQ交流群：399652146

相关阅读