用有向图指导大模型自动设计组合优化算法，效果显著优于现有方法。
DGA$_2$D: Directed Graph-Guided Automated Algorithm Design with Large Language Models
- 将算法设计建模为有向图上的路径搜索，节点是可替换的算子模块。
- 在12类组合优化问题上，平均解距改善达10.96个百分点。
- 适合想自动化设计优化算法的研究者或工程团队使用。
大型语言模型（LLM）的发展为求解NP难组合优化问题（COPs）的自动化启发式设计（AHD）带来了新机遇。然而，现有基于LLM的AHD方法大多受限于固定的求解器模板，仅能对孤立模块进行调优。实现完全自主、系统级的算法设计至关重要，但面临生成算子可靠性低、搜索空间巨大及信用分配无效等挑战。为此，本文提出一种有向图引导的自动化算法设计框架DGA$_2$D。该框架将开放的程序空间结构化为有向图，每个节点代表一个功能算子，可由多个候选代码实现实例化，有向路径构成完整的算法流水线。引入一阶路径依赖的信用分配机制，严格依据拓扑上下文评估代码变体。在涵盖复杂调度与路由等12类不同COP的大量实验中，DGA$_2$D表现出一致的实证优势，相比最先进的LLM基线，平均归一化差距降低最多达10.96个百分点。
原文摘要 · Abstract (English)
The rapid development of Large Language Models (LLMs) has opened new avenues for Automated Heuristic Design (AHD) for solving NP-hard combinatorial optimization problems (COPs). However, existing LLM-driven AHD methods are largely confined to rigid solver templates, relegating the search process to isolated module tuning. Transitioning to fully autonomous, system-level algorithm design is essential but fraught with low reliability of generated operators, extremely large search spaces, and ineffective credit assignment. To overcome these drawbacks, this paper proposes a Directed Graph-Guided Automated Algorithm Design framework, termed DGA$_2$D. It structures the open-ended program space as a directed graph, where each node represents a functional operator that can be instantiated using one of multiple candidate code implementations, while directed walks constitute complete algorithmic pipelines. A first-order path-dependent credit assignment mechanism is introduced to evaluate code variations strictly based on their topological context. Extensive experiments across 12 distinct COPs, ranging from complex scheduling to routing, demonstrate the consistent empirical advantages of DGA$_2$D. It reduces the average normalized gap by up to 10.96 percentage points compared to state-of-the-art LLM baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。