多目标进化算法详述-MOEA/D与NSGA2优劣比较
多目标进化算法系列
- 多目标进化算法(MOEA)概述
- 多目标优化-测试问题及其Pareto前沿
- 多目标进化算法详述-MOEA/D与NSGA2优劣比较
- 多目标进化算法-约束问题的处理方法
- 基于C#的多目标进化算法平台MOEAPlat实现
NSGA-II由Kalyanmoy Deb等人于2002年在文章"A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II"中提出,是对1994年提出的NSGA的改进,相比于NSGA,NSGA2的改进主要两点:
- 提出一种快速非支配排序,使得Pareto支配排序的时间复杂度由优化到;
- 提出一种拥挤距离来衡量解的分布性,并基于此选择种群中的合适的个体
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的散点图。
很显然,对于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