Skip to content
返回搜索结果

NSGA-II — 非支配排序遗传算法 II

年份
2002
类型
Evolutionary multi-objective optimisation algorithm

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

NSGA-II(非支配排序遗传算法 II)是多目标进化优化(multi-objective evolutionary optimisation)的标准参考算法,由 Deb、Pratap、Agarwal 和 Meyarivan 于 2002 年提出。它不将多个冲突的目标折叠成单一分数,而是通过多代进化候选解的种群,并利用快速非支配排序和拥挤距离度量(crowding distance metric)来保持多样性,从而返回一组帕累托最优的权衡解——即帕累托前沿(Pareto front)。

方法背后的直觉

设想您想设计一种产品,要求其成本尽可能低且耐用性尽可能高。成本越低通常意味着耐用性越差,因此不存在唯一的完美答案——存在一系列合理的折衷方案。NSGA-II 的工作方式类似于一个由相互竞争的设计组成的种群:每一代都会淘汰在所有目标上都被其他设计支配的较差设计,并分散保留下来的设计,使其覆盖完整的权衡范围,而不是聚集在某个角落。经过足够多的代数后,您将得到一个丰富的选择菜单——帕累托前沿——从中选择符合您优先级的平衡方案。

历史学

NSGA-II 由 Kalyanmoy Deb 及其印度理工学院坎普尔分校的同事于 2002 年发表,作为原始 NSGA (Srinivas & Deb, 1994) 的修正且大幅改进的版本。关键创新包括:复杂度为 O(MN²) 的快速非支配排序程序、用于在没有共享参数的情况下维持解多样性的显式拥挤距离算子,以及精英选择机制。2002 年发表在《IEEE Transactions on Evolutionary Computation》上的论文已成为进化计算领域引用率最高的研究之一,并将 NSGA-II 确立为多目标进化算法的事实基准。后来的变体——NSGA-III (2014) 及其他——将该框架扩展到多目标问题。

何时使用

当一个问题有两个或多个冲突的目标函数,且无法在不丢失信息的情况下将它们合并为单一标准时,即可应用 NSGA-II。决策变量可以是连续的、二元的或分类的,并且不需要对目标景观(objective landscape)进行任何分布假设。该算法适用于工程设计、资源分配、调度和投资组合问题,在这些问题中,一系列权衡解比单一最优解更有用。需要足够多的代数(通常是几百代或更多)才能实现良好的前沿覆盖;运行代数太少是主要的失败模式。

局限与注意事项

  • 当目标数量超过三或四个时,性能会下降——拥挤距离在高维空间中成为一个糟糕的多样性度量。
  • 需要仔细调整种群大小和代数;代数太少会导致前沿覆盖不足。
  • 涉及昂贵仿真的目标函数评估会使该算法在计算上成本高昂。
  • 结果是随机的:不同的随机种子可能产生不同的帕累托前沿,因此建议进行多次运行和统计比较(例如,使用超体积指标)。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 在单次运行中产生一组多样化的帕累托最优权衡解,避免了因使用不同权重而重复优化的需要。
  • 快速非支配排序的运行时间为 O(MN²)(M 为目标数,N 为种群大小),对于中等规模问题是可行的。
  • 精英选择确保早期找到的优秀解不会被丢弃。
  • 适用于连续、二元和分类决策变量,无需分布假设。
  • 已在工程、运筹学和计算科学领域得到广泛验证。

应用

  • 工程设计:同时最小化机械部件的重量和最大化结构强度。
  • 环境与能源系统:在电网或可再生能源规划中平衡成本、排放和可靠性。
  • 医疗保健与运筹学:同时优化患者等待时间、资源利用率和成本的调度。
  • 金融领域的投资组合优化和商业领域的项目选择:权衡回报、风险和流动性。
  • 机器学习中的超参数调优:优化准确性与模型复杂性或推理时间。

使用方式

使用方式

1

通过在边界内随机(或按设计)采样决策变量来创建候选解的种群。种群大小的设置要足够大,以确保从一开始就跨目标空间具有多样性。

2

每个候选解都被解码为决策变量值,并评估每个目标函数。结果是每个个体的目标分数向量。当目标涉及仿真或昂贵的模型时,此步骤通常是计算瓶颈。

3

通过非支配排序对解进行排序:第一前沿包含所有在每个目标上均不被其他解支配的解;第二前沿包含仅被第一前沿中的解支配的解;依此类推。在每个前沿内,计算拥挤距离分数以衡量一个解与其邻居的隔离程度——拥挤距离越大,表示该解占据前沿中一个不那么拥挤的区域。

4

精英选择策略(elitist selection strategy)将当前种群与后代合并,并保留 N 个最佳个体,按顺序填充前沿,并使用拥挤距离来打破最后一个可接受前沿内的平局。这保证了前几代中找到的优秀解永远不会丢失。

5

选定的个体通过遗传算子进行繁殖——二元锦标赛选择(binary tournament selection)、模拟二元交叉(simulated binary crossover, SBX)和多项式变异(polynomial mutation)——产生新的后代种群。这些算子在探索有希望的解的邻域的同时,保持有意义的变化。

6

通过“评估-进化-重复”的步骤,执行指定代数的迭代。收敛性通过帕累托前沿的目视检查或超体积指标(hypervolume indicator)跟踪来判断。最终输出是逼近真实帕累托前沿的非支配解集。

常见陷阱

  • 运行少于几百代通常会产生不完整的帕累托前沿;如果计算预算紧张,请考虑加权单目标优化。
  • 将单目标问题视为多目标问题是不必要的——应使用单目标优化器。
  • 未能设置合理的变量边界会导致种群永远无法达到搜索空间的可行或有意义的区域。
  • 仅报告帕累托前沿中的一个解而不披露整个前沿,会隐藏 NSGA-II 旨在揭示的权衡结构。

常见问题

NSGA-II 需要多少代数?

没有普遍规则,但运行少于几百代通常会产生不完整的帕累托前沿。一种实用的方法是绘制超体积指标随代数的变化图,并在其稳定时停止。如果计算预算不允许,加权单目标优化器是更安全的选择。

什么是帕累托前沿?

帕累托前沿是无法在不使至少一个其他目标恶化的情况下改进任何一个目标的一组解。NSGA-II 近似这个前沿,为您提供完整的平衡折衷方案菜单,而不是单一答案。

NSGA-II 能处理两个以上的目标吗?

可以,但拥挤距离——多样性机制——在目标数量超过三或四个(“多目标”区域)时效果会变差。对于具有五个或更多目标的问题,通常首选 NSGA-III 或基于分解的算法,如 MOEA/D。

NSGA-II 是确定性的吗?

否。遗传算子和初始种群涉及随机性,因此不同随机种子的不同运行可能会产生不同的帕累托前沿近似。最佳实践是多次运行算法,并使用超体积指标比较前沿质量。

相关方法

参考文献

  1. Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

    打开 DOI 文献
    已复制。
  2. Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.

    打开 DOI 文献
    已复制。