Ant colony optimization in Scala 111 points by stuxnet79 on Oct 4, 2016 | hide | past | favorite | 10 comments

 A few remarks.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.html2) 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.
 > 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 :-)
 > 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.
 Sure, but in combinatorial optimization many heuristics appeared after 1992 (variable neighborhood search, feasibility pump, RINS to name just a few).