NSGA-II快速非支配排序算法理解

本文共470个字,预计阅读时间需要2分钟。

快速的非支配排序

在NSGA进行非支配排序时,规模为N的种群中的每个个体都要针对M个目标函数和种群中的N-1个个体进行比较,复杂度为O(MN),因此种群中的N个个体都比较结束的复杂度为O(MN2),即每进行一次Pareto分级的时间复杂度为O(MN2)。在最坏的情况下,每个Pareto级别都只含有一个个体,那么需要进行N次分级所需要的时间复杂度则会上升为O(MN3)。鉴于此,论文中提出了一种快速非支配排序法,该方法的时间复杂度为O(MN2)。

该算法需要保存两个量:

(1).支配个数np。该量是在可行解空间中可以支配个体p的所有个体的数量。

(2).被支配个体集合SP。该量是可行解空间中所有被个体p支配的个体组成的集合。

下面是fast_nondominated_sort的伪代码

下面是C++实现:

matlab代码:

NSGA2具体算法实现还在编写中。

4 位极客在 “NSGA-II快速非支配排序算法理解” 留下足迹

  1. 想问一下,你用matlab写的NSGA-II里面的改进演绎排序的出处在哪里呀,我想在我论文里引用一下你这里面的排序方法,不知道怎么引用,可以回复我下吗,谢谢啦。

    • Deb et al., “A Fast and Elitist Multiobjective Genetic Algorithm.” 就直接引用原文

      • 我是说那个非支配排序那段,matlab代码注释里面写的使用采用改进的deductive sort。想用改进的deductive sort不知道怎么引用。

  2. 您好,算法很好用,不过有个小问题:当存在多个相同的解时,该算法只保留了一个,再小补一下,就非常棒了。

评论