🥳 Welcome! This is a codebase that accompanies the paper ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution.
Give ReEvo 5 minutes, and get a state-of-the-art algorithm in return!
-
- Usage 🔑
- 4.1. Dependency
- 4.2. To run ReEvo
- 4.3. Available problems
- 4.4. Simple steps to apply ReEvo to your problem
- Usage 🔑
- Apr 2024: Added use cases for Neural Combinatorial Optimization (NCO) and Electronic Design Automation (EDA). The paper will be updated soon.
- Feb 2024: We are excited to release ReEvo! 🚀
We introduce Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics (HHs) 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 much surpassing human capabilities with its scalable LLM inference, Internet-scale domain knowledge, and powerful evolutionary search.
We can improve the following types of algorithms:
- Neural Combinatorial Optimization (NCO)
- Genetic Algorithm (GA)
- Ant Colony Optimization (ACO)
- Guided Local Search (GLS)
- Constructive Heuristics
on the following problems:
- Traveling Salesman Problem (TSP)
- Capacitated Vehicle Routing Problem (CVRP)
- Orienteering Problem (OP)
- Multiple Knapsack Problems (MKP)
- Bin Packing Problem (BPP)
- Decap Placement Problem (DPP)
with both black-box and white-box settings.
- Set your LLM API key (OpenAI API, ZhiPu API, Llama API) here or as an environment variable.
- OPENAI_API_KEY =
- Running logs and intermediate results are saved in
./outputs/main/by default. - Datasets are generated on the fly.
- Some test notebooks are provided in
./problems/*/test.ipynb.
- Python >= 3.11
- openai >= 1.0.0
- hydra-core
- scipy
You may install the dependencies above via pip install -r requirements.txt.
Problem-specific dependencies:
tsp_aco(_black_box): pytorch, scikit-learncvrp_aco(_black_box)/mkp_aco(_black_box)/op_aco(_black_box)/NCO: pytorchtsp_gls: numba==0.58
# e.g., for tsp_aco
python main.py problem=tsp_aco
python main.py problem=tsp_aco timeout==1000Check out ./cfg/ for more options.
- Traveling Salesman Problem (TSP):
tsp_aco,tsp_aco_black_box,tsp_constructive,tsp_gls,tsp_pomo,tsp_lehd - Capacitated Vehicle Routing Problem (CVRP):
cvrp_aco,cvrp_aco_black_box,cvrp_pomo,cvrp_lehd - Bin Packing Problem (BPP):
bpp_offline_aco,bpp_offline_aco_black_box,bpp_online - Multiple Knapsack Problems (MKP):
mkp_aco,mkp_aco_black_box - Orienteering Problem (OP):
op_aco,op_aco_black_box - Decap Placement Problem (DPP):
dpp_ga
- Define your problem in
./cfg/problem/. - Generate problem instances and implement the evaluation pipeline in
./problems/. - Add function_description, function_signature, and seed_function in
./prompts/.
If you encounter any difficulty using our code, please do not hesitate to submit an issue or directly contact us! If you find our work helpful (or if you would be so kind as to offer us some encouragement), please consider kindly giving us a star, and citing our paper.
@misc{ye2024reevo,
title={ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution},
author={Haoran Ye and Jiarui Wang and Zhiguang Cao and Guojie Song},
year={2024},
eprint={2402.01145},
archivePrefix={arXiv},
primaryClass={cs.NE}
}We are very grateful to Federico Berto, Yuan Jiang, Yining Ma, Chuanbo Hua, and AI4CO community for valuable discussions and feedback.
Also, our work is built upon the following projects, among others:
- DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization
- Eureka: Human-Level Reward Design via Coding Large Language Models
- Algorithm Evolution Using Large Language Model
- Mathematical discoveries from program search with large language models
- An Example of Evolutionary Computation + Large Language Model Beating Human: Design of Efficient Guided Local Search
- DevFormer: A Symmetric Transformer for Context-Aware Device Placement