Research map / Large language models / Agents, code and math
HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes two entropy-based diversity indices (SWDI, CDI) for LLM-based evolutionary program search, analyzes FunSearch/EoH/ReEvo through them, and introduces HSEvo, which adds harmony-search parameter tuning and flash reflection to balance diversity and objective score.
Problem
LLM-based evolutionary program search for automatic heuristic design lacks understanding of heuristic search-space diversity and struggles to balance exploration and exploitation, leading to unstable objective scores.
Approach
Measure population diversity of LLM-generated heuristic code via code-embedding clustering (Shannon-Wiener index) and an MST-based entropy (CDI), then build HSEvo, which combines a genetic algorithm with harmony search over extracted heuristic parameters, persona-diverse initialization, and a cheaper flash reflection step.
Key results
- HSEvo achieves best objective score on all three tasks, e.g., BPO 1.07 ± 1.11 vs EoH 3.17 ± 2.97 and ReEvo 2.48 ± 3.74 (lower is better in the reported metric)
- On OP, HSEvo reaches CDI 5.67 ± 0.41 and objective -14.62 ± 0.12, versus ReEvo's 5.02 and -14.54
- EoH has highest CDI on BPO and TSP but worst objective score, showing a diversity-performance trade-off
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use HSEvo instead of FunSearch | LLM-EPS · BPO | Obj.: 2.05 \pm 2.01 -> \mathbf{1.07 \pm 1.11} | Helped |
| use HSEvo instead of ReEvo | LLM-EPS · BPO | CDI: 4.91 \pm 0.53 -> 5.68 \pm 0.35 | Helped |
| use HSEvo instead of ReEvo | LLM-EPS · TSP | Obj.: 0.05 \pm 0.06 -> \mathbf{0.02 \pm 0.03} | Helped |
| use HSEvo instead of ReEvo | LLM-EPS · TSP | CDI: 5.15 \pm 0.19 -> 5.41 \pm 0.21 | Helped |
| use HSEvo instead of ReEvo | LLM-EPS · OP | Obj.: -14.54 \pm 0.21 -> \mathbf{-14.62 \pm 0.12} | Helped |
| add harmony search to ReEvo (ablation) | ReEvo · OP | CDI: 5.02 \pm 0.13 -> 5.11 \pm 0.27 | Helped |
| add harmony search to ReEvo (ablation) | ReEvo · OP | Obj.: -14.54 \pm 0.21 -> -14.58 \pm 0.38 | Helped |
| replace ReEvo reflection with flash reflection; use 150K tokens (ablation) | ReEvo · OP | Obj.: -13.84 \pm 1.13 -> \mathbf{-14.36 \pm 0.19} | Helped |
| replace ReEvo reflection with flash reflection; use 150K tokens (ablation) | ReEvo · OP | CDI: 4.43 \pm 0.23 -> 4.63 \pm 0.37 | Helped |
| replace ReEvo reflection with flash reflection; use 150K tokens (ablation) | ReEvo · OP | Obj. | Helped |
Surprising findings
- EoH attains the highest diversity yet the worst objective score on BPO and TSP
- Harmony search added to ReEvo gives only marginal gains, since ReEvo lacks a diversity mechanism
Limitations
- HSEvo does not reach the highest CDI (EoH is higher on BPO, TSP, OP)
- Evaluated only with gpt-4o-mini and three problems with 3 runs each, so variance is high
- FunSearch could not be extended to OP due to unresolved conflicts
Experimental setup
Datasets: Weibull bin packing instances (5k items, C=100) TSP100 instances OP50 instances (DeepACO generation)
Benchmarks: BPO TSP100 with GLS OP50 with ACO
Metrics: objective score Cumulative Diversity Index Shannon-Wiener Diversity Index
Baselines: FunSearch EoH ReEvo
Builds on: FunSearch EoH ReEvo harmony search
Closest papers by meaning
- ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (NeurIPS 2024 · similarity 0.92)
- Multi-Objective Evolution of Heuristic Using Large Language Model (AAAI 2025 · similarity 0.91)
- $A_2$DEPT: Large Language Model–Driven Automated Algorithm Design via Evolutionary Program Trees (ICML 2026 · similarity 0.91)
- Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (ICML 2024 · similarity 0.91)
- Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design (ICML 2025 · similarity 0.89)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.