The Library
Learning heuristics for weighted CSPs through deep reinforcement learning
Tools
Chen, Dingding, Chen, Ziyu, He, Zhongshi, Gao, Junsong and Su, Zhizhuo (2023) Learning heuristics for weighted CSPs through deep reinforcement learning. Applied Intelligence, 53 . 8844-8863 . doi:10.1007/s10489-022-03992-5 ISSN 0924-669X.
|
PDF
WRAP-Learning-heuristics-weighted-CSPs-deep-reinforcement-22.pdf - Accepted Version - Requires a PDF viewer. Download (842Kb) | Preview |
Official URL: http://doi.org/10.1007/s10489-022-03992-5
Abstract
Weighted constraint satisfaction problems (WCSPs) are one of the most important constraint programming models aiming to find a cost-minimal solution. Due to its NP-hardness, solving a WCSP usually requires efficient heuristics to explore high-quality solutions. Unfortunately, such heuristics are hand-crafted and may not be generalizable across different cases. On the other hand, although Deep Learning (DL) has been proven to be a promising way to learn heuristics for combinatorial optimization problems, the existing DL-based methods are unsuitable for WCSPs since they fail to exploit the problem structure of WCSPs. Besides, such methods are often based on Supervised Learning (SL), making the learned heuristics less efficient since it is challenging to generate a sufficiently large training corpus. Therefore, we propose a novel Deep Reinforcement Learning (DRL) framework to train the model on large-scale problems, so that the model could mine more sophisticated patterns and provide high-quality heuristics. By exploiting the problem structure, we effectively decompose the problem by using a pseudo tree, and formulate the solution construction process as a Markov decision process with multiple independent transition states. With Graph Attention Networks (GATs) parameterized deep Q-value network, we learn the optimal Q-values through a modified Bellman equation that considers the multiple transition states, and extract the solution construction heuristics from the trained network. Besides constructing solutions greedily, our heuristics can also be applied to many meta-heuristics such as beam search and large neighborhood search. The experiments show that our DRL-boosted algorithms significantly outperform the counterparts with their heuristics derived from the SL model, their counterparts with traditional tabular-based heuristics and state-of-the-art methods on benchmark problems.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Engineering > WMG (Formerly the Warwick Manufacturing Group) | ||||||||
Journal or Publication Title: | Applied Intelligence | ||||||||
Publisher: | Springer New York LLC | ||||||||
ISSN: | 0924-669X | ||||||||
Official Date: | April 2023 | ||||||||
Dates: |
|
||||||||
Volume: | 53 | ||||||||
Page Range: | 8844-8863 | ||||||||
DOI: | 10.1007/s10489-022-03992-5 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 1 September 2022 | ||||||||
Date of first compliant Open Access: | 3 August 2023 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year