NSGA2
快速的、精英主义的、多目标遗传算法
背景
使用非支配排序和共享的多目标进化算法（EA）主要受到批评：1）（3）O(MN^3)计算复杂度（其中，M为目标函数数量和人口数量 N）； 2）非民族主义的方法； 3）需要指定共享参数。 在本文中，我们提出了一种基于非支配排序的多目标EA（MOEA），称为非支配排序遗传算法II（NSGA-II），它可以缓解上述三个难题。 具体来说，提出了一种具有（2）计算复杂度的快速非支配排序方法。 另外，提出了一个选择算子，该算子通过组合父母和后代种群并选择最佳的（相对于适应性和传播性）解决方案来创建交配池。 针对棘手的测试问题的仿真结果表明，与帕累托归档的演化策略和强度帕累托EA相比，拟议的NSGA-II在大多数问题中都能找到更好的解决方案分布，并且能够在真正的帕累托最优前沿附近找到更好的收敛性。 另外两个精英MOEA特别重视创建多样化的帕累托最优阵线。
此外，我们修改了优势的定义，以便有效地解决约束性多目标问题。 将受约束的NSGA-II在许多测试问题（包括五目标七约束的非线性问题）上的仿真结果与另一个受约束的多目标优化器进行了比较，并且观察到NSGA-II的性能要好得多。
方法
非支配排序
将种群 P 分级为 F1，F2， F3…
对于每个个体，有两个参数：
- n_p，支配 p 的个体数
- S_p，被 p 支配的个体数
算法首先对每个个体计算 n_p 和 S_p，并将 n_p = 0 的个体放入 F1集合中，并设 p_rank = 1。这个操作的时间复杂度为 O(N^2)，空间复杂度O(N^2)，N 为种群的个体数。
非支配排序步骤：
- 对集合 F_i（i 初始化为 1）中的每个个体 p（n_p = 0），它的支配个体集合为 S_p，遍历集合中的每个元素 q，执行 n_q -= 1，如果 q 仅被 p 支配（即 n_q = 1），则代表它是下一层 F_(i + 1) 的元素，q_rank = i + 1，将其加入到集合 Q 中。
- i = i + 1，记 F_i 中得到的个体为第 i 个非支配层的个体，F_i = Q ，重复步骤 1，直到整个种群被分级。
拥挤度
拥挤度是指种群中给定个体的周围个体的密度,直观上可表示为个体。
长方形的周长就是 i 的拥挤度。拥挤距离计算需要根据每个目标函数值按升序对人群进行排序。
在带精英策略的非支配排序遗传算法中，拥挤度的计算是保证种群多样性的一个重要环节。
拥挤距离计算需要根据每个目标函数值按升序对人群进行排序。
I[i].m 是集合 I 中的第 i 个个体的第 m 个对象函数值。
算法步骤：
初始化每个个体的拥挤度为 0，对于每个目标函数值 m，对种群进行排序，令两个边界的两个个体拥挤度为无穷。
计算拥挤度：
将每个归一化后的值加入拥挤度，其中
为每个函数值归一化后的值。
拥挤度比较算子
在经过非支配排序和拥挤度计算后，我们得到非支配排序 i_rank 和拥挤度 i_distance。
在具有不同非支配等级的两个解决方案之间，我们倾向于非支配等级较低（更好）的解决方案。否则，如果两个解决方案属于同一个非支配层，那么我们更喜欢位于不拥挤的解决方案（拥挤度越大，证明当前解决方案越稀疏）。
主循环
最初，将创建一个随机的父母群体。 人口基于非统治进行排序。 每个解决方案的适应性（或等级）均等于其非支配级别（1是最佳级别，2是次佳级别，依此类推）。 因此，假定适合度最小。 首先，通常使用二元锦标赛选择，重组和变异运算符来创建大小为后代的种群Q0。
首先得到一个合并种群
，种群大小为 2N。对该种群进行非支配排序，最优非支配集合 F1 中的解是最优解，比种群中的其他解更加重要。如果 F1 的大小小于 N，将其加入新种群P_(t + 1)，将剩下的非支配层按照它们的顺序加入 P_(t + 1)。
我们要使 P_(t + 1)的大小为 N，对最后一个非支配层（例如 图2中的 F3）使用拥挤度比较算子对解进行降序排序，取最后一个非支配层的前 N - |P _ (t + 1)|个解。然后对 P_(t + 1)进行选择，交叉和变异得到 Q _ (t + 1)，然后继续进行下一次循环。
“变异”运算符是用于生成修饰种群的多个运算符（如交叉，变异等）的集合。 交叉算子的目的是从交配池中随机选择两个或多个解决方案（父代），并通过在父解决方案之间交换信息来创建一个或多个解决方案。 交叉算子的交叉概率为p; 指出参与交叉操作的人口成员的比例。 剩下的1-p人口的比例只是复制到修改后的（儿童）人口中。 在具有n个实值变量并涉及与两个父解的交叉的实参优化的上下文中，每个变量可以一次交叉。 依赖于两个父变量值之间的差异的概率分布通常用于创建两个新数字，作为围绕两个父变量值的子变量[5]。 除了可变方式重组算子，矢量方式重组算子还建议将父解决方案变量之间的相关性传播到创建的子解决方案中[6，7]。
支配
非支配前沿
图中的非支配前言为 3，5，6 从 3 到 5 ，f1 的收益变大，但 f2 收益变小。
实验
与单目标优化不同，多目标优化中有两个目标：1）收敛到帕累托最优集；2）维持帕累托最优集的解的多样性。
第一个度量 γ 度量到一组已知的Pareto最优解的收敛程度。第二个度量标准 Δ 衡量获得的解决方案之间实现的扩展程度。
