Research map / Large language models / Agents, code and math
Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model
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 EoH, an evolutionary framework where LLMs co-evolve natural-language thoughts and Python code of heuristics via five prompt strategies, evaluated on online bin packing, TSP (GLS), and flow shop scheduling.
Problem
Automatic heuristic design is labour-intensive when done manually, and prior LLM+EC approaches like FunSearch require huge numbers of LLM queries and only evolve code.
Approach
Evolve heuristics as paired natural-language thoughts and code, using LLMs in genetic operators with five exploration/modification prompt strategies that reason over parent thoughts and codes, achieving strong results with a few thousand LLM queries.
Key results
- On online bin packing 1k_C500, EoH achieves 2.13% gap to lower bound versus 6.75% for FunSearch and 4.50% for Best Fit, using a few thousand LLM queries versus ~1M for FunSearch.
- On TSPLib subset, EoH reaches 0.00% gap on pr124, kroA150, and u159, and average gap 0.28% over 29 instances, the best among compared methods.
- On Taillard flow shop instances, EoH obtains average gap 0.23%, versus 0.36% for ILS2 (hand-crafted perturbation) and 2.48% for PFSPNet.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use EoH rather than FunSearch | online bin packing heuristics · Weibull instances across sizes and capacities | gap to lower bound: 1.18% vs 2.23% | Mixed |
| use EoH rather than KGLS | TSP heuristics · TSPLib (29 instances) | gap to best-known solution: 0.36 -> 0.28 | Helped |
| use EoH rather than ILS2 | FSSP heuristics · Taillard instances (average) | gap to best-known solution: 0.36 -> 0.23 | Helped |
| add M1, M2, M3, and E2 prompt strategies to E1 (ablation) | EoH online bin packing · Weibull instances | gap to lower bound: 4.28% -> 2.24% (1k_100); 0.97% -> 0.80% (5k_100); 5.86% -> 2.13% (1k_500) | Helped |
| add natural-language thoughts to code-only evolution (ablation) | EoH online bin packing · Weibull instances | average gap to lower bound: 2.57 -> 0.66 | Helped |
| make prompts output both thoughts and codes rather than thoughts only (ablation) | EoH online bin packing · 5k Weibull instances | average gap to lower bound: 0.85 -> 0.66 | Helped |
| add an existing FunSearch heuristic to the initial population | EoH online bin packing · 5k Weibull instances | average gap to lower bound: 0.66 -> 0.55 | Helped |
Surprising findings
- Code-only evolution (EoC) overfits badly on bin packing, with gaps above 100% on several Weibull sets despite good training-distribution results.
- EoH with GPT-3.5 is not uniformly best: on 10k_C100, FunSearch's heuristic (0.33%) beats EoH (0.61%).
Limitations
- Relies on the GPT-3.5-turbo LLM for main results; generalization to other LLMs shown only on bin packing 5k.
- Evaluation cost per candidate is high since each heuristic is run on an instance set, and experiments are limited to three problems.
- Results for some baselines (e.g., GNNGLS, NeuralGLS) are taken from original papers rather than re-run.
Experimental setup
Datasets: Weibull bin packing instances TSP100 random instances Taillard flow shop instances TSPLib
Benchmarks: Weibull online bin packing instances TSPLib TSP20/50/100 random instances Taillard flow shop instances
Metrics: gap to lower bound (%) relative distance to best-known (%) gap to Concorde (%) average relative makespan (%)
Baselines: First Fit Best Fit FunSearch Nearest insertion Farthest insertion Google OR-Tools AM POMO LEHD GUPTA CDS NEH
Builds on: FunSearch chain-of-thought genetic programming
Closest papers by meaning
- Multi-Objective Evolution of Heuristic Using Large Language Model (AAAI 2025 · similarity 0.92)
- HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs (AAAI 2025 · similarity 0.91)
- ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (NeurIPS 2024 · similarity 0.90)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.88)
- Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design (ICML 2025 · similarity 0.86)
- Simple Baselines are Competitive with Code Evolution (NeurIPS 2026 · similarity 0.86)
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.