DGA₂D: Directed Graph-Guided Automated Algorithm Design with Large Language Models

2026/08/01 by Jiale Zhao, Zimu Chen, Sirui Mao +3
Computer Science · #cs.AI #cs.NE

paper · pdf

46 pages, 5 figures, including supplementary material

arxiv created 2026/08/01 · arxiv updated 2026/08/04

Abstract

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₂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₂D. It reduces the average normalized gap by up to 10.96 percentage points compared to state-of-the-art LLM baselines.

Citations

• Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization
• HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs
• ConfigX: Modular Configuration for Evolutionary Algorithms via Multitask Reinforcement Learning
• A Systematic Survey on Large Language Models for Algorithm Design
• LLaMEA: A Large Language Model Evolutionary Algorithm for Automatically Generating Metaheuristics
• Learning from Offline and Online Experiences: A Hybrid Adaptive Operator Selection Framework
• ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
• AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration
• POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
• Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method