CVaR-RMD: CVaR Selection Pressure for Robust Metaheuristic Discovery

📄 arXiv: 2610.25697v1 📥 PDF

作者: Ruodai Cui, Li Niu

分类: cs.AI

发布日期: 2026-10-19

备注: Accepted to Findings of EMNLP 2026. Code: https://github.com/BeyondHeaven/CVaR-RMD

💡 一句话要点

提出CVaR-RMD以解决启发式算法选择中的风险敏感性问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 启发式算法 条件价值风险 自动化算法设计 鲁棒性 组合优化

📋 核心要点

  1. 现有方法在选择启发式算法时，往往依赖于平均性能，导致在不同条件下的表现不稳定，容易忽视极端失败情况。
  2. CVaR-RMD框架通过引入条件价值风险的概念，利用大型语言模型对启发式程序进行变异，并在多样化评估条件下进行排名，从而增强算法的鲁棒性。
  3. 实验结果表明，CVaR-RMD在三个组合优化领域中显著提高了算法的上尾性能和稳定性，降低了失败率，同时保持了良好的平均性能。

📝 摘要（中文）

近年来，大型语言模型被用于通过迭代程序搜索发现启发式算法，展现出自动化算法设计的潜力。然而，基于平均性能的候选选择可能在不同实例、随机种子和问题规模上表现不佳，因为均值目标可能掩盖罕见但严重的失败。我们提出了CVaR-RMD，这是一种风险敏感的进化框架，利用大型语言模型变异可执行的启发式程序，并根据异构评估条件下的经验条件价值风险对候选进行排名。在三个组合优化领域中，基于CVaR的选择提高了上尾性能，降低了失败率，同时保持了竞争力的平均性能。这些提升在更大的未见实例和独立策划的领域内基准测试中依然有效。

🔬 方法详解

问题定义：论文旨在解决在启发式算法选择中，基于平均性能的评估方法可能导致在不同实例和条件下的表现不佳，尤其是忽视了极端失败的风险。

核心思路：提出CVaR-RMD框架，通过条件价值风险（CVaR）来评估和选择启发式算法候选，强调在多样化评估条件下的表现，从而提高算法的鲁棒性和稳定性。

技术框架：该框架包括三个主要模块：首先，利用大型语言模型对现有启发式程序进行变异；其次，在多个异构评估条件下进行性能测试；最后，根据CVaR对候选进行排名和选择。

关键创新：CVaR-RMD的核心创新在于引入条件价值风险作为选择标准，与传统的基于均值的选择方法相比，更加关注算法在极端情况下的表现，从而提高了整体鲁棒性。

关键设计：在设计中，关键参数包括评估条件的多样性和CVaR的计算方式，损失函数则侧重于降低失败率，同时保持平均性能的竞争力。

🖼️ 关键图片

fig_0
img_1
img_2

📊 实验亮点

实验结果显示，CVaR-RMD在三个组合优化领域中，相较于传统方法，显著提高了上尾性能，降低了失败率，且在更大的未见实例上依然保持良好表现。这表明该方法在实际应用中具有较强的适应性和稳定性。

🎯 应用场景

该研究的潜在应用领域包括组合优化、调度问题和资源分配等复杂问题的自动化算法设计。通过提高算法的鲁棒性，CVaR-RMD能够在实际应用中有效应对不确定性和极端情况，具有重要的实际价值和未来影响。

📄 摘要（原文）

Large language models have recently been used to discover heuristics through iterative program search, offering a promising approach to automated algorithm design. However, candidates selected by average performance may degrade across instance families, random seeds, and problem scales because mean-based objectives can obscure rare but severe failures. We propose CVaR-RMD, a risk-sensitive evolutionary framework that uses an LLM to mutate executable heuristic programs and ranks candidates by empirical conditional value-at-risk over heterogeneous evaluation conditions. Across three combinatorial optimization domains, CVaR-based selection improves upper-tail performance and reduces failure rates while maintaining competitive mean performance. These gains persist on larger unseen instances and independently curated within-domain benchmarks