Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristic

• URL: http://arxiv.org/abs/2302.14678v1
• Date: Tue, 28 Feb 2023 15:39:42 GMT
• Title: Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristic
• Authors: Syu-Ning Johnn, Victor-Alexandru Darvariu, Julia Handl, Joerg Kalcsics
• Abstract summary: We formulate the choice of operators as a Markov Decision Process. We propose a practical approach based on Deep Reinforcement Learning and Graph Neural Networks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Dynamic operator management in meta-heuristics using reinforcement learning: an application to permutation flowshop scheduling problems [0.3495246564946556]
  This study develops a framework based on reinforcement learning to dynamically manage a large portfolio of search operators within meta-heuristics. A Q-learning-based adaptive operator selection mechanism is used to select the most suitable operator from the dynamically updated portfolio. The performance of the proposed framework is analyzed through an application to the permutation flowshop scheduling problem.
  arXiv  Detail & Related papers  (2024-08-27T08:38:17Z)
• Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization [6.713974813995327]
  We present MEMENTO, an approach that leverages memory to improve the adaptation of neural solvers at time. We successfully train all RL auto-regressive solvers on large instances, and show that MEMENTO can scale and is data-efficient. Overall, MEMENTO enables to push the state-of-the-art on 11 out of 12 evaluated tasks.
  arXiv  Detail & Related papers  (2024-06-24T08:18:19Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• Switchable Decision: Dynamic Neural Generation Networks [98.61113699324429]
  We propose a switchable decision to accelerate inference by dynamically assigning resources for each data instance. Our method benefits from less cost during inference while keeping the same accuracy.
  arXiv  Detail & Related papers  (2024-05-07T17:44:54Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Constrained Multi-objective Optimization with Deep Reinforcement Learning Assisted Operator Selection [28.088046969822543]
  This work proposes an online operator selection framework assisted by Deep Reinforcement Learning. The proposed approach can adaptively select an operator that maximizes the improvement of the population according to the current state. The framework is embedded into four popular CMOEAs and assessed on 42 benchmark problems.
  arXiv  Detail & Related papers  (2024-01-15T09:51:19Z)
• Adaptive operator selection utilising generalised experience [0.8287206589886879]
  Reinforcement Learning (RL) has recently been proposed as a way to customise and shape up a highly effective adaptive selection system. This paper proposes and assesses a RL-based novel approach to help develop a generalised framework for gaining, processing, and utilising the experiences for both the immediate and future use.
  arXiv  Detail & Related papers  (2023-12-04T00:27:59Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Meta-Wrapper: Differentiable Wrapping Operator for User Interest Selection in CTR Prediction [97.99938802797377]
  Click-through rate (CTR) prediction, whose goal is to predict the probability of the user to click on an item, has become increasingly significant in recommender systems. Recent deep learning models with the ability to automatically extract the user interest from his/her behaviors have achieved great success. We propose a novel approach under the framework of the wrapper method, which is named Meta-Wrapper.
  arXiv  Detail & Related papers  (2022-06-28T03:28:15Z)
• Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning [80.45697245527019]
  We show that a greedy selection rule explicitly looking ahead to select cuts that yield the best bound improvement delivers strong decisions for cut selection. We propose a new neural architecture (NeuralCut) for imitation learning on the lookahead expert.
  arXiv  Detail & Related papers  (2022-06-27T16:07:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.