Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristic

Syu-Ning Johnn, Victor-Alexandru Darvariu, Julia Handl, Jӧrg Kalcsics

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

ALNS is a popular metaheuristic with renowned efficiency in solving combinatorial optimisation problems. However, despite 16 years of intensive research into ALNS, whether the embedded adaptive layer can efficiently select operators to improve the incumbent remains an open question. In this work, we formulate the choice of operators as a Markov Decision Process, and propose a practical approach based on Deep Reinforcement Learning and Graph Neural Networks. The results show that our proposed method achieves better performance than the classic ALNS adaptive layer due to the choice of operator being conditioned on the current solution. We also discuss important considerations such as the size of the operator portfolio and the impact of the choice of operator scales. Notably, our approach can also save significant time and labour costs for handcrafting problem-specific operator portfolios.
Original languageEnglish
Title of host publicationOptimization and Learning
Subtitle of host publicationOLA 2023
EditorsBernabe Dorronsoro, Francisco Chicano, Gregoire Danoy, El-Ghazali Talbi
Publication statusE-pub ahead of print - 31 May 2023
EventOLA'2023 Int. Conf. on Optimization and Learning -
Duration: 3 May 20235 May 2023

Publication series

NameCommunications in Computer and Information Science
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937


ConferenceOLA'2023 Int. Conf. on Optimization and Learning


Dive into the research topics of 'Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristic'. Together they form a unique fingerprint.

Cite this