ai4co / llm-as-hh Goto Github PK

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

License: MIT License

Python 89.99% Jupyter Notebook 10.01%

ant-colony-optimization automatic-algorithm-generation bin-packing-problem evolutionary-algorithms genetic-algorithm hyper-heuristics large-language-models llm-agent multiple-knapsack-problem neural-combinatorial-optimization orienteering-problem reinforcement-learning traveling-salesman-problem vehicle-routing-problem

llm-as-hh's Introduction

Large Language Models as Hyper-Heuristics for Combinatorial Optimization

🥳 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!

1. News 📰
1. Introduction 🚀
1. Exciting Highlights 🌟
1. Usage 🔑
  - 4.1. Dependency
  - 4.2. To run ReEvo
  - 4.3. Available problems
  - 4.4. Simple steps to apply ReEvo to your problem
1. Citation 🤩
1. Acknowledgments 🫡

1. News 📰

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! 🚀

2. Introduction 🚀

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

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 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}
}

6. Acknowledgments 🫡

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:

llm-as-hh's People

Contributors

Stargazers

Watchers

Forkers

xi7997 wuyuesong akrichikov ahmed-salah00 khalidallam222 henry-yeh ziao-guo zsl1314521664 langkhachhoha yining043 githubwhutfan lpjdragon

llm-as-hh's Issues

Seed function is invalid exception

Hello ReEvo team!

I've been trying to use ziphuAi instead of Gpt4 to run the prompts. I've provided the api key for ziphuAi, and I've done some changes in the config.yaml to enable that.

# LLM parameters
model: GLM-4  # LLM model (other options include gpt-4-turbo-preview, GLM-3-Turbo, GLM-4)
temperature: 1  # temperature for chat completion
suffix: GLM  # suffix for generated files (indicates LLM model)

but when I run the code an exception happens due to seed function. Can you please help with that?

Here is the full error:

python main.py problem=tsp_constructive algorithm=reevo
[2024-04-08 13:05:18,818][root][INFO] - Workspace: C:\Users\kjkj0\LLM-as-HH\outputs\main\2024-04-08_13-05-18
[2024-04-08 13:05:18,819][root][INFO] - Project Root: C:\Users\kjkj0\LLM-as-HH
[2024-04-08 13:05:18,819][root][INFO] - Using LLM: GLM-4
[2024-04-08 13:05:18,819][root][INFO] - Using Algorithm: reevo
[2024-04-08 13:05:19,378][root][INFO] - Problem: tsp_constructive
[2024-04-08 13:05:19,378][root][INFO] - Problem description: Solving Traveling Salesman Problem (TSP) with constructive heuristics. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
[2024-04-08 13:05:19,378][root][INFO] - Function name: select_next_node
[2024-04-08 13:05:19,379][root][INFO] - Evaluating seed function...
[2024-04-08 13:05:19,389][root][INFO] - Seed function code:
import numpy as np
def select_next_node_v2(current_node: int, destination_node: int, unvisited_nodes: set, distance_matrix: np.ndarray) -> int:
    """Select the next node to visit from the unvisited nodes."""
    threshold = 0.7
    c1, c2, c3, c4 = 0.4, 0.3, 0.2, 0.1
    scores = {}
    for node in unvisited_nodes:
        all_distances = [distance_matrix[node][i] for i in unvisited_nodes if i != node]
        average_distance_to_unvisited = np.mean(all_distances)
        std_dev_distance_to_unvisited = np.std(all_distances)
        score = c1 * distance_matrix[current_node][node] - c2 * average_distance_to_unvisited + c3 * std_dev_distance_to_unvisited - c4 * distance_matrix[destination_node][node]
        scores[node] = score
    next_node = min(scores, key=scores.get)
    return next_node
[2024-04-08 13:05:19,389][root][INFO] - Iteration 0: Running Code 0
[2024-04-08 13:05:19,553][root][INFO] - Iteration 0: Code Run 0 execution error!
[2024-04-08 13:05:19,572][root][INFO] - Iteration 0, response_id 0: Objective value: inf
Error executing job with overrides: ['problem=tsp_constructive', 'algorithm=reevo']
Traceback (most recent call last):
  File "C:\Users\kjkj0\LLM-as-HH\main.py", line 52, in <module>
    main()
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\main.py", line 94, in decorated_main
    _run_hydra(
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\_internal\utils.py", line 394, in _run_hydra
    _run_app(
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\_internal\utils.py", line 457, in _run_app
    run_and_report(
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\_internal\utils.py", line 223, in run_and_report
    raise ex
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\_internal\utils.py", line 220, in run_and_report
    return func()
           ^^^^^^
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\_internal\utils.py", line 458, in <lambda>
    lambda: hydra.run(
            ^^^^^^^^^^
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\_internal\hydra.py", line 132, in run
    _ = ret.return_value
        ^^^^^^^^^^^^^^^^
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\core\utils.py", line 260, in return_value
    raise self._return_value
  File "C:\Users\kjkj0\LLM-as-HH\revo-venv-ziphu\Lib\site-packages\hydra\core\utils.py", line 186, in run_job
    ret.return_value = task_function(task_cfg)
                       ^^^^^^^^^^^^^^^^^^^^^^^
  File "C:\Users\kjkj0\LLM-as-HH\main.py", line 31, in main
    reevo = ga(cfg, ROOT_DIR)
            ^^^^^^^^^^^^^^^^^
  File "C:\Users\kjkj0\LLM-as-HH\reevo.py", line 26, in __init__
    self.init_population()
  File "C:\Users\kjkj0\LLM-as-HH\reevo.py", line 98, in init_population
    raise RuntimeError(f"Seed function is invalid. Please check the stdout file in {os.getcwd()}.")
RuntimeError: Seed function is invalid. Please check the stdout file in C:\Users\kjkj0\LLM-as-HH\outputs\main\2024-04-08_13-05-18.