Johnn, SN;
Darvariu, VA;
Handl, J;
Kalcsics, J;
(2023)
GRAPH Reinforcement Learning for Operator Selection in the ALNS Metaheuristic.
In:
International Conference on Optimization and Learning OLA 2023: Optimization and Learning.
(pp. pp. 200-212).
Springer, Cham
Preview |
Text
main.pdf - Accepted Version Download (595kB) | Preview |
Abstract
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.
| Type: | Proceedings paper |
|---|---|
| Title: | GRAPH Reinforcement Learning for Operator Selection in the ALNS Metaheuristic |
| Event: | International Conference on Optimization and Learning: OLA 2023 |
| ISBN-13: | 9783031340192 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-031-34020-8_15 |
| Publisher version: | https://doi.org/10.1007/978-3-031-34020-8_15 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Adaptive Large Neighbourhood Search, Markov Decision Process, Deep Reinforcement Learning, Graph Neural Networks |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10173646 |
Archive Staff Only
 |
View Item |
