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

全栈程序员-站长 • 2022年5月19日上午8:20 • 未分类 • 阅读 163

大家好，又见面了，我是你们的朋友全栈君。

多目标进化算法系列

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

提出一种快速非支配排序，使得Pareto支配排序的时间复杂度由 $O(N^3)$ 优化到 $O(N^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的优时如下：

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

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

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

从低维多目标优化问题(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 在高维情况下分布性也不是很好