PaperlayerView exact revision on arXiv

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

arXiv:2609.00023v1cs.NEcs.LG

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.

    Source: §I · pp. 1–2

  • 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.

    Source: §I · p. 2, §III · p. 2, A. Semantic Recombination via LLMs · p. 3

  • 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).

    Source: D. Experimental Results and Analysis · p. 4

  • Takeaways & Limitations

    Experiments on TSP instances of varying scales report superior optimization accuracy and robust generalization for ES-AHD compared with evaluated baselines.

    Source: D. Experimental Results and Analysis · p. 4, §V · p. 5

Abstract

from arXiv · show

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.Source: §I · p. 1
  • Traditional AHD methods use predefined building blocks and search spaces, limiting their ability to design heuristics beyond those constraints.Source: §I · p. 1

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.Source: §I · pp. 1–2
  • Fixed sampling temperatures can produce repeated flawed code, creating an exploration–exploitation imbalance during LLM-driven heuristic evolution.Source: §I · p. 2

ES-AHD Contributions

  • Semantic recombination extracts a Core Insight from Top-K candidates and converts random mutation into center-guided directional sampling.Source: §I · p. 2
  • Stochastic temperature sampling maps ES covariance adaptation to LLM search variance, shrinking refinement steps while retaining occasional higher-temperature exploration.Source: 2) Stochastic Covariance Adaptation… · p. 2

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.Source: §III · p. 2
  • Classical ES maintains λ individuals and selects the top µ performers to update the search center through recombination.Source: A. Semantic Recombination via LLMs · pp. 2–3

Semantic Recombination

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

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

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.Source: C. Overall ES-AHD Framework · p. 3
  • 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.Source: C. Overall ES-AHD Framework · p. 3

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.Source: B. Experimental Setup · p. 3
  • Experiments evaluate the algorithms on TSP instances with N = 20, 50, 100 to assess optimization accuracy, robustness, and scalability.Source: B. Experimental Setup · p. 3
  • 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.Source: B. Experimental Setup · p. 4
  • All LLM-based AHD methods use GLM 4-Flash as the underlying heuristic-generation engine for fair comparison.Source: B. Experimental Setup · p. 4

C. Baseline Algorithms

The comparison includes three established LLM-driven AHD baselines representing code-space evolution, iterative rewriting, and automated program-space function discovery.

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.

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.Source: §V · p. 5
  • 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.Source: §V · pp. 4–5
  • 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.Source: Table I · p. 5, Table II · p. 5
  • 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.Source: §V · p. 5

Related papers

Loading 2609.00023v1…