arXiv:2604.12898cs.AImath.CO2026-04被引 1

BEAM用双层进化生成高效启发式算法,显著提升求解性能。

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

  • 外层用遗传算法优化算法结构,内层用蒙特卡洛树搜索实现细节。
  • 在CVRP问题上优化差距降低37.84%,优于现有最先进方法。
  • 适合需要自动设计复杂启发式算法的研究者与工程师。

基于大语言模型的超启发式(LHH)近年来成为自动设计启发式算法的有效方法。然而,多数现有LHH仅在预定义求解器中优化单一函数时表现良好,其单层演化难以生成完整的高性能求解器。尽管部分变体引入超参数调优或通过迭代局部修改生成复杂代码,仍缺乏高层次算法建模,导致探索效率有限。为此,我们将启发式设计重新建模为双层优化问题,提出贝姆(BEAM):一种双层记忆自适应算法演化框架。外层利用遗传算法(GA)对含函数占位符的高层算法结构进行演化,内层则通过蒙特卡洛树搜索(MCTS)实现这些占位符。我们进一步引入自适应记忆模块以促进复杂代码生成。为支持复杂代码生成评估,我们指出从零开始或使用代码模板的局限性,并提出知识增强(KA)流程。在多个优化问题上的实验表明,BEAM显著优于现有LHH,尤其在混合型车辆路径问题(CVRP)启发式设计中,平均最优性差距降低37.84%。此外,BEAM设计的启发式算法超越了当前最优最大独立集(MIS)求解器KaMIS。

原文摘要 · Abstract (English)

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.

算法演化启发式设计大模型应用

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。