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.
$ git clone git@github.com:ai4co/reevo.git # download reevo code
$ cd reevo
$ python3 -m venv ./venv # [optional] create virtual environment
$ source ./venv/bin/activate # [optional] activate virtual environment
$ pip install -r requirements.txt # install dependencies
$ pip install numba==0.58 # dependency specifically required by `tsp_gls`
$ export OPENAI_API_KEY=xxxxxxxxxx # set openAI API key, other service providers are also available
$ python3 main.py problem=tsp_gls
tsp_aco, tsp_aco_black_box, tsp_constructive, tsp_gls, tsp_pomo, tsp_lehdcvrp_aco, cvrp_aco_black_box, cvrp_pomo, cvrp_lehdbpp_offline_aco, bpp_offline_aco_black_box, bpp_onlinemkp_aco, mkp_aco_black_boxop_aco, op_aco_black_boxdpp_ga$ export LLAMA_API_KEY=xxxxxxxxxxxxxxxxxxxx
$ python3 main.py llm_client=llama_api llm_client.model=gemma2-9b
@inproceedings{ye2024reevo,
title={ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution},
author={Haoran Ye and Jiarui Wang and Zhiguang Cao and Federico Berto and Chuanbo Hua and Haeyeon Kim and Jinkyoo Park and Guojie Song},
booktitle={Advances in Neural Information Processing Systems},
year={2024},
note={\url{https://github.com/ai4co/reevo}}
}| Sep. 2024 | ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution has been accepted at NeurIPS 2024 🥳 |
|---|---|
| May 2024 | We release a new paper version |
| Apr. 2024 | Novel use cases for Neural Combinatorial Optimization (NCO) and Electronic Design Automation (EDA) |
| Feb. 2024 | We are excited to release ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution 🚀 |