NSGA-Ⅱ算法是一种性能优良的多目标进化算法，运行效率高，产生局部收敛的几率较小，尤其是针对维度较小的目标时，优化效果很好。该算法是在NSGA 算法 （Non-dominated Sorting Genetic Algorithms，NSGA）基础上提出的改进算法。
1.NSGA 算法
1995年，Srinivas和Deb 提出了非支配排序遗传算法。这是一种基于Pareto最优概念的遗传算法，是众多的多目标优化遗传算法中体现Golbderg思想最直接的方法。该算法在许多问题上得到应用，但仍存在以下问题：
（1）计算复杂度较高。
（2）没有精英策略。精英策略可以加速算法的执行速度，而且也能在一定程度上确保已经找到的满意解不被丢失。
（3）需要指定共享半径σshare。
2.NSGA-Ⅱ算法的优点
2000年，Deb又提出NSGA 的改进算法——带精英策略的非支配排序遗传算法NSGA-Ⅱ。NSGA-Ⅱ针对以上的缺陷在三个方面进行了改进[92]：
（1）提出了快速非支配排序法，降低了算法的计算复杂度。
（2）提出了拥挤度和拥挤度比较算子，代替了需要指定共享半径的适应度共享策略，并在快速排序后的同级比较中作为胜出标准，使准Pareto域中的个体能扩展到整个Pareto域，并均匀分布，保持了种群的多样性。
（3）引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，并通过对种群中所有个体的分层存放，使得最佳个体不会丢失，迅速提高种群水平。
3.常规NSGA-Ⅱ算法流程
（1）在一定范围内，通过随机产生N 组参数进行初始化，并计算对应的优化目标值。
（2）对初始化的群进行非支配排序。对于群P 中的每个个体p：
1）令Sp=Φ。这个序列包括被p 支配的个体组合。
2）令np=0。这是支配p 的个体数目。
3）对于群P 中的每个个体p，如果p 支配q，那么Sp=Sp∪q；如果q支配p，那么
4）如果np=0，prank=1。将p 添加到第一列等级非支配集合F1=F1∪{p}，群P 中的每个个体都需要进行这样的计算。
5）对于Sp 中的每个q，nq=nq-1。
6）如果在后续队列中没有任何个体支配q，那么qrank=prank+1。
对于被队列qrank 中的个体所支配的个体，转到5），直到没有任何个体被其他个体支配为止。
（3）对于在同一非支配序列队列中的个体，设定拥挤度。对于每个队列Fi，n是其中个体的数目。(www.xing528.com)
1）对每个个体的拥挤度初始化为0。
2）对每个优化目标函数m，根据优化目标m 的值进行排序，即
4）如果np=0，prank=1。将p 添加到第一列等级非支配集合F1=F1∪{p}，群P 中的每个个体都需要进行这样的计算。
5）对于Sp 中的每个q，nq=nq-1。
6）如果在后续队列中没有任何个体支配q，那么qrank=prank+1。
对于被队列qrank 中的个体所支配的个体，转到5），直到没有任何个体被其他个体支配为止。
（3）对于在同一非支配序列队列中的个体，设定拥挤度。对于每个队列Fi，n是其中个体的数目。
1）对每个个体的拥挤度初始化为0。
2）对每个优化目标函数m，根据优化目标m 的值进行排序，即
对每个个体的边界值设为无穷大（k=1和k=n），则从k=2到k=n-1有
对每个个体的边界值设为无穷大（k=1和k=n），则从k=2到k=n-1有
式中 I（k+1）m——I中的第k+1个个体的第m 个优化目标值。
（4）基于以下两点在群中选择个体：①非支配序列prank；②拥挤度距离Fj（dj）。
令p＜q，如果 prank＜qrank，则非支配序列相同时，Fj（dp）＜Fi（dq）。
（5）进行遗传算法计算，产生子群，并对子群进行优化目标函数值计算。
（6）将父群和子群混合在一起，进行非支配排序并计算拥挤度，然后根据非支配排序和拥挤度选择产生下一代的群体。进入步骤（5），直至达到预设的代数。
式中 I（k+1）m——I中的第k+1个个体的第m 个优化目标值。
（4）基于以下两点在群中选择个体：①非支配序列prank；②拥挤度距离Fj（dj）。
令p＜q，如果 prank＜qrank，则非支配序列相同时，Fj（dp）＜Fi（dq）。
（5）进行遗传算法计算，产生子群，并对子群进行优化目标函数值计算。
（6）将父群和子群混合在一起，进行非支配排序并计算拥挤度，然后根据非支配排序和拥挤度选择产生下一代的群体。进入步骤（5），直至达到预设的代数。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
