Source-linked AI summary
Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model
Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, Qingfu Zhang
TL;DR
Manual heuristic design is labor-intensive and requires substantial expertise, motivating automatic methods. EoH combines LLMs with evolutionary computation to evolve natural-language thoughts and executable codes, and it reports stronger performance across benchmark problems with relatively few LLM requests. Its scope remains bounded by the early development of LLM-assisted heuristic evolution.
Problem
Manual heuristic design is labor-intensive and demands rich expert experience, motivating automatic heuristic design.
Method
EoH combines LLMs and evolutionary computation to evolve natural-language thoughts alongside executable heuristic codes.
Results
EoH outperforms human hand-crafted heuristics in some instances across three optimization benchmarks while using only a few thousand LLM requests.
Takeaways & Limitations
EoH offers a principled approach to automatic algorithm design within the evaluated optimization problems.
Takeaways & Limitations
LLM-assisted evolution of heuristics remains in its very early infancy.
Abstract
from arXiv · showhide
Heuristics are widely used for dealing with complex search and optimization problems. However, manual design of heuristics can be often very labour extensive and requires rich working experience and knowledge. This paper proposes Evolution of Heuristic (EoH), a novel evolutionary paradigm that leverages both Large Language Models (LLMs) and Evolutionary Computation (EC) methods for Automatic Heuristic Design (AHD). EoH represents the ideas of heuristics in natural language, termed thoughts. They are then translated into executable codes by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it very effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent AHD methods including FunSearch. Particularly, the heuristic produced by EoH with a low computational budget (in terms of the number of queries to LLMs) significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.
1. Introduction
Heuristic design is valuable for complex optimization but remains labor-intensive and dependent on expert knowledge. EoH addresses this bottleneck by evolving both natural-language ideas and executable codes with LLMs and EC.
- Manual heuristic design is labor-intensive and demands rich expert experience, creating a bottleneck for application-specific algorithms.
- AHD automatically selects, tunes, or constructs effective heuristics for a given problem class.
- FunSearch searches the space of heuristic functions represented as programs, but requires substantial computational resources to produce quality heuristics.
- EoH represents heuristic ideas as thoughts, translates them into executable code with LLMs, and evolves both representations cooperatively.
- EoH uses prompt strategies intended to guide LLMs toward more diverse and effective heuristics.
- Experiments evaluate EoH against existing AHD methods on three combinatorial optimization benchmark problems, with reported advantages over FunSearch using fewer LLM queries on online bin packing.
2. Background and Related Works
Automatic heuristic design combines algorithmic search with machine learning and evolutionary computation, while FunSearch demonstrates the promise and computational cost of LLM-assisted program search.
- Hyper-heuristics automatically tune heuristics or combine algorithmic components, but genetic programming requires handcrafted components and domain knowledge.
- LLM optimizers directly generate trial solutions through in-context learning, but face challenges on complex problems with large search spaces.
- Evolutionary computation has been applied to both code and text generation, including LLM-assisted automatic search.
- FunSearch can outperform handcrafted algorithms on some optimization problems but may require millions of programs, making it impractical for many users.
3. Evolution of Heuristics (EoH)
EoH evolves populations of heuristics represented by natural-language thoughts, executable code, and fitness values. LLM-guided exploration, modification, evaluation, and selection jointly drive the search.
- Heuristic Representation: EoH maintains both a natural-language description of each heuristic and its corresponding code implementation.
- Evolutionary Prompts: LLMs generate new heuristics through prompt strategies that reason over existing thoughts and codes, including exploration and modification operations.
- Population Evolution: Candidate heuristics are evaluated on problem instances, assigned fitness values, and selected to form subsequent populations.
- Main Idea: Each EoH individual is a heuristic for a target problem rather than a candidate solution to the optimization problem itself.
- Population Evolution: Each generation can add at most 5N newly generated heuristics before retaining the N best individuals.
- Algorithm: The pipeline initializes heuristics with LLM prompts, generates code in a predefined format, evaluates feasibility and fitness, and adds feasible candidates.
4. Experiments
Experiments evaluate EoH on online bin packing, TSP, and FSSP against handcrafted, automatically designed, and neural or solver-based methods. EoH achieves strong performance across these settings, converges in about 20 generations, and benefits from evolving thoughts alongside codes.
- Online bin packing: EoH evaluates online bin packing using Weibull instances and a fitness based on the average ratio of bins used to the lower bound.The evaluation compares first fit, best fit, and FunSearch heuristics across varying sizes and capacities.
- Experimental settings: EoH designs online bin-packing scoring functions that assign incoming items to bins using item size and remaining bin capacities.The item is assigned to the bin with the maximum score.
- Experimental settings: EoH designs Guided Local Search heuristics for TSP by producing methods that update the distance matrix.The updated landscape guides local search toward more promising areas.
- Online bin packing: 2.13% gap was achieved by EoH on 1k-item, capacity-500 instances, where FunSearch performed worse than two handcrafted heuristics.Across tested sizes and capacities, EoH was best except on the 10k C100 set and used only a few thousand LLM queries versus FunSearch’s around 1 million.
- TSP and FSSP: EoH converges after about 20 generations on TSP and produces the best results on all reported TSP and FSSP test sets.On TSP, EoH consistently outperforms other heuristics and reaches gap= 0% on pr124, kroA150, and u159; on FSSP, it is best among all compared heuristics.
- Ablation study: EoH performs best on average among its variants, while EoH-e2 is second best and EoC performs worst or second worst.The authors attribute positive contributions to M1, M2, M3, and E2, and report that the thought component is beneficial.
5. Discussion and Future Works
Ablation and sensitivity studies show that EoH benefits from jointly evolving heuristic thoughts and codes, effective prompt-based search, stronger LLMs, and expert heuristics. The discussion also identifies open directions involving domain-specific models, heuristic search spaces, and human interaction.
- Interaction between Thoughts and Codes: Evolving both thoughts and codes performs substantially better than using only codes or only thoughts in evolutionary prompts.EoH also outperforms the variant that uses both representations but outputs only thoughts during evolution.
- Different LLMs: EoH generates good-performance heuristics across GPT3.5, Gemini Pro, CodeLlama, and Deepseek.With 2,000 LLM queries, EoH using different LLMs performs better than randomly querying GPT3.5 10,000 times; GPT3.5 and Gemini Pro outperform the other tested models.
- Use of Expert Heuristic: Including an elite expert heuristic in the initial population improves results, with EoH expert surpassing both original EoH and FunSearch on the test case.The authors attribute this to expert knowledge being inherited and evolved during the search.
- Future Works: The authors characterize LLM-assisted evolution of heuristics as being in its very early infancy and identify automatic algorithm design as needing substantial further development.The discussion frames this as a promising but still developing research area.
- Future Works: Future research should study domain-specific LLMs, the search spaces of heuristics, and efficient interaction between EoH and human experts.These directions target specialized domain knowledge, theoretical understanding, and expert participation in generating, modifying, or evaluating heuristics.
6. Conclusion
The paper introduces EoH, which combines LLMs and evolutionary computation to automatically design heuristics by evolving both natural-language thoughts and executable codes. Across online bin packing, traveling salesman, and flow shop scheduling, EoH outperforms human-designed heuristics on some instances and achieves better performance on most test instances with only a few thousand LLM requests.
- 6. Conclusion: EoH combines large language models and evolutionary computation to design heuristics automatically.Its central representation and search strategy evolve both high-level thoughts and executable codes.
- 6. Conclusion: EoH was tested on online bin packing, traveling salesman, and flow shop scheduling benchmark problems.The conclusion reports results across three well-studied optimization problems.
- 6. Conclusion: EoH outperforms human hand-crafted heuristics on some problem instances and achieves better performance on most test instances with only a few thousand LLM requests.The paper presents this as evidence for a principled approach to automatic algorithm design.
- Related Work: Prior neural-solver and hybrid approaches often require substantial effort to design and train domain-specific neural models.This work is situated among end-to-end neural solvers and methods combining neural solvers with classic heuristics.
- Related Work: EoH prompt strategies can be viewed as Chain-of-Thought variants that use parent heuristics and instructions as in-context information.The related-work discussion connects EoH's prompting approach to extensions such as tree-of-thoughts and graph-of-thoughts.
- Implementation: EoH prompts combine task descriptions, strategy-specific instructions, expected outputs, notes, and parent heuristics.The appendix describes this structure for initialization and evolution procedures.
B.2. Heuristic Evolution
E2 generates a new heuristic by extracting a shared idea from five selected parent heuristics, designing a heuristic from that idea, and producing its executable implementation in one step.
- Prompt Engineering: Initialization and E2 are illustrated as examples of the prompt engineering used in EoH.Other evolution operators use the same five-part prompt structure.
- Heuristic Evolution: Five parent heuristics are selected from the population as inputs to E2.Each parent includes a high-level description and a detailed Python implementation.
- Heuristic Evolution: E2 first asks the LLM to identify and summarize the common idea across the selected heuristics.The shared concept is used as the basis for generating the next heuristic.
- Heuristic Evolution: E2 then designs a new heuristic from the shared idea and produces its code implementation in the same evolutionary step.The figure describes the sequence as observation and summarization, design, and code generation.
B.3. Designed Heuristic
The designed heuristics are represented as Python functions that score bins for the current item, after which the item is assigned to the highest-scoring bin.
- Designed Heuristic: The heuristic function takes the current item and remaining bin capacities as inputs and returns scores for the bins.At each step, the item is assigned to the bin with the highest score.
- Designed Heuristic: Human-designed heuristics can be implemented in one line, whereas EoC, FunSearch, and EoH produce more complicated functions.The paper notes that the latter heuristics are consequently difficult for human designers to achieve.
B.4. More Results
EoH achieves strong bin-packing performance across varied Weibull instances while using far fewer LLM queries than FunSearch. Its generated heuristics can also operate within guided local search using simple operators.
- Bin packing results: 1.18% average gap to the lower bound makes EoH the best-performing heuristic across the evaluated Weibull instances.EoH also generalizes better across capacities while matching the best training-distribution gap.
- Bin packing results: A few thousand LLM queries give EoH a much smaller computational budget than FunSearch’s approximately 1 million queries.The comparison is reported for online bin packing.
- Application within guided local search: EoH-designed heuristics work with guided local search and only two basic local search operators for TSP and FSSP.The resulting algorithms remain competitive despite using simpler local search than state-of-the-art solvers.
- Application within guided local search: Guided local search alternates local search with perturbation, where a heuristic strategy updates the objective landscape after local optima are reached.EoH designs the strategy used for this objective-function update.
C.3. Designed Heuristic Strategy
For TSP, EoH designs a guided-local-search strategy that updates the distance matrix using distance statistics, route-use information, penalties, and random factors.
- TSP strategy: EoH’s TSP strategy modifies the original distance matrix by adding random factors and intermediate statistics.The cited statistics include average distances, average edge use, and a penalty on the current locally optimal route.
C.4. More Experimental Results
EoH is evaluated on random Euclidean TSP instances and TSPLib benchmarks against handcrafted, guided-local-search, and neural methods. It outperforms the other heuristics in average gap on the 29 TSPLib instances.
- Compared methods: EoH is compared with handcrafted GLS variants, neural GLS methods, and neural combinatorial-optimization solvers.The comparison includes GLS, EBGLS, KGLS, GNNGLS, NeuralGLS, AM, GCN, POMO, BQ, and LEHD.
- Random TSP instances: The random-instance evaluation uses 1,000 instances each for TSP20, TSP50, and TSP100, reporting average gap to Concorde and average runtime.Instances contain 20, 50, or 100 randomly generated locations in [0, 1]^2.
- TSPLib results: EoH outperforms all other heuristics in average gap across 29 TSPLib instances.The comparison includes both handcrafted methods and the other evaluated approaches.
D.3. More Results
EoH is evaluated on Taillard flow-shop instances against classic, iterated-local-search, and neural heuristics. It performs best on most test sets and attains a 0.23% average gap.
- Compared methods: The comparison includes classic FSSP heuristics, neural solvers, local search, and two iterated-local-search methods.ILS2 uses the same framework and local-search operators but a human hand-crafted perturbation heuristic.
- FSSP results: EoH achieves the best average gap of 0.23% on the Taillard flow-shop benchmark.It is best on most of the 11 test sets spanning 20–200 jobs and 5–20 machines.
- FSSP results: EoH outperforms commonly used heuristics and recent deep-learning neural solvers on the evaluated Taillard instances.The benchmark reports average gaps to Taillard upper bounds over 10 instances per test set.