Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Reijnen, Robbert, Zhang, Yingqian, Lau, Hoong Chuin, Bukhsh, Zaharah
Format:	Preprint
Published:	2022
Subjects:	Machine Learning Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

_version_	1866916435605848064
author	Reijnen, Robbert Zhang, Yingqian Lau, Hoong Chuin Bukhsh, Zaharah
author_facet	Reijnen, Robbert Zhang, Yingqian Lau, Hoong Chuin Bukhsh, Zaharah
contents	The Adaptive Large Neighborhood Search (ALNS) algorithm has shown considerable success in solving combinatorial optimization problems (COPs). Nonetheless, the performance of ALNS relies on the proper configuration of its selection and acceptance parameters, which is known to be a complex and resource-intensive task. To address this, we introduce a Deep Reinforcement Learning (DRL) based approach called DR-ALNS that selects operators, adjusts parameters, and controls the acceptance criterion throughout the search. The proposed method aims to learn, based on the state of the search, to configure ALNS for the next iteration to yield more effective solutions for the given optimization problem. We evaluate the proposed method on an orienteering problem with stochastic weights and time windows, as presented in an IJCAI competition. The results show that our approach outperforms vanilla ALNS, ALNS tuned with Bayesian optimization, and two state-of-the-art DRL approaches that were the winning methods of the competition, achieving this with significantly fewer training observations. Furthermore, we demonstrate several good properties of the proposed DR-ALNS method: it is easily adapted to solve different routing problems, its learned policies perform consistently well across various instance sizes, and these policies can be directly applied to different problem variants.
format	Preprint
id	arxiv_https___arxiv_org_abs_2211_00759
institution	arXiv
publishDate	2022
record_format	arxiv
spellingShingle	Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning Reijnen, Robbert Zhang, Yingqian Lau, Hoong Chuin Bukhsh, Zaharah Machine Learning Artificial Intelligence The Adaptive Large Neighborhood Search (ALNS) algorithm has shown considerable success in solving combinatorial optimization problems (COPs). Nonetheless, the performance of ALNS relies on the proper configuration of its selection and acceptance parameters, which is known to be a complex and resource-intensive task. To address this, we introduce a Deep Reinforcement Learning (DRL) based approach called DR-ALNS that selects operators, adjusts parameters, and controls the acceptance criterion throughout the search. The proposed method aims to learn, based on the state of the search, to configure ALNS for the next iteration to yield more effective solutions for the given optimization problem. We evaluate the proposed method on an orienteering problem with stochastic weights and time windows, as presented in an IJCAI competition. The results show that our approach outperforms vanilla ALNS, ALNS tuned with Bayesian optimization, and two state-of-the-art DRL approaches that were the winning methods of the competition, achieving this with significantly fewer training observations. Furthermore, we demonstrate several good properties of the proposed DR-ALNS method: it is easily adapted to solve different routing problems, its learned policies perform consistently well across various instance sizes, and these policies can be directly applied to different problem variants.
title	Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning
topic	Machine Learning Artificial Intelligence
url	https://arxiv.org/abs/2211.00759