TY - GEN
T1 - Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristic
AU - Johnn, Shunee
AU - Darvariu, Victor-Alexandru
AU - Handl, Julia
AU - Kalcsics, Jӧrg
N1 - Funding Information:
This work was partially supported by The Alan Turing Institute under the Enrichment Scheme and the UK EPSRC grant EP/N510129/1.
Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023/5/31
Y1 - 2023/5/31
N2 - 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.
AB - 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.
U2 - 10.1007/978-3-031-34020-8_15
DO - 10.1007/978-3-031-34020-8_15
M3 - Conference contribution
T3 - Communications in Computer and Information Science
BT - Optimization and Learning
A2 - Dorronsoro, Bernabe
A2 - Chicano, Francisco
A2 - Danoy, Gregoire
A2 - Talbi, El-Ghazali
PB - Springer
T2 - OLA'2023 Int. Conf. on Optimization and Learning
Y2 - 3 May 2023 through 5 May 2023
ER -