ReEvo
Reflective Evolution
An evolutionary search over heuristics in which a second LLM role writes short and long 'reflections' that steer crossover and mutation.
The loop
- Proposes
Heuristic code produced by LLM crossover and elitist mutation
- Judged by
Running the heuristic on problem instances to get an objective value
- Steers
Short-term reflection compares parents; long-term reflection accumulates hints; both feed later prompts ('verbal gradient')
Headline result
Across six combinatorial problems (TSP, CVRP, OP, MKP, BPP, DPP), with a budget of 100 heuristic evaluations and GPT-3.5 Turbo, ReEvo beats EoH on sample efficiency in five problems, and designed heuristics improved neural solvers, for example POMO's TSP1000 gap from about 52% to 29%. Its genetic algorithm for decap placement scored 12.98 vs 12.41 for the expert-designed one.
What this does not prove
Authors' benchmark set-ups with GPT-3.5 Turbo as the main model; 'state of the art' refers to the compared methods in the paper.
How it generalizes the harness
Evolutionary search is the solver over a population, and the product is a heuristic or operator that runs without the model.
Classification
| What it proposes | Heuristic |
|---|---|
| Generative model | Pretrained LLMs, frozen (GPT-3.5 Turbo, GPT-4 Turbo, Llama 3 70B compared) |
| Algorithmic authority | Objective evaluation on problem instances |
| Feedback | Written reflection |
| What gets updated | Prompt context and population of candidates |
| When it runs | Offline, at design time |
| Validity | Empirical (measured) |
| Evidence | Experiments reported |
| Lineage | Derivative |