NSGA-ll

此博客的很多内容均来自 博客园 Alexander 博主的文章，我只做了整理方便今后自己回顾，因此很感谢博主的分享
2017年11月28日

NSGA-ll：Non-Dominated Sorting Genetic Algorithm-ll，带精英策略的非支配排序遗传算法

Pareto支配关系定义、Pareto最优解定义、一般的非支配分层排序算法请参考网上相关内容，或者我的名为NSGA的博客文章

为什么有NSGA-ll
顾名思义，NSGA-ll是对NSGA的改进，是在NSGA不能有效解决问题的时候被提出来的。Kalyanmoy Deb等人在他们的介绍NSGA-ll的论文中提到了NSGA算法主要的局限，即
1. High computational complexity of non-dominated sorting，非支配排序的时间复杂度太高，为$O(mN^3)$，其中m为目标（objectives）个数，N为种群大小；
2. Lack of elitism，缺少精英策略。研究表明，精英策略可以有效地增强GA的效果，同时避免好种群的流失；
3. Need for specifying the sharing parameter $\sigma _{share}$，需要指定共享半径$\sigma _{share}$，具有人为的偶然性。

而NSGA-II针对以上的缺陷通过以下三个方面进行了改进：
1. A fast non-dominated sorting approach，提出了快速非支配排序方法，降低了算法的计算复杂度。由原来的$O(mN^3)$降到$O(mN^2)$，其中，m为目标函数个数，N为种群大小；
2. Elitism，引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，并通过对种群中所有个体的分层存放，使得最佳个体不会丢失，迅速提高种群水平；
3. Density Estimation && Crowded Comparison Operator，提出了拥挤度和拥挤度比较算子，代替了需要指定共享半径的适应度共享策略，并在快速排序后的同级比较中作为胜出标准，使准Pareto域中的个体能扩展到整个Pareto域，并均匀分布，保持了种群的多样性。

NSGA-ll的基本思想
首先，随机产生规模为N的初始种群，非支配排序后通过遗传算法的选择、交叉、变异三个基本操作得到第一代子代种群；其次，从第二代开始，将父代种群与子代种群合并，进行快速非支配排序，同时对每个非支配层中的个体进行拥挤度计算，根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群；最后，通过遗传算法的基本操作产生新的子代种群。依此类推，直到满足程序结束的条件。相应的程序流程图如下图所示：

快速非支配排序算法 fast non-dominated sorting algorithm

1. 首先，对于每一个解决方案（solution）我们需要定义两个参数，分别是$n_i$和$S_i$。