NSGA

支配与非支配

对于多个目标函数的问题，我们一般不能找到都很满足条件的解，比如手机价格低，肯定性能就差，一部性价比高的手机就能支配绝大多数手机。

一个解S1，对于任何一个目标函数，适应度都比另一个S2的要大，那么就说这个解S1严格支配S2。当然也有可能某一目标函数的适应度相等，那样就是非严格的支配。对于解S1，目标函数F1适应度优于解S2的目标函数F1适应度，但是在目标函数F2上，解S2优于解S1，这样，我们就称这两个解是互相非支配的。就像七个葫芦兄弟，各有本事，谁也不服谁，他们就是互相非支配的😁。

如何进行非支配排序？

1. 设$i=1$
2. 对于所有的$j=1，2，3$等，且$j$不等于$i$，按照以上定义比较个体$x_i$和$x_j$之间的支配关系
3. 如果不存在任何一个个体$x_j$支配$x_i$，则$x_i$标记为非支配个体
4. 令$i=i+1$，转到步骤2，直到找到所有的非支配个体

种群分层

通过一次上述步骤，可以得到种群的第一级非支配层，然后忽略这些被标记的个体，再次遵循步骤1到4，就会得到第二支配层。以此类推，直到整个种群被分层。

思考一下时间复杂度是多少？

NSGA是不带任何方法的直接非支配排序。设目标数$(F_1,F_2\dots F_M)$为$M$，种群个体数为$N$。一个个体进行一次排序的时间复杂度为$MN$（要与$N-1$个体比较，要比较$M$个目标）。第一轮要比较$N$个个体，因此第一轮的时间复杂度为$M{N}^2$。在最坏的情况下，每轮只有一个个体为当前一轮排序的非支配解，则要$O(N)$轮排序。因此NSGA的时间复杂度为$O(M{N}^3)$。

虚拟适应度值

种群分层结束后，需要给每级指定一个虚拟适应度值，级别越小，说明其中的个体越优，赋予越高的虚拟适应值，反之级别越大，赋予越低的虚拟适应值。这样可以保证在复制操作中级别越小的非支配个体有更多的机会被选择进入下一代，使得算法以最快的速度收敛于最优区域。

NSGA-Ⅱ

对于NSGA的三大改进，使得算法效率大大提升。

快速非支配排序

如何体现一个快字？

对于每个个体 $i$ 都设有以下两个参数 $n(i)$ 和 $S(i)$，

$n(i)$ ：在种群中支配个体$i$的解个体的数量number。

$S(i)$ ：被个体$i$所支配的解个体的集合set。

步骤

1. 第一轮初始化个体，$n_p$为0，$S_p$为空集。第一轮与NSGA相同，时间复杂度为$O(M{N}^2)$。此时将$n_p=0$的个体加入第一级非支配集$F_1$。
2. 对上一轮集合$F_1$中，取一个个体$p$，在$p$的$S_p$集合中，依次将个体$q$的$n_q$减去一，若此时$n_q=0$，则将其加入下一轮排序的非支配解集$F_2$。这里可以将每一个个体看成一个结构体，里面包含一个变量和一个存放结构体的数组，三层集合嵌套。
3. 重复步骤2。时间复杂度在最坏情况下，每一次只能取一个到下一层非支配解集，每一轮需要花费$O(N)$,一共需要$O(N-1)$轮，所以总的时间复杂度为$O(M{N}^2)=O(M{N}^2)+O(N^2)$。

拥挤度排序

为了保持解群体的分布性和多样性，NSGA-II提出使用计算聚集距离。分布距离的使用只是为了在后面建立偏序集所使用，优先权还是在非支配排序上。

计算方法就是利用前后个体的目标函数差值计算，可以理解为画一个矩形，顶点是前后个体，计算的就是在矩形中间的个体的拥挤度。在这之间要将同一层非支配的个体按照某一目标函数排序。

$$P[i{]}_{\text{distance }}=\sum _{k=1}^r(P[i+1{]}_{.f_k}-P[i-1{]}_{.f_k})$$

如果某个方向上的距离很大，就会很大程度上影响总的距离的大小。为了使每个方向上的目标函数对拥挤距离有等效的影响力，需要每个目标函数上的距离要规则化normalized。所以要在最后除以如下变量:

$$P[i{]}_{\text{distance }}=\frac{P[i{]}_{\text{distance }}}{(f_k^{max}-f_k^{min})}$$

在二维目标函数中：

$$P[i{]}_{\text{distance }}=(P[i+1{]}_{.f_1}-P[i-1{]}_{f_1})+(P[i+1{]}_{.f_2}-P[i-1{]}_{.f_2})$$

构造偏序集

经过了排序和拥挤度计算，群体中的每一个个体都有两个属性：非支配序$irank$和拥挤度$id$，则定义偏序关系${\prec }_n$为：当满足条件$i_{rank}<j_{rank}$，或满足$i_{rank}=j_{rank}$且$i_d>j_d$时，定义$i{\prec }_{n}j$。也就是说：如果两个个体的非支配排序不同，取排序号较小的个体（分层排序时，先被分离出来的个体)，如果两个个体在同一级，取周围较不拥挤的个体。

精英策略

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

总结

流程

首先，随机产生规模为$N$的初始种群$P_t$，经过非支配排序、选择、交叉和变异，产生子代种群$Q_t$，并将两个种群联合在一起形成大小为$2N$的种群$R_t$。

然后，进行快速非支配排序，同时对每个非支配层中的个体进行拥挤度计算，根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群$P_{t+1}$ 。

最后，通过遗传算法的基本操作产生新的子代种群$Q_{t+1}$，$P_{t+1}$与$Q_{t+1}$合并形成新的种群$R_t$，重复以上操作，直到满足程序结束的条件。

时间复杂度

NSGA-II的时间花费有三部分构成：

1. 快速非支配排序（non-dominated sort):
2. 计算聚集距离（crowding distance assignment)：
3. 构造偏序集（sorting on set):

所以总时间复杂度为 $O(M{N}^2)$。

参考文献：

NSGA-II 解读

纯小白超详细的非支配排序遗传算法原理讲解