写在前面：NSGA III算法在数学上比NSGA II算法要复杂得多，尤其是在参考点那里，我也不是看得很明白，所以这篇文章只是尝试梳理下NSGA III的整体改进思路和优势，不对函数、公式、代码之类的细节做过多分析。如有错误，恳请指出！
算法简介
NSGA-III（Non-dominated Sorting Genetic Algorithm III）算法是NSGA-II的改进版，是多目标优化领域中的重要算法之一。该算法在选择机制上进行了创新，通过引入广泛分布的参考点来维持种群的多样性，其关键优势在于其能够有效地平衡多样性和收敛性，以找到Pareto前沿上的高质量解。
NSGA-III的主体框架与NSGA II基本一致，其主要步骤如下：
- 初始化种群：
- 随机生成一个初始种群，其中包含多个个体（解）。
- 每个个体通常由一组决策变量表示。
- 非支配排序：
- 对初始种群中的个体进行非支配排序。
- 将个体分为不同的等级，其中第一级包含Pareto前沿上的非支配解，第二级包含被第一级支配的解，以此类推。
- 计算每个解的拥挤度，以度量其在前沿中的密度。
- 选择操作：
- 选择一部分解用于创建下一代种群。
- 选择前几个非支配级别中的所有解，以确保高质量的解被保留。
- 对于同一等级的解，根据它们的拥挤度选择一部分以维持多样性。
- 选择的解将进入下一代种群。
- 交叉和变异：
- 使用交叉和变异操作生成下一代解。
- 通过交叉操作，两个父代解可以产生一个或多个子代解。
- 通过变异操作，对个体的决策变量进行微小的随机变化。
- 更新种群：
- 将新生成的解与上一代种群合并，形成新的2N种群。
- 如果种群大小超过所需大小，可以使用选择策略来选择最适合的解。
- 迭代：
- 检查终止条件是否满足。通常，可以设置最大迭代次数或其他收敛标准作为终止条件。
- 如果终止条件未满足，返回步骤2，继续进行下一代进化。
- 如果满足终止条件，输出结果。返回找到的Pareto前沿上的高质量解集合作为算法的输出。
NSGA-III的关键特点是它的能力维护多样性和寻找Pareto前沿上的高质量解。它通过非支配排序、环境选择和多样性维护策略来实现这些目标，使其在多目标优化问题中非常有效。
多目标问题
为什么会有NSGA III算法？
NSGA III算法是从NSGA II算法改进改进过来的，其出现的原因自然是，NSGA II在求解一些问题的时候仍然存在局限性。两种算法各有其适应的问题特点，在原论文中，NSGA III算法的提出主要是期望求解Many-objective问题。
Multi-objective和Many-objective
原文：
Loosely,many-objective problems are defined as problems having four or more objectives.Two and three-objective prob lems fall into a different class as the resulting Pareto-optimal front,in most cases,in its totality can be comprehensively visualized using graphical means.Although a strict upper bound on the number of objectives for a many-objective optimization problem is not so clear,except a few occasions [15],most practitioners are interested in a maximum of 10 to 15 objectives.
简单来说，当一个多目标优化问题包含4个或更多的目标函数时，人们会倾向于将其视为 “Many-objective” 问题。这是因为在目标函数数量增加时，问题的复杂性显著增加，解决方案的多样性变得更加关键，同时性能评估也更加具有挑战性。
即：
- Multi-objective→2-3个目标函数；
- Many-objective→4个及以上（通常为10-15个）目标函数，
NSGA II→NSGA III
同上一篇NSGA II一样，这里直接梳理NSGA III相对于NSGA II的改进点。
由于NSGA III是在NSGA II的基础上，为求解Many-objective问题进行改进的，而Many-objective相对Multi-objective的一个显著特点就是，所谓量变引起质变，Many-objective的解空间相比Multi-objective要大得多，解的分布也显得比较稀疏，这就导致算法在对最优解进行搜索时，算法在某个解分布密度较大的地方，很容易陷入局部最优解。因此，NSGA III的改进主要针对于如何保留解的多样性，避免算法陷入局部最优，而保留解的多样性以及跳出局部最优的关键就在于遗传算法的选择操作。
为突出NSGA III的具体改进，根据原文献，可将其选择操作进一步细化成以下几个流程：
将种群划分为非支配性级别——确定超平面上的参考点——种群个体的自适应归一化——关联操作——小生境保留操作——生成子代种群的遗传操作
下面将根据这一流程介绍NSGA III在NSGA II的基础上进行的几点改进。
1. 多层级分层排序
NSGA-III引入了多层级分层排序，这是其最显著的改进。在NSGA-III中，种群被分为多个分层级别，每个级别包含不同密度的解决方案。这种分层排序使算法能够更好地维护Pareto前沿上的均匀分布解。
这个在上边的选择流程中没有明确的体现，但是我认为，NSGA III算法的精髓，就是解的层级分配和排序。
回想一下NSGA II算法的非支配排序，它是直接将父代和子代种群拼接成2N的新种群之后，再对这个2N种群进行排序。而NSGA III为了应对Many-objective问题的解在高维解空间上分布的稀疏性问题，不是直接对2N种群进行非支配排序，而是对种群中的个体（解）进行分层后，对每层进行非支配排序。实际上，NSGA III在解的搜索阶段，就已经通过类似统计学中分层采样的思想，对解进行了分层。
广为人知的参考点法，在我看来，是实现多层级分层排序的一个手段。
参考点具体是如何引入的呢？我看不懂公式，所以只能结合图和文字一点点来猜。
简单说就是，NSGA-III通过某种方法，从解空间中选择规定数量的、均匀分布的、能够覆盖整个目标空间的、自适应调整的参考点。这些参考点就相当于在解空间中打下的标记，告诉后续的解搜索算法，这里还有一块被标记的区域需要搜索，不要漏掉了。
一个个参考点以及参考点周围聚拢过来的候选解，慢慢地形成了解的不同层级（当然，可以将具有相似特征的参考点附近的解视为同一层级）。
多层级分层排序流程：
- 选择参考点：NSGA-III选择一组参考点（reference points），这些点位于目标空间中，用于衡量解在目标空间中的优越性。通常，参考点是均匀分布的，以覆盖整个目标空间。
- 分层级别的分配：接下来，将解分配到不同的层级级别。解的分配基于它们与参考点的比较，具体来说，是解与最接近的参考点之间的距离。每个解被分配到最接近的参考点所对应的层级级别。
- 级级别的排序：在每个层级级别内，使用非支配排序（non-dominated sorting）将解排序。这是为了确定解的非支配性，即解是否在该层级内不被其他解所支配。
- 选择解：从每个层级级别中选择一定数量的解，以形成新一代的种群。通常，选择的策略可能包括非支配排序和拥挤度（crowding distance）的考虑，以确保选择均匀分布在每个层级内。
通过这种方式，NSGA-III能够确保解在Pareto前沿上的分布均匀，并且可以更好地逼近Pareto前沿。参考点的选择和解的分配是多层级分层排序的核心概念，使算法能够有效地处理多目标优化问题，维护均匀分布的解，提高性能。
2. 种群个体的自适应归一化
NSGA-III算法中的自适应归一化是对每个个体的目标函数值进行的归一化。这是为了将不同目标之间的值进行比较，并确定个体在多目标优化中的相对优越性。自适应归一化通常通过与参考点之间的距离来实现，这些参考点通常均匀分布在目标空间中。
具体来说，对于每个个体，NSGA-III计算它与每个参考点之间的距离。然后，通过将个体到最近参考点的距离作为归一化值，确定个体在目标空间中的优越性。这有助于选择具有不同优越性的个体，并维持解在Pareto前沿上的均匀分布。
自适应归一化是NSGA-III算法的一个关键概念，它有助于确定解的相对优越性，以支持多目标优化的解选择过程。这种归一化考虑了不同目标之间的权重和距离，以便更好地维持解的多样性和均匀分布。
3. 关联操作
在NSGA-III中，关联操作是用于将种群中的每个个体与参考点相关联的过程，以确定每个个体在多目标优化中的相对优越性。
关联操作流程如下：
- 种群个体归一化：对于每个目标函数值，将其进行归一化，以将所有目标值映射到[0, 1]的范围内。这是为了确保不同目标之间的值具有可比性。
- 计算与参考点的距离：对于每个个体，计算其与每个参考点之间的距离。通常使用欧氏距离或其他距离度量来计算。
- 确定关联：将每个个体与最近的参考点关联。即，每个个体被认为与最近的参考点相关联，这将决定其在多目标空间中的位置。
- 确定层级级别：基于关联的结果，将解分配到不同的层级级别。这有助于确保解的分布在多目标空间中均匀，以支持多样性和均匀性。
可以将NSGA-III中的关联操作视为一种类似于聚类的过程，将种群中的个体分组成多个类别，其中每个类别由最接近的参考点来定义。每个参考点代表不同的类别或群集，而个体与最接近的参考点相关联，意味着它们被归入相应的类别。
通过这个关联操作，NSGA-III能够确定每个个体在多目标空间中的相对位置，这将在后续的选择过程中用于选择解以构建下一代的种群。这个过程有助于维护多样性并更好地逼近Pareto前沿。
4. 小生境保留操作
在NSGA-III中，关联操作将每个个体与最近的参考点相关联。每个参考点及其周围关联的个体构成了一个聚类类别，这个聚类类别可以被视为一个小生境。每个小生境中的个体与同一个参考点具有相似的目标函数值，因此它们在目标空间中相对接近。在选择操作中，通常会从不同的小生境中选择个体，以确保选择的解具有广泛的多样性，从而更好地逼近Pareto前沿。小生境保留操作是NSGA-III算法维持多样性的关键机制之一。
小生境操作是在已经划分好各种小生境的基础上实现的，其目的是根据每个小生境的大小来选择个体以填充各自的小生境，从而维持多样性。在NSGA-III中，每个小生境（聚类类别，包括与参考点相关联的个体）都有一个预定的大小或容量，小生境的大小是由与参考点相关联的个体数量来决定的。在小生境操作中，目标是确保每个小生境内有足够的个体，以维持多样性和均匀分布。
因此，操作的目标是填充每个小生境，使其包含所需数量的个体。这些个体可以是从其他小生境中选择的，以确保每个小生境内的个体数量达到所需的大小。在填充小生境时，通常会选择与参考点关联度最高的个体，以确保它们在多目标空间中相对接近。
这个过程将重复进行，直到每个小生境都包含所需数量的个体。通过这种方式，NSGA-III确保了不同小生境内的个体数量均衡，并维持了多样性，以支持更好的多目标优化搜索。
小生境操作流程：
- 计算小生境的大小：首先，确定每个小生境（关联的参考点和相关个体组成的聚类类别）的大小。小生境大小通常由与参考点相关联的个体数量（p_j）来决定。
- 选择小生境：从已经划分好的小生境中，确定具有最小小生境计数的小生境集合 J。这些小生境将用于进行小生境操作。
- 小生境操作：
- 对于每个选定的小生境 j，执行以下操作：
- 如果小生境 j 为空（p_j = 0），则需要从其他小生境（F_j）中选择一个与参考点 j 相关联的个体，通常是选择与参考线垂直距离最短的个体，并将其添加到小生境中（P+ 集合）。然后，增加小生境 j 的计数 p_j。
- 如果小生境 j 不为空（p_j > 0），则需要从小生境 j 中随机选择一个与参考点 j 相关联的个体，并将其添加到小生境中（P+1 集合）。然后，增加小生境 j 的计数 p_j。
- 重复操作：上述小生境操作将在每个选定的小生境上重复，以确保小生境的填充。这个过程通常会重复 K 次，以确保 P+ 集合中的所有空位置都被填充。
5. 无参数特性
与NSGA-Ⅱ一样，NSGA-Ⅲ算法除了通常的遗传参数如种群规模、终止参数、交叉和变异概率及其相关参数外，不需要设置任何新的参数。参考点的数量H 不是一个算法参数，因为这完全由用户来决定。种群规模N 取决于H ，因为N≈H。参考点的位置同样取决于用户对所获得的解中的偏好信息。
【调度算法】NSGA III（2）https://developer.aliyun.com/article/1541024
