ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution

TL;DR

ReEvo is a method that uses LLMs as hyper-heuristics to automatically generate heuristics for combinatorial optimization problems, combining evolutionary search with LLM reflections to efficiently explore the heuristic space.

Problem

NP-hard combinatorial optimization problems rely on domain experts' trial-and-error heuristic design. Existing automated design methods involve heavy manual intervention or have limited heuristic spaces. LLM-based hyper-heuristics (LHHs) have the potential to overcome these limitations but lack efficient search strategies.

Approach

ReEvo explores the heuristic space via an evolutionary algorithm and provides verbal gradients through LLM reflections on the performance of generated heuristics in each generation. This feedback guides the generation of heuristics in the next generation. It is applicable to various COPs (e.g., traveling salesman problem, knapsack problem) and algorithm types (metaheuristics, evolutionary algorithms, heuristics, neural solvers).

Results & Contribution

ReEvo achieves state-of-the-art or competitive performance across five heterogeneous algorithm types, six different COPs, and both white-box and black-box settings. It is more sample-efficient than prior LHHs, finding good heuristics with fewer evaluations. It presents a new paradigm for LLM-based hyper-heuristics and makes significant contributions to the field of automated heuristic design.