NSGA-II( 快速非支配排序遗传算法）

三个创新点：

• 快速非支配排序
• 拥挤距离
• 比较算子

一、快速非支配排序法

非支配解 (Nondominated Solution)：

在多目标优化中，我们通常关注的是同时优化多个目标函数。设想我们有两个解 S1 和 S2，它们各自在若干个目标函数上有不同的值。我们说解S1​支配 解 S2 的条件是：对所有目标函数，S1 的表现都不差于 S2，并且至少在一个目标上优于 S2。

具体说来，设目标函数为 f1,f2,…,fn，那么S1支配S2的数学表达为：

• f1(S1)≤f1(S2)
• f2(S1)≤f2(S2)
• ...
• fn(S1)≤fn(S2)

且至少存在一个k使得 fk(S1)<fk(S2)。

如果解S1 没有被任何其他解支配，那么我们称 S1 是一个 非支配解

帕累托前沿 (Pareto Front)

帕累托前沿是由所有非支配解（第一前沿）组成的集合。 在二维间中，帕累托前沿可以通过绘制目标函数的值来可视化。帕累托前沿呈现一种弯曲形状，表明在不同目标之间进行权衡的需求。

比如 2023 年 C 题 228 优秀论文

​​

非支配排序 (Nondominated Sorting)

类似离散数学中偏序关系的概念：

在多目标优化过程中，种群中的解可以被分成若干个不同水平的帕累托前沿。这个过程称为 非支配排序。

1. 第一前沿（Pareto front 1）：不受其他解支配的解（也就是说，所有解中最优的那一层）。
2. 第二前沿（Pareto front 2）：这一层次上的解被第一前沿的解支配，但同一层上的解之间相互不支配。
3. 第三前沿（Pareto front 3）：依此类推。

快速非支配排序法（Fast nondominated sorting）

是一种快速计算每个解的支配数的一种算法，比传统非支配排序法降低了时间复杂度，不需要掌握原理，但是原理如下：

​​

二、拥挤距离方法(crowded-comparison)

解的多样性是非常重要的。拥挤距离衡量解的密度。拥挤距离越大，说明该解在目标空间中相对稀疏，可能更具代表性；反之，拥挤距离越小，说明该解周围有很多其他解，可能需要被淘汰。

拥挤距离的计算步骤

1. 按目标函数值排序：

   • 对于每个非支配前沿，分别对每个目标函数的值进行排序。假设我们有 M个目标函数，对每个目标函数m：

     将解按照目标函数 fm 的值进行升序排序。

2. 设置边界解的拥挤距离：

   • 对于每个目标函数的边界解（即最小值和最大值），我们将其拥挤距离设置为无穷大。这样可以确保这些解在选择过程中不会被淘汰。

3. 计算每个解的拥挤距离：

   • 对于每个解i在目标函数 m 下，计算其拥挤距离：

     \text{distance}(i, m) = \frac{f_{m}^{\text{next}} - f_{m}^{\text{prev}}}{f_{m}^{\text{max}} - f_{m}^{\text{min}}}

     其中：
     f_{m}^{\text{next}} 是解 i 在目标函数 m 排序后相邻的解的目标值。
     f_{m}^{\text{prev}} 是解 i 在目标函数 m 排序后相邻的解的目标值。
     f_{m}^{\text{max}} 和 f_{m}^{\text{min}} 分别是目标函数 m 的最大值和最小值。

   • ​​

4. 归一化和求和：

   对于每个解i 的总拥挤距离：

   \text{拥挤距离d}(i) = \sum_{m=1}^{M} \text{distance}(i, m)

   这样，每个解的拥挤距离就是其在所有目标函数下的距离值之和

​​

比较算子(Crowded-Comparison Operator)

种群中的每个个体都有两个属性：

• 非支配等级i​**_rank**：1 是最高等级
• 拥挤距离i​**_distance**

定义一个比较顺序​≺​_n：对于不同非支配等级的两个解，倾向于选择 rank 值更低的解，如果两个解的等级相同，倾向于选择拥挤距离更大或者说拥挤区域更小的解。

​​

三、NSGA-II 主循环

1. 初始化种群：

   随机生成一个初始种群 P0 ，包含 N个个体，每个个体都对应一个解。

2. 评估适应度：

   对种群中的每个个体进行评估，计算其在所有目标上的适应度值。

3. 非支配排序

4. 拥挤距离计算

5. 选择操作：

   根据非支配排序和拥挤距离来选择个体

6. 交叉与变异操作

7. 合并父代和子代形成 2N 并计算非支配排序及拥挤距离

   将父代种群 P​_t 和子代种群合并，得到新的种群P​_t​+Q​_t，在这个合并后的种群中，执行非支配排序及拥挤距离计算。

8. 选择新种群（2N 中选 N）（核心步骤） ：

   从合并后的种群 2N 中选择出N 个个体作为下一代种群P​_t+1。

   基于：比较算子(​Crowded-Comparison Operator)**

   ​​

   ​​

9. 终止条件：

   检查是否满足终止条件，否则返回第 2 步进入下一代。

四、NSGA-II 的使用

（1）在真正的使用中：

需要说清楚的：

• 选择交叉变异的操作是怎么做的

略写：

• NSGA-II 的快速非支配排序和拥挤距离

  比如：​

（2）如何得出最优解：

我们发现 NSGA-II 最后得出的前沿非支配解，而不是唯一解，还是需要我们筛选

比如 2023C228：

​​

所以我觉得可以使用 TOPSIS 对解进行优劣解排序

‍