NSGAII（带精英策略的非支配排序的遗传算法）.pdf

NSGA II （带精英策略的⾮⽀配排序的遗传算法） NSGA⼀II的基本算法流程 ： （1）⾸先,随机产⽣ 模为N的初始种群,⾮⽀配排序后通过遗传算法的选择、交叉、变异三个基本操作得到第⼀代⼦代种群; （2）其次,从第⼆代开始,将⽗代种群与⼦代种群合并,进⾏快速⾮⽀配排序,同时对每个⾮⽀配层中的个体进⾏拥挤度计算,根据⾮⽀配关系以 及个体的拥挤度选取合适的个体组成新的⽗代种群; （3）最后,通过遗传算法的基本操作产⽣新的⼦代种群:依此类推,直到满⾜程序结束的条件。 1. 快速的⾮⽀配排序 该算法需要保存两个量 ： (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 ) e se 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 whi e F[i] : Q = [ ] for p in F[i] : for q in Sp: #对所有在Sp集合中的个体进⾏排序 nq -= 1 if nq == 0: #如果该个体的⽀配个数为0，则该个体是⾮⽀配个体 q_ rank = i+2 #该个体Pareto级别为当前最⾼级别加 1。此时i初始值为0，所以要加2 Q.append( q ) F.append( Q ) i += 1 2.排挤算法和精英策略 原始的NSGA算法中使⽤共享函数的⽅法来维持物种的多样性，这种⽅法包含⼀个**共享参数，该参数为所求解问题中所期望的共享范围。 在该范围内，两个个体共享彼此的适应度。**但是该⽅法有两个难点 ： (1).共享函数⽅法在保持多样性的性能很⼤程度上依赖于所选择的共享参数值。 (2).种群中的每个个体都要与其余的个体相⽐较，因此该⽅法的全局复杂度为O(N2)。 在NSGA2中使⽤了排挤算法和精英策略来代替共享函数算法。⽽要实现这两种⽅法，⾸先我们需要定义两个操作 ：密度估算和排挤算⼦。 密度估算⽅法 ： 要对拥挤距离进⾏计算，则需要根据每个⽬标函数对种群中的所有个体按升序进⾏排序。第⼀个和最后⼀个个体的拥挤距离设为⽆穷⼤，第i 个个体的拥挤距离则设为第i+ 1和第i个体的所有 ⽬标函数值之差的和。具体⽅法如下⾯伪代码 ： f crowding_distance_assignment( I ) nLen = en( I ) # I中的个体数量 for i in I: i.distance = 0 #初始化所有个体的拥挤距离 for obj Fun in M: #M为所有 ⽬标函数的列表 I = sort( I, obj Fun ) #按照 ⽬标函数obj Fun进⾏升序排序 I[0] = I[ en[I]-1 ] = ∞ #对第⼀个和最后⼀个个体的距离设为⽆穷⼤ for i in xrange( 1, en(I) - 2 ) : I[i].distance = I[i].distance + ( obj Fu