Using Self-Organizing Maps to Solve the Traveling Salesman Problem(diego.codes)
diego.codes
Using Self-Organizing Maps to Solve the Traveling Salesman Problem
https://diego.codes/post/som-tsp/
35 comments
It does not “solve” it though. It’s not even an approximation (which is also NP-hard in the general case, not sure about the Euclidean case).
It doesn't solve it, because it doesn't handle roads
Can you explain your comment a bit better?
I believe that the Travelling Salesman problem abstracts the roads anyway. I.e. two points are at distance x if you can travel from one to the other in x time. This could mean that there is a fast but physically far connection like a Highway, or a very short distance over a dirt road which forces you to drive at a lower speed.
So if two points that are close (in reality) but have no direct connection should have a very high distance in the model.
This has to be taken in account when you provide the dataset, but does not make the system unfeasible.
EDIT:typos
I believe that the Travelling Salesman problem abstracts the roads anyway. I.e. two points are at distance x if you can travel from one to the other in x time. This could mean that there is a fast but physically far connection like a Highway, or a very short distance over a dirt road which forces you to drive at a lower speed.
So if two points that are close (in reality) but have no direct connection should have a very high distance in the model.
This has to be taken in account when you provide the dataset, but does not make the system unfeasible.
EDIT:typos
I presume to handle the roads you just have to change the distance function to use an API like Google Maps, TomTom, GraphHopper.
This would significantly impact performance though.
This would significantly impact performance though.
Yes, and additionally the problem is then not Euclidian anymore. For example the triangular inequality (distance from A to B directly is always shorter than or equal to distance from A to B via C) does not hold. I'd guess that that will deteriorate results from this method since it relies on the Euclidian distance from the current circle to the points to be visited.
I don't understand why you think traveling by road breaks the triangle inequality. If the time/distance along roads from A to B is fastest via C, then just go via C...
The triangle inequality is precisely the statement that this never happens.
You misunderstand. I'm saying that a situation such as:
dist(AB): 3km
dist(AC): 1km
dist(CB): 1km
is impossible even if those are road distances rather than Euclidean distances. If the road distance of traveling A->C->B is 2km then dist(AB) should not be greater than 2km.
dist(AB): 3km
dist(AC): 1km
dist(CB): 1km
is impossible even if those are road distances rather than Euclidean distances. If the road distance of traveling A->C->B is 2km then dist(AB) should not be greater than 2km.
So long as you're measuring in kilometers, as the bird flies. If you're talking about the distance a car would have to drive... okay, you're correct that it'd be possible to drive through C and thereby cut down on cost, but that's somewhat besides the point.
The algorithm this article is talking about assumes that all points are on an Euclidean map, and the distance between them is simply the Euclidean distance. This requires the triangle inequality to hold for straight lines, and allows optimizations based on that assumption.
The inequality in itself is a weaker statement than saying the whole thing is euclidean, and I haven't read it carefully enough to be sure which is required, but any violation of it is necessarily a violation of the assumptions that make this heuristic work.
The algorithm this article is talking about assumes that all points are on an Euclidean map, and the distance between them is simply the Euclidean distance. This requires the triangle inequality to hold for straight lines, and allows optimizations based on that assumption.
The inequality in itself is a weaker statement than saying the whole thing is euclidean, and I haven't read it carefully enough to be sure which is required, but any violation of it is necessarily a violation of the assumptions that make this heuristic work.
Agreed. I was just responding to Zeebrommer's claim that the triangle inequality fails with road distances.
Your best bet is to calculate a full cost (time/distance) matrix upfront before running the optimisation.
Both Google and GraphHopper offer cost matrix calculations as part of their web API. I imagine in both cases you need an expensive API key though.
If you're going to use GraphHopper, you might as well install it yourself, import the OpenStreetMap file for the region you want, and use it to calculate the cost matrix on your own computer for free!
Both Google and GraphHopper offer cost matrix calculations as part of their web API. I imagine in both cases you need an expensive API key though.
If you're going to use GraphHopper, you might as well install it yourself, import the OpenStreetMap file for the region you want, and use it to calculate the cost matrix on your own computer for free!
Yes good point. Pre-loading the full distance matrix is the right thing to do here. That's what we were doing at a startup as I was at a few years ago. GraphHopper is quite expandable so it is nice to work with once you understand how it functions.
But you definitely need to put your Java hat on :).
But you definitely need to put your Java hat on :).
I've not read the article in detail, but it looks to me like they have produced a more efficient brute force method, which might be impressive but isn't nearly the same as solving it in any mathematical sense.
Neural networks, self-organizing maps, genetic programming. It feels like we're back in the 80s.
I recently read a math paper: abelian groups, hilbert spaces, lebesgue measures. It felt like we're back in the 1900s.
don't forget VR
One of the professors in my PhD programme made his name by showing that anything you can do with a self-organising map, you can do with a Gaussian process. The work essentially killed off self-organising maps as a field of study.
One time we had seminar where a guest speaker had used self-organising maps, and the professor literally fell off his chair.
One time we had seminar where a guest speaker had used self-organising maps, and the professor literally fell off his chair.
How exactly did theoretical equivalence result kill SOM's as field of study?
There is similar connection between deep fully connected neural networks and Gaussian process.
Deep Neural Networks as Gaussian Processes https://arxiv.org/abs/1711.00165
There is similar connection between deep fully connected neural networks and Gaussian process.
Deep Neural Networks as Gaussian Processes https://arxiv.org/abs/1711.00165
In much the same way the result you linked to slowed research into single-hidden-layer NNs. Another example is when the failure to learn XOR killed off the preceptron and nearly killed neural networks as a whole.
Researchers like low-hanging fruit, and some results just make a topic look barren.
Researchers like low-hanging fruit, and some results just make a topic look barren.
> result you linked to slowed research into single-layer NNs.
You are thinking different link.
You are thinking different link.
Yep, sorry. I'm thinking of the (much older) results referred to in the abstract of the linked article.
Proving two things equivalent does not invalidate the use of one or the other.
Interesting, can you link the paper please? I'd love to read it
They probably referred to this:
https://en.wikipedia.org/wiki/Generative_topographic_map
https://en.wikipedia.org/wiki/Generative_topographic_map
7.5% longer than is optimal is way too much.
Doing simple 2-opt/3-opt heuristic (10-100ms CPU time of optimization, 200 lines of code) gets you to 1-3% of the optimum.
Doing simple 2-opt/3-opt heuristic (10-100ms CPU time of optimization, 200 lines of code) gets you to 1-3% of the optimum.
That CPU time sounds reasonable for just 2-opt but I've found that 3-opt takes longer for tours with that many stops. The quickest strategy that involves 3-opt is to do a run of 2-opt followed by 3-opt, but for instances with 500 stops this can take nearly a second to run, even after parallelizing and optimising the code.
The tools you use will also make a difference. Python is difficult to make as performant as C.
The tools you use will also make a difference. Python is difficult to make as performant as C.
Yeah, I was thinking of a C++ implementation. The nested for loops get optimized very well for the 3-opt case. There's also a couple of tricks one can do with preloading (simd) of distances for evaluating 2,3-opt simultaneously. That all fits into 200 lines of code. There's also the fact that after executing the best moves there's a lot of previously evaluated moves that are still valid. This also fits into those 200 lines.
Not trivial, but IMO less trivial than self-organizing maps.
Not trivial, but IMO less trivial than self-organizing maps.
> after executing the best moves there's a lot of previously evaluated moves that are still valid
Ah, this has crossed my mind as well, but I hadn't got round to implementing it yet. You could even determine a set of independent swaps per iteration and perform them all in parallel.
Ah, this has crossed my mind as well, but I hadn't got round to implementing it yet. You could even determine a set of independent swaps per iteration and perform them all in parallel.
> where we are able to find a route traversing 734 cities only 7.5% longer than the optimal in less than 25 seconds
I could be wrong, but that does not sound like a very good method.
But I am all for people writing blog posts and exploring methods in order to learn, of course.
I could be wrong, but that does not sound like a very good method.
But I am all for people writing blog posts and exploring methods in order to learn, of course.
It doesn't "solve" anything, it just gives an admissible solution.
or at least _a_ solution
Nice writeup Diego ;)
I worked with Diego (the author) on a first version of this, since it was a project in the course "Artificial Intelligence Programming" IT3105 at NTNU in Trondheim, Norway where we both stayed in our Erasmus a year ago.
While it is not very sophisticated to use SOMs for this problem, it was rather meant as an implementation exercise. And TSP allows a graphical representation of the process, which is nice too. That said, we spent way too much time in the course implementing and fine tuning Genetic algorithms...
I worked with Diego (the author) on a first version of this, since it was a project in the course "Artificial Intelligence Programming" IT3105 at NTNU in Trondheim, Norway where we both stayed in our Erasmus a year ago.
While it is not very sophisticated to use SOMs for this problem, it was rather meant as an implementation exercise. And TSP allows a graphical representation of the process, which is nice too. That said, we spent way too much time in the course implementing and fine tuning Genetic algorithms...
If you can excuse the embarassing mess of file structure, the core lib is here, buried among a dozen other pet projects from my student days: https://github.com/KyleGalvin/Typhoon/blob/master/Cpp/SOM.cp...
Edit: it seems (on second glance) the above link is exactly the TSP problem, wired up with SDL. The core library is here: https://github.com/KyleGalvin/Typhoon/blob/master/Cpp/src/so...