Name
Abstract | ||
|---|---|---|
Recent work applying deep reinforcement learning (DRL) to solve traveling salesman problems (TSP) has shown that DRL-based solvers can be fast and competitive with TSP heuristics for small instances, but do not generalize well to larger instances. In this work, we propose a novel approach named MAGIC that includes a deep learning architecture and a DRL training method. Our architecture, which integrates a multilayer perceptron, a graph neural network, and an attention model, defines a stochastic policy that sequentially generates a TSP solution. Our training method includes several innovations: (1) we interleave DRL policy gradient updates with local search (using a new local search technique), (2) we use a novel simple baseline, and (3) we apply curriculum learning. Finally, we empirically demonstrate that MAGIC is superior to other DRL-based methods on random TSP instances, both in terms of performance and generalizability. Moreover, our method compares favorably against TSP heuristics and other state-of-the-art approach in terms of performance and computational time. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1109/SSCI50451.2021.9659970 | SSCI |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenbin Ouyang | 1 | 0 | 0.34 |
| Yisen Wang | 2 | 0 | 2.37 |
| Shaochen Han | 3 | 0 | 0.34 |
| Zhejian Jin | 4 | 0 | 0.34 |
| Paul Weng | 5 | 157 | 16.39 |