非支配排序遗传算法（NSGA）是基于遗传算法的多目标优化算法，都是基于Pareto最优解讨论的多目标优化算法。 1.Pareto支配关系： 对于最小化多目标问题，n个目标分量fi（i=1……n）组成的向量f（X）=（f1（X），f2（X）……fn（X）），任意给定两个决策变量Xu，Xv∈U： 
2.Pareto最优解定义 多目标优化问题与单目标优化问题有很大差异。当只有一个目标函数时，人们寻找最好的解，这个解优于其他所有解，通常是全局最大或者最小，即全局最优解。而当存在多个目标时，优于目标之间存在冲突无法比较，所以很难找到一个解使得所有目标函数同时最优，也就是说，一个解可能对于某个目标函数是最好的，单对于其他的目标函数却不是最好的，甚至是最差的。因此，对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是：无法再改进任何目标函数的同时不削弱至少一个其它目标函数。这种解称作非支配解或者叫 Pareto最优解。 对于最小化多目标问题，n个目标分量fi（i=1……n）组成的向量f（X）=（f1（X），f2（X）……fn（X）），Xu∈U为决策变量，若Xu为Pareto最优解，则需满足： 
3.NSGA一般流程 NSGA采用的非支配分层方法，可以使好的个体有更大的机会遗传到下一代；适应度共享策略则是得准Pareto面上的个体均匀分布，保持群体多样性，克服了超级个体的过度繁殖，防止过早的收敛（早熟）。 流程图如下： 
从图中可以看出，算法首先判断种群是否全部分级，如果全部分级，则在分级的基础上，使用基于拥挤策略（拥挤策略者是适应度高，但是不影响外界环境的个体）的小生境技术对虚拟适应度值进行调整，并确定每个种群的虚拟适应度值，然后根据虚拟适应度值的大小，确定优先选择使用遗传算法进行处理的种群。 NSGA与简单的遗传算法的主要区别在于：该算法在选择算子执行之前根据个体之间的支配关系进行了分层。其选择算子、交叉算子和变异算子与简单遗传算法没有区别。 4.非支配排序 考虑一个目标函数个体为K（K>1）、规模大小为N的种群，通过非支配排序算法可以对该种群进行分层，具体步骤如下；
- 设j=1
- 对于所有的g=1,2……n且g≠j，基于适应度函数比较个体xj和个体xr之间的支配和非支配关系
- 如果不存在任何一个个体xr优于xj，则xj标记为非支配个体
- 令j=j+1，转到步骤（1），直到找打所有的非支配个体
通过上述步骤得到的非支配个体集是种群的第一级非支配层;然后,忽略这些标记的非支配个体,再遵循步骤(1)一(4),就会得到第二级非支配;依此类推,直到整个种群被分类。 5.虚拟适应度值的确定 在对种群进行非支配排序的过程中，需要给每一个非支配层制定一个虚拟适应度值。级数越大，虚拟适应度值越小；反之，虚拟适应度值越大。这样可以保证在选择操作中等级较低的非支配个体有更多的机会被选择进入下一代，使得算法以最快的速度收敛于最优区域。另一方面，为了得到分布均匀的Pareto最优解集，就要保证当前非支配层上的个体具有多样性。NSGA中引入了基于拥挤策略的小生境技术，即通过适应度共享函数的方法对原先指定的虚拟适应度值进行重新指定。 6.共享小生境技术 
共享度适应值即为个体与种群中其他个体间共享函数值之和。 以上内容均来自于我对百度文库相关内容的整理。
