Automated Heuristic Design

Ask about this topic

Overview

Automated heuristic design studies how to create efficient rules that guide search and decision-making in problems such as vehicle routing, job scheduling, classical planning, and hardware design. Common approaches use genetic programming, evolutionary search, learned policies, or large language models to generate and refine executable heuristics using solver or simulator feedback. Current work increasingly combines these methods with memory, diverse heuristic portfolios, instance specialization, and transfer across tasks, while evaluating solution quality, runtime, and performance on held-out cases. A central challenge is balancing flexible search with reliable generalization, affordable evaluation, and guarantees such as execution safety or admissibility.

Latest papers

CardsList

84 papers15 papers in the last four weeks, up 200% on the four weeks before. 0.1% of all new papers.

Aug 4, 2026

Beyond Average Performance: Dynamic Instance Clustering and Specialized Algorithm Design in LLM-Assisted Evolutionary Search

Large Language Model-assisted Evolutionary Search (LES) has emerged as a powerful paradigm for automated algorithm design. However, existing LES methods primarily optimize for average performance, inherently directing search effort toward instances that contribute most to this metric while leaving others poorly served, resulting in weak tail robustness and limited real-world reliability. To address this limitation, we propose Dynamic Instance Clustering and Specialized Algorithm Design (DyCA), an LES framework with a feature-free, structure-aware mechanism for constructing reliable algorithm portfolios under heterogeneous instance distributions. DyCA treats instance clustering as a co-evolving component within the search process, reusing accumulated evaluation data as feature-free signals to progressively partition instances with similar algorithmic response patterns. The uncovered clusters decompose the mixed objective into a set of structure-aware sub-objectives, thereby enabling finer-grained and more adaptive guidance for specialized algorithm design. Experimental results across four algorithm design tasks with heterogeneous instances demonstrate that DyCA outperforms state-of-the-art LES baselines, improving tail robustness by an average of 15.2% and overall performance by 7.1% while maintaining competitive head performance.

Qinglong Hu, Qingfu Zhang, Fei Liu +3

Department of Computer Science, City University of Hong Kong, Hong Kong, China · Huawei Noah’s Ark Lab, China

Algorithm SelectionAutomated Algorithm DiscoveryAutomated Heuristic DesignClusteringLarge Language Model-Guided Optimization
AskPDF
Aug 1, 2026

Neuro-Evolved Heuristics for Variable Gapped Common Subsequence Identification

This study addresses the Variable Gapped Longest Common Subsequence Problem (VGLCSP), a variant of the classical longest common subsequence problem with additional gap constraints and applications in sequence alignment and time-series analysis. While the two-sequence version has been widely studied using dynamic programming, the generalized multi-sequence form is usually solved with beam search-based heuristics, whose hand-crafted designs often lack robustness. To overcome this limitation, we propose a learning-based approach for automatically designing more effective data-driven heuristics. The heuristics are represented by a neural network with predefined architecture, whose weights are optimized by a genetic algorithm within a neuro-evolutionary framework. The learning process alternates between weight optimization and evaluation within an iterative multi-source beam search procedure, a state-of-the-art method for the problem. Rather than constructing solutions directly, the neural network learns to guide the search process, producing a neuro-evolved heuristic. We further introduce an ensemble heuristic that combines the scores of learned and the best-performing hand-crafted heuristic. Integrated into the iterative multi-source beam search framework, the resulting hybrid approach outperforms existing methods on both synthetic benchmark instances and newly introduced real-world instances with data-driven gap constraints.

Marko Djukanović, Christian Blum, Aleksandar Kartelj +2

University of Nova Gorica, Nova Gorica, Slovenia · Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain · Faculty of Mathematics, University of Belgrade, Belgrade, Serbia +2

Automated Heuristic DesignNeural Combinatorial OptimizationNeuroevolution
AskPDF
Aug 1, 2026

DGA2_2D: Directed Graph-Guided Automated Algorithm Design with Large Language Models

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

Jiale Zhao, Zimu Chen, Sirui Mao +3

School of Automation Science and Electrical Engineering, Beihang University, Beijing, China · School of Computer Science and Engineering, Beihang University, Beijing, China

Automated Algorithm DiscoveryAutomated Heuristic DesignLarge Language Model-Guided OptimizationLLM-Based Program SynthesisCombinatorial Optimization
AskPDF
Jul 31, 2026

MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

Automated heuristic design (AHD) with large language models (LLMs) has produced strong heuristics for combinatorial optimization problems (COPs). Yet existing frameworks optimize for average performance on a small fixed dataset and steer the search with "verbal gradients" distilled from scalar better/worse feedback. No single heuristic dominates across instance distributions, and scalar feedback tells the LLM whether a heuristic improved, but not where in the instance space or why. We propose MOSAIC, a grid-based framework that adversarially co-evolves problem instances and specialist heuristics inside a Quality-Diversity (QD) archive indexed by structural instance features. Instances evolve to expose weaknesses of the current heuristics, and heuristics evolve to eliminate them by specializing to the newly exposed regions. Each archive cell keeps a specialist heuristic, representative instances, and insights explaining what works in its region, forming a persistent memory that accumulates over the evolutionary search. For each heuristic pair sampled from distant grid regions, an LLM-guided evolutionary loop generates discriminative instances, and a decision tree identifies the feature-space regions where each heuristic wins. A reflection LLM then contrasts the two heuristics to produce multi-directional insights that persist in those regions and guide crossover and mutation. The archive is simultaneously a co-evolved benchmark of discriminative instances and a pool of region specialist heuristics, from which greedy selection extracts a compact complementary portfolio. Across COPs, test sizes, and LLM backbones, the portfolio consistently outperforms state-of-the-art LLM-based AHD methods, and the co-evolved instances attain higher feature-space coverage and stronger heuristic discrimination than evolutionary instance-generation baselines.

Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

Georgia Institute of Technology

Algorithm SelectionAutomated Heuristic DesignLarge Language Model-Guided OptimizationCombinatorial OptimizationQuality-Diversity Optimization
AskPDF
Jul 30, 2026

LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency

Combinatorial problems appear in numerous industrial applications. A common approach is to formulate these problems as declarative constraint models that can subsequently be compiled to and solved by a range of back-end solvers. Recent work shows that Large Language Models (LLMs) can produce correct models from natural language, but even a correct model can be expensive to solve because performance remains sensitive to modelling choices. In this work, we investigate whether LLMs can automate performance-oriented model reformulation. Inspired by Automatic Heuristic Design (AHD), we use an evolutionary framework in which an LLM proposes candidate reformulations that are verified and benchmarked against the user-defined baseline model. We compare AHD-adapted search strategies that control which prior attempts, instructions, and measured feedback enter each prompt. Existing retention strategies prioritize recency or performance, but do not explicitly diversify the context. To cover this gap, we introduce Profile-Diverse Retention (PDR), which applies Maximal Marginal Relevance (MMR) to instance-level runtime vectors to retain behaviourally diverse attempts. We systematically evaluate the strategies on eight CSPLib problems using validation-based final model selection. The results show that: (i) iterative reformulation can produce substantial held-out speedups; (ii) strategies that keep the retained context diverse outperform those that retain only recent or the fastest attempts; and (iii) validation-based selection improves the held-out speedup of every strategy.

Kostis Michailidis, Dimos Tsouros, Nguyen Dang +1

1DTAI, KU Leuven, Belgium · University of Western Macedonia, Greece · University of St Andrews, United Kingdom

Automated Heuristic DesignEvolutionary OptimizationLarge Language Model-Guided OptimizationConstraint Programming
AskPDF
Jul 29, 2026

AutoPSO: A Meta-framework for Automated Particle Swarm Optimization

Particle swarm optimization (PSO) is a widely used metaheuristic, prized for its simplicity and small parameter set. Although decades of research have produced numerous PSO variants that improve performance by modifying key components (e.g., parameter schedules, swarm topologies, or updating rules), two fundamental challenges persist. First, most existing approaches are problem-specific and hand-crafted, leading to poor cross-task generalization and forcing practitioners to navigate an impractically large design space, which also hinders systematic reuse of prior effective mechanisms. Second, mainstream implementations remain CPU-bound, constraining scalability and substantially increasing computational cost in real-world applications. To address these challenges, we propose AutoPSO, a highly automated meta-framework for constructing customized PSO algorithms. AutoPSO formulates PSO-based optimization as a bi-level process: an outer search explores the joint space of effective PSO components, while an inner loop instantiates candidate variants to solve the target task and provide feedback. The outer search operates over a curated, open-design component pool, supporting flexible replacement of the component set and the outer optimizer. Crucially, by leveraging EvoX for population tensorization and batched evaluations, AutoPSO can efficiently assess thousands of particles within practical time budgets. Comprehensive experiments on numerical benchmarks and neuroevolution robotic control tasks demonstrate that AutoPSO consistently discovers novel PSO variants that significantly outperform strong baselines. Ablation and scalability studies further highlight the contribution of individual algorithmic components and confirm that AutoPSO achieves increasing performance gains with larger swarm sizes. Code is available at {https://github.com/EMI-Group/autopso}.

Xinmeng Yu, Jiaxin Gao, Jianguo Zhang +2

Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China · Pengcheng Laboratory, Shenzhen 518000, China · Department of Data Science and Artificial Intelligence, The Hong Kong Polytechnic University, Hong Kong SAR, China +2

Automated Algorithm DiscoveryAutomated Heuristic DesignParticle Swarm Optimization
AskPDF
Jul 26, 2026

SpecAHD: Localize to Specialize for Automated Heuristic Design in Large-Scale Routing Problems

LLM-based automated heuristic design (AHD) typically scores executable programs on complete instances or within fixed solver components. In large-scale routing problems, localized reconstruction reduces the size of each optimization task, but repair regions within the same incumbent can exhibit substantially different structures. One construction rule must therefore compromise across them. In this paper, we propose SpecAHD, a coupled bilevel framework for within-instance specialization. An upper-level search learns where to expose bounded repair regions, while a lower-level search evolves a complementary repertoire of executable heuristics for the induced repair tasks. The upper-level program determines the repair tasks seen by the lower level, while checked repair outcomes determine how upper-level programs are evaluated. The lower-level objective favors heuristics that perform well on average or solve tasks that the current repertoire handles poorly. For the repair tasks induced by a fixed upper-level program and a fixed lower-level candidate pool, this objective is monotone submodular, allowing greedy repertoire selection with a (1-1/e) approximation guarantee. Across four routing problems and multiple LLM backbones, SpecAHD reduces held-out objective cost by up to 57.7% against the strongest competing AHD baseline and outperforms the per-instance baseline envelope on most public instances.

Kezhao Lai, Yutao Lai, Hai-Lin Liu

School of Mathematics and Statistics, Guangdong University of Technology, China

Automated Heuristic DesignLarge Language Model-Guided OptimizationCombinatorial OptimizationVehicle RoutingBilevel Optimization
AskPDF
Jul 24, 2026

On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics

Selection Hyper-heuristics (HHs) automate algorithmic design by selecting from a set of low-level heuristics which one to apply at each stage of the optimisation process. Several impressive results have been recently rigorously proven regarding the performance of selection hyper-heuristics (HHs) for standard benchmark functions. However, the learning mechanisms employed by these HHs are considerably simplified compared to the machine learning techniques typically used in real world applications. In this paper we analyse a Reinforcement Learning Hyper-heuristic (RLHH) from the literature. The only previous result available proved that for a wide range of parameter settings, RLHH does not learn to select heuristics appropriately for the standard LeadingOnes benchmark function. In this paper, we rigorously prove that with appropriate parameter values RLHH equipped with two random local search operators, RLS_1 and RLS_2 optimises the LeadingOnes benchmark function in the best possible expected runtime achievable with the two operators up to lower order terms. Experiments show that for realistic problem sizes it is faster than the Generalised Random Gradient HH which was previously proven to also have optimal expected runtime up to lower order terms.

Pietro S. Oliveto, Zhenyu Wang, Peizhou Wu +1

Southern University of Science and Technology, 518055 Shenzhen, China

Reinforcement LearningAutomated Heuristic DesignMetaheuristic Optimization
AskPDF
Jul 22, 2026

AlphaRoute: Large Language Models as Semantic Optimizers for Multi-Objective Routing

Very Large Scale Integration (VLSI) global routing is an NP-hard combinatorial optimization problem requiring signal net assignment across capacity-constrained 3D grids while minimizing congestion, wirelength, and via transitions. Because traditional heuristics rely on static penalty schedules that fail on complex congestion topologies, we present AlphaRoute: a multi-objective adaptive search framework reformulating rip-up and reroute (R&R) into a dynamic optimization system. We introduce SHAP-based overflow decomposition to isolate per-net congestion, driving targeted subgraph extraction via 3D Dijkstra maze routing and an adaptive PathFinder policy. Crucially, AlphaRoute employs Large Language Models (LLMs) as semantic policy optimizers. Bounded by a deterministic knowledge graph, the LLMs interpret congestion metrics to dynamically adjust penalty parameters. Evaluated on ISPD 2025 benchmarks, AlphaRoute reduces overflow by 98.6% on MEMPOOL. On the constrained ARIANE design, we achieve an overflow of 146,109 (a 29.8x reduction in overflow over the state of the art), yielding a penalized score of S_orig = 0.0538 versus the State-of-the-art (SOTA) 1.780. These results demonstrate that superior algorithmic search geometry can overcome the latency of interpreted Python implementations.

Kabir Murjani, Mishri Bhavsar, Manish I. Patel +1

Department of Electrical Engineering, Institute of Technology, Nirma University, Ahmedabad, India · Department of Electronics and Communication Engineering, Institute of Technology, Nirma University, Ahmedabad, India · Center for Semiconductor Microelectronics, Arizona State University, Tempe, Arizona, USA

Automated Heuristic DesignLarge Language Model-Guided OptimizationElectronic Design AutomationCombinatorial OptimizationMulti-Objective Optimization
AskPDF
Jul 20, 2026

Automated Discovery Has No Universally Superior Harness

Autonomous discovery systems such as OpenEvolve and TTT-Discover are often used as general-purpose harnesses. However, in practice these are composite systems combining several design choices about archives, parent selection, exploration, and budget allocation into a single recipe. Because discovery runs are expensive and inherently stochastic, existing harnesses are often compared using too few independent trials to distinguish key methodological improvements from run-to-run variance. We systematically decompose OpenEvolve-style evolutionary search and the TTT-Discover search harness into its constituent components and systematically evaluate 30 budget-matched harnesses across 12 model-problem pairs using more than 3.1 million LLM rollouts and repeated-trial statistical analysis. Our results show that discovery harnesses have a generalization problem: No fixed harness is reliably superior across the evaluated model-problem pairs, and variants of OpenEvolve generally underperform simpler alternatives. Thus, harness choice is better viewed as a hyperparameter rather than as a universal recipe, and should be tailored to the specific problem and underlying model. We also find that early discovery progress predicts final performance, and use this property to present a budget-matched adaptive-allocation experiment that starts multiple harnesses, prunes weak partial runs, and reallocates compute to stronger survivors, outperforming both commitment to a randomly sampled fixed harness and a non-adaptive harness ensemble. Together, these results motivate shifting from fixed harness selection to online adaptation guided by early performance. We release all run pools including baseline null distributions for every model-problem pair as reusable statistical infrastructure against for future harness proposals.

Akshat Gupta, Jermaine Lei, Alexander Lu +2

UC Berkeley · MIT, MIT-IBM Watson AI Lab

Automated Algorithm DiscoveryAutomated Heuristic DesignEvolutionary OptimizationAgent Harness OptimizationLarge Language Model-Guided Scientific DiscoveryHyperparameter Optimization
AskPDF
Jul 19, 2026

CoEvoP&R: Co-Evolving Placement Objectives with Routing Feedback via Large Language Models

Analytical placers rely on differentiable objective functions to guide placement, typically combining intermediate surrogate metrics such as half-perimeter wirelength (HPWL) and cell-density penalties. However, these placement-stage surrogates remain misaligned with downstream routed and timing quality. Prior work reduces this gap with human-designed terms or learned black-box surrogates, but the former requires expert retuning and the latter is difficult to explain, debug, or deploy in analytical placement flows. CoEvoP&R addresses these limitations with a large language model (LLM)-based framework that automatically evolves analytical placement objectives. At each generation, the prompt combines the restricted objective interface, baseline context, and archived prior candidates with routing-related feedback from placement, timing proxy, and routing tools. The LLM proposes readable differentiable objectives, which are embedded and validated in DREAMPlace, evaluated through a timing proxy and an actual router, and stored with their feedback to guide later generations. Across eight ChiP-Bench Nangate45 designs and three seeds, CoEvoP&R reduces post-route routed wirelength and congestion by 16.9% and 36.7%, with gains of 0.70 ns in worst negative slack and a 912 ns reduction in total negative slack magnitude over native DREAMPlace. Across eight ICCAD 2015 Superblue designs, it reduces post-route routed wirelength and congestion by 5.4% and 23.2%. Code is available at https://github.com/FCHXWH823/CoEvoP-R.git.

Ruogu Chen, Weihua Xiao, Ramesh Karri +1

University of Alberta Edmonton, Alberta, Canada · New York University New York, New York, United States

Automated Heuristic DesignLarge Language Model-Guided OptimizationElectronic Design Automation
AskPDF
Jul 15, 2026

How to Guide LLM Generation: Dual-Surrogate Guided Search for Automated Heuristic Design

Large language models (LLMs) have made automated heuristic design (AHD) increasingly practical by generating executable heuristic code from task descriptions and evaluator feedback. Yet under a limited query and evaluation budget, search efficiency depends critically on a pre-generation decision. Before each LLM query and black-box evaluation, the system must choose which archived heuristics to reuse as parents and which generation operator should transform them. Existing methods typically choose such actions with predefined rules, leaving the expected outcome of each concrete operator-parent action only indirectly modeled. Therefore, we propose \fullmethod{} (\method{}), a surrogate-guided action-selection module for operator-parent selection in LLM-based AHD. \method{} guides the LLM code-generation process by scoring pre-generation actions with two complementary surrogates. Specifically, a transition surrogate is proposed to predict the latent distribution of the child representation induced by an operator-parent action, while an instance-conditioned utility surrogate is proposed to estimate the expected performance of sampled child latents. Moreover, we propose an uncertainty-aware acquisition rule that combines predicted utility, utility uncertainty, and transition uncertainty to select the next LLM generation action. Across a diverse heuristic-design suite, \method{} is competitive with strong LLM-AHD baselines, and ablation and action-selection analyses suggest that its behavior goes beyond simple archive ranking or fixed operator preferences.

Yuhan Wang, Chaoda Peng, Xingyu Wu +2

College of Mathematics and Informatics, South China Agricultural University · Department of Data Science and Artificial Intelligence, The Hong Kong Polytechnic University · College of Artificial Intelligence, Nankai University

Surrogate-Assisted OptimizationAutomated Heuristic DesignLarge Language Model-Guided OptimizationLLM Code Generation
AskPDF
Jul 13, 2026

RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience

Automatic Heuristic Design (AHD) has emerged as a transformative approach for solving combinatorial optimization problems. While recent Large Language Model (LLM)-based methods have shown promise, they predominantly rely on fixed evolutionary operators and struggle to effectively accumulate and reuse historical search experience. This paper proposes RefineEvo, a novel evolutionary framework that transforms AHD from a static trial-and-error process into a planning-guided, experience-driven system. RefineEvo introduces a Planner to dynamically schedule evolutionary operators and trigger refinement based on the current search state, and a Reflector to distill valuable lessons into a Bidirectional Experience Pool containing both positive insights and negative pitfalls. This synergistic framework enables the system to adapt its search tools to the evolving complexity of the problem and leverage trajectory-aware, situation-conditioned insights to guide generation. Experiments on several classic combinatorial optimization benchmarks demonstrate that RefineEvo consistently outperforms strong baselines. In particular, RefineEvo delivers superior solution quality while improving token efficiency, enabling more efficient and autonomous heuristic design.

Yang Wu, Junran Pan, Yifan Zhang +3

C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing · University of Chinese Academy of Sciences, Nanjing +1

Automated Heuristic DesignEvolutionary OptimizationLarge Language Model-Guided OptimizationCombinatorial Optimization
AskPDF
Jul 6, 2026

QDEvo: A Multi-Objective Quality-Diversity Framework for Automated Heuristic Design

The integration of Large Language Models (LLMs) with evolutionary computation has emerged as a powerful paradigm for automated heuristic design in combinatorial optimization. However, existing approaches suffer from mode collapse, converging to homogeneous populations that lack semantic diversity and fail to explore the full algorithmic space. We propose Quality-Diversity Evolution (QDEvo), a multi-objective framework that integrates Quality-Diversity optimization with LLM-driven heuristic search, maintaining an unbounded archive of semantically diverse algorithms using pre-trained code embeddings and incorporating hierarchical self-reflection to guide the evolutionary process. Extensive experiments across standard benchmarks and real-world industrial applications demonstrate that QDEvo significantly outperforms state-of-the-art methods in both Hypervolume and Inverted Generational Distance metrics. Our framework enables the discovery of heuristics that are simultaneously high-performing, computationally efficient, and semantically diverse, providing practitioners with a rich portfolio of solutions for complex optimization problems.

Nam Do Khanh, Nhat Nguyen Tran Minh, Dat Pham Vu Tuan +2

Hanoi University of Science and Technology Hanoi, Vietnam · George Mason University Fairfax, Virginia, USA

Automated Algorithm DiscoveryAutomated Heuristic DesignMetaheuristic OptimizationLarge Language Model-Guided OptimizationCombinatorial OptimizationQuality-Diversity Optimization+1
AskPDF
Jun 30, 2026

RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search

Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics for a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training distribution into the LLM-based evolutionary search loop. RAISE treats robust AHD as a constrained adversarial instance search problem: the outer loop evolves heuristics via LLM operators, while an LLM-free inner loop efficiently identifies hard instances within an epsilon-ball around the training instance set using a basis distribution parameterization with boundary projection. Comprehensive experiments on Online Bin Packing (OBP), Online Job Shop Scheduling (OJSP), and Online Vehicle Routing (OVRP) across five distribution families demonstrate that existing LLM-based AHD methods degrade by up to 19 times under distribution shift, while RAISE consistently maintains strong performance across all tested distributions and problem scales

Fei Liu, Alessio Figalli, Patrick Owen +1

University of Zurich · 2ETH Zurich

Distribution Shift RobustnessAutomated Algorithm DiscoveryAutomated Heuristic DesignLarge Language Model-Guided OptimizationRobust Optimization
AskPDF
Jun 12, 2026

MeEvo: Metacognitive Evolution Combined with Natural Evolution for Automatic Heuristic Design

Large Language Models (LLMs) have advanced Automatic Heuristic Design (AHD) by enabling heuristic generation through reasoning and code synthesis. In LLM-based AHD, the LLM reasons about algorithm design and generates executable heuristic code. Existing architectures adopt two main paradigms: Natural Evolution applies crossover and mutation to this code to explore diverse strategies, but discards the reasoning traces behind the design decisions, weakening knowledge retention; Metacognitive Evolution retains these reasoning traces and refines them through reflection, but lacks population-level recombination, limiting exploration. These limitations reduce search efficiency, stability, and solution quality on complex problems. To address this gap, we propose MeEvo, an AHD framework that cyclically couples Natural Evolution and Metacognitive Evolution with operator balance that shifts from exploration to exploitation. Natural Evolution explores heuristic code while recording LLM-generated reasoning traces, fitness values, errors and best heuristic into a shared history; Metacognitive Evolution then reflects on this history to generate improved heuristics that feed into the next Natural Evolution cycle. This design enables population-driven exploration and reflection-driven refinement to reinforce each other. Experiments on five optimization problems show that MeEvo achieves stronger performance and lower variance than tested LLM-based AHD architectures, especially on complex constrained tasks.

Zishang Qiu, Xinan Chen, Rong Qu +1

School of Computer Science, University of Nottingham Ningbo China, Ningbo, China · School of Computer Science, University of Nottingham, Nottingham, UK

Automated Heuristic DesignEvolutionary OptimizationLarge Language Model-Guided OptimizationMetacognition in Language Models
AskPDF
Jun 9, 2026

Learning Splitting Heuristics for Parallel String Solvers

String constraint solvers are crucial for reasoning about string-manipulating programs. However, many practical string constraints are undecidable, and real-world applications often present complex constraints that challenge current solvers. The rise of multi-core architectures offers an opportunity for parallel solving. A key parallel solving method is cube-and-conquer, in which the quality of splitting heuristics is critical to effectively dividing the search space. Unfortunately, manually designing the heuristics is labor-intensive, and handcrafted heuristics are often sub-optimal. This paper introduces a data-driven approach to automatically generating splitting heuristics. We frame the problem of selecting a splitting atom as a learning task, using features from input formulas and dynamic data from solver execution. We implement this approach in two popular string solvers, Z3seq and Z3str4, demonstrating that the learned heuristics outperform manually designed ones in the number of solved formulas and the average solving time.

Chenhao Gao, Peisen Yao

The State Key Laboratory of Blockchain and Data Security, Zhejiang University Hangzhou, China

Automated Algorithm DiscoveryAutomated Heuristic DesignLearning to OptimizeSatisfiability Modulo TheoriesConstraint Programming
AskPDF
Jun 3, 2026

Learning Admissible Heuristics via Cost Partitioning

Admissible heuristics are essential for optimal planning, yet learning them remains challenging due to the risk of overestimation. Cost partitioning combines multiple abstraction heuristics while preserving admissibility, but computing optimal partitions online is expensive. We propose a framework that learns to infer admissible cost partitions by leveraging the Lagrangian dual equivalence between cost partitioning and multiplier prediction. Planning states and patterns are encoded as labelled graphs, and an action-centric variant of the Weisfeiler-Leman algorithm extracts structural feature vectors. A deep architecture with axial self-attention and a softmax output layer maps these features to cost weights that satisfy the partition constraints by construction, ensuring admissibility. Experiments demonstrate reduced node expansions compared to suboptimal partitioning baselines while maintaining strict admissibility. To our knowledge, this is the first machine-learned heuristic guaranteed to be admissible.

Hugo Barral, Quentin Cappart, Marie-José Huguet +1

LAAS-CNRS, Universit´e de Toulouse, CNRS, INSA, Toulouse, France · Polytechnique Montr´eal, Montr´eal, Canada · UCLouvain, Louvain-la-Neuve, Belgium +1

Automated Heuristic DesignLearning to Optimize
AskPDF
Jun 1, 2026

LLM-Evolved Pattern Generators for Optimal Classical Planning

Learned heuristics have recently become a competitive alternative to traditional domain-independent heuristics for satisficing planning. Existing approaches, however, focus on improving search guidance rather than guaranteeing admissibility, which makes them unsuitable for optimal classical planning. We present the first method for learning domain-dependent heuristics that are admissible by design and thus preserve the optimality guarantees of A* search. Instead of learning a direct mapping from states to heuristic values, we learn to construct abstractions that induce admissible heuristics. We use an LLM-driven evolutionary program-synthesis framework to obtain, for each domain, a program that produces a pattern collection for any task in that domain, and we combine the resulting patterns admissibly via saturated cost partitioning. Empirically, the learned programs encode interpretable domain-specific insights, run with negligible overhead at test time and yield heuristics that match the coverage of state-of-the-art domain-independent baselines on several domains while evaluating each state substantially faster.

Windy Phung, Dominik Drexler, Arnaud Lequen +1

Linköping University, Sweden

Automated Heuristic DesignSymbolic Planning
AskPDF
May 30, 2026

LLM-Driven Co-Evolutionary Automated Heuristic Design for Bi-Component Coupled Combinatorial Optimization

While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing methods typically generate and evolve heuristics as a single operator or search strategy, limiting their ability to model strong coupling among multiple decision substructures in problems such as the Traveling Thief Problem (TTP) and the Traveling Purchaser Problem (TPP). In this work, we propose CoEvo-AHD, an LLM-driven dual-population co-evolutionary framework for automated heuristic design in coupled combinatorial optimization. Unlike prior methods that evolve individual heuristics in isolation, CoEvo-AHD leverages LLMs to co-evolve two closely related operator populations. A cooperative evaluation mechanism explicitly captures interactions between route and selection operators, while pairwise scoring and synergistic joint crossover help discover complementary operator logic for joint improvement across coupled decision subspaces. We further design a tool-invocation environment library that encapsulates frequently used core operations, such as local-search delta computation, into callable functions, enabling LLM-generated operators to use standardized interfaces instead of reimplementing inefficient and error-prone problem-specific loops. Experiments on TTP and TPP show that CoEvo-AHD automatically discovers cooperative heuristic combinations and achieves competitive solution quality against traditional heuristics.

Mingen Kuang, Xudong Deng, Xi Lin +3

Xi’an Jiao Tong University · Northwestern Polytechnical University

Automated Heuristic DesignEvolutionary OptimizationMetaheuristic OptimizationLarge Language Model-Guided OptimizationCombinatorial Optimization
AskPDF
May 28, 2026

LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning

Heuristic search is the dominant paradigm in symbolic AI planning, and the strongest heuristics are the result of decades of work by planning researchers. Recent work has shown that large language models (LLMs) can design heuristics for individual planning domains, but no LLM-generated heuristic has so far worked on arbitrary planning tasks. In this paper, we use evolutionary search to produce the first LLM-generated domain-independent heuristics that exceed the hand-engineered state of the art. We let an LLM mutate parent heuristics written in C++, store candidates in a MAP-Elites archive keyed on informedness and speed and calculate fitness scores by blending coverage with solving time. To place the evolved programs in context, we additionally benchmark a broad set of hand-engineered heuristics on their informedness-speed tradeoff, which to our knowledge has not been done before. On unseen testing domains, our best evolved heuristic solves more tasks than even the strongest baseline, with our full heuristic suite spanning the Pareto frontier of said tradeoff. We also find that seeding evolution from the trivial blind heuristic outperforms seeding from the strong FF heuristic, even when the resulting program is itself an FF variant, and that LLM reasoning effort affects how often candidates compile much more than the quality of those that do. Because the evolved programs are plain C++, they slot into existing planners as drop-in replacements and inherit the soundness and completeness guarantees of the underlying search.

Elliot Gestrin, Jendrik Seipp

Linköping University, Sweden

Automated Heuristic DesignSymbolic PlanningLLM-Based Program Synthesis
AskPDF
May 16, 2026

Latent Heuristic Search: Continuous Optimization for Automated Algorithm Design

The integration of Large Language Models (LLMs) into evolutionary frameworks has established a new paradigm for automated heuristic discovery. Despite their promise, these methods typically search in the discrete space of program syntax, relying on stochastic sampling to navigate a highly non-convex optimization landscape. This work proposes a continuous heuristic discovery framework that shifts optimization to a learned latent manifold. We employ an encoder to map discrete programs into continuous embeddings and train a differentiable surrogate model to predict performance, enabling gradient-based search. To regularize the optimization trajectory, an invertible normalizing flow maps these embeddings to a structured Gaussian prior, where we perform gradient ascent. The resulting optimized latent vectors are projected through a learned mapper into soft prompts, which condition a frozen LLM to synthesize novel executable heuristics. We evaluate the proposed method on the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), the Knapsack Problem (KSP), and Online Bin Packing (OBP). Empirical results demonstrate that continuous latent-space optimization achieves performance competitive with state-of-the-art discrete evolutionary baselines while offering a complementary methodological alternative for automated algorithm design. The implementation code is available at https://github.com/cheikh025/LHS.

Cheikh Ahmed, Mahdi Mostajabdaveh, Zirui Zhou

Huawei Technologies Canada, Burnaby, Canada

Surrogate-Assisted OptimizationAutomated Algorithm DiscoveryAutomated Heuristic DesignLarge Language Model-Guided OptimizationLLM-Based Program SynthesisLatent Space Optimization
AskPDF
May 11, 2026

Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies

LLM-based automatic heuristic design has shown promise for generating executable heuristics for combinatorial optimization, but existing methods mainly rely on delayed endpoint performance. We propose a teacher-aware evolutionary framework that uses independently trained learned optimization policies as behavioral teachers. Instead of deploying or imitating the teacher, our method queries it on states visited by candidate heuristic programs and uses its action preferences as local feedback for evolution. The resulting search discovers static executable heuristics guided by both task performance and teacher-derived behavioral signals. Experiments on scheduling, routing, and graph optimization benchmarks show that our method improves over performance-driven LLM heuristic evolution baselines while requiring no neural inference at deployment. These results suggest that learned optimization policies can be repurposed as behavioral feedback sources for automatic heuristic discovery.

Minyu Chen, Song Qin, Ling-I Wu +2

Shenzhen Technology University · Shanghai Polytechnic University · Shanghai Jiao Tong University

Automated Heuristic DesignEvolutionary OptimizationLLM-Based Program SynthesisProgram Synthesis
AskPDF
May 9, 2026

AHD Agent: Agentic Reinforcement Learning for Automatic Heuristic Design

Automatic heuristic design (AHD) has emerged as a promising paradigm for solving NP-hard combinatorial optimization problems (COPs). Recent works show that large language models (LLMs), when integrated into well-designed frameworks (i.e., LLM-AHD), can autonomously discover high-performing heuristics. However, existing LLM-AHD frameworks typically treat LLMs as passive generators within fixed workflows, where the model generates heuristics from manually designed, limited context. Such context may fail to capture state-dependent information (e.g., specific failure modes), leading to inefficient trial-and-error exploration. To overcome these limitations, we propose AHD Agent, a novel tool-integrated, multi-turn framework that empowers LLMs to proactively decide whether to generate heuristics or invoke tools to retrieve targeted evidence from the solving environment. To effectively train such a dynamic decision-making agent, we introduce an agentic reinforcement learning (RL) system, which leverages a novel environment synthesis pipeline to optimize a compact model's generalizable AHD capabilities. Experiments across eight diverse domains, including four held-out tasks, demonstrate that our 4B-parameter agent matches or surpasses state-of-the-art baselines using much larger models, while requiring significantly fewer evaluations. Model and inference scaling analysis further reveals that AHD Agent offers an effective trajectory toward truly autonomous heuristic design.

Haoze Lv, Ning Lu, Ziang Zhou +1

Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation, Department of Computer Science and Engineering, Southern University of Science and Technology · Zhongguancun Academy · The Hong Kong University of Science and Technology

Agentic RLAutomated Heuristic DesignCombinatorial OptimizationLLM Agent TrainingRL for Tool Use
AskPDF
May 8, 2026

HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization

Large Language Models have recently emerged as a promising paradigm for automated heuristic design for NP-hard combinatorial optimization problems. Despite this progress, existing LLM-based methods typically rely on monolithic workflows constrained by rigid templates, thereby restricting memory-guided exploration and triggering premature convergence to local optima. To design an autonomous and collaborative architecture, we introduce HMACE, a Heterogeneous Multi-Agent Collaborative Evolution framework that reconceptualizes heuristic search as an organizational design problem. HMACE decomposes each evolutionary generation into an autonomous, role-specialized loop with four coordinated agents: a Proposer for strategy exploration, a Generator for executable heuristic synthesis, an Evaluator for empirical assessment, and a Reflector for archive-backed memory update. By coupling behavior-aware retrieval, lightweight candidate filtering, and fitness-grounded archive updates, HMACE guides the search toward diverse and promising heuristic behaviors while avoiding redundant evaluations. Extensive evaluations on representative COPs, including TSP, Online BPP, MKP, and PFSP, show that HMACE achieves a favorable quality-efficiency trade-off compared to state-of-the-art single-agent and multi-agent baselines. In the matched LLM-driven reference comparison, HMACE achieves the lowest average gaps on TSP and Online BPP (0.464% and 0.223%, respectively), while requiring only 0.13M and 0.42M tokens for the two tasks, substantially fewer than the compared baselines.

Yuping Yan, Jirui Han, Fei Ming +2

School of Engineering Westlake University

Multi-Agent LLM SystemsMulti-Agent System OptimizationAutomated Heuristic DesignEvolutionary OptimizationLarge Language Model-Guided OptimizationCombinatorial Optimization+1
AskPDF
May 7, 2026

CoupleEvo: Evolving Heuristics for Coupled Optimization Problems Using Large Language Models

Many real-world optimization problems consist of multiple tightly coupled subproblems whose solutions must be coordinated to achieve high overall performance. However, existing large language model driven automated heuristic design approaches are limited to single-problem settings. In this paper, we propose CoupleEvo. CoupleEvo proposes three evolutionary coordination strategies to evolve heuristics for coupled optimization problems: the sequential strategy evolves heuristics for one subproblem after the other; the iterative strategy alternates the evolution of heuristics for different subproblems over successive generations; and the integrated strategy evolves heuristics for all problems simultaneously. The approach is evaluated on two representative coupled optimization problems. Experimental results show that decomposition-based strategies (sequential and iterative) provide more stable convergence and higher solution quality, while the integrated evolution strategy suffers from increased search complexity and variability. These findings highlight the importance of coordinating evolutionary search across interdependent subproblems and demonstrate the potential of LLM-driven heuristic design for complex coupled optimization problems. The code is available: https://github.com/tb-git-kit-research/CoupleEvo.

Thomas Bömer, Bastian Amberg, Max Disselnmeyer +1

Karlsruhe Institute of Technology Karlsruhe, Germany

Automated Heuristic DesignEvolutionary OptimizationMetaheuristic OptimizationLarge Language Model-Guided Optimization
AskPDF
May 7, 2026

Back to the Beginning of Heuristic Design: Bridging Code and Knowledge with LLMs

Large language models (LLMs) have recently advanced automatic heuristic design (AHD) for combinatorial optimization (CO), where candidate heuristics are iteratively proposed, evaluated, and refined. Most existing approaches search over executable programs and distill insights from execution feedback to guide later iterations. Because this process moves from low-level implementations to high-level principles, we refer to it as a bottom-up paradigm. We argue that this view is incomplete and introduce a complementary top-down perspective: knowledge becomes the primary search object and code merely instantiates and tests it, making what is learned explicit and reusable across problems and trajectories. We formalize this shift through a statistical-learning view that exposes a distortion--compression trade-off, and instantiate it in both population-based and tree-based AHD frameworks. Across CO and tasks beyond it, knowledge-first search improves discovery efficiency, transfer, and generalization, often outperforming code-centric pipelines, while combining both strategies yields further gains. Our results suggest that progress in AHD depends on iteratively constructing and evolving interpretable hypotheses that retain value beyond a single search trajectory.

Nguyen Viet Tuan Kiet, Bui Dinh Pham, Dao Van Tung +2

Hanoi University of Science and Technology, Hanoi, Vietnam · University of Sydney, Sydney, Australia

Automated Heuristic DesignLarge Language Model-Guided OptimizationCombinatorial Optimization
AskPDF
Apr 27, 2026

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

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.

Bin Chen, Shouliang Zhu, Beidan Liu +4

The Institute of Intelligent Computing, University of Electronic Science and Technology of China, Chengdu 611731, China · College of Systems Engineering, National University of Defense Technology, Changsha 410073, China · Academy of Military Medical Sciences, Beijing 100071, China

Automated Algorithm DiscoveryAutomated Heuristic DesignMetaheuristic OptimizationLarge Language Model-Guided OptimizationGenetic ProgrammingLLM-Based Program Synthesis+1
AskPDF
Apr 14, 2026

BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design

Large Language Model-based Hyper Heuristic (LHH) has recently emerged as an efficient way for automatic heuristic design. However, most existing LHHs just perform well in optimizing a single function within a pre-defined solver. Their single-layer evolution makes them not effective enough to write a competent complete solver. While some variants incorporate hyperparameter tuning or attempt to generate complex code through iterative local modifications, they still lack a high-level algorithmic modeling, leading to limited exploration efficiency. To address this, we reformulate heuristic design as a Bi-level Optimization problem and propose BEAM (Bi-level Memory-adaptive Algorithmic Evolution). BEAM's exterior layer evolves high-level algorithmic structures with function placeholders through genetic algorithm (GA), while the interior layer realizes these placeholders via Monte Carlo Tree Search (MCTS). We further introduce an Adaptive Memory module to facilitate complex code generation. To support the evaluation for complex code generation, we point out the limitations of starting LHHs from scratch or from code templates and introduce a Knowledge Augmentation (KA) Pipeline. Experimental results on several optimization problems demonstrate that BEAM significantly outperforms existing LHHs, notably reducing the optimality gap by 37.84% on aggregate in CVRP hybrid algorithm design. BEAM also designs a heuristic that outperforms SOTA Maximum Independent Set (MIS) solver KaMIS.

Chuyang Xiang, Yichen Wei, Jiale Ma +2

Automated Heuristic DesignLarge Language Model-Guided OptimizationBilevel Optimization
AskPDF
Apr 9, 2026

PyVRP+^+: LLM-Driven Metacognitive Heuristic Evolution for Hybrid Genetic Search in Vehicle Routing Problems

Designing high-performing metaheuristics for NP-hard combinatorial optimization problems, such as the Vehicle Routing Problem (VRP), remains a significant challenge, often requiring extensive domain expertise and manual tuning. Recent advances have demonstrated the potential of large language models (LLMs) to automate this process through evolutionary search. However, existing methods are largely reactive, relying on immediate performance feedback to guide what are essentially black-box code mutations. Our work departs from this paradigm by introducing Metacognitive Evolutionary Programming (MEP), a framework that elevates the LLM to a strategic discovery agent. Instead of merely reacting to performance scores, MEP compels the LLM to engage in a structured Reason-Act-Reflect cycle, forcing it to explicitly diagnose failures, formulate design hypotheses, and implement solutions grounded in pre-supplied domain knowledge. By applying MEP to evolve core components of the state-of-the-art Hybrid Genetic Search (HGS) algorithm, we discover novel heuristics that significantly outperform the original baseline. By steering the LLM to reason strategically about the exploration-exploitation trade-off, our approach discovers more effective and efficient heuristics applicable across a wide spectrum of VRP variants. Our results show that MEP discovers heuristics that yield significant performance gains over the original HGS baseline, improving solution quality by up to 2.70% and reducing runtime by over 45% on challenging VRP variants.

Manuj Malik, Jianan Zhou, Shashank Reddy Chirra +1

Singapore Management University Singapore, Singapore · Nanyang Technological University Singapore, Singapore · University of Oxford Oxford, England

Automated Heuristic DesignLarge Language Model-Guided OptimizationVehicle RoutingEvolutionary OptimizationGenetic Algorithms
AskPDF