BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design

📄 arXiv: 2604.12898v1 📥 PDF

作者: Chuyang Xiang, Yichen Wei, Jiale Ma, Handing Wang, Junchi Yan

分类: cs.AI, math.CO

发布日期: 2026-04-14

备注: 24 pages, 11 figures

💡 一句话要点

提出BEAM以解决现有LHH在启发式设计中的局限性

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

关键词: 双层优化 遗传算法 蒙特卡洛树搜索 自适应记忆 启发式设计 算法进化 复杂代码生成

📋 核心要点

  1. 现有的LHH方法在优化单一函数时表现良好，但在生成完整求解器方面存在局限性，缺乏高层次的算法建模。
  2. 本文提出BEAM，通过将启发式设计视为双层优化问题，外层使用遗传算法进化算法结构，内层通过蒙特卡洛树搜索实现功能占位符。
  3. 实验结果显示，BEAM在多个优化问题上表现优异，特别是在CVRP混合算法设计中，最优性差距减少了37.84%。

📝 摘要（中文）

基于大型语言模型的超启发式（LHH）最近成为自动启发式设计的有效方法。然而，大多数现有LHH仅在预定义求解器内优化单一函数，其单层进化使其在编写完整求解器方面效果不佳。为此，本文将启发式设计重新表述为双层优化问题，提出了BEAM（双层记忆自适应算法进化）。BEAM的外层通过遗传算法进化高层算法结构，而内层则通过蒙特卡洛树搜索实现这些结构。实验结果表明，BEAM在多个优化问题上显著优于现有LHH，尤其在CVRP混合算法设计中将最优性差距减少了37.84%。

🔬 方法详解

问题定义：本文旨在解决现有LHH在启发式设计中的局限性，特别是在编写完整求解器时的低效性和探索能力不足的问题。

核心思路：通过将启发式设计重新表述为双层优化问题，BEAM的外层通过遗传算法进化高层算法结构，内层则利用蒙特卡洛树搜索实现这些结构，从而提高探索效率和生成能力。

技术框架：BEAM的整体架构包括外层的遗传算法模块和内层的蒙特卡洛树搜索模块，此外还引入了自适应记忆模块以支持复杂代码生成。

关键创新：BEAM的主要创新在于双层优化框架的引入，使得高层算法结构的进化与具体实现相结合，显著提高了探索效率，与传统单层进化方法形成鲜明对比。

关键设计：在设计中，关键参数包括遗传算法的选择机制和蒙特卡洛树搜索的策略，此外，自适应记忆模块的设计也为复杂代码生成提供了支持。具体的损失函数和网络结构细节在实验部分进行了详细描述。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，BEAM在多个优化问题上显著优于现有的LHH，特别是在CVRP混合算法设计中，最优性差距减少了37.84%。此外，BEAM设计的启发式算法在最大独立集求解器KaMIS上也表现出色，进一步验证了其有效性。

🎯 应用场景

该研究的潜在应用领域包括自动化算法设计、优化问题求解以及智能系统的开发。BEAM的创新方法能够有效提升启发式算法的设计效率，具有广泛的实际价值，未来可能在工业界和学术界产生深远影响。

📄 摘要（原文）

Large Language Model-based Hyper Heuristic (LHH) has recently emerged as an efficient way for automatic heuristic design. However, most existing LHHs just perform well in optimizing a single function within a pre-defined solver. Their single-layer evolution makes them not effective enough to write a competent complete solver. While some variants incorporate hyperparameter tuning or attempt to generate complex code through iterative local modifications, they still lack a high-level algorithmic modeling, leading to limited exploration efficiency. To address this, we reformulate heuristic design as a Bi-level Optimization problem and propose \textbf{BEAM} (Bi-level Memory-adaptive Algorithmic Evolution). BEAM's exterior layer evolves high-level algorithmic structures with function placeholders through genetic algorithm (GA), while the interior layer realizes these placeholders via Monte Carlo Tree Search (MCTS). We further introduce an Adaptive Memory module to facilitate complex code generation. To support the evaluation for complex code generation, we point out the limitations of starting LHHs from scratch or from code templates and introduce a Knowledge Augmentation (KA) Pipeline. Experimental results on several optimization problems demonstrate that BEAM significantly outperforms existing LHHs, notably reducing the optimality gap by 37.84\% on aggregate in CVRP hybrid algorithm design. BEAM also designs a heuristic that outperforms SOTA Maximum Independent Set (MIS) solver KaMIS.