|Neural Networks Take On Traveling Salesman|
|Written by Mike James|
|Wednesday, 04 May 2022|
The Traveling Saleman problem can be solved better by a neural network approach than by traditional methods - is this important?
The Traveling Salesman Problem (TSP) is NP Hard and so there is no point even trying to find an efficient algorithm for it. Wrong. Just because a problem is difficult to solve exactly it doesn't mean that we can't find a good solution very quickly. As long as you don't demand an exact solution, there are heuristics that provide solutions that are good enough for most purposes. However "good enough" doesn't mean that we don't want, or even need, a better solution. The main problem with creating heuristic algorithms is spotting what features might be related to the outcome. For example, I could propose an algorithm where we should visit towns according to the first letter of their names - clearly not a good heuristic because town names have nothing to do with the order that you should visit them to minimize the distance traveled. But what should you use - what features are related to the quantity you are trying to optimize?
Finding good features is something that neural networks do well and a research team from the University of Cambridge has just announced that using a neural network to help a guided local search. The idea is that if you knew the optimal solution you could work out the cost of including a different selection of route to give you a sub-optimal solution - the cost is generally called the global regret. If you knew the regret of each part of the route you could solve the problem completely by greedily selecting each part of the route to minimize the regret. Of course, you can't do this because it is equivalent to trying every possible route and this is what makes the problem NP hard.
The solution adopted is to use a neural network to estimate the regret of each part of the path to perform a local search by varying the current solution by accepting modifications that have a lower cost.
The results are that the method outperforms other methods based on machine learning, but hand-crafted methods are still better by a large margin. It is argued that the neural network approach is more flexible in that it can take additional constraints into account, which makes it more suitable for real world real time route planning.
This research is really just another step towards an improved TSP algorithm using machine learning. We know that better algorithms exist - surely a neural network can find them? The problem is probably one of finding a good representation that the network can digest.
Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
Benjamin Hudson, Qingbiao Li, Matthew Malencia, Amanda Prorok
Amoeba Solves Traveling Salesman Problem
The Physical Travelling Salesman Challenge
Programmer's Guide To Theory - NP & Co-NP
To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
or email your comment to: email@example.com
|Last Updated ( Wednesday, 04 May 2022 )|