Ant colony optimization in Scala
blog.haberkucharsky.com
blog.haberkucharsky.com
1) Ant colony is one of many nature-inspired heuristics. They are not guaranteed to find an optimal solution. There are very advanced algorithms and implementations that can solve hard problem like the TSP to proven optimality. The state of the art is Concorde, which has even an iPhone app:
http://www.math.uwaterloo.ca/tsp/concorde.html
2) There are many alternative approaches to solving problems like this. A common theme to these approaches is to be smarter about where in the solution space (the set of possible solutions) they search based on heuristics (past information).
"Heuristic" comes from the Greek word that means "to find", so a heuristic doesn't necessarily rely on past information.
3) In general, if there are n locations, then the number of possible solutions is n!
Let's say O(n!). Assuming the distance A-->B is the same as B-->A (as in the symmetric traveling salesman problem), for n=3 there is only one loop, and hence only one solution instead of 3! = 6.
4) Ant colony optimization 1 is a novel optimization approach that was invented by Marco Dorigo in 1992.
Well, a method invented 24 years ago is not exactly novel.
Given most things in computer science are older than 1970, I think 1992 counts as being quite new :-)
Anyone whose remotely interested in heuristics will tell you that heuristics like ant colony optimization are a dime a dozen, and dozens of new heuristics are being published in top scientific journals every single year.
Dozens and dozens.
Some journal editions even include multiple articles from the same author presenting new heuristics.
Things are so out of control in the field of stochastic search methods that this sad state of affairs even originated a theorem that is used to try to justify this loss of focus: the no free lunch theorem.
This field is plagued by people who succeed at marketing their own pet heuristic method instead of favouring actual results.
does this algorithm lead to the same conclusion?
When it comes to static problems like TSP, the translation of the problem has a lot of influence on how likely the heuristic is to fall into local optima. For instance in the case of ACO you have pheromone trails that are intended to dissipate faster as the distance between food increases. When translating something like TSP you have a decision to make: you can go literal and use the physical distance between edges on a graph (causing closer nodes to be more heavily weighted). Or you could use the total distance of the circuit (causing edges that occur in better solutions to be more heavily weighted). Or you can blend them both -- which is what it looks like the author did.
These algorithms are heuristics and are not intended to necessarily give you the "best" answer, but to get you a "pretty good" answer on messy problems that don't neatly fit into a problem that has been heavily researched like TSP.
ACO for dynamic environments generally require much more attention to how the problem is applied to the environment or the generation of a more hybrid approach.