在接触学习多目标优化的问题上，经常会被提及到多目标遗传算法NSGA-II，网上也看到了很多人对该算法的总结，但真正讲解明白的以及配套用算法实现的文章很少，这里也对该算法进行一次详解与总结。会有侧重点的阐述，不会针对NSGA以及算法复杂度等等进行，有相关需求可自行学习了解。文末附有Python与Matlab两种的源代码案例。

目录

1、什么是非支配遗传算法

2、支配与非支配关系

2.1、种群分层

2.2、如何进行分支配排序

3、拥挤度（密度评估）

4、快速非支配性排序方法

5、偏序关系

6、 什么是精英策略

7、NSGA-II算法的基本思想

8、Matlab非支配代码实现

9、Python代码完整版实现

10、算法改进策略说明

文末有彩蛋

在串讲算法原理之前，先说明几个关键词。

        非支配排序遗传算法NSGA (Non-dominated Sorting Genetic Algorithms)是由Srinivas和Deb于1995年提出的。这是一种基于Pareto最优概念的遗传算法，它是众多的多目标优化遗传算法中体现Goldberg思想最直接的方法。该算法就是在基本遗传算法的基础上，对选择再生方法进行改进:将每个个体按照它们的支配与非支配关系进行分层，再做选择操作，从而使得该算法在多目标优化方面得到非常满意的结果。

        在最小化问题中， 理解起来就是，任意一个目标分量，的值都不大于，并且在这些目标分量中至少存在一个目标分量的值严格比的值小，记作.

        当出现大量满足支配与非支配的个体时，会出现一种如下的分层现象。因为优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是：无法在改进任何目标函数的同时不削弱至少一个其他目标函数。         这种解称作非支配解（nondominated solutions）或Pareto最优解（Pareto optimal solutions），形象展示如下：

（1）设i=1；

（2）所有的且，按照以上定义比较个体和个体之间的支配与非支配关系；

（3）如果不存在任何一个个体优于，，则标记为非支配个体

（4）令i=i+1，转到步骤（2），直到找到所有的非支配个体。

     通过上述步骤得到的非支配个体集是种群的第一级非支配层，然后忽略这些已经标记的非支配个体（即这些个体不再进行下一轮比较），再遵循步骤（1）-（4），就会得到第二级非支配层。依此类推，直到整个种群被分层。

        为了获得对种群中某一特定解附近的密度估计， 我们沿着对应目标计算这个解两侧的两点间的平均距离。 这个值是对用最近的邻居作为顶点形成的长方体的周长的估计（称之为拥挤距离）。在图 1 中， 第i 个解在其前沿的拥挤距离（用实心圆标记）是长方体的平均边长（用虚线框表示。（用实心圆标记的点是同一非支配前沿的解）

        拥挤距离的计算需要根据每个目标函数值的大小对种群进行升序排序。此后，对于每个目标函数，边界解（对应函数最大最小值的解）被分配一个无穷距离值。所有中间的其他解被分配一个与两个相邻解的函数值的归一化差的绝对值相同的距离值。 对其他目标函数继续进行这种计算。总的拥挤距离值为对应于每个目标的各个距离之和。在计算拥挤距离之前， 归一化每个目标函数。 下面所示的算法概述了非支配性解集 中所有解的拥挤距离计算过程。对非支配性解集进行拥挤距离分配

         这里， 是指集合中第个个体的第个目标函数值，参数  和是第m 个目标函数的最大和最小值.

        对于每个个体 都设有以下两个参数 和 ，： 在种群中支配个体 的解个体的数量。： 被个体 所支配的解个体的集合。

  1）找到种群中所有 n(i)=0 的个体， 将它们存入当前集合F(1)； 2）对于当前集合 F(1) 中的每个个体 ， 考察它所支配的个体集 ， 将集合 中的每个个体 k 的 n(k) 减去1， 即支配个体 k 的解个体数减1；（ 对其他解除去被第一层支配的数量， 即减 1） 如 n(k)-1=0则将个体 k 存入另一个集H。 （ 3） 将 F(1) 作为第一级非支配个体集合， 并赋予该集合内个体一个相同的非支配序 i(rank)， 然后继续对 H 作上述分级操作并赋予相应的非支配序， 直到所有的个体都被分级。 其计算复杂度为，m为目标函数个数， N为种群大小。按照1 )、 2） 的方法完成所有分级,示意图如下。

        由于经过了排序和拥挤度的计算，群体中每个个体都得到两个属性：非支配序和拥挤度，则定义偏序关系为：当满足条件，或满足且时，定义。也就是说：如果两个个体的非支配排序不同，取排序号较小的个体（分层排序时，先被分离出来的个体）；如果两个个体在同一级，取周围较不拥挤的个体。

        NSGA-II 算法采用精英策略防止优秀个体的流失， 通过将父代和子代所有个体混合后进行 非支配排序的方法。 精英策略的执行步骤：

1） 随机产生规模为N的初始种群Pt，经过非支配排序、 选择、 交叉和变异， 产生子 代种群Qt， 并将两个种群联合在一起形成大小为2N的种群Rt,； 2）进行快速非支配排序， 同时对每个非支配层中的个体进行拥挤度计算， 根据非支 配关系以及个体的拥挤度选取合适的个体组成新的父代种群Pt+1﹔ 3） 通过遗传算法的基本操作产生新的子代种群Qt+1， 将Pt+1与Qt+1合并形成新的种 群Rt， 重复以上操作， 直到满足程序结束的条件

 Matlab版本的数据案例（重点以拥挤度函数与非支配排序为主），网上案例很多都是使用matlab，请自行查阅学习。