💻 computer science

A2DEPT: Large Language Model-Driven Automated Algorithm Design via Evolutionary Program Trees

A2DEPT 是一个新颖的框架，它在进化程序树搜索中将大语言模型作为系统级架构师，并结合反馈驱动的修复机制，自主合成用于组合优化问题的完整可执行算法，从而克服现有方法的僵化模板限制并实现卓越性能。

原作者： Bin Chen, Shouliang Zhu, Beidan Liu, Yong Zhao, Tianle Pu, Huichun Li, Zhengqiu Zhu

发布于 2026-04-28

📖 1 分钟阅读☕ 轻松阅读

原作者： Bin Chen, Shouliang Zhu, Beidan Liu, Yong Zhao, Tianle Pu, Huichun Li, Zhengqiu Zhu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你需要解决一个庞大而复杂的谜题，比如为1000辆卡车规划配送路线，或者为拥有数百台机器的工厂制定生产调度。这些就是“组合优化问题”。传统上，人类必须坐下来，手工设计解决这些谜题的规则（启发式方法）。这一过程缓慢，需要深厚的专业知识，而且一旦问题发生细微变化，这些规则往往就会失效。

最近，我们开始利用大语言模型（LLMs）——也就是那些能撰写文章和代码的同一种人工智能——来协助设计这些规则。然而，大多数现有方法就像给人工智能一套附带固定说明书的乐高积木。人工智能可以替换几块积木（微调特定规则），但无法改变城堡的整体结构。如果说明书要求“建造一座塔”，即使建造一座桥梁效果更好，人工智能也无法决定去建桥。

A2DEPT 应运而生。

作者提出了一种名为 A2DEPT（基于进化程序树的自动化算法设计）的新系统。与其给人工智能一本固定的说明书，不如让它充当一位总建筑师，能够从地基开始重新设计整座建筑。

以下是其工作原理，使用简单的类比说明：

1. 思想的“树”

想象一棵家谱树，但树中的不是人，而是计算机程序。

树根： 过程始于几个基本的、可运行的程序。
树枝： 人工智能对某个程序进行修改（变异），从而创建一个“子代”程序。
选择： 就像在自然界中一样，某些子代程序比其父代更擅长解决谜题。系统会保留最好的程序，并尝试进一步改进它们。

2. “施工队”（三位工人）

为了确保人工智能不会仅仅生成随机且错误的代码，A2DEPT 使用三种特定类型的“工人”来编辑程序：

修补匠（微调）： 这位工人进行微小且安全的调整。他们可能会微调一个数字，或修复特定函数内的逻辑错误，就像打磨工具一样。他们不改变蓝图。
建筑师（宏观变异）： 这位工人行事大胆。他们可以拆掉一面墙并建造一个新房间。他们可以重写程序的主流程，改变算法从头到尾的思考方式。
混合者（交叉）： 这位工人从两个不同的“父代”程序中提取最佳想法，将它们融合在一起，创造出混合子代。

3. “安全检查员”（程序维护）

这里存在最大的挑战：当你让人工智能重新设计整个程序时，它往往会生成无法运行的代码。它可能会调用一个不存在的函数，或者忘记导入某个库。

问题： 过去，如果代码出错，整个尝试就会被丢弃。
A2DEPT 的解决方案： 他们增加了一位安全检查员。在新代码进行测试之前，这位检查员会扫描它。如果缺少某部分（例如缺失的函数），检查员会立即要求人工智能补写该缺失部分。如果代码存在死胡同（从未被使用的部分），检查员会将它们剔除。
结果： 这确保了人工智能生成的几乎每一个新想法实际上都是可运行的，从而使搜索过程能够持续进行而不会陷入停滞。

4. “智能过滤器”（混合选择）

系统如何决定保留哪些程序？

“足够好”规则： 有时，一个新程序虽然比父代稍差，但它拥有独特的结构，可能会在未来带来突破。A2DEPT 使用一种智能过滤器（基于一种称为“模拟退火”的方法），允许这些“有潜力但目前较差”的程序存活下来，防止系统陷入局部困境。
“多样性”规则： 它还会从历史树中随机挑选一些旧的、有趣的程序，以保持搜索的多样性，确保它们不会变得千篇一律。

他们发现了什么？

作者在各种困难的谜题上测试了 A2DEPT（例如卡车路线规划、工作调度以及在图中寻找模式）。

更好的结果： 与那些受限于固定模板的先前人工智能方法相比，A2DEPT consistently 找到了更优的解决方案。
差距缩小： 在标准测试中，与次优方法相比，它将人工智能解决方案与完美解决方案之间的“差距”缩小了近 10%。
鲁棒性： 即使在非常困难的问题上（例如具有有限电池和严格时间窗口的电动汽车），其他方法往往无法找到任何有效解，而 A2DEPT 依然表现良好。

总结

A2DEPT 就像是从数字填色画套装（你只能改变颜色）升级到了完整的建筑工地（你可以改变墙壁、屋顶和地基）。通过将智能进化搜索与能够即时修复错误代码的“安全检查员”相结合，它使人工智能能够发明全新的方法来解决复杂问题，而不仅仅是微调旧方法。

以下是论文《A2DEPT：基于进化程序树的自动算法设计大语言模型驱动》的详细技术总结。

1. 问题定义

本文针对组合优化问题（COP）的**自动启发式设计（AHD）**挑战。

背景：COP（如旅行商问题 TSP、车辆路径问题、作业车间调度）通常属于 NP 难问题。传统的手工启发式设计劳动密集型，需要深厚的领域专业知识，且往往难以泛化到不同的问题变体。
当前局限：近期基于大语言模型（LLM）的 AHD 方法（如 FunSearch、EoH、ReEvo）已展现出潜力，但存在一个关键瓶颈：它们在固定的算法模板内运行。它们仅优化孤立的启发式组件（如评分函数），而保持周围的求解器逻辑（控制流、回溯、迭代结构）僵化不变。
差距：这种“受模板束缚”的方法限制了系统层面的创新。如果模板对特定问题不是最优的，启发式方法无法进行补偿。此外，从优化单个组件转向设计完整求解器（即开放式自动算法设计，AAD）引入了巨大的挑战：
1. 可执行性不稳定：自由形式的代码生成常导致编译错误、依赖缺失或运行时失败。
2. 搜索空间爆炸：有效且高性能的完整程序空间巨大且稀疏。
3. 信用分配不透明：当整个算法在进化时，很难将性能提升归因于特定的代码变更。

2. 方法论：A2DEPT 框架

作者提出了A2DEPT（基于进化程序树的自动算法设计），这是一个将大语言模型视为系统级架构师以进化完整、可执行求解器程序的框架。

核心组件：

树结构进化搜索：
- 不同于基于种群的方法，A2DEPT 维护一个全局搜索树，其中节点代表可执行程序、其得分及生成元数据。
- 混合选择策略：
  - 模拟退火（SA）主选择：利用 Metropolis 准则，基于得分改进接受父子对，保留“父子细化”关系。
  - 玻尔兹曼补充选择：为防止搜索坍缩为贪婪的 Top-k 选择并保留多样性，系统使用玻尔兹曼概率从全局树历史中采样额外的父代。这使得“表现不佳但结构有潜力”的分支得以幸存。
- 动态再退火：如果搜索停滞（ $N_{stall}$ 代内无改进），则提高温度以恢复探索能力。
具有自适应调度的分层算子：
为了解决信用分配问题并实现结构变更，A2DEPT 使用三个层级的算子，并根据反馈进行自适应调度：
- 微调（ $m_1$ ）：对可变策略函数进行局部编辑（例如，细化评分公式），同时保持接口不变。
- 宏突变（ $m_2$ ）：对求解器的入口点和控制流进行自上而下的重新设计。它允许大语言模型调用未定义的辅助函数，这些函数稍后会被填充。
- 语义交叉（ $e_1$ ）：通过整合两个父代的互补机制，合成混合程序。
- 自适应调度：基于子节点的性能变化（ $\bar{r}$ ）更新特定节点的权重向量。成功的算子得到加强，而不成功的算子受到惩罚，从而在微细化和宏重构之间动态转移搜索精力。
程序维护机制（可执行性强制）：
为了使开放式生成具有实用性，A2DEPT 包含一个轻量级、反馈驱动的修复循环：
- 结构化表示：程序被分为不可变的“前言”（导入、常量）和可变的“函数注册表”。
- 依赖修复：当生成的程序调用未定义的函数（宏突变中常见）时，构建依赖图。大语言模型被迭代提示以实现缺失的函数，直到程序达到“依赖封闭”状态。
- 剪枝：剪除不可达代码，以防止死逻辑的累积。

3. 主要贡献

范式转变：从受模板束缚的 AHD（优化组件）转向开放式 AAD（进化完整求解器），解锁了更丰富的设计空间。
A2DEPT 框架：引入了一种具有混合选择（SA + 玻尔兹曼）和分层算子的树结构进化搜索，以导航庞大的程序空间。
可靠性机制：提出了一种用于自动依赖修复的程序维护循环，以及一种结构化表示，以确保进化过程中的可执行性。
实证验证：证明了在多样化的 NP 难基准测试中，其性能始终优于最先进的基于大语言模型的基线。

4. 实验结果

作者在六个 NP 难问题上评估了 A2DEPT：MIS、CVRP、CFLP、FJSP（标准基准）以及CEVRPTW、MRCPSP（高约束基准）。

标准基准上的性能：
- A2DEPT 在所有任务上均优于所有基于大语言模型的基线（FunSearch、EoH、ReEvo、MCTS-AHD）。
- 关键指标：在标准基准上，相对于最强的竞争 AHD 基线，A2DEPT 将平均归一化最优性间隙降低了 9.8%。
- 它取得了与非大语言模型参考（如在 MIS 问题上与 Gurobi 相当）相媲美的结果。
高约束问题：
- 在 CEVRPTW 和 MRCPSP 上，A2DEPT 实现了最低的**不可行率（IR）**和最佳的最优性间隙，证明了其在碎片化搜索空间中的鲁棒性，而其他方法往往难以找到有效解。
泛化能力：
- A2DEPT 在不同的设计框架（如引导局部搜索）和实例分布上表现出强大的泛化能力。
- 消融研究证实，移除任何组件（例如玻尔兹曼采样、自适应调度或维护循环）都会显著降低性能。
连续优化：
- 该框架也被成功应用于连续领域（常微分方程求解、求根、控制策略），发现了新颖的数值求解器，其在刚性问题上优于专门的工业基线（如 LSODA）。

5. 意义与影响

系统级创新：A2DEPT 证明了大语言模型可以充当“算法架构师”，而不仅仅是代码生成器。通过进化整个求解器逻辑，它能够发现组件级调整无法实现的结构范式（例如，从构建性贪婪启发式转变为迭代局部搜索框架）。
可扩展性：该框架解决了开放式代码生成的“可执行性”瓶颈，使得在没有人工干预的情况下进化复杂的多模块程序成为可能。
未来方向：论文指出，虽然当前方法局限于研究原型规模，但该途径为自动合成工业级求解器铺平了道路，前提是未来的工作能够解决大型代码库的模块化管理和静态类型检查问题。

总之，A2DEPT代表了自动算法设计的重大飞跃，从“填充固定模板的空白”转向“撰写整本书”，从而在解决复杂组合优化问题时实现了卓越的性能和鲁棒性。