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.
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.
This is awesome. I did exactly this for a course project in 2012. While the travelling salesman problem code seems to have been refactored out, I have a C++ library for SOMs and hierarchical SOMs that are attatched to some openGL code that demonstrates the categorization of RGB colors by label.
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.
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.
> 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.
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 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.
It abstracts away roads by using a graph as input (in the general case). In the post the author tackles the Euclidean TSP, where points are given by coordinates and you can freely travel.
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...
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.
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.
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!
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 :).
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.
One time we had seminar where a guest speaker had used self-organising maps, and the professor literally fell off his chair.