Traveling Salesman Problem with Neural Network

I was curious if there were any new developments in solving the traveling salesman problem using something like a Hopfield recurrent neural network. I feel like I saw something about recent research getting a breakthrough in this, but I can't find the academic papers anywhere. Is anyone aware of any new, novel developments in this area?

• What research have you done? Have you searched on Google Scholar?
– D.W.
Mar 9 '16 at 16:42
• I read the paper on Stack LSTM's, which I was told might help: arxiv.org/pdf/1506.02516.pdf, but I'm not seeing the connection.
– Rob
Mar 9 '16 at 20:06
• drop by Computer Science Chat for possibly more discussion/ analysis
– vzn
Mar 9 '16 at 23:31

This Medium post lists the latest (not a full list of course) studies in the combinatorial optimization domain. All three papers use Deep Reinforcement Learning, which does not need any training set but learns completely from its own experience.

I have been working on the first paper for some time and inference time is on milliseconds level. According to their experiments, the approximation ratio (a metric they use to benchmark their own method) on 1000-1200 test cases reaches to 1.11.

• It would be interesting to know the best approx ratio of the best algorithm not using any neural network with comparable execution time. So that we can have an idea of the gain brought by neural network compared to the best classic combinatorial algorithm (at similar exec time). Feb 16 at 11:11

there are many papers on using artificial neural networks to solve TSP including recurrent and Hopfield networks, and they "succeed" in a rough sense, but so far there does not seem to be any evidence that the techniques are in any way (strongly?) superior to other algorithmic approaches, so its something more like a research curiosity at the moment. the use of ANNs for this problem is indeed counterintuitive from the pov of combinatorial algorithmics and the mechanisms by which the problem inputs/ outputs are encoded are novel and tend to vary, and maybe are not yet so standardized. the authors seem maybe more interested in demonstrating "proof of concept" and a comparison with other algorithm types seems more rare (there is some in the last paper). see eg

• I believe that it will be possible for neural networks to solve within a confidence interval with some consistency. As in a top 5% solution 85% of the time, I was just curious to learn how this sort of problem was solved with a neural network, because I just read the deepmind paper on Neural Stacks. It seems like Neural Networks, especially Deep Reinforcement learning networks, can handle any problem a genetic algorithm would have in the past. So that was the progression in my mind.
– Rob
Mar 10 '16 at 0:41

I commented this on another answer, but I think it deserves its own answer. Some Google Brain fellows presented a method for solving TSP using an architecture reminiscent of seq2seq in the 2017 paper NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING. In the introduction, they call out a (1985) paper that uses Hopfield networks to solve TSP. So that idea has been around for a while.

Another answer mentioned the 2015 "Pointer Networks" paper. It did something similar to this paper, but it was a supervised algorithm - it needed labeled data. The 2017 paper doesn't require this (by using negative tour length as a reward signal in a reinforcement learning algorithm).

The heuristic "always bet on neural nets" hasn't let me down (but then again, I've never been through an AI winter).

• Beware, though: the paper makes clear that their results are "far from state-of-the-art" in solving TSP. It's kinda like marvelling at a dancing dog. The point is not that it dances particularly well; the amazing part is that it can do anything approaching dancing at all.
– D.W.
Oct 10 '18 at 7:00
• Thanks for responding, I'm happy to revisit this curiosity again!
– Rob
Oct 10 '18 at 16:15
• I don't know D.W., I remember when deep learning was the dancing dog of image recognition... and language modeling... and chess... and Go... Oct 10 '18 at 19:31

I don't see any reason to expect Hopfield recurrent neural networks to help with the traveling salesman problem.

Neural networks are a form of machine learning, and they are effective when we have a labelled training set: a bunch of instances, where for each we know the input (the feature vector) and the correct label/classification/output. Machine learning is often useful for finding patterns when we're not sure exactly how to define what the right output is; "we know it when we see it".

In contrast, the traveling salesman problem is a combinatorial problem: we want to know the shortest route through a graph. There's no issue in defining or specifying what the right output is: it's a well-defined mathematical problem. There's no obvious reason to think machine learning would be useful for the traveling salesman problem.

• This paper makes reference to attempting to apply a neural network to the traveling salesman problem: arxiv.org/pdf/1506.03134.pdf . So I'm not completely crazy. My curiosity about the issue was how it could be utilized because I couldn't imagine a way. I appreciate you taking the time though and if you look through the article I'd love to hear what you think.
– Rob
Mar 9 '16 at 21:00
• Also, this paper makes reference to using a hopfield network to solve the traveling salesman problem cdn.intechopen.com/pdfs-wm/4612.pdf , so not total buzzword bingo ;-)
– Rob
Mar 9 '16 at 21:02
• @Rob, that somebody wrote up something and posted it on arXiv doesn't mean it isn't way off. Unless this got serious review, I'd be very wary. Mar 10 '16 at 12:09
• Some PHd's from UC Berkeley working for google sounds like a reputable enough team to me.....
– Rob
Mar 10 '16 at 18:57
• Here is the Google Brain team showing TSP optimization using a seq2seq model openreview.net/pdf?id=rJY3vK9eg "We focus on the traveling salesman problem (TSP) and train a recurrent neural 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 neural network using a policy gradient method." Oct 10 '18 at 4:09