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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What research have you done? Have you searched on Google Scholar? $\endgroup$– D.W. ♦Commented Mar 9, 2016 at 16:42
-
$\begingroup$ 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. $\endgroup$– RobCommented Mar 9, 2016 at 20:06
-
$\begingroup$ drop by Computer Science Chat for possibly more discussion/ analysis $\endgroup$– vznCommented Mar 9, 2016 at 23:31
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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). $\endgroup$ Commented Feb 16, 2021 at 11:11
$\begingroup$
$\endgroup$
1
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
Traveling salesman problem using neural network techniques / Abdel-Moetty
Using Hopfield Networks to Solve Traveling Salesman Problems Based on Stable State Analysis Technique / Feng, Douligeris
Comparison of Neural Networks for Solving the Travelling Salesman Problem / La Maire, Mladenov
A Recurrent Neural Network to Traveling Salesman Problem / Siqueira, Scheer, Steiner
-
3$\begingroup$ 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. $\endgroup$– RobCommented Mar 10, 2016 at 0:41
$\begingroup$
$\endgroup$
3
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).
-
2$\begingroup$ 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. $\endgroup$– D.W. ♦Commented Oct 10, 2018 at 7:00
-
$\begingroup$ Thanks for responding, I'm happy to revisit this curiosity again! $\endgroup$– RobCommented Oct 10, 2018 at 16:15
-
$\begingroup$ 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... $\endgroup$– Sam H.Commented Oct 10, 2018 at 19:31
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ 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. $\endgroup$– RobCommented Mar 9, 2016 at 21:00
-
$\begingroup$ 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 ;-) $\endgroup$– RobCommented Mar 9, 2016 at 21:02
-
$\begingroup$ @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. $\endgroup$– vonbrandCommented Mar 10, 2016 at 12:09
-
1$\begingroup$ Some PHd's from UC Berkeley working for google sounds like a reputable enough team to me..... $\endgroup$– RobCommented Mar 10, 2016 at 18:57
-
$\begingroup$ 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." $\endgroup$– Sam H.Commented Oct 10, 2018 at 4:09