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

**Authors:** Haoran Ye, Jiarui Wang, Zhiguang Cao, Guojie Song  
**arXiv:** [2402.01145](https://arxiv.org/abs/2402.01145)  
**Date:** 2024-02-02  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2402.01145v1/

## Key points

- Large language models (LLMs) are used in design automation for solving NP-hard combinatorial optimization problems (COPs)
- Language Hyper-Heuristics (LHHs) utilize LLMs to generate heuristics
- LHHs offer advantages such as minimal manual intervention and open-ended heuristic spaces
- Reflective Evolution (ReEvo) is a searching framework that emulates the reflective design approach used by human experts
- ReEvo utilizes scalable LLM inference, Internet-scale domain knowledge, and powerful evolutionary search algorithms
- ReEvo outperforms human designs and neural solvers in generating heuristics for COPs
- Verbal reflections for evolution lead to smoother fitness landscapes and better search results
- LHHs enable efficient algorithm design automation even for complex black-box COPs
- The research highlights the potential of using LLMs and reflective evolution techniques in automating the design process for challenging combinatorial optimization problems

## Summary

This paper discusses the use of large language models (LLMs) in the field of design automation for solving NP-hard combinatorial optimization problems (COPs). COPs are challenging problems that often require domain experts to engage in a trial-and-error heuristic design process. However, with the emergence of LLMs, there has been renewed interest in automating this process. In this study, the authors introduce Language Hyper-Heuristics (LHHs), a variant of Hyper-Heuristics that utilizes LLMs to generate heuristics. LHHs offer several advantages including minimal manual intervention and open-ended heuristic spaces. To further enhance LHHs, the authors propose Reflective Evolution (ReEvo), a searching framework that emulates the reflective design approach used by human experts. ReEvo surpasses human capabilities by utilizing scalable LLM inference, Internet-scale domain knowledge, and powerful evolutionary search algorithms. The authors evaluate ReEvo across 12 COP settings and make several key observations. Firstly, verbal reflections for evolution lead to smoother fitness landscapes and explicit inference of black-box COP settings, resulting in better search results. Secondly, heuristics generated by ReEvo in just a few minutes outperform state-of-the-art human designs and neural solvers. Finally, LHHs enable efficient algorithm design automation even when faced with complex black-box COPs, demonstrating their potential for real-world applications. Overall, this research highlights the potential of using LLMs and reflective evolution techniques to automate the design process for solving challenging combinatorial optimization problems. The code for this work is available on GitHub for further exploration and experimentation.