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排序时在时间上最差情况下，每个Pareto类只包含一个个体，n次分级所需时间复杂度上升到O(MN3 )。 因此，论文提出了时间复杂度为O(MN2 )的高速非支配排序法。
该算法需要存储两个量： (1)支配数量np。 该量是个体的数量，因为在可行解空间中可以支配个体p。 )2)被支配个体集合SP。 该量是由可行解空间中所有个体p支配的个体组成的集合。 排序算法的伪代码如下。 如果deffast_nondominated_sort(p ) : f=[ ] for pinp : Sp=[ ] NP=0forqinp : ifpq : # p控制q，则将q添加到sp列表中)如果p受q支配，则np加1 np =1 if np==0: p_rank=1 # )，如果该个体的np为0，则该个体为Pareto第一级f1.append [ p ] f.append [ fff 对：forqinSP3360# Sp集中的所有个体进行排名，如果nq -=1 if nq==0: #该个体的支配个数为0，则该个体的非支配个体q_rank=i 2 #该个体的Pareto水平为当前最高水平加1 此时，I的初始值为0，因此加上2q.append(q ) F.append(Q ) q ) i =1。 在上面的伪代码中，可以假设第一个部分循环是双重循环，时间复杂度为o ) n2 )，第二个部分循环总共有x个级别，每个级别最多有(N-N/x )个个体，因此循环数为x * () 2。 种群中个体多样性的保持
的原始NSGA算法使用共享函数来保持物种多样性。 此方法包含共享参数，该参数是要解决的问题所期望的共享范围。 在这个范围内，两个个体共享彼此的适应度。 但是，这种方法有两个难点。 (1) .共享函数方法维持多样性的性能很大程度上取决于所选择的共享参数值。 )2) .由于种群中的每个个体必须与其余个体进行比较，因此该方法的全局复杂度为o(n2 )。 NSGA2使用排斥算法和精英策略代替共享函数算法。 要实现这两种方法，必须首先定义两个操作：密度估计和排斥运算符。 (1) .计算密度估计拥挤距离，需要将种群内的所有个体按目标函数按升序排序。 设第一个和最后一个个体的拥挤距离无限大，第I个个体的拥挤距离为第I个和第I个个体的所有目标函数值之差之和。 具体方法是以下伪代码。 def crowding _ distance _ assignment (I ) nLen=len(I ) I ) #I中的个体数for i in I: i.distance=0 #初始设定所有个体的拥挤距离forobjfuninm objFun ) )根据目标函数objFun按升序排序I[0]=I[ len[I]-1 ]= #设第一个和最后一个个体间的距离为无限大for i in xrange(1) 1， len(I )2) :I(I ).distance=I(I ).distance ) obj fun (I (i1 ) )-obj fun (I (I-1 ) )/) max 其复杂度为o(Mnlogn )。 3。 主体循环部分
(1)随机初始化起始种群P0。 然后，非支配性地对P0进行排序，初始化每个个体的rank值。 (2) t=0)3) .通过二进制冠军方法从Pt中选择个体，进行交叉和变异操作，生成下一代种群Qt。 (4)计算新种群的obj值，)5) .通过综合Pt和Qt，生成组合种群Rt=Pt UQt。 (6) .对Rt进行非支配性排序，根据排斥和精英保存策略选择n个个体，构成下一代种群Pt 1。 (7) .跳至步骤3，循环至满足结束条件。 步骤5的具体操作如下图所示。 伪代码如下。 while condition : rt=ptq TF=fast _ non dominate _ sort (rt ) pt1=[]I=0whilelen(pt1 ) len ) f (in : crowding
(1) .非支配地位，最差复杂度为o(m ) 2n )。 )2) .拥塞距离估计赋值，最差复杂度为o(m(2n ) log (2n ) )。 )3) .拥挤操作的排名，最差的复杂度为o(2nlog ) 2n ) )。