ReEvo: Large language models as hyper-heuristics with reflective evolution

• Main Authors: YE, Haoran, WANG, Jiarui, CAO, Zhiguang, BERTO, Federico, HUA, Chuanbo, KIM, Haeyeon, PARK, Jinkyoo, SONG, Guojie
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Artificial Intelligence and Robotics; Programming Languages and Compilers
• Online Access: https://ink.library.smu.edu.sg/sis_research/9815; https://ink.library.smu.edu.sg/context/sis_research/article/10815/viewcontent/2402.01145v3.pdf
• Institution: Singapore Management University

The omnipresence of NP-hard combinatorial optimization problems (COPs) compels domain experts to engage in trial-and-error heuristic design process. 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 generic searching framework that emulates the reflective design approach of human experts while far surpassing human capabilities with its scalable LLM inference, Internet-scale domain knowledge, and powerful evolutionary search. Evaluations across 12 COP settings show that 1) verbal reflections for evolution lead to smoother fitness landscapes, explicit inference of black-box COP settings, and better search results; 2) heuristics generated by ReEvo in minutes can outperform state-of-the-art human designs and neural solvers; 3) LHHs enable efficient algorithm design automation even when challenged with black-box COPs, demonstrating its potential for complex and novel real-world applications. Our code is available: https://github.com/ai4co/LLM-as-HH.