NSGA2 算法中文版详细介绍
NSGA2 主要是对 NSGA 算法的改进。NSGA 是 N. Srinivas 和 K. Deb 在 1995 年发表的一篇
名为《Multiobjective function optimization using nondominated sorting genetic algorithms》
的论文中提出的。
该算法在快速找到 Pareto 前沿和保持种群多样性方面都有很好的效果,不过在这么多年的
应用中也出现了如下的一些问题:
1。非支配排序的时间复杂的很大,为 O(MN3)。其中 M 为目标函数的数量,N 为种群规
模。
2。不支持精英策略。精英策略在保持好的个体及加速向 Pareto 前沿收敛方面都有很好的表
现。
3。需要自己指定共享参数。该参数将对种群的多样性产生很大的影响。
NSGA2 算法将在以下方面进行改进:
1。快速的非支配排序
在 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 支配的个体组成的集合。
排序算法的伪代码如下:
def fast_nondominated_sort( P ):
F = [ ]
for p in P:
Sp = [ ]
np = 0
for q in P:
if p > q: #如果 p 支配 q,把 q 添加到 Sp 列表中
Sp.append( q )
else if p < q: #如果 p 被 q 支配,则把 np 加 1
np += 1
if np == 0:
p_rank = 1 #如果该个体的 np 为 0,则该个体为 Pareto 第一级
F1.append( p )
F.append( F1 )
i = 0
while F[i]:
Q = [ ]
for p in F[i]:
for q in Sp: #对所有在 Sp 集合中的个体进行排序
nq -= 1
评论3