Source-linked AI summary
ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, Guojie Song
TL;DR
NP-hard COPs make heuristic design laborious, while traditional heuristic spaces rely on human-defined components. The paper introduces LHHs and ReEvo, combining LLM-generated heuristics with evolutionary search and reflective verbal guidance; across five algorithmic types and six COPs, ReEvo produces competitive or state-of-the-art solvers with improved sample efficiency over prior LHHs.
Problem
NP-hard COPs have heterogeneous constraints and objectives, compelling domain experts to laboriously develop approximate-solution heuristics.
Method
ReEvo uses LLMs to generate heuristic code within evolutionary search, with short- and long-term reflections guiding selection, crossover, and mutation.
Results
Across five heterogeneous algorithmic types, six COPs, and white-box and black-box settings, ReEvo yields state-of-the-art or competitive solvers and greater sample efficiency than prior LHHs.
Takeaways & Limitations
LHHs provide an open-ended alternative to manually predefined heuristic spaces, while ReEvo supports efficient heuristic search across diverse COP solver types.
Takeaways & Limitations
Experiments limit heuristic evaluations to 100 shots, and results do not necessarily scale to larger evaluation budgets.
Abstract
from arXiv · showhide
The omnipresence of NP-hard combinatorial optimization problems (COPs) compels domain experts to engage in trial-and-error heuristic design. The long-standing endeavor of design automation has gained new momentum with the rise of large language models (LLMs). This paper introduces Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics that leverages LLMs for heuristic generation, featuring minimal manual intervention and open-ended heuristic spaces. To empower LHHs, we present Reflective Evolution (ReEvo), a novel integration of evolutionary search for efficiently exploring the heuristic space, and LLM reflections to provide verbal gradients within the space. Across five heterogeneous algorithmic types, six different COPs, and both white-box and black-box views of COPs, ReEvo yields state-of-the-art and competitive meta-heuristics, evolutionary algorithms, heuristics, and neural solvers, while being more sample-efficient than prior LHHs.
1 Introduction
NP-hard combinatorial optimization problems require laborious, problem-specific heuristic design, motivating automated approaches. The paper introduces LHHs and ReEvo to expand heuristic search with LLM generation, evolutionary exploration, and reflection.
- NP-hard COPs have distinct constraints and objectives, making approximate heuristic design laborious for domain experts.
- Language Hyper-Heuristics use LLMs to generate heuristics, extending Hyper-Heuristics beyond manually predefined heuristic spaces.
- ReEvo combines evolutionary search with LLM self-reflections to explore heuristic spaces and provide verbal gradients.
- ReEvo introduces fitness landscape analysis and black-box prompting for reliable LHH evaluation.
- Across five heterogeneous algorithmic types and six COPs, ReEvo produces state-of-the-art or competitive solvers and improves sample efficiency over prior LHHs.
2 Related work
Prior work spans traditional Hyper-Heuristics, neural combinatorial optimization, LLM-based optimization, and self-reflection. ReEvo extends these directions by using comparative verbal feedback inside evolutionary heuristic search.
- Traditional Hyper-Heuristics select or combine heuristics from human-predefined components, limiting their heuristic spaces.
- Neural combinatorial optimization searches neural architectures and solution pipelines as a heuristic space for end-to-end COP solving.
- LLM code generation has been applied to debugging, code optimization, algorithmic challenges, robotics, task solving, prompt optimization, and algorithmic improvement.
- Self-reflection methods use linguistic feedback, while ReEvo applies verbal feedback to comparative analyses of two heuristics within evolutionary search.
3 Language Hyper-Heuristics for Combinatorial Optimization
Hyper-Heuristics optimize over heuristic configurations rather than directly over COP solutions. LHHs use LLMs to generate heuristics in an open-ended space, with performance estimated across problem instances.
- Hyper-Heuristics search a heuristic space to select or generate effective heuristics while indirectly optimizing the underlying COP.
- A formal HH seeks h* = argmin_h∈H F(h), where F is a meta-objective over heuristics.
- Language Hyper-Heuristics generate heuristics with LLMs, replacing manually predefined heuristic spaces with open-ended exploration.
- The meta-objective is defined as expected heuristic performance for a COP and estimated by average performance across problem instances.
4 Language Hyper-Heuristic with ReEvo
ReEvo frames LLM-generated heuristics as individuals in an evolutionary search. Generator and reflector LLMs combine heuristic variation with short- and long-term reflections to guide exploration.
- Vanilla LHH randomly searches through repeated LLM generations, but is sample-inefficient and weak at reasoning about complex or black-box COPs.
- ReEvo uses generator and reflector LLMs in an evolutionary framework whose individuals are heuristic code snippets.
- ReEvo iterates through selection, short-term reflection, crossover, long-term reflection, and elitist mutation, evaluating heuristics after crossover and mutation.
- Unlike traditional genetic programming, ReEvo uses LLM-generated code snippets without a predefined encoding format beyond a specified function signature.
- Short-term reflections compare parent performance to guide offspring generation, while long-term reflections summarize accumulated expertise for later improvement.
- Elitist mutation samples multiple heuristics around the current best one using task specifications and long-term reflections.
5 Heuristic generation with ReEvo
ReEvo applies Language Hyper-Heuristics across diverse optimization algorithms and problems, producing competitive solvers by evolving penalty heuristics, ACO measures, genetic operators, constructive heuristics, and attention reshaping.
- Scope: ReEvo spans routing, subset, grouping, electronic-design, and neural combinatorial optimization settings across heterogeneous solver types.The evaluated problems include TSP, CVRP, OP, MKP, BPP, and DPP.
- Penalty heuristics for Guided Local Search: ReEvo evolves GLS penalty heuristics and improves KGLS while outperforming stated GLS and neural baselines.KGLS-ReEvo uses one heuristic from TSP20 through TSP200, whereas NCO baselines require problem-size-specific training.
- Heuristic measures for Ant Colony Optimization: ReEvo heuristics consistently outperform expert-designed and neural ACO heuristics across COPs and problem sizes.On TSP50, OP50, and MKP100, ReEvo also outperforms DeepACO when DeepACO is overfit to the test size.
- Genetic operators for Electronic Design Automation: ReEvo-generated genetic operators produce a DPP genetic algorithm that outperforms the expert-designed GA and DevFormer.The operators are evolved sequentially for crossover and mutation.
- Constructive heuristics: ReEvo generates constructive TSP heuristics that achieve better results than GHPP on TSPLIB benchmark instances.ReEvo results are averaged over three runs with different starting nodes.
- Attention reshaping for Neural Combinatorial Optimization: ReEvo tailors attention reshaping to neural models and problem distributions, improving original NCO models and outperforming expert-designed reshaping.The reported implementation adds negligible solving time in the cited CVRP1000 example.
6 Evaluating ReEvo
ReEvo is evaluated through fitness-landscape analysis, component ablations, black-box prompting, and comparisons with EoH across multiple COPs and LLMs. The evaluations examine whether reflections improve neighborhood structure, search quality, and sample efficiency.
- Fitness landscape analysis: ReEvo defines an LHH neighborhood as heuristics that an LLM can generate by mutating the current heuristic in response to a prompt.The neighborhood is approximated by repeatedly sampling from the LLM’s conditional generation distribution.
- Fitness landscape analysis: Smaller correlation length indicates a more rugged fitness landscape, and ReEvo’s reflection-based random walks produce less rugged landscapes and better search results.The analysis averages correlation length over three runs with 40 random-walk steps each.
- Comparative evaluations: Black-box prompting hides COP information while asking LHHs to generate heuristics from general problem representations such as edge_attr instead of distance_matrix.This setting is intended to evaluate heuristic design for novel problems rather than retrieve code tailored to prominent COPs.
- Ablation studies: ReEvo improves sample efficiency over generation without evolution, and its long-term reflection, short-term reflection, crossover, and mutation components each contribute positively in white-box and black-box prompting.The ablation evaluates ACO heuristic generation for TSP100.
- Comparative evaluations: ReEvo demonstrates superior sample efficiency to EoH across TSP, CVRP, OP, MKP, and BPP using GPT-3.5 Turbo, GPT-4 Turbo, and Llama 3 (70B).Each comparison uses black-box prompting and three runs per setting.
7 Discussions and limitations
The discussion positions ReEvo for costly-evaluation settings and contrasts LHHs with neural combinatorial optimization methods. It also identifies limitations involving evaluation scale and dependence on capable LLMs.
- When to use ReEvo as an LHH: ReEvo is intended for settings where heuristic evaluation is costly because experiments use only 100 evaluation shots and results do not necessarily scale up.Allowing many evaluations could obscure the contribution of reflection and other prompting techniques.
- LHH and NCO methods: LHHs generate interpretable rule-based heuristics, whereas NCO methods generate black-box neural policies that may be more expressive but can underfit less complexly?The supplied passage states that rule-based heuristics may underfit in complex environments; the comparison concerns interpretability and expressiveness.
- LHH and NCO methods: LHHs require fewer than 100 heuristic evaluations and about 5 minutes to evolve a strong heuristic, while many NCO methods require millions of samples and days of training.The comparison is framed around practicality when solution evaluation is expensive.
- The choice of LLMs for ReEvo: Reflection is more effective with capable LLMs, while many open-source LLMs are not capable enough to guarantee statistically significant improvement from reflections.The authors expect this limitation to diminish as LLM capabilities improve.
- Benchmarking LHHs: Benchmarking LHHs should prioritize heuristic evaluations because method differences become nearly indistinguishable when many evaluations are allowed.The discussion treats LLM-query overhead as negligible relative to costly real-world heuristic evaluations.
8 Conclusion
The paper concludes that LHHs and ReEvo broaden automated heuristic design through open-ended LLM-generated heuristics, reflective evolutionary search, and evaluations spanning diverse algorithms, COPs, and problem views. The authors report strong solver results and identify broader applications and theoretical foundations as future directions.
- 8 Conclusion: ReEvo combines evolutionary computation with LLM reflections to search open-ended heuristic spaces for Language Hyper-Heuristics.The framework interprets genetic cues through verbal reflections and uses them to guide heuristic search.
- 8 Conclusion: Across five heterogeneous algorithmic types, six COPs, and white-box and black-box settings, ReEvo produces state-of-the-art and competitive solvers.The reported solver types include meta-heuristics, evolutionary algorithms, heuristics, and neural solvers.
- 8 Conclusion: ReEvo extends LHH research through reflective evolutionary search, applications across GLS, EDA, ACO, and NCO, fitness-landscape analysis, and black-box evaluation.These dimensions are presented as extensions beyond concurrent work on Evolution of Heuristics.
- Future directions: ReEvo is generally applicable to string-based optimization when reflecting on relative string performance is meaningful.Preliminary prompt-tuning experiments reportedly favored ReEvo over random search and vanilla genetic programming.
- Implementation: Adapting ReEvo to a new problem setting requires defining the problem description, function description, and function signature.The prompt structure is described as flexible and extensible.
C Detailed experimental setup
The experiments apply ReEvo across GLS, ACO, and related settings, using repeated evolutionary runs, validation-based selection, and parallel evaluation when possible.
- Evaluation protocol: Three ReEvo runs are performed for each COP setting, and the best validation heuristic is selected for final testing on 64 held-out instances.The selection procedure separates validation-based heuristic choice from final evaluation.
- Evaluation protocol: When hardware permits, heuristics from the same generation are generated, reflected upon, and evaluated in parallel.A single run can take approximately two minutes to hours, and costs about $0.06 with GPT3.5 Turbo.
- Guided Local Search: ReEvo is applied to GLS, where heuristics guide perturbation-enhanced local search by prioritizing edges with higher heuristic values for penalization.Training evaluates heuristics on TSP200 using 1200 GLS iterations.
- Ant Colony Optimization: ACO alternates solution sampling with pheromone updates, while heuristics bias sampling toward more promising regions and ReEvo searches for those heuristics.ACO evaluations use parameters adjusted for performance and efficient evaluation.
C.3 Genetic operators for Electronic Design Automation
The EDA experiments use an expert-designed genetic algorithm for DPP and sequentially optimize its crossover and mutation operators with ReEvo.
- Setup: The expert-designed GA represents DPP solutions as decap locations on a power distribution network and serves as an imitation-learning expert policy.DPP seeks capacitor placements that suppress probing-port impedance while respecting keep-out regions.
- Genetic operators: The baseline GA uses a population of 20, retains 4 elites, selects the better half for crossover, and repairs mutations that violate placement constraints.Its operators include random initialization, elitism, random crossover, and feasibility-aware mutation.
- ReEvo optimization: ReEvo sequentially optimizes crossover and mutation while holding the remaining GA pipeline fixed.Mutation optimization additionally uses the best crossover previously generated by ReEvo.
- Evaluation: Training evaluates the objective on three randomly generated instances using 10 GA iterations per instance, with final testing on the dataset from the reference study.The setup includes separately specified ReEvo, ACO, and GLS parameter tables.
D Benchmark problems
The benchmark suite covers routing, subset, grouping, and electronic-design problems, with synthetic or reference-based instance generation tailored to each problem.
- Routing problems: TSP seeks the shortest route visiting every city exactly once and returning to the origin, with synthetic nodes sampled uniformly from the unit square.The benchmark uses Euclidean-style synthetic instances.
- Routing problems: CVRP extends TSP with vehicle-capacity constraints and minimizes delivery distance; instances use unit-square locations, demands from 1 through 9, and capacity 50.The depot is placed at the unit-square center.
- Routing problems: OP maximizes collected node score under a maximum tour length, with challenging prize and length settings across instance sizes.Maximum lengths are 3, 4, 5, 8, and 12 for OP50 through OP1000.
- Subset problems: MKP assigns weighted-value items among multiple knapsacks to maximize value without exceeding capacities, using uniformly sampled values and weights.Instance generation follows the DeepACO procedure.
- Grouping problems: BPP packs variable-size objects into fixed-capacity bins while minimizing bin count, using capacity 150 and item sizes from 20 to 100.The benchmark follows the cited construction procedure.
- Electronic design automation: DPP optimizes decoupling-capacitor placement in a power-distribution network to improve power integrity, using 10 × 10 instances and reference test cases.Training and validation instances follow Kim et al., while tests are drawn directly from that work.
E Generated heuristics
ReEvo generates heuristics for neural, evolutionary, local-search, constructive, and ACO solvers across the benchmark problems, including black-box settings and seeded search.
- Overview: The section reports the best heuristics generated by ReEvo across all problem settings.Reported settings include neural combinatorial optimization, GLS, ACO, constructive TSP solving, and DPP genetic algorithms.
- Guided Local Search: The generated TSP_GLS heuristic combines local distance statistics with global distance structure.The construction uses reciprocal and logarithmic distance terms together with local and global components.
- Genetic algorithms: For DPP_GA, ReEvo-generated operators include crossover that combines parent segments and mutation followed by feasibility repair.The mutation operator avoids probing-port and prohibited locations through a repairing step.
- Ant Colony Optimization: The TSP_ACO black-box heuristic applies feature engineering and normalization to edge attributes before computing heuristic values.In this setting, edge_attr represents the distance matrix.
- Ant Colony Optimization: The MKP_ACO black-box heuristic operates on normalized item prizes and multidimensional weights, while the BPP_ACO heuristic is reported as another ReEvo-generated result.The black-box MKP interface names item_attr1 as prizes and item_attr2 as multidimensional weights.
- Constructive heuristics: The constructive TSP heuristic was seeded with AEL’s best heuristic and therefore closely mirrors its weighted combination of four factors.This is explicitly attributed to the choice of seed for ReEvo.