Skip to content
返回搜索结果

稳健遗传算法 — 不确定性下的演化优化

提出者
Jin, Y. and Branke, J. (systematic formalization); roots in Holland (1975)
年份
2005 (systematic survey); earlier applications from late 1990s
类型
Metaheuristic evolutionary optimizer with robustness mechanism
类别
Simulation / optimization

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

字号

它有什么作用?

稳健遗传算法(RGA)扩展了标准遗传算法,旨在寻找不仅在标称设计点表现良好,而且在决策变量、参数或适应度评估中存在不确定性时也能表现良好的解决方案。通过将明确的稳健性度量纳入选择压力,RGA 在最优性与对扰动的敏感性之间取得了平衡,使其适用于现实世界变异性下的工程设计、调度和策略优化。

方法背后的直觉

经典的遗传算法搜索最优解,但“最优”在理想条件下可能在实践中很脆弱——输入的微小变化可能导致性能崩溃。稳健遗传算法提出一个不同的问题:哪些解决方案在预期的扰动范围内都能保持可接受的良好性能?它通过在适应度评估过程中采样候选解的邻域,并奖励那些性能退化平缓而非灾难性的候选解来实现这一点。其结果是演化出的种群不仅是最优的,而且在现实操作条件下是可靠地接近最优的。

历史学

进化计算中的稳健优化起源于 20 世纪 90 年代末,其驱动因素是工程设计问题,其中制造公差使得标称最优设计不可靠。Jin 和 Branke 在 2005 年的 IEEE 综述系统地梳理了该领域,区分了不确定性类型和稳健性度量。Beyer 和 Sendhoff 在 2007 年的综合性回顾中建立了将稳健进化算法与经典稳健优化联系起来的理论基础,巩固了稳健遗传算法作为进化计算的一个公认子领域。

何时使用

当优化问题涉及参数不确定性、有噪声的适应度评估,或者部署的解决方案必须在现实世界的可变条件下可靠地执行时,使用稳健遗传算法——例如,具有制造公差的工程设计、具有需求变异性的供应链调度,或适应度噪声显著的超参数调优。当经典优化产生的解决方案在技术上最优但实践中脆弱时,它尤其有价值。当问题纯粹是确定性的且计算预算紧张时,请勿使用 RGA——重复的适应度采样会显著增加评估成本。如果不确定性模型本身表征不佳,则应避免使用 RGA,因为稳健性保证取决于假定扰动分布的准确性。

局限与注意事项

  • 适应度评估成本随每代每个个体的扰动样本数量而增加,对于评估成本高昂的问题来说计算成本很高。
  • 稳健性结果仅与其假定的不确定性分布一样有效——错误指定的分布可能导致虚假信心。
  • 标准遗传算法算子(交叉、变异)在设计上并非固有稳健性,因此通常需要仔细的算子调整或代理辅助。
  • 没有收敛保证;该方法可能返回高质量但无法证明最优的稳健解决方案。
  • 由于有噪声的适应度景观,平衡种群多样性和收敛速度比确定性遗传算法更微妙。

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

优势

  • 找到既好又稳定的解决方案,减少在现实世界变异性下的性能下降。
  • 处理梯度下降的稳健优化失败的非凸、多模态和混合变量搜索空间。
  • 无需重新制定核心算法即可灵活适应不同的稳健性标准(期望、方差、最坏情况)。
  • 可以与 NSGA-II 或其他多目标框架结合,以明确权衡最优性与稳健性。
  • 适用于各种领域——工程、物流、金融、政策分析——只需最少的领域特定修改。

应用

  • 在制造和操作条件不确定性下的空气动力学形状优化
  • 具有随机需求和提前期变异性的供应链网络设计
  • 在梯度估计有噪声的情况下进行神经网络超参数调优
  • 具有不确定植物模型的动态系统的稳健控制器参数调优
  • 资产回报率分布估计不确定时的投资组合优化
  • 具有机器故障和加工时间变异性的生产环境中的稳健调度

使用方式

使用方式

1

定义搜索空间和不确定性的来源——这可能是目标函数评估中的噪声、问题参数中的不确定性(环境或制造公差),或决策变量实现中的变异性。指定稳健性是表述为最小化预期的性能下降(基于期望)还是界定最坏情况的结果(最小-最大或基于方差)。

2

为每个候选解 x 选择并构建一个稳健性度量。常见的选择包括:(1)扰动分布下的期望适应度 E[f(x+δ)];(2)均值和方差的加权组合 E[f] + λ·Var[f];或(3)有界不确定集上的最小最坏情况适应度 min。此度量将取代或补充标称适应度函数。

3

使用标准的遗传算法初始化方法(随机、拉丁超立方体或领域特定启发式)初始化 N 个候选解的种群。确保种群多样性以支持对稳健帕累托前沿的探索,尤其是在稳健性和标称最优性是竞争目标时。

4

对于每个个体,通过从不确定性分布中采样 s 个扰动场景并计算聚合适应度来估计稳健性度量。样本数量 s 在评估成本和统计精度之间进行权衡。可以使用重采样方法、显式平均或代理模型来管理计算成本。

5

像标准遗传算法一样应用选择(锦标赛、基于排名或适应度比例)、交叉和变异算子。由于稳健性可能与最优性冲突,多目标公式(例如,将平均性能和性能方差作为单独的目标与 NSGA-II 一起处理)很常见。聚类或适应度共享可以维持稳健-最优权衡前沿的多样性。

6

在满足停止标准(代数限制、适应度停滞或目标稳健性阈值)之前,跨代重复适应度评估和变异算子。输出最终种群或最佳稳健个体,报告标称性能和稳健性指标,以便从业者能够做出明智的选择。

常见陷阱

  • 每个适应度评估使用过少的扰动样本会产生不可靠的稳健性估计,导致选择脆弱的个体,就好像它们是稳健的一样。
  • 当最优性和稳健性确实冲突时,应用单一标量稳健性度量可能会丢失重要的权衡信息——首选多目标公式。
  • 在设置种群大小和样本数量时忽略计算预算限制,常常使 RGA 不切实际;对于昂贵的评估,请使用代理辅助变体或自适应采样。
  • 混淆随机遗传算法(具有无噪声适应度的随机搜索)与稳健遗传算法(具有明确的稳健性感知适应度)——它们解决的问题不同,不应互换使用。
  • 未能通过针对分布外扰动场景测试最终解决方案来验证稳健性声明,这可能会揭示报告的稳健性是针对训练不确定性模型过拟合的。

常见问题

稳健遗传算法与标准遗传算法有何不同?

标准遗传算法在每个候选解的标称设计点评估其适应度。稳健遗传算法通过在每个候选解周围的扰动邻域内采样来评估适应度,因此选择压力奖励那些平均表现良好(或在最坏情况下表现良好)的解决方案,而不仅仅是在一个点上表现良好。这改变了进化过程中“更好”的含义。

通常需要多少个扰动样本每个个体?

所需数量取决于噪声水平和稳健性估计所需的精度。在实践中,对于中等噪声问题,每代每个个体 10-50 个样本是常见的。对于评估成本非常高的情况,使用代理模型或多项式混沌展开来减少直接模拟调用,同时保持统计保真度。

稳健遗传算法可以与多目标优化结合吗?

是的——这是最实用的组合之一。将标称性能和稳健性度量(例如,性能方差)作为 NSGA-II 中的独立目标,可以得到稳健-最优权衡的帕累托前沿,使决策者能够选择他们愿意为稳定性牺牲多少最优性。

期望型稳健性与最坏情况稳健性在 RGA 中有何区别?

期望型稳健性最小化了采样场景下的平均性能下降——适用于不确定性频繁但有界的情况。最坏情况(最小-最大)稳健性保证了在定义不确定集内最不利扰动下的性能——在安全关键或对抗性环境中更受青睐,因为必须避免罕见但灾难性的故障。

当不确定性分布未知时,稳健遗传算法是否适用?

表征不充分的不确定性会削弱稳健解决方案的可靠性。当分布未知时,从业者应使用无分布或最坏情况公式处理有界不确定集,将 RGA 与敏感性分析相结合以识别哪些不确定输入最重要,并通过在各种场景下进行实证验证来验证解决方案。

相关方法

参考文献

  1. Jin, Y., Branke, J. (2005). Evolutionary optimization in uncertain environments — a survey. IEEE Transactions on Evolutionary Computation, 9(3), 303–317.

    打开 DOI 文献
    已复制。
  2. Beyer, H.-G., Sendhoff, B. (2007). Robust optimization — A comprehensive survey. Computer Methods in Applied Mechanics and Engineering, 196(33–34), 3190–3218.

    打开 DOI 文献
    已复制。