• 即将更新图形学,编译原理,机器学习等文章,谢谢关注~
  • 由于算法限制,搜索时注意简化关键字,谢谢支持~
  • 网站不兼容IE5.0及以下,请使用主流浏览器访问.
  • NSGA-II快速非支配排序算法理解

    快速的非支配排序

    在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具体算法实现还在编写中。

    读者评分
    [评分人数: 0 平均分: 0]

    评论

    OmegaXYZ