NSGA-II算法的学习笔记
1. 算法优劣性（相较于第一代NSGA）
① NSGA-II添加了精英策略，即保存群体中适应度在第一层级的个体。
②NSGA-II提出了新的给群体按照非支配关系排序的方法，提高了算法速度。其中又使用了拥挤度概念来对非支配层级中同一级的个体进行排序。
2. 算法流程
Began
初始化父代种群P0
给P0中的所有个体按非支配关系排序
按照排序给所有个体分配适应度，最佳适应度值设为1
进行遗传算法操作（选择、交叉、变异）生成子代种群Q0
△Then
R0 = P0 ∪ Q0
给R0按非支配关系（一种偏序关系）排序，并按照个体的支配个数分级F1、F2、F3..
描述该偏序关系的哈斯图的最高点为F1，以此类推。
对于每一级Fi 计算每个个体的拥挤度 并依此排序
至此，得到R0集合中所有个体的排序
△ After
按照顺序从R0选择个体作为下一代的父代
R1 = ∅
R1 = R1 ∪ F1
如果R1个体数小于种群数量限制N
R1 = R1 ∪ F2
如果R1个体数M大于种群数量限制N
则从F2中按照拥挤度排序将M-N的个体放入到R1中。
Then
对R1进行遗传算法操作（选择、交叉、变异）生成子代种群Q1
重复操作，直到达到种群的迭代次数或得到最优解。
Postscript：每次遗传操作后都要记录种群情况。
3. 流程图
4.NSGAII算法的三个关键步骤
排序算法的伪代码如下：
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
if nq == 0: #如果该个体的支配个数为0，则该个体是非支配个体
q_rank = i+2 #该个体Pareto级别为当前最高级别加1。此时i初始值为0，所以要加2
Q.append( q )
F.append( Q )
i += 1
在上面伪代码中，第一部分循环为二重循环，时间复杂度为O(N2)，第二部分循环中，我们可以假设共有x个级别，而每个级别中最多有（N-N/x）各个体，每个个体的支配集合中也最多有（N- N/x）各个体。由此可得出循环次数为x*（N-N/x）*（N-N/x）=（（x-1）2/x2）N2M，即时间复杂度为O(MN2)。
具体方法如下面伪代码：
nLen = len( I ) #I中的个体数量
for i in I:
i.distance = 0 #初始化所有个体的拥挤距离
for objFun in M: #M为所有目标函数的列表
I = sort( I, objFun ) #按照目标函数objFun进行升序排序
I[0] = I[ len[I]-1 ] = ∞ #对第一个和最后一个个体的距离设为无穷大
for i in xrange( 1, len(I) - 2 ):
I[i].distance = I[i].distance + ( objFun( I[i+1] ) - objFun( I[i-1] ) )/(Max(objFun()) - Min(objFun()) )
伪代码中的objFun( i )是对个体i求其目标函数值。Max(objFun())为目标函数objFun()的最大值，Min(objFun())为目标函数objFun的最小值。其复杂度为O(MNlogN)。