Skip to content
返回搜索结果

随机NSGA-II — 不确定性下的演化多目标优化

提出者
Deb, K. et al. (NSGA-II base); Hughes, E. J. and subsequent researchers for stochastic extensions
年份
2001–2002
类型
Evolutionary multi-objective optimization under uncertainty
类别
Simulation / optimization

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

字号

它有什么作用?

随机NSGA-II扩展了NSGA-II演化算法,以处理噪声、不确定或概率性的目标函数。通过对多个评估中的随机目标进行平均或抽样,它能识别对不确定性具有鲁棒性的帕累托最优解,使其适用于工程设计、供应链和政策优化等实际变异性至关重要的领域。

方法背后的直觉

NSGA-II是解决多目标问题中寻找多样化帕累托最优权衡解的最有效算法之一。然而,标准版本假设目标评估是确定性的。在实践中,模拟、实验和实际系统通常会返回带噪声的输出。随机NSGA-II通过重新采样或统计估计每个解的真实适应度来解决这个问题,然后应用NSGA-II的快速非支配排序和拥挤距离选择,以在存在噪声的情况下可靠地导航帕累托前沿。其核心思想是,通过预期性能(或其支配概率)对解进行排序,即使单个评估不可靠,也能恢复正确的帕累托结构。

历史学

NSGA-II由Deb等人于2002年提出,作为一种快速、精英的多目标遗传算法,并迅速成为基准标准。随机扩展不久后出现,由需要处理模拟噪声的工程优化社区推动。Hughes(2001)形式化了不确定性下的多目标排序。自2000年代中期以来,出现了许多变体,涵盖了自适应重采样、支配概率和噪声下的预期超体积改进。

何时使用

当您面临多目标优化问题,其中目标通过模拟、实验或噪声传感器进行评估,并且您需要对不确定性范围(而不仅仅是平均值)保持良好性能的解决方案时,请使用随机NSGA-II。它特别适用于制造公差下的工程设计、需求不确定性下的供应链优化以及具有随机输入的环保或政策模型。当目标是确定性且评估成本低廉时(标准NSGA-II就足够了),当可靠估计所需的重复次数使总预算不可行时,或者当问题是单目标时(请改用随机单目标EA),请勿使用它。当噪声分布高度非平稳或以违反独立同分布(i.i.d.)抽样假设的方式结构化时,请避免使用它。

局限与注意事项

  • 计算成本随每次评估的重复次数r、种群大小和代数而增加——对于昂贵的模拟可能变得过高。
  • 选择合适的重复次数r并非易事:太少会导致排序错误,太多会浪费预算。
  • 没有关于收敛到真实随机帕累托前沿的正式保证;质量取决于预算和噪声水平。
  • 使用估计均值进行支配比较会忽略估计不确定性,这可能在高噪声下导致错误排序。

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

优势

  • 通过非支配排序和拥挤距离,继承了NSGA-II强大的帕累托前沿发现和多样性保持能力。
  • 明确考虑目标函数噪声,生成在实际部署中鲁棒可靠的解决方案。
  • 灵活的框架——随机估计可以使用平均、基于分位数或支配概率的方法,而无需改变核心算法。
  • 适用于无法获得梯度信息的黑盒模拟模型。
  • 生成完整的帕累托前沿而非单一解决方案,为决策者提供明确的权衡选择。

应用

  • 鲁棒工程设计:在制造公差和载荷变异性下优化结构或机械部件。
  • 供应链网络设计:在需求和供应量随机时,最小化成本和提前期。
  • 环境政策建模:当气候影响模型具有不确定参数时,寻找帕累托最优的减排策略。
  • 投资组合优化:当资产收益遵循随机过程时,平衡预期收益和风险。
  • 医疗资源分配:在不确定的患者到达率和治疗效果下,优化成本和患者结果。
  • 能源系统规划:在随机风能和太阳能发电剖面下,确定可再生能源设施的规模。

使用方式

使用方式

1

定义具有k个随机目标函数f_1(x,xi), ..., f_k(x,xi)的多目标优化问题,其中xi表示从已知或估计分布中抽取的随机参数。指定决策变量边界、约束以及用于估计每个目标期望值的重复评估次数(重复次数)r。

2

在可行决策空间内随机初始化一个包含N个候选解的种群。对于每个个体,分配一个长度为k的适应度估计向量,并将其初始化为零。设置代数计数器g = 0,并定义停止准则(最大代数G_max或收敛容差)。

3

对于种群中的每个个体x_i,通过从其分布中抽样xi(或运行r次模拟重复)来精确评估每个目标f_j(x_i, xi) r次。将真实目标估计为样本均值:f_j_hat(x_i) = (1/r) * sum_{l=1}^{r} f_j(x_i, xi_l)。可选地计算标准误差以用于自适应重采样策略。

4

对估计的目标向量应用快速非支配排序。如果对于所有j,f_j_hat(x_a) <= f_j_hat(x_b)且至少有一个j严格小于,则解x_a支配x_b。将每个解分配到帕累托前沿等级F_1, F_2, ...,其中F_1包含不被任何其他解支配的解。

5

基于帕累托等级和拥挤距离(以保持多样性)使用二元锦标赛选择来选择父代。应用遗传算子——模拟二元交叉(SBX)和多项式变异——生成大小为N的子代种群Q。合并父代和子代种群(大小为2N),重新评估随机目标,重新排序,然后根据等级和拥挤距离选择前N个解。

6

增加g。如果g < G_max且帕累托前沿尚未稳定,则从随机评估步骤重复。否则,返回最终的帕累托前沿F_1作为非支配鲁棒解集。在目标空间中报告近似帕累托前沿以供决策者选择。

常见陷阱

  • 每个个体只使用一次重复(r=1)会将噪声视为信号,导致帕累托前沿在不同运行中高度不稳定——始终至少使用r >= 3并验证收敛性。
  • 忽略随机目标的方差可能会选择平均看起来不错但在尾部情景中表现不佳的解决方案——当尾部风险很重要时,考虑基于分位数或最坏情况的目标公式。
  • 在不检查噪声是否平稳的情况下应用该方法:如果噪声特性随决策变量值而变化,则需要自适应重采样或异方差模型。
  • 将输出的帕累托前沿视为最终决策,而不评估样本外鲁棒性——始终使用保留的模拟运行验证推荐的解决方案。

常见问题

每个个体评估应该使用多少次重复r?

一个常见的起点是r = 5–30,具体取决于目标的变异系数。将更多重复分配给精英解决方案或使用序贯抽样直到满足置信度标准的自适应策略效率更高。对于昂贵的模拟,r = 3–5和较大的种群通常是实际的折衷方案。

随机NSGA-II与标准NSGA-II有何不同?

唯一的结构差异在于目标评估:标准NSGA-II评估f(x)一次并假设结果是精确的,而随机NSGA-II评估f(x, xi) r次并使用样本均值(或另一个鲁棒性统计量)作为有效目标。所有排序、选择和遗传算子机制保持不变。

我可以使用随机NSGA-II与支配概率而不是平均目标吗?

是的。支配概率方法用随机支配概率取代确定性支配比较,这在高度噪声下更具原则性。这需要每次比较更多的样本,但在噪声相对于目标差异较大时会产生更可靠的排名。

如果我的模拟对于多次重复来说太昂贵怎么办?

考虑代理辅助方法:构建目标函数的高斯过程或神经网络元模型,用它来廉价地估计均值和方差,并应用预期改进或改进概率标准来代替重复的直接评估。

随机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. Hughes, E. J. (2001). Evolutionary multi-objective ranking with uncertainty and noise. In Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization (EMO 2001), Lecture Notes in Computer Science, vol. 1993, pp. 329–343. Springer.

    打开 DOI 文献
    已复制。