Neural Combinatorial Optimization with Reinforcement Learning
  This paper presents a framework to tackle combinatorial optimization problems
using neural networks and reinforcement learning. We focus on the traveling
salesman problem (TSP) and train a recurrent network that, given a set of city
coordinates, predicts a distribution over different city permutations. Using
negative tour length as the reward signal, we optimize the parameters of the
recurrent network using a policy gradient method. We compare learning the
network parameters on a set of training graphs against learning them on
individual test graphs. Despite the computational expense, without much
engineering and heuristic designing, Neural Combinatorial Optimization achieves
close to optimal results on 2D Euclidean graphs with up to 100 nodes. Applied
to the KnapSack, another NP-hard problem, the same method obtains optimal
solutions for instances with up to 200 items.
