非支配排序遗传算法三（NSGA-III）

非支配排序遗传算法三（NSGA-III）

引用

CSDN

1.

https://blog.csdn.net/tian9527663/article/details/146217177

NSGA-III（Non-dominated Sorting Genetic Algorithm III）是一种先进的多目标优化算法，由Kalyanmoy Deb和Himanshu Jain于2014年提出。该算法在NSGA-II的基础上进行了改进，引入了参考点和小生境保留策略，能够更有效地处理大规模多目标优化问题。本文将详细介绍NSGA-III算法的核心机制，包括参考点生成、归一化处理、关联操作和小生境保留等关键步骤。

参考点生成机制

一、参考点的数学定义与生成方法
NSGA-III通过预定义的参考点确保解集在目标空间中的多样性。这些参考点基于标准化超平面生成，具体定义如下：

1. 标准化超平面

• 对于 M 目标优化问题，标准化超平面是一个 (M−1) 维单位单纯形。
• 顶点位于各坐标轴截距为1处，例如三维目标空间中顶点为(0,1,0)、(0,0,1)(0,0,1)，构成等边三角形（图1）。
  

2. 参考点数量公式
   若每个目标轴划分为 p等分，则参考点总数 H由组合数公式计算：
   

• 三维目标（M=3）且 p=4 时，H=(3+4−1 4)=(6 4)=15。
• 参考点分布如图1所示，在标准化三角形内形成均匀网格。

3. 生成过程

• 使用Das和Dennis系统化方法，在超平面上生成均匀分布的参考点。
• 每个参考点对应一个权重向量，确保解集覆盖整个帕累托前沿。
  二、参考点的几何分布与可视化（图1解析）
  图1展示了三维目标空间中 p=4时的15个参考点，其分布特征如下：

1. 顶点与边界的参考点

• 顶点：三个顶点 (0,1,0)、(0,0,1)(0,0,1) 对应极端解（单一目标最优，其他目标为零）。
• 边中点：每条边被分为4段，边界上的参考点代表两个目标的权衡解（如 (0.75,0.25,0)）。

2. 内部参考点

• 内部点的坐标满足f1 +f2 +f3 =1，例如 (0.5,0.25,0.25)。
• 这些点引导算法探索目标间的平衡解，避免偏向某一目标。

3. 参考线与理想点

• 参考线：连接理想点（通常为原点）与参考点的射线，用于关联解集与参考方向。
• 理想点：假设为各目标的最小值，但在标准化超平面中常设为(0,0,0)，与实际前沿无关。
  三、NSGA-III中参考点的作用

1. 多样性维护

• 每个参考点关联一个子区域，算法优先选择与稀疏参考点最近的个体，确保解集广泛覆盖前沿。
• 通过小生境保留策略（Niche Preservation），避免相似解过度聚集。

2. 偏好融入

• 若用户提供偏好参考点（如特定区域的密集分布），算法会优先逼近这些区域，实现交互式决策支持。
• 例如，用户可在超平面上标记关注区域，NSGA-III将生成对应区域的解集。

3. 高维扩展性

• 参考点生成方法可扩展至任意目标数。例如，M=5 且 p=3 时，参考点数为 (5+3−1 3)=(7 3)=35。
• 通过调整 p控制分布密度，平衡计算开销与解集分辨率。
  NSGA-III通过系统化生成的参考点，在高维多目标优化中有效平衡收敛性与多样性。图1直观展示了三维目标空间中的参考点分布，其数学基础为组合数公式与单位单纯形几何。该方法的核心优势在于：

1. 适应性：支持用户偏好与自动生成两种模式。
2. 可扩展性：通过调整 pp 适应不同目标数与计算资源。
3. 理论保障：均匀分布的参考点确保解集覆盖整个帕累托前沿。

NSGA-III算法框架

自适应归一化机制

归一化算法框架

关联操作

1. 关联操作的目的
在NSGA-III中，关联操作的核心目标是确保种群成员在归一化后的目标空间中均匀分布，从而维持解集的多样性。通过将每个种群成员与预定义的参考点关联，算法能够系统性地引导搜索过程覆盖整个Pareto前沿，避免解集在某些区域过度集中。

3. 关联操作步骤

关联算法

算法流程

小生境保留操作

算法框架

计算复杂度

本文原文来自CSDN