LLM-as-HH

LLM-as-HH

Large Language Models as Hyper-Heuristics for Combinatorial Optimization (CO)

Stars: 78

Visit
 screenshot

LLM-as-HH is a codebase that accompanies the paper ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution. It introduces Language Hyper-Heuristics (LHHs) that leverage LLMs for heuristic generation with minimal manual intervention and open-ended heuristic spaces. Reflective Evolution (ReEvo) is presented as a searching framework that emulates the reflective design approach of human experts while surpassing human capabilities with scalable LLM inference, Internet-scale domain knowledge, and powerful evolutionary search. The tool can improve various algorithms on problems like Traveling Salesman Problem, Capacitated Vehicle Routing Problem, Orienteering Problem, Multiple Knapsack Problems, Bin Packing Problem, and Decap Placement Problem in both black-box and white-box settings.

README:

Large Language Models as Hyper-Heuristics for Combinatorial Optimization

🥳 Welcome! This is a codebase that accompanies the paper Large Language Models as Hyper-Heuristics for Combinatorial Optimization.

Give ReEvo 5 minutes, and get a state-of-the-art algorithm in return!

Table of Contents

1. News 📰

  • 2024.05: We release a new paper version.
  • 2024.04: Novel use cases for Neural Combinatorial Optimization (NCO) and Electronic Design Automation (EDA).
  • 2024.02: We are excited to release ReEvo! 🚀

2. Introduction 🚀

Diagram of 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.

3. Exciting Highlights 🌟

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.

4. Usage 🔑

  • Set your LLM API key (OpenAI API, ZhiPu API, Llama API) here or as an environment variable.
  • 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.

4.1. Dependency

  • 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-learn
  • cvrp_aco(_black_box) / mkp_aco(_black_box) / op_aco(_black_box) / NCO: pytorch
  • tsp_gls: numba==0.58

4.2. To run ReEvo

# e.g., for tsp_aco
python main.py problem=tsp_aco

Check out ./cfg/ for more options.

4.3. Available problems

  • 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

4.4. Simple steps to apply ReEvo to your problem

  • 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/.

4.5. Use Alternative LLMs

Use the cli parameter llm_client to designate an LLM API provider, and llm_client.model to determine the model to use. For example,

$ export LLAMA_API_KEY=xxxxxxxxxxxxxxxxxxxx
$ python main.py llm_client=llama_api llm_client.model=gemma2-9b

Supported LLM API providers and models including (to be noted that only chat models are supported):

5. Citation 🤩

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 are so kind as to offer us some encouragement), please consider giving us a star, and citing our paper.

@article{ye2024large,
      title={Large Language Models as Hyper-Heuristics for Combinatorial Optimization}, 
      author={Haoran Ye and Jiarui Wang and Zhiguang Cao and Federico Berto and Chuanbo Hua and Haeyeon Kim and Jinkyoo Park and Guojie Song},
      year={2024},
      journal={arXiv preprint arXiv:2402.01145},
      note={\url{https://github.com/ai4co/LLM-as-HH}}
}

6. Acknowledgments 🫡

We are very grateful to Yuan Jiang, Yining Ma, Yifan Yang, and AI4CO community for valuable discussions and feedback.

Also, our work is built upon the following projects, among others:

For Tasks:

Click tags to check more tools for each tasks

For Jobs:

Alternative AI tools for LLM-as-HH

Similar Open Source Tools

For similar tasks

For similar jobs