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

📄 arXiv: 2604.24043v1 📥 PDF

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

分类: cs.AI

发布日期: 2026-04-27

备注: Preprint

💡 一句话要点

A2DEPT：基于大语言模型与进化程序树的自动化算法设计

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

关键词: 自动化算法设计 大语言模型 进化算法 组合优化 启发式算法

📋 核心要点

  1. 现有基于LLM的自动化启发式设计方法依赖固定算法模板，限制了系统级算法的表达能力，只能进行组件级调优。
  2. A2DEPT将LLM作为算法架构师，通过进化程序树进行系统级算法设计，并采用反馈驱动的修复机制保证生成算法的可执行性。
  3. 实验结果表明，A2DEPT在组合优化问题上优于现有基于LLM的自动化启发式设计方法，在标准基准测试中优化差距降低了9.8%。

📝 摘要（中文）

针对组合优化问题（COPs）启发式算法设计传统上需要大量领域知识这一挑战，本文提出了一种基于大语言模型（LLM）的自动化算法设计方法A2DEPT。A2DEPT将LLM视为系统级算法架构师，通过树状结构的进化搜索探索广阔的程序空间，结合混合选择和分层算子，实现完整算法的迭代优化。为了保证开放式生成的实用性，A2DEPT采用轻量级的程序维护循环，执行反馈驱动的修复以确保可执行性。实验结果表明，A2DEPT在标准和高度约束的基准测试中均优于具有代表性的基于LLM的基线方法，在标准基准测试中，相对于最强的竞争AHD基线，平均归一化最优性差距降低了9.8%。

🔬 方法详解

问题定义：论文旨在解决组合优化问题（COPs）中启发式算法设计高度依赖领域知识，且现有基于LLM的方法受限于固定算法模板，算法表达能力不足的问题。现有方法主要集中在组件级别的调优，无法实现系统级别的算法创新。

核心思路：论文的核心思路是将LLM视为系统级别的算法架构师，利用LLM的强大生成能力，结合进化算法的搜索能力，在更大的程序空间中探索更优的算法结构。通过进化程序树表示算法，并使用反馈驱动的修复机制保证生成算法的可执行性。

技术框架：A2DEPT的整体框架包含以下几个主要模块：1) 初始化：使用LLM生成初始的算法程序树种群。2) 进化搜索：通过混合选择（例如锦标赛选择和轮盘赌选择）和分层算子（例如交叉和变异）对种群进行进化。3) 程序维护：对生成的程序进行测试，并使用反馈驱动的修复机制修复不可执行的程序。4) 评估：评估生成算法的性能，并选择最优的算法。

关键创新：A2DEPT的关键创新在于：1) 将LLM应用于系统级别的算法设计，突破了现有方法的组件级别调优的限制。2) 采用进化程序树表示算法，能够表达更复杂的算法结构。3) 引入反馈驱动的修复机制，保证了生成算法的可执行性，使得开放式生成成为可能。

关键设计：A2DEPT的关键设计包括：1) 程序树的表示方式：程序树的节点表示算法的操作，例如变量赋值、循环、条件判断等。2) 混合选择策略：结合锦标赛选择和轮盘赌选择，平衡了种群的多样性和收敛速度。3) 分层算子：根据程序树的结构，设计了分层交叉和变异算子，保证了算法结构的有效性。4) 反馈驱动的修复机制：根据程序执行的错误信息，使用LLM对程序进行修复。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

A2DEPT在标准和高度约束的基准测试中均优于现有的基于LLM的自动化启发式设计方法。在标准基准测试中，A2DEPT相对于最强的竞争AHD基线，平均归一化最优性差距降低了9.8%。实验结果表明，A2DEPT能够有效地利用LLM的生成能力和进化算法的搜索能力，自动化设计出高性能的启发式算法。

🎯 应用场景

A2DEPT具有广泛的应用前景，可应用于各种组合优化问题，例如旅行商问题、车辆路径问题、调度问题等。该方法可以自动化生成高效的启发式算法，降低算法设计的门槛，加速算法开发过程，并有可能发现超越人工设计的更优算法。未来，A2DEPT可以扩展到其他类型的优化问题，例如连续优化问题和多目标优化问题。

📄 摘要（原文）

Designing heuristics for combinatorial optimization problems (COPs) is a fundamental yet challenging task that traditionally requires extensive domain expertise. Recently, Large Language Model (LLM)-based Automated Heuristic Design (AHD) has shown promise in autonomously generating heuristic components with minimal human intervention. However, most existing LLM-based AHD methods enforce fixed algorithmic templates to ensure executability, which confines the search to component-level tuning and limits system-level algorithmic expressiveness. To enable open-ended solver synthesis beyond rigid templates, we propose Automated Algorithm Design via Evolutionary Program Trees (A2DEPT), which treats LLMs as system-level algorithm architects. A2DEPT explores the vast program space via a tree-structured evolutionary search with hybrid selection and hierarchical operators, enabling iterative refinement of complete algorithms. To make open-ended generation practical, we enforce executability with a lightweight program-maintenance loop that performs feedback-driven repair. In experiments, A2DEPT consistently outperforms representative LLM-based baselines on both standard and highly constrained benchmarks. On the standard benchmarks, it reduces the mean normalized optimality gap by 9.8% relative to the strongest competing AHD baseline.