Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
Qiang Ma, Suwen Ge, Danyang He et al. · arXiv (Cornell University) · 2019
In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding layer on the input, which captures relationships between nodes. Furthermore, to approximate solutions to constrained combinatorial optimization problems such as the TSP with time windows, we train hierarchical GPNs (HGPNs) using RL, which learns a hierarchical policy to find an optimal city permutation under constraints. Each layer of the hierarchy is designed with a separate reward function, resulting in stable training. Our results demonstrate that GPNs trained on small-scale TSP50/100 problems generalize well to larger-scale TSP500/1000 problems, with shorter tour lengths and faster computational times. We verify that for constrained TSP problems such as the TSP with time windows, the feasible solutions found via hierarchical RL training outperform previous baselines. In the spirit of reproducible research we make our data, models, and code publicly available.
Cited by 134 works. doi:10.48550/arxiv.1911.04936 Open-access PDF
Authors
References
- Reinforcement Learning: An Introduction
- Attention Is All You Need
- Simple statistical gradient-following algorithms for connectionist reinforcement learning
- Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories
- The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization
- The Euclidean travelling salesman problem is NP-complete
- Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem
- Pointer networks
- Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
- Formal Semantics for Kolmogorov-Arnold Network Representations of Operational Games