Source-linked AI summary
ES-AHD: An Evolution Strategy Framework for Automatic Heuristic Design
Yutao Lai, Kezhao Lai, Hai-Lin Liu, Yuping Wang, Ping Guo
TL;DR
LLM-driven automatic heuristic design is hindered by blind individual-level mutation and imbalanced exploration. ES-AHD integrates evolution-strategy ideas through semantic recombination and stochastic temperature adaptation, and experiments report strong performance across TSP scales.
Problem
LLM-driven automatic heuristic design relies on individual-level mutation that produces blind search and an imbalance between exploration and exploitation.
Method
ES-AHD uses LLMs to extract Core Insights from elite heuristics for center-guided sampling and maps ES covariance adaptation to stochastic temperature updates.
Results
ES-AHD achieves a Top-4 Average Training Score of -6.209, outperforming EoH (-6.345) and FunSearch (-6.364), while achieving the best validation results on Val20, Val50 (6.449), and Val100 (8.911).
Takeaways & Limitations
Experiments on TSP instances of varying scales report superior optimization accuracy and robust generalization for ES-AHD compared with evaluated baselines.
Abstract
from arXiv · showhide
In this paper, we introduce ES-AHD, a novel framework that fundamentally integrates Evolution Strategy (ES) into Large Language Model (LLM)-driven Automatic Heuristic Design (AHD). Existing evolutionary approaches predominantly rely on random, individual-level mutation, leading to blind search and an imbalance between exploration and exploitation. To address these issues, ES-AHD introduces two core mechanisms. First, Semantic Recombination via LLMs discards traditional point-to-point reproduction. By leveraging the LLM's contextual reasoning to explicitly extract core insights from top-performing individuals, the algorithm establishes a promising semantic search direction. This transforms random code mutation into targeted, center-guided sampling inspired by ES. Second, Stochastic Covariance Adaptation via Temperature Sampling dynamically addresses the exploration-exploitation dilemma. By mapping the covariance matrix in ES to the LLM's sampling temperature, the framework employs a stochastic random walk mechanism with momentum. This approach primarily shrinks the search radius for micro-level code refinement, while retaining the critical ability to occasionally sample higher temperatures to escape semantic local optima. Ultimately, ES-AHD provides a highly directional, robust, and efficient search paradigm, significantly accelerating the generation of high-quality heuristic algorithms. The source code is available at: https://github.com/Mriya0306/ES-AHD.
I. INTRODUCTION
ES-AHD addresses blind search and exploration–exploitation imbalance in LLM-driven automatic heuristic design by combining semantic recombination with stochastic temperature adaptation.
- Motivation: Traditional heuristic design is time-consuming, labor-intensive, and difficult to generalize because it relies heavily on domain experts.Manual design requires mathematical knowledge, trial-and-error, and insights into problem structure.
- Motivation: Traditional AHD methods use predefined building blocks and search spaces, limiting their ability to design heuristics beyond those constraints.
- Related Work and Gap: LLM-based evolutionary methods improve heuristic generation but can remain blind because they rely on point-to-point random crossover or mutation.
- Related Work and Gap: Fixed sampling temperatures can produce repeated flawed code, creating an exploration–exploitation imbalance during LLM-driven heuristic evolution.
- ES-AHD Contributions: Semantic recombination extracts a Core Insight from Top-K candidates and converts random mutation into center-guided directional sampling.
- ES-AHD Contributions: Stochastic temperature sampling maps ES covariance adaptation to LLM search variance, shrinking refinement steps while retaining occasional higher-temperature exploration.
III. METHODOLOGY: THE ES-AHD FRAMEWORK
ES-AHD reformulates heuristic design as continuous-like optimization in a high-dimensional semantic space, using LLM reflection over elite programs to define a semantic search center.
- Framework Formulation: ES-AHD treats syntactically valid heuristic programs as a discrete search space while formulating their design as continuous-like optimization in high-dimensional semantic space.
- Framework Formulation: Classical ES maintains λ individuals and selects the top µ performers to update the search center through recombination.
- Semantic Recombination: Because directly averaging discrete code fragments is mathematically intractable and logically flawed, ES-AHD replaces arithmetic averaging with semantic recombination.
- Semantic Recombination: The elite set consists of the top µ programs from the population, which an LLM aggregates using contextual reasoning and summarization.
- Semantic Recombination: The resulting Core Insight occupies a natural-language embedding space and serves as the semantic equivalent of the ES distribution mean.
B. Stochastic Covariance Adaptation via Temperature Sampling
ES-AHD combines zero-shot population initialization, elite evaluation, semantic center updates, and stochastic temperature adaptation to guide successive heuristic sampling.
- Framework Procedure: ES-AHD initializes λ syntactically valid heuristic programs by zero-shot LLM sampling from the problem description at temperature T0.
- Framework Procedure: Each generation evaluates candidate fitness, selects the top µ heuristics as elites, and continuously tracks the global best heuristic.
- Framework Procedure: Semantic recombination prompts the LLM to extract recurring high-performance logic from elites and synthesize a textual Core Insight as the generation’s distribution mean.
- Framework Procedure: Stochastic covariance adaptation samples Gaussian noise and uses a constant step-size δ to update temperature, preventing early search stagnation.
- Framework Procedure: The updated semantic center and temperature generate λ new candidates through center-guided, parameterized semantic perturbation.
A. Problem Description: Traveling Salesman Problem (TSP)
The supplied passage describes stochastic temperature adaptation: momentum and Gaussian noise regulate semantic search variance while preserving exploration beyond local optima.
- Stochastic Covariance Adaptation: The current temperature retains momentum from the previous generation through factor (1 − δ) while adding Gaussian noise scaled by δ.
- Stochastic Covariance Adaptation: A positive lower bound Tmin prevents search variance from collapsing and ensures valid LLM inference.
- Stochastic Covariance Adaptation: The stochastic covariance walk primarily shrinks the search radius for micro-level refinement while occasionally sampling higher temperatures to escape semantic local optima.
C. Overall ES-AHD Framework
ES-AHD formulates heuristic design as continuous-like optimization in a high-dimensional semantic space and updates a semantic search center to sample high-performance heuristics. For TSP, the LLM designs a greedy construction heuristic that selects each next city using tour state and distance information.
- The framework uses a problem description and target fitness function to update a semantic search center for sampling high-performance heuristics.
- For TSP, the LLM generates a greedy select_next_node function that constructs a complete tour by iteratively choosing the next city.The function uses the current node, destination node, unvisited nodes, and distance matrix.
B. Experimental Setup
The experiments evaluate ES-AHD and other LLM-based AHD methods on TSP instances spanning three problem sizes, using training and validation route-quality measures under a shared LLM configuration.
- The study empirically evaluates ES-AHD on TSP instances of different scales.
- Experiments evaluate the algorithms on TSP instances with N = 20, 50, 100 to assess optimization accuracy, robustness, and scalability.
- The primary training metric is Top-4 Average Score, while validation reports average route distances for Val20, Val50, and Val100.Top-4 Average Score is the negative total route distance from the four best generated heuristics; higher scores indicate shorter routes.
- All LLM-based AHD methods use GLM 4-Flash as the underlying heuristic-generation engine for fair comparison.
C. Baseline Algorithms
The comparison includes three established LLM-driven AHD baselines representing code-space evolution, iterative rewriting, and automated program-space function discovery.
- EoH uses LLMs as crossover and mutation operators to search directly in heuristic code space.
- ReEvo iteratively rewrites and optimizes existing heuristic code through LLM prompting.
- FunSearch pairs a pretrained LLM with an automated evaluator to discover novel functions in program space.
D. Experimental Results and Analysis
ES-AHD achieves the strongest reported performance on the TSP N = 50 comparison and shows substantial performance on the broader TSPLib benchmark. Its advantage is clearest through 100-node instances, while ReEvo slightly leads on the largest evaluated scale.
- ES-AHD achieves the best performance among all evaluated methods on the TSP N = 50 comparison.
- -6.209 is ES-AHD’s Top-4 Average Training Score, outperforming EoH (-6.345) and FunSearch (-6.364).
- ES-AHD achieves the best validation results on Val20, Val50 (6.449), and Val100 (8.911), with a route-quality advantage over ReEvo through 100 nodes.On the largest evaluated scale, ReEvo slightly outperforms ES-AHD.
- ES-AHD demonstrates substantial performance on TSPLib, which contains real-world and synthetic instances varying in scale and spatial distribution.
V. CONCLUSION
ES-AHD integrates Evolution Strategy into LLM-driven Automatic Heuristic Design through elite-based semantic recombination and stochastic temperature adaptation. The framework evaluates and selects candidates iteratively, reports comparative results on TSP scales and TSPLIB, and identifies extensions to more complex domains.
- Conclusion: Each generation evaluates candidates, selects the elite set, updates the global best, extracts an insight with an LLM, and adapts temperature before sampling.The listed pipeline includes elite selection, semantic recombination, stochastic covariance adaptation, and covariance-guided sampling.
- Conclusion: ES-AHD integrates Evolution Strategy into LLM-driven Automatic Heuristic Design to address blind search and convergence imbalance.The framework replaces individual-level code mutation with directional sampling and dynamically regulates the semantic search radius.
- Conclusion: The paper reports comparative evaluations in Table I across problem scales from N = 20 to 100 and in Table II on TSPLIB instances.Table I reports Top-4 average training scores alongside validation results; Table II reports results on TSPLIB instances.
- Conclusion: Future work extends ES-AHD toward more complex combinatorial optimization domains, including vehicle routing and 3D bin packing, and macro-level tree search.These directions aim to further enhance sampling efficiency in massive heuristic spaces.