好久没有写读书笔记了，今日写一下非支配排序遗传算法（NSGA-II）的原理，作为今后复习的一个参考，主要工作内容借鉴的一个很久以前下载的NSGA-II介绍的PPT，侵删。阅读前需要具备遗传算法（GA）知识，以及之前写过的一篇文章，多目标优化之帕累托最优
NSGA-II是基于NSGA-I进行改进的，深入学习可以阅读著名论文《A fast and elitist multiobjective genetic algorithm: NSGA-II》，谷歌学术显示引用量已经达到26350次，其主要改进了三个内容：(1)提出了快速非支配排序算法；(2)采用拥挤度和拥挤度比较算子；(3)引入精英策略。
1：非支配排序算法
通过非支配排序算法对规模为n的种群进行分层，具体步骤如下：
(1)设i=1；
(2)对于所有的j=1,2.......n ，且 j ≠ i，按照以上定义，比较个体
![]() 和个体
![]() 之间的支配与非支配关系；
(3)如果不存在任何一个个体
![]() 优于
![]() ，则
![]() 标记为非支配个体；
(4)令
![]() ，转到步骤(2)，直到找到所有的非支配个体。
通过上述步骤得到的非支配个体集是种群的第一级非支配层，然后，忽略这些已经标记的非支配个体(即这些个体不再进行下一轮比较)，再遵循步骤(1)-(4)，就会得到第二级非支配层。依此类推，直到整个种群被分层。而NSGA-II的快速非支配排序，降低了计算的复杂度，具体的算法没怎么看了。
2：采用拥挤度和拥挤度比较算子
(1) 拥挤度估计：为了得到种群中特定解周围的解的拥挤度估计，我们根据每一目标函数计算这点两侧的两个点的平均距离。这个数值作为以最近邻居作为顶点的长方体周长的估计（称为拥挤系数）。在下图中，第i个解在它所在前沿面的拥挤系数是它周围长方体的长度（如虚线框所示），拥挤度的计算保证种群多样性。
拥挤系数的计算需要根据每一目标函数值的大小的升序顺序对种群进行排序（即假如得到第一级非支配层，则对其按照目标函数的大小进行排序，然后计算拥挤度）。因此，对每一目标函数，边界解（拥有最大和最小值的解）被指定为无穷大距离的值。所有其它中间的解都被指定为等于两个相邻解的函数值归一化后的绝对差值。计算方法对其它目标函数也是这样。全部拥挤系数值是通过个体每一目标的距离值的加和计算得到的，每一目标函数在计算拥挤系数前都会进过归一化处理。
具体步骤
①每个点的拥挤度
![]() 置为 0；
② 针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷，即
③ 对其他个体进行拥挤度的计算：
其中：
![]() 表示 i 点的拥挤度，
![]() 表示 i+1点的第 j 个目标函数值，
![]() 表示 i -1点的第 j个目标函数值。
(2) 拥挤比较算子
经过前面的快速非支配排序和拥挤度计算之后，种群中的每个个体i都拥有两个属性：非支配排序决定的非支配序
![]() （级数，即第几级）和拥挤度
![]() 。依据这两个属性，可以定义拥挤度比较算子：个体i与另一个个体 j 进行比较，只要下面任意一个条件成立，则个体i获胜。
① 如果个体i所处非支配层优于个体 j 所处的非支配层，即
![]() <
② 如果他们有相同的等级，且个体i比个体 j 有一个更大的拥挤距离，即
![]() 且
第一个条件确保被选择的个体属于较优的非劣等级。第二个条件根据它们的拥挤距离选择由于在同一非劣等级而不分胜负的两个个体中位于较不拥挤区域的个体(有较大的拥挤度
![]() )。胜出的个体进入下一个操作。
3：精英策略
首先将第t代产生的新种群
![]() 与父代
![]() 合并组成
![]() ，种群大小为 2N 。然后
![]() 进行非支配排序，产生一系列非支配集
![]() 并计算拥挤度。由于子代和父代个体都包含在
![]() 中，则经过非支配排序以后的非支配集
![]() 中包含的个体是
![]() 中最好的，所以先将
![]() 放入新的父代种群
![]() 中。如果的大小小于 N ，则继续向
![]() 中填充下一级非支配集
![]() ，直到添加
![]() 时，种群的大小超出 N ，对
![]() 中的个体使用拥挤度比较算子，使
![]() 个体数量达到N 。然后通过遗传算子(选择、交叉、变异)产生新的子代种群
| 
转播
