PaperlayerView exact revision on arXiv

Source-linked AI summary

HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs

Pham Vu Tuan Dat, Long Doan, Huynh Thi Thanh Binh

arXiv:2412.14995v1cs.NEcs.AI

TL;DR

Manual heuristic design is laborious, while the properties of LLM-EPS heuristic search spaces and their diversity remain insufficiently understood. The paper analyzes diversity in prior approaches, proposes two metrics and HSEvo, and reports a balance of diversity and objective performance across its experiments.

  • Problem

    Prior LLM-EPS work had not thoroughly explored heuristic search-space properties or population diversity, despite the importance of understanding these spaces for automatic algorithm design.

    Source: §1 · p. 2

  • Method

    The paper proposes two Shannon-entropy-inspired diversity metrics, analyzes prior LLM-EPS approaches, and introduces HSEvo with harmony search and genetic-algorithm components.

    Source: §1 · p. 2, §4 · p. 6

  • Results

    HSEvo maintains a good balance between diversity and objective performance, and achieves the best objective score on all three AHD tasks while not surpassing EoH on CDI.

    Source: §6 · p. 7, §5.2 · p. 7

  • Takeaways & Limitations

    The authors conclude that balancing population diversity and optimization performance is important in LLM-EPS for AHD problems.

    Source: §6 · p. 7

    Extending FunSearch to the OP problem with an ACO solver was omitted because conflicts could not be resolved with reasonable effort.

    Source: Harmony search analysis · p. 7

Abstract

from arXiv · show

Automatic Heuristic Design (AHD) is an active research area due to its utility in solving complex search and NP-hard combinatorial optimization problems in the real world. The recent advancements in Large Language Models (LLMs) introduce new possibilities by coupling LLMs with evolutionary computation to automatically generate heuristics, known as LLM-based Evolutionary Program Search (LLM-EPS). While previous LLM-EPS studies obtained great performance on various tasks, there is still a gap in understanding the properties of heuristic search spaces and achieving a balance between exploration and exploitation, which is a critical factor in large heuristic search spaces. In this study, we address this gap by proposing two diversity measurement metrics and perform an analysis on previous LLM-EPS approaches, including FunSearch, EoH, and ReEvo. Results on black-box AHD problems reveal that while EoH demonstrates higher diversity than FunSearch and ReEvo, its objective score is unstable. Conversely, ReEvo's reflection mechanism yields good objective scores but fails to optimize diversity effectively. With this finding in mind, we introduce HSEvo, an adaptive LLM-EPS framework that maintains a balance between diversity and convergence with a harmony search algorithm. Through experimentation, we find that HSEvo achieved high diversity indices and good objective scores while remaining cost-effective. These results underscore the importance of balancing exploration and exploitation and understanding heuristic search spaces in designing frameworks in LLM-EPS.

1 Introduction

Manual heuristic design is laborious and expert-intensive, motivating automatic heuristic design. Although LLM-EPS has produced strong heuristics, its search spaces remain poorly understood; this paper introduces diversity metrics and HSEvo to address that gap.

1 Introduction

  • Manual heuristic design and configuration can be laborious and require substantial expertise, motivating AHD for selecting, tuning, or constructing heuristics automatically.Hyper-heuristics remain constrained by human-predefined spaces, while neural combinatorial optimization faces inductive-bias, interpretability, and generalizability limitations.Source: §1 · p. 1
  • LLM-EPS couples LLMs with evolutionary computation to generate heuristics, following work including FunSearch, EoH [Liu et al. 2024a], and ReEvo [Ye et al. 2024b].The passage reports that these approaches have demonstrated improvements and generated quality heuristics.Source: §1 · p. 1
  • Unlike classic AHD's mathematical spaces such as R^n, LLM-EPS searches a space of programs representing heuristics, a space whose properties prior frameworks largely left unexamined.The paper identifies understanding these spaces as important for establishing foundations for automatic algorithm design.Source: §1 · pp. 1–2
  • The paper introduces two Shannon-entropy-inspired diversity metrics and studies their relationship to objective performance across optimization problems.It uses the analysis of heuristic search-space properties to inform the design of HSEvo.Source: §1 · p. 2
  • HSEvo aims to balance diversity and objective performance, using the Shannon–Wiener Diversity Index and Cumulative Diversity Index to assess evolutionary progress.The framework also adds a harmony-search component and enhances initialization, crossover, and mutation.Source: §1 · p. 2
  • The paper's stated contributions are the two diversity measures and HSEvo, a framework intended to balance diversity with objective performance.Source: §1 · p. 2

2 Background and Related Works

The background reviews LLM-EPS approaches that combine language models and evolutionary search, then motivates studying diversity in these systems. Prior work has explored population diversity and entropy, but diversity in LLM-EPS remains insufficiently studied.

2.1 LLM-based Evolutionary Program Search

  • FunSearch, EoH, and ReEvo represent LLM-EPS approaches using island-based evolution, genetic algorithms with Chain of Thought prompting, and reflective heuristic refinement, respectively.The passage describes their use across mathematical and combinatorial optimization tasks.Source: §2.1 · p. 2

2.2 Diversity in Evolutionary Computation

  • Evolutionary-computation research has studied measuring and maintaining population diversity, with Shannon entropy prominent for quantifying diversity and predicting genetic-algorithm behavior, but LLM-EPS diversity remains insufficiently explored.Source: §2.2 · p. 2

3 Diversity measurement metrics

This section encodes program-valued LLM-EPS populations, defines SWDI and CDI diversity metrics, and analyzes their relationship to objective performance in prior frameworks.

3.1 Population encoding

  • The proposed encoding removes comments and docstrings, standardizes code style, then converts code snippets into vector representations using a code-embedding model.Source: §3.1 · pp. 2–3

3.5 Diversity analysis on previous LLM-EPS framework

  • On BPO/TSP, EoH had highest CDI but worst objective score; ReEvo and FunSearch had lower CDI yet better objective performance on all three problems, while OP favored high CDI.The figure presents CDI and objective scores for previous LLM-EPS approaches across AHD problems.Source: Figure 2 · p. 3, §3.5 · p. 4

3.2 Shannon–Wiener Diversity Index

  • SWDI applies Shannon entropy to cluster proportions, with high values marking even population spread and exploration, and low values marking concentration and exploitation that risks premature convergence.Source: §3.2 · p. 3

3.3 Cumulative Diversity Index

  • CDI applies Shannon entropy to Euclidean MST edge-distance proportions to measure whole-population spread; it remains unnormalized so cluster and candidate counts contribute to diversity.Source: §3.3 · pp. 3–4

3.4 Exploring the correlation between objective score and diversity measurement metrics

  • Across ReEvo's BPO runs, exploration-driven SWDI increases accompanied objective gains, while exploitation-driven decreases prolonged local-optimum stagnation and low CDI could hinder escape.The section reports three experimental runs.Source: §3.4 · p. 4

4 Automatic Heuristic Design with HSEvo

HSEvo combines genetic search with harmony-search-based tuning to balance population diversity and objective performance, while using flash reflection to reduce LLM costs. Its pipeline includes initialization, selection, reflection, crossover, mutation, and parameter optimization.

Individual encoding

  • HSEvo encodes each individual as an LLM-generated code string, allowing flexible representations without a predefined encoding format.The authors also note this makes evaluation on AHD problems easier.Source: §4 · p. 5

Initialization

  • HSEvo initializes its population from task specifications and can incorporate seed heuristics or external domain knowledge, using varied role prompts to encourage diverse generations.Prompts can assign roles ranging from optimization experts to Albert Einstein.Source: §4 · p. 5

Selection

  • HSEvo randomly selects parent pairs to balance exploration and exploitation and counter premature convergence.The authors relate premature convergence to the SWDI trajectory observed in their analysis.Source: §4 · p. 5

Flash reflection

  • Flash reflection groups and deduplicates selected individuals, analyzes mixed-, good-, and poor-ranking parent pairs, then compares successive analyses to produce guidance.That guidance is used in subsequent stages, including crossover.Source: §4 · p. 6

Crossover

  • Crossover combines parent algorithms using flash-reflection guidance, aiming to produce offspring that inherit successful attributes from both parents.The prompt includes task specifications, parent heuristics, guidance, and generation instructions.Source: §4 · p. 6

Elitist mutation

  • In elitist mutation, the generator LLM mutates the best-performing heuristic using insights from flash reflections, with the elite heuristic and task details included in the prompt.The stated aim is to improve the heuristic while preserving the quality of top solutions.Source: §4 · p. 6

Harmony Search

  • HSEvo uses harmony search to tune parameters of strong individuals, then returns each tuned individual to the population to support optimization alongside diversity.Parameters such as thresholds and weights are extracted from the best individual; marked individuals are not tuned again in later steps.Source: §4 · p. 6

5 Experiments

Experiments compare HSEvo with prior LLM-EPS frameworks on three AHD problems and report objective-score and diversity outcomes. Ablations examine harmony search and flash reflection, including performance under different token budgets.

5.1 Experimental Setup

  • The experiments use BPO, TSP, and OP; frameworks ran under identical environmental settings, with search and heuristic evaluation on a single CPU core.The tasks involve online bin packing, TSP perturbation for Guided Local Search, and path selection for an ACO solver, respectively.Source: §5.1 · pp. 6–7

5.2 Experiment results

  • HSEvo achieved the best objective score on all three AHD tasks, though its CDI remained below EoH; on BPO, it outperformed FunSearch and ReEvo by a huge margin.The reported comparison is summarized in Table 2; no specific score values are supplied here.Source: §5.2 · p. 7
  • On BPO, HSEvo’s objective score improved significantly while SWDI was around 3.0 and then decreased only marginally; ReEvo’s smaller improvement occurred as SWDI fell around 3.0 and 2.7.The authors compare HSEvo’s first run with ReEvo’s third run; Figure 5 plots HSEvo’s diversity indices and objective scores across runs.Source: §5.2 · p. 7, Figure 5 · p. 7

5.3 Ablation study

  • The ablation study examines the contributions of harmony search and flash reflection.For harmony search, the authors add it to ReEvo rather than remove it from HSEvo.Source: §5.3 · p. 7, Harmony search analysis · p. 7

Harmony search analysis

  • On OP, HSEvo outperformed ReEvo and ReEvo with harmony search on both objective score and CDI, while adding harmony search to ReEvo yielded only marginal improvement.The authors attribute the limited gain to ReEvo lacking a mechanism to promote diversity; extending FunSearch to OP with an ACO solver caused unresolved conflicts.Source: Harmony search analysis · p. 7

Flash reflection analysis

  • With 150K tokens, ReEvo using flash reflection outperformed HSEvo in optimization performance with comparable CDI; at a larger token budget, it did not improve both metrics, while HSEvo reached 5.67 and -14.62.The authors conclude that flash reflection without a diversity-promoting mechanism is insufficient to improve LLM-EPS optimization.Source: Flash reflection analysis · p. 7

6 Conclusion

The paper highlights population diversity as important in LLM-EPS for AHD and presents HSEvo as a framework for balancing diversity with optimization performance. Its experiments and ablations report that the framework maintains this balance and examine its components.

6 Conclusion

  • HSEvo combines diversity-driven harmony search and a genetic algorithm to balance population diversity with optimization performance in AHD.The authors report experiments and ablations to assess the framework and its components.Source: §6 · p. 7
  • The paper proposes SWDI and CDI and analyzes diversity in earlier LLM-EPS approaches, finding that they either underemphasize population diversity or face a diversity–optimization trade-off.Source: §6 · p. 7
  • The authors conclude that population diversity is important in LLM-EPS for AHD problems.Source: §6 · p. 7

A Benchmark dataset details

The benchmark evaluates HSEvo and LLM-EPS on three optimization problems with distinct datasets and solver settings. BPO uses direct heuristic evaluation, while TSP and OP use Guided Local Search and Ant Colony Optimization, respectively.

A Benchmark dataset details

  • The study evaluates BPO, TSP, and OP using data configurations and generation setups described as challenging and used in recent studies.The cited related work includes Romera-Paredes et al. (2024), Liu et al. (2024a), and Ye et al. (2024b).Source: A Benchmark dataset details · p. 10

A.1 Bin Packing Online (BPO)

  • BPO uses five randomly generated Weibull instances of size 5k with bin capacity C = 100, and LLM-EPS designs heuristics that solve it directly without an external solver.The benchmark is online: items are packed as they arrive, without prior knowledge of future items.Source: §A.1 · p. 10

A.2 Traveling Salesman Problem (TSP)

  • TSP uses 64 randomly generated instances with 100 nodes in [0, 1]^2 and Guided Local Search with a perturbation phase prioritizing edges with higher heuristic values for penalization.The benchmark evaluates search-penalty heuristics; it uses one perturbation move.Source: §A.2 · p. 10

A.3 Orienteering Problem (OP)

  • OP instances contain 50 uniformly sampled nodes, including the depot, and use Ant Colony Optimization with population size 20 under a maximum tour length constraint of 3.The prize distribution follows Kool, Van Hoof, and Welling (2018).Source: §A.3 · p. 10

B.1 Objective scores and diversity measurement metrics

The diversity analysis specifies its embedding model, similarity threshold, and token budget, and points to additional ReEvo results for TSP and OP.

B.1 Objective scores and diversity measurement metrics

  • The diversity analysis uses CodeT5+3 embeddings, a similarity threshold α = 0.95, and a maximum budget of 450K tokens per run.Source: §B.1 · p. 10
  • Additional diversity-analysis results for ReEvo on TSP are presented in Figure 6.Source: §B.1 · p. 10
  • Additional diversity-analysis results for ReEvo on OP are presented in Figure 7.Source: §B.1 · p. 10

B.2 Diversity analysis on previous LLM-EPS frameworks

The analysis evaluates FunSearch, EoH, and ReEvo across three AHD benchmarks using the diversity-evaluation process described earlier.

B.2 Diversity analysis on previous LLM-EPS frameworks

  • The diversity analysis compares FunSearch, EoH, and ReEvo across all three benchmark datasets.Source: §B.2 · p. 10
  • The benchmark set comprises BPO, TSP, and OP.Source: §B.2 · p. 10
  • The experiments follow the same diversity-evaluation process as Section B.1, with framework parameters and LLM information reported in Table 1.Source: §B.2 · p. 10

C HSEvo prompt examples

The appendix documents HSEvo’s prompts for initialization, reflection, crossover, elitist mutation, and harmony search, along with problem-specific prompt materials and generated heuristics.

C.1 Task description prompts

  • Task prompts assign generator personas in round-robin order to encourage different viewpoints and population diversity.The prompts request Python code and provide the task, function name, and description.Source: §C.1 · p. 11

C.2 Population initialization prompt

  • Population initialization asks the LLM to creatively improve a trivial seed heuristic and return code for a v2 function.The seed function is the trivial heuristic for the corresponding problem.Source: §C.2 · p. 12

C.3 Flash reflection prompts

  • Flash reflection compares ranked heuristics and extracts advice, while subsequent reflection distinguishes prior reflections associated with discovered versus undiscovered heuristics.The ranked list groups selected parent pairs, removes duplicates, and orders them by objective scores.Source: §C.3 · p. 12

C.4 Crossover prompt

  • Crossover prompts combine better and worse parent heuristics using flash-reflection guidance to produce an improved function.Source: §C.4 · p. 12

C.5 Elitist mutation prompt

  • Elitist mutation prompts ask for a better mutated function based on the current elitist heuristic, optionally using flash-reflection hints.Source: §C.5 · p. 13

C.6 Harmony Search prompts

  • Harmony Search prompts extract thresholds, weights, or hardcoded variables from the elitist code and request parameter ranges for them.Source: §C.6 · p. 13

C.7 Problem-specific prompts

  • Problem-specific prompt materials include problem descriptions, function descriptions, function signatures, and seed functions for the benchmark settings.Tables 6 and 7 contain the descriptions, while Figures 8 and 9 show signatures and seed functions.Source: §C.7 · p. 13, Table 6 · p. 13, Table 7 · p. 13

D Generated heuristics

Related papers

Loading 2412.14995v1…