RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search

📄 arXiv: 2606.31801v1 📥 PDF

作者: Fei Liu, Alessio Figalli, Patrick Owen, Nicola Serra

分类: cs.AI

发布日期: 2026-06-30

💡 一句话要点

提出RAISE框架以解决LLM优化启发式设计的鲁棒性问题

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

关键词: 自动化启发式设计 大型语言模型 鲁棒性 对抗实例搜索 进化搜索 在线调度 资源优化

📋 核心要点

  1. 现有LLM-AHD方法在固定训练实例集上优化启发式，面对真实世界的分布变化时性能显著下降。
  2. RAISE框架通过将受限的最坏情况实例搜索整合到LLM驱动的进化搜索中，提升了启发式设计的鲁棒性。
  3. 实验结果显示，RAISE在五个分布族的在线问题上表现优异，性能保持稳定，显著优于传统方法。

📝 摘要（中文）

基于大型语言模型（LLM）的自动化启发式设计（AHD）在发现高质量启发式方面取得了显著进展。然而，现有方法在固定训练实例集上优化启发式，面对真实世界的分布变化时可能会出现严重失效。本文提出了鲁棒对抗实例搜索（RAISE）框架，将受限的最坏情况实例搜索整合到LLM驱动的进化搜索循环中。RAISE将鲁棒AHD视为一个受限的对抗实例搜索问题：外部循环通过LLM操作进化启发式，而无LLM的内部循环则高效识别训练实例集周围的困难实例。综合实验表明，现有LLM-AHD方法在分布变化下性能下降高达19倍，而RAISE在所有测试的分布和问题规模中均能保持强劲表现。

🔬 方法详解

问题定义：本文旨在解决现有LLM-AHD方法在面对分布变化时的鲁棒性不足问题。现有方法在固定的训练实例集上优化启发式，导致在真实应用中性能显著下降。

核心思路：RAISE框架的核心思路是将鲁棒AHD视为一个受限的对抗实例搜索问题，通过在进化搜索中引入最坏情况实例的搜索，增强启发式的适应性和鲁棒性。

技术框架：RAISE的整体架构包括外部循环和内部循环。外部循环利用LLM操作进化启发式，而内部循环则在训练实例集周围的epsilon-ball内高效识别困难实例，使用基础分布参数化和边界投影技术。

关键创新：RAISE的主要创新在于将受限的最坏情况实例搜索与LLM驱动的进化搜索相结合，形成了一种新的鲁棒AHD方法。这一设计使得启发式在面对分布变化时能够保持稳定性能。

关键设计：RAISE框架中，内部循环的epsilon-ball范围和基础分布参数化是关键设计元素，确保了对困难实例的有效识别。此外，边界投影技术的应用提升了搜索的效率和准确性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，现有LLM-AHD方法在分布变化下性能下降高达19倍，而RAISE在所有测试的分布和问题规模中均能保持强劲表现，显示出其在鲁棒性方面的显著提升。

🎯 应用场景

该研究的潜在应用领域包括在线调度、物流优化和资源分配等问题，能够为实际场景中的启发式算法设计提供更为鲁棒的解决方案。未来，RAISE框架有望在更多复杂的动态环境中得到应用，提升算法的适应性和效率。

📄 摘要（原文）

Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics for a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training distribution into the LLM-based evolutionary search loop. RAISE treats robust AHD as a constrained adversarial instance search problem: the outer loop evolves heuristics via LLM operators, while an LLM-free inner loop efficiently identifies hard instances within an epsilon-ball around the training instance set using a basis distribution parameterization with boundary projection. Comprehensive experiments on Online Bin Packing (OBP), Online Job Shop Scheduling (OJSP), and Online Vehicle Routing (OVRP) across five distribution families demonstrate that existing LLM-based AHD methods degrade by up to 19 times under distribution shift, while RAISE consistently maintains strong performance across all tested distributions and problem scales