2024

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

Ye, Haoran, Wang, Jiarui, Cao, Zhiguang et al.

Understand

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.

Built on

Correlated and uncorrelated fitness landscapes and how to tell the difference
E. Weinberger · 1990
Earlier work this paper cites.
Tsplib—a traveling salesman problem library
G. Reinelt · 1991
Earlier work this paper cites.
A measure of landscapes
W. Hordijk · 1996
Earlier work this paper cites.
Guided local search and its application to the traveling salesman problem
C. Voudouris and E. Tsang · 1999
Earlier work this paper cites.
Ant colony optimization and local search for bin packing and cutting stock problems
J. Levine and F. Ducatelle · 2004
Earlier work this paper cites.
Power distribution networks with on-chip decoupling capacitors
M. Popovich, A. Mezhiba, and E. G. Friedman · 2007
Earlier work this paper cites.
Analyzing the landscape of a graph based hyper-heuristic for timetabling problems
G. Ochoa, R. Qu, and E. K. Burke · 2009
Earlier work this paper cites.
Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics
J. Hromkovič · 2013
Earlier work this paper cites.
Decoupling-capacitor allocation problem solved by genetic algorithm
K. Shibasaka, K. Kanazawa, and M. Yasunaga · 2013
Earlier work this paper cites.
Hyper-heuristics: theory and applications
N. Pillay and R. Qu · 2018
Earlier work this paper cites.
Evolutionary electronics: automatic design of electronic circuits and systems by genetic algorithms
R. S. Zebulum, M. A. Pacheco, and M. M. B. Vellasco · 2018
Earlier work this paper cites.
Knowledge-guided local search for the vehicle routing problem
F. Arnold and K. Sörensen · 2019
Earlier work this paper cites.
A gp hyper-heuristic approach for generating tsp heuristics
G. Duflo, E. Kieffer, M. R. Brust, G. Danoy, and P. Bouvry · 2019
Earlier work this paper cites.
Multi-objective optimization of decoupling capacitors for placement and component value
I. Erdin and R. Achar · 2019
Earlier work this paper cites.
Attention, learn to solve routing problems!
W. Kool, H. van Hoof, and M. Welling · 2019
Earlier work this paper cites.
Genetic algorithm pdn optimization based on minimum number of decoupling capacitors applied to arbitrary target impedance
F. de Paulis, R. Cecchetti, C. Olivieri, and M. Buecker · 2020
Earlier work this paper cites.
Recent advances in selection hyper-heuristics
J. H. Drake, A. Kheiri, E. Özcan, and E. K. Burke · 2020
Earlier work this paper cites.
Hybrid ant colony optimization algorithm for multiple knapsack problem
S. Fidanova · 2020
Earlier work this paper cites.
Learning the travelling salesperson problem requires rethinking generalization
Original
C. K. Joshi, Q. Cappart, L.-M. Rousseau, and T. Laurent · 2020
Earlier work this paper cites.
Pomo: Policy optimization with multiple optima for reinforcement learning
Y.-D. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, and S. Min · 2020
Earlier work this paper cites.
Policy gradient reinforcement learning-based optimal decoupling capacitor design method for 2.5-d/3-d ics using transformer network
H. Park, M. Kim, S. Kim, S. Jeong, S. Kim, H. Kang, K. Kim, K. Son, G. Park, K. Son, et al · 2020
Earlier work this paper cites.
An enhanced deep reinforcement learning algorithm for decoupling capacitor selection in power distribution network design
L. Zhang, W. Huang, J. Juang, H. Lin, B.-C. Tseng, and C. Hwang · 2020
Earlier work this paper cites.
Machine learning for combinatorial optimization: a methodological tour d’horizon
Y. Bengio, A. Lodi, and A. Prouvost · 2021
Earlier work this paper cites.
Deep reinforcement learning framework for optimal decoupling capacitor placement on general pdn with an arbitrary probing port
H. Kim, H. Park, M. Kim, S. Choi, J. Kim, J. Park, S. Kim, S. Kim, and J. Kim · 2021
Earlier work this paper cites.
Acs-ophs: Ant colony system for the orienteering problem with hotel selection
S. Sohrabi, K. Ziarati, and M. Keshtkaran · 2021
Earlier work this paper cites.
A dynamic space reduction ant colony optimization for capacitated vehicle routing problem
J. Cai, P. Wang, S. Sun, and H. Dong · 2022
Earlier work this paper cites.
Graph neural network guided local search for the traveling salesperson problem
B. Hudson, Q. Li, M. Malencia, and A. Prorok · 2022
Earlier work this paper cites.

Similar

Sym-nco: Leveraging symmetricity for neural combinatorial optimization
M. Kim, J. Park, and J. Park · 2022
Cited alongside, same era.
Competition-level code generation with alphacode
Y. Li, D. Choi, J. Chung, N. Kushman, J. Schrittwieser, R. Leblond, T. Eccles, J. Keeling, F. Gimeno, A. Dal Lago, et al · 2022
Cited alongside, same era.
Transformer network-based reinforcement learning method for power distribution network (pdn) optimization of high bandwidth memory (hbm)
H. Park, M. Kim, S. Kim, K. Kim, H. Kim, T. Shin, K. Son, B. Sim, S. Kim, S. Jeong, et al · 2022
Cited alongside, same era.
Improving ant colony optimization efficiency for solving large tsp instances
R. Skinderowicz · 2022
Cited alongside, same era.
Planning with large language models for code generation
S. Zhang, Z. Chen, Y. Shen, M. Ding, J. B. Tenenbaum, and C. Gan · 2022
Cited alongside, same era.
Large language models are human-level prompt engineers
Original
Y. Zhou, A. I. Muresanu, Z. Han, K. Paster, S. Pitis, H. Chan, and J. Ba · 2022
Cited alongside, same era.
RL4CO: a unified reinforcement learning for combinatorial optimization library
F. Berto, C. Hua, J. Park, M. Kim, H. Kim, J. Son, H. Kim, J. Kim, and J. Park · 2023
Cited alongside, same era.
Large language models can implement policy iteration
E. Brooks, L. A. Walls, R. Lewis, and S. Singh · 2023
Cited alongside, same era.
Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization
D. Drakulic, S. Michel, F. Mai, A. Sors, and J.-M. Andreoli · 2023
Cited alongside, same era.
Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy
Original
C. Gao, H. Shang, K. Xue, D. Li, and C. Qian · 2023
Cited alongside, same era.
A hierarchical hyper-heuristic for the bin packing problem
F. Guerriero and F. P. Saccomanno · 2023
Cited alongside, same era.
Connecting large language models with evolutionary algorithms yields powerful prompt optimizers
Original
Q. Guo, R. Wang, J. Guo, B. Li, K. Song, X. Tan, G. Liu, J. Bian, and Y. Yang · 2023
Cited alongside, same era.

Then

Reflexion: Language agents with verbal reinforcement learning
N. Shinn, F. Cassano, A. Gopinath, K. R. Narasimhan, and S. Yao · 2023
Later among the works it cites.
Solving np-hard min-max routing problems as sequential generation with equity context
Original
J. Son, M. Kim, S. Choi, and J. Park · 2023
Later among the works it cites.
Neuralgls: learning to guide local search with graph convolutional network for the traveling salesman problem
J. Sui, S. Ding, B. Xia, R. Liu, and D. Bu · 2023
Later among the works it cites.
Difusco: Graph-based diffusion solvers for combinatorial optimization
Z. Sun and Y. Yang · 2023
Later among the works it cites.
The rise and potential of large language model based agents: A survey
Original
Z. Xi, W. Chen, X. Guo, W. He, Y. Ding, B. Hong, M. Zhang, J. Wang, S. Jin, E. Zhou, et al · 2023
Later among the works it cites.
Reinforcement learning-based non-autoregressive solver for traveling salesman problems
Original
Y. Xiao, D. Wang, H. Chen, B. Li, W. Pang, X. Wu, H. Li, D. Xu, Y. Liang, and Y. Zhou · 2023
Later among the works it cites.
A survey on reinforcement learning for combinatorial optimization
Y. Yang and A. Whinston · 2023
Later among the works it cites.
Deepaco: Neural-enhanced ant systems for combinatorial optimization
H. Ye, J. Wang, Z. Cao, H. Liang, and Y. Li · 2023
Later among the works it cites.
Automatic hyper-heuristic to generate heuristic-based adaptive sliding mode controller tuners for buck-boost converters
D. Zambrano-Gutierrez, J. Cruz-Duarte, and H. Castañeda · 2023
Later among the works it cites.
Self-taught optimizer (stop): Recursively self-improving code generation
Original
E. Zelikman, E. Lorch, L. Mackey, and A. T. Kalai · 2023
Later among the works it cites.
Learning large neighborhood search for vehicle routing in airport ground handling
J. Zhou, Y. Wu, Z. Cao, W. Song, J. Zhang, and Z. Chen · 2023
Later among the works it cites.
Surgical cases assignment problem using an efficient genetic programming hyper-heuristic
L. Zhu, Y. Zhou, S. Sun, and Q. Su · 2023
Later among the works it cites.
Tackling prevalent conditions in unsupervised combinatorial optimization: Cardinality, minimum, covering, and more
Original
F. Bu, H. Jo, S. Y. Lee, S. Ahn, and K. Shin · 2024
Closest in time.
A match made in consistency heaven: when large language models meet evolutionary algorithms, 2024
W. Chao, J. Zhao, L. Jiao, L. Li, F. Liu, and S. Yang · 2024
Closest in time.
Moco: A learnable meta optimizer for combinatorial optimization
Original
T. Dernedde, D. Thyssens, S. Dittrich, M. Stubbemann, and L. Schmidt-Thieme · 2024
Closest in time.
Evolving code with a large language model, 2024
E. Hemberg, S. Moskal, and U.-M. O’Reilly · 2024
Closest in time.
A novel physics-assisted genetic algorithm for decoupling capacitor optimization
L. Jiang, L. Zhang, S. Tan, D. Li, C. Hwang, J. Fan, and E.-P. Li · 2024
Closest in time.
Ant colony sampling with gflownets for combinatorial optimization
Original
M. Kim, S. Choi, J. Son, H. Kim, J. Park, and Y. Bengio · 2024
Closest in time.
Bridging evolutionary algorithms and reinforcement learning: A comprehensive survey, 2024
P. Li, J. Hao, H. Tang, X. Fu, Y. Zheng, and K. Tang · 2024
Closest in time.
Evolution of heuristics: Towards efficient automatic algorithm design using large language mode
Original
F. Liu, X. Tong, M. Yuan, X. Lin, F. Luo, Z. Wang, Z. Lu, and Q. Zhang · 2024
Closest in time.
Position paper: Leveraging foundational models for black-box optimization: Benefits, challenges, and future directions
Original
X. Song, Y. Tian, R. T. Lange, C. Lee, Y. Tang, and Y. Chen · 2024
Closest in time.
Himap: Learning heuristics-informed policies for large-scale multi-agent pathfinding
Original
H. Tang, F. Berto, Z. Ma, C. Hua, K. Ahn, and J. Park · 2024
Closest in time.
Evolutionary computation in the era of large language model: Survey and roadmap, 2024
X. Wu, S. hao Wu, J. Wu, L. Feng, and K. C. Tan · 2024
Closest in time.
Distilling autoregressive models to obtain high-performance non-autoregressive solvers for vehicle routing problems with faster inference speed
Y. Xiao, D. Wang, B. Li, M. Wang, X. Wu, C. Zhou, and Y. Zhou · 2024
Closest in time.
Glop: Learning global partition and local construction for solving large-scale routing problems in real-time
H. Ye, J. Wang, H. Liang, Z. Cao, Y. Li, and F. Li · 2024
Closest in time.
Understanding the importance of evolutionary search in automated heuristic design with large language models
R. Zhang, F. Liu, X. Lin, Z. Wang, Z. Lu, and Q. Zhang · 2024
Closest in time.
Evaluation of openai o1: Opportunities and challenges of agi
Original
T. Zhong, Z. Liu, Y. Pan, Y. Zhang, Y. Zhou, S. Liang, Z. Wu, Y. Lyu, P. Shu, X. Yu, et al · 2024
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…