Multi-Objective Evolution of Heuristic Using Large Language Model
Authors: Shunyu Yao, Fei Liu, Xi Lin, Zhichao Lu, Zhenkun Wang, Qingfu Zhang
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Experiments 5.1 Experimental Settings Problems & Implementation Details We demonstrate MEo H on two representative combinatorial optimization problems: 1) Online Bin Packing Problem... 2) Travelling Salesman Problem... Environments To ensure fairness and consistency, all experiments in this study were conducted on a computer equipped with an Intel Core i7-11700 processor and 32GB of memory. GPT3.5-turbo is employed as the per-trained LLM, with each experiment repeated three times to ensure the robustness and reliability of the results. Performance Metric Objectives 1) Optimal Gap... 2) Efficiency... Metric 1) Hypervolume... 2) IGD... Baseline Methods In this study, our primary focus lies in exploring LLM-based automated heuristic design approaches. Consequently, we compare the two closest related works, namely Fun Search (Romera-Paredes et al. 2024) and Eo H (Liu et al. 2024a). |
| Researcher Affiliation | Academia | 1Department of Computer Science, City University of Hong Kong, Hong Kong, China 2School of System Design and Intelligent Manufacturing, Southern University of Science and Technology, Shen Zhen, China {shunyuyao8, fliu36}-EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: MEo H 1: Input: Population size N; Maximum number of iterations T, Parent selection size d; Initial population P 0; Pre-trained LLM L. 2: Output: Approximate Pareto-set P . 3: if P 0 = then 4: for i = 1, . . . , N do 5: o Generation(L); 6: P 0 P 0 o 7: end for 8: end if 9: for t = 1, . . . , T do 10: for i = 1, . . . , N do 11: P parent Parent Selection(P t 1, d); 12: o Search(L, P parent); 13: P t 1 P t 1 o 14: end for 15: P t Population Management(P t 1, N) 16: end for 17: P P T |
| Open Source Code | Yes | Code https://github.com/Optima-City U/LLM4AD |
| Open Datasets | Yes | We demonstrate MEo H on two representative combinatorial optimization problems: 1) Online Bin Packing Problem (BPP) (Seiden 2002),... The generated heuristics are evaluated on 5 Weibull instances with 5, 000 items (referred to as 5k), and the capacity of bins is 100. We inherit the settings from Romera-Paredes et al. (2024)... 2) Travelling Salesman Problem (TSP) (Reinelt 2003),... The coordinate of each node is randomly sampled from [0, 1] (Kool, van Hoof, and Welling 2018). ... a variety of TSP instances with up to 1, 002 nodes from TSPLIB (Reinelt 1991). |
| Dataset Splits | Yes | The generated heuristics are evaluated on 5 Weibull instances with 5, 000 items (referred to as 5k), and the capacity of bins is 100. We evaluate the fitness of designed heuristics during evolution on 64 instances with 100 nodes. The problem sizes in our test include 5k, 10k, and 100k, and the capacities of the bins are set at 100 and 500. Each test set consists of five instances sampled from Weibull distribution (Romera-Paredes et al. 2024). |
| Hardware Specification | Yes | To ensure fairness and consistency, all experiments in this study were conducted on a computer equipped with an Intel Core i7-11700 processor and 32GB of memory. |
| Software Dependencies | No | The paper mentions "GPT3.5-turbo" as the LLM used, but it does not provide specific version numbers for any software libraries or dependencies, such as Python versions, deep learning frameworks (e.g., PyTorch, TensorFlow), or other specialized packages with their corresponding versions. |
| Experiment Setup | Yes | The experimental parameter settings are as follows: the number of generations is 20, and the population size is 20 and 10 for online BPP and TSP, respectively. Each crossover operator selects 5 parent heuristics to reproduce the offspring heuristics. The number of iterations and running time in the GLS for TSP is limited to 1, 000 and 60 seconds, respectively. |