李 璇

个人站

Whatever is worth doing at all is worth doing well


Nondominated Sorting Genetic Algorithm II (NSGA-II)

目录

NSGA-II 简介

  Nondominated Sorting Genetic Algorithm II (NSGA-II),又名 a nondominated sorting-based multiobjective EA (MOEA),是由 NSGA 改进而来的,用于解决复杂的、多目标优化问题。该算法是 K-Deb 在 2002 年论文《A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II》中提出。

  针对 NSGA 中存在的问题:1)复杂度 \(O(MN^3)\),\(M\) 为优化目标个数,\(N\) 为种群规模;2)非精英主义;3)需要指定共享参数,该参数将对种群的多样性产生很大的影响。与此相比, NSGA-II 有几个特点:1)复杂度相对较低,为 \(O(MN^2)\) ;2)维护了精英个体,即在迭代过程中保留了最为精英的部分;3)不需要用户指定类似共享参数之列的参数,减少用户主观指定的参数,NSGA-II中从新定义了拥挤距离代替共享参数。

NSGA-II 主流程

NSGA-II 主循环流程与一般的 GA 类似,在构建后代种群是方法尤其独特性,其具体步骤为:

  • 构建新一代种群:父代 + 子代
  • 对新一代种群进行非支配排序和拥挤距离评估
  • 精选新一代种群个体:对于不同支配等级的个体,优选支配等级小的个体;对于拥有相同支配等级的,选择拥挤距离大的个体;
  • 对该种群进行交叉、变异操作,产生子代种群;

其主要流程如下:

伪代码如下所示:

快速非支配排序

  提及多目标优化,一般需要了解 Pareto Optimal,快速非支配排序就是依据此进行排序。对于 Pareto Optimal 的概念这里不做介绍,感兴趣的读者可以自行查阅。

快速非支配排序中的 2 个概念:

  • 被支配个体集合 \(S_p\) : 解空间中,可以支配个体 \(p\) 的所有个体构成的集合;
  • 支配个体数 \(n_p\) : 解空间中,被个体 \(p\) 支配的所有个体的数量;

其主要步骤如下:

  • 计算每个个体的 \(n_p\) 和 \(S_p\) 
  • \(n_p=0\) 的个体归属于 \(\mathcal{F}_1\);然后令这些个体的 \(S_p\) 所有个体的 \(n_p-1\);
  • \(n_p=0\) 的个体归属于 \(\mathcal{F}_2\);以此类推,直到所有个体处理完毕;

其伪代码如下:

上述算法的时间复杂度为\(O(M(2N)^2)\)。

多样性保留

在 NSGA 中通过共享参数保持解能相对均匀分布,也就是尽量要保持解的多样性。对于 NSGA-II 则是采用拥挤距离来维持种群多样性。

拥挤距离定义如下:拥挤距离等于解在各个目标函数的方向上的前后两个解的距离和。在二维时,就等于图像矩形轴周长的一半。

其计算的伪代码如下:

上述算法的时间复杂度为\(O(M(2N)log(2N))\)。

注意:如果某个方向上的距离很大,就会很大程度上影响总的距离的大小。为了使每个方向上的目标函数对拥挤距离有等效的影响力(无量纲化),需要每个目标函数上的距离要规则化normalized。

在进行个体选择时,需要比较个体优劣,对于处于不同支配等级的个体,支配等级越低,则越优;对于处于同一支配等级的个体,则比较拥挤距离:距离越大,表明周围解的密度越小,则分布越均匀,则越优。其比较规则如下:

NSGA-II 的代码已在 K-Deb 实验室网站公布:http://www.iitk.ac.in/kangal/codes.shtml,可以下载下来学习。