BEAM：面向LLM驱动启发式设计的双层记忆自适应算法演化

摘要

基于大语言模型的超启发式方法（LHH）近来已成为自动启发式设计的高效途径。然而，大多数现有LHH只能在预定义求解器内优化单个函数。其单层演化使其不足以写出称职的完整求解器。尽管一些变体引入超参数调优或尝试通过迭代局部修改生成复杂代码，但仍缺乏高层的算法建模，导致探索效率有限。为解决这一问题，我们将启发式设计重新表述为双层优化问题，并提出BEAM（双层记忆自适应算法演化）。BEAM的外层通过遗传算法（GA）演化带有函数占位符的高层算法结构，内层则通过蒙特卡洛树搜索（MCTS）实现这些占位符。我们进一步引入自适应记忆模块以促进复杂代码生成。为支持复杂代码生成的评估，我们指出从零开始或从代码模板启动LHH的局限性，并引入知识增强（KA）流水线。在多个优化问题上的实验结果表明，BEAM显著优于现有LHH，在CVRP混合算法设计中总体将最优性差距降低37.84%。BEAM还设计出优于SOTA最大独立集（MIS）求解器KaMIS的启发式算法。

BEAM：面向LLM驱动启发式设计的双层记忆自适应算法演化：论文配图 — 图 2：我们的 BEAM 管道。外层通过遗传进化设计启发式（代码）结构（the heuristic()）；内层通过MCTS设计函数(func_i()s)。每次设计新功能时都会进行评估，以确保功能质量。整个遗传进化结束后，打印出最好的启发式（代码结构+函数），并将函数（func_i()s）存储到自适应存储器中，以供将来的代码结构直接调用。正如我们的实验（表 V）所示，BEAM 的性能优于 Google 的 AlphaEvolve [9]。