Ant colony optimization in Scala(blog.haberkucharsky.com)
blog.haberkucharsky.com
Ant colony optimization in Scala
http://blog.haberkucharsky.com/technology/2015/10/12/travelling-ants.html
10 comments
> 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 :-)
> 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.
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).
Thank you kindly! I've made some corrections based on these comments.
the pheromone trails are known to lead to sub-optimal paths
does this algorithm lead to the same conclusion?
does this algorithm lead to the same conclusion?
One of the biggest drawbacks with things like ACO (ant colony optimization) are actually more in dynamic environments rather than static ones like these. Pheromone trails tend to reinforce the information from the old topology rather than the new topology and you need to add more wrinkles to the algorithm to better adapt to a changing environment.
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.
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.
not really, depends on the evaporation rate of the pheromone. If you increase the evaporation co-efficient it's more suited to a dynamic environment
It's much more nuanced than that though. Increasing the evaporation rate also makes exploitation much harder, not to mention that the positive feedback cycle on previously very good edges can take a long time to dissipate.
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.
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.
Can you provide a source for that? Would like to read that paper.
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.