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

名称

非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm, NSGA），NSGA-II，多目标遗传算法（Multi-Objective Genetic Algorithm, MOGA）

分类

查看分类思维导图

非支配排序遗传算法是一种多目标优化算法，隶属于演化计算领域，而演化计算又是计算智能的一个分支。该算法与其他多目标演化算法密切相关，如 SPEA、PAES 和 MOEA/D。

• 计算智能
  • 演化计算
    • 多目标优化
      • 非支配排序遗传算法（NSGA）

策略

非支配排序遗传算法是一种基于种群的元启发式方法，通过选择、交叉和变异等操作对候选解集合进行迭代改进。其核心特征在于利用非支配排序，根据解的 Pareto 最优性对种群个体进行分层排序。

非支配排序

在每一代中，NSGA 根据解之间的支配关系将种群划分为不同的前沿。若一个解在至少一个目标上优于另一个解，且在其余目标上不劣于该解，则称该解支配另一个解。第一前沿包含所有非支配解，第二前沿包含仅被第一前沿中解所支配的解，依此类推。

拥挤距离

为了维持解集的多样性，NSGA 还会计算每个前沿内各个解的拥挤距离。拥挤距离用于衡量某个解在目标空间中周围解的稠密程度。算法会优先保留拥挤距离较大的解，以避免解过度聚集，并促进 Pareto 前沿的均匀分布。

选择与繁殖

NSGA 采用二元锦标赛选择来选取父代个体。选择过程同时考虑非支配等级和拥挤距离，优先选择来自更优前沿的解；若两个解位于同一前沿，则优先选择拥挤距离更大的解。选出的父代经过交叉和变异产生子代，随后与当前种群合并，并进入下一轮非支配排序。

过程

数据结构：

• 种群：候选解的集合
• 前沿：种群中由非支配解构成的一个子集
• 拥挤距离：衡量某个解在目标空间中周围解分布密度的指标

参数：

• 种群规模：种群中解的数量
• 交叉概率：两个父代解之间执行交叉操作的概率
• 变异概率：对某个解执行变异操作的概率
• 最大迭代代数：算法的停止条件

步骤：

1. 随机初始化种群。
2. 计算每个解的目标函数值。
3. 对种群执行非支配排序。
   1. 创建一个空的前沿集合。
   2. 找出所有非支配解，并将其加入第一前沿。
   3. 将第一前沿中的解从种群中移除。
   4. 重复步骤 3.2 和 3.3，直到所有解都被分配到某一前沿。
4. 计算各前沿内每个解的拥挤距离。
5. 使用二元锦标赛选择父代。
   1. 从种群中随机选取两个解。
   2. 选择前沿等级更优（等级值更低）的解。
   3. 若两个解处于同一前沿，则选择拥挤距离更大的解。
6. 通过交叉和变异生成子代。
7. 将当前种群与子代种群合并。
8. 重复步骤 3–7，直到达到最大迭代代数。
9. 返回非支配解集合（第一前沿）作为 Pareto 最优解集。

注意事项

优点：

• 能够在 Pareto 前沿上维持一组具有良好分布性的多样化解
• 适用于多个相互冲突目标的优化问题
• 不需要预先掌握问题结构或目标函数的特殊性质

缺点：

• 随着目标数量和种群规模增加，计算复杂度会显著提高
• 在处理高维多目标问题（通常超过 3–4 个目标）时可能面临困难
• 算法性能依赖于遗传算子及参数设置的合理性

启发式建议

种群规模

• 较大的种群规模有助于增强对搜索空间的探索能力，但也会带来更高的计算代价
• 通常可根据问题复杂度将种群规模设置在 50–200 之间

交叉概率与变异概率

• 较高的交叉概率（0.8–0.9）有助于增强对优良解的利用
• 较低的变异概率（0.01–0.1）有助于维持多样性并跳出局部最优
• 需要根据期望的探索—开发平衡对二者进行协调设置

遗传算子

• 应选择与解表示方式相匹配的交叉与变异算子（如二进制编码、实数编码）
• 可通过实验比较不同算子及其变体，以确定表现更优的组合方式

停止准则

• 应结合可用计算资源和时间预算设置最大迭代代数
• 可监测 Pareto 前沿的收敛情况；若在连续若干代内未观察到显著改进，则可提前终止算法

问题特定改进

• 可结合领域知识和问题特定启发式信息，以提升搜索效率
• 可根据具体问题特征，对遗传算子、选择机制或解表示方式进行定制化设计