Generalization in Deep RL for TSP Problems via Equivariance and Local Search

Autor:	Ouyang, Wenbin, Wang, Yisen, Weng, Paul, Han, Shaochen
Rok vydání:	2021
Předmět:	Computer Science - Machine Learning Computer Science - Artificial Intelligence
Druh dokumentu:	Working Paper
Popis:	Deep reinforcement learning (RL) has proved to be a competitive heuristic for solving small-sized instances of traveling salesman problems (TSP), but its performance on larger-sized instances is insufficient. Since training on large instances is impractical, we design a novel deep RL approach with a focus on generalizability. Our proposition consisting of a simple deep learning architecture that learns with novel RL training techniques, exploits two main ideas. First, we exploit equivariance to facilitate training. Second, we interleave efficient local search heuristics with the usual RL training to smooth the value landscape. In order to validate the whole approach, we empirically evaluate our proposition on random and realistic TSP problems against relevant state-of-the-art deep RL methods. Moreover, we present an ablation study to understand the contribution of each of its component Comment: 18 pages, 2 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2110.03595 Zobrazit plný text záznamu View this record from Arxiv