A2DEPT：基于进化程序树的LLM驱动自动化算法设计

摘要

为组合优化问题（COP）设计启发式算法是一项基础而具挑战性的任务，传统上需要大量领域专业知识。近来，基于大语言模型（LLM）的自动化启发式设计（AHD）展现出在极少人工干预下自主生成启发式组件的前景。然而，现有大多数基于LLM的AHD方法为保证可执行性而强制使用固定算法模板，这把搜索限制在组件级调参，限制了系统级算法表达能力。为实现超越刚性模板的开放式求解器合成，我们提出基于进化程序树的自动化算法设计（A2DEPT），它把LLM视为系统级算法架构师。A2DEPT通过带混合选择与分层算子的树结构进化搜索探索庞大的程序空间，实现对完整算法的迭代精炼。为使开放式生成切实可行，我们用执行反馈驱动的轻量程序维护循环来保证可执行性。实验中，A2DEPT在标准及高度受限基准上均持续优于代表性的LLM基线。在标准基准上，相比最强的竞争AHD基线，它把平均归一化最优性差距降低了9.8%。

A2DEPT：基于进化程序树的LLM驱动自动化算法设计：论文配图 — 图 2：A2DEPT 框架概述。 (a) 范式从模板绑定的 AHD（LLM在固定求解器框架内填充启发式槽）转变为开放式 AAD（LLM综合完整的求解器程序）。 (b) A2DEPT 维护全局搜索树，并通过混合选择和自适应算子调度以批量方式扩展边界。 (c) 程序维护管道通过依赖性分析、迭代修复和修剪来增强可执行性，生成用于在 𝒟\mathcal{D} 上进行评估的可执行程序。