I've been reading things here and there for a while now about using an "ant colony" model as a heuristic approach to optimizing various types of algorithms. However, I have yet to find an article or book that discusses ant colony optimizations in an introductory manner, or even in a lot of detail. Can anyone point me at some resources where I can learn more about this idea?
+2
A:
On the off chance that you know German (yes, sorry …), a friend and I have written an introduction with code about this subject which I myself find quite passable. The text and code uses the example of TSP to introduce the concept.
Even if you don't know German, take a look at the code and the formulas in the text, this might still serve.
Konrad Rudolph
2009-01-14 21:09:58
Thanks for this link! Unfortunately, my German is limited to what I learned in middle school (want to discuss the weather?) but Google Translate did a great job on the article.
MattK
2009-01-14 21:37:21
I think the translation of the XKCD comic went rather well … the rest … not so much. ;-) Note: This not is how German I speak in normal.
Konrad Rudolph
2009-01-14 21:54:32
+1
A:
See for example this article on scholarpedia.
There is also discussion here in the What is the most efficient way of finding a path through a small world graph? question.
David Schmitt
2009-01-14 21:11:02
+2
A:
National Geographic wrote an interesting article awhile back talking about some of the theories.
DShook
2009-01-14 21:35:12
+1
A:
At first glance this seems to be closely related to (or prehaps a special case of) the Metropolis algorithm. So that's another possible direction for searching.
Addition: This PDF file includes a reference to the original Metropolis paper from 1953.
dmckee
2009-01-14 21:36:25
+2
A:
The best resource for these topics is Google scholar. Ive been working on Ant Colony Optimization algorithms for a while, here are some good papers:
- Ant Colony Optimization - A New Metaheuristic
- Ant Colony Optimization - Artificial Ants as a Computational Intelligence Technique
Just search for "Ant Colony" on google scholar.
Also, search for papers published by Marco Dorigo.
martinus
2009-01-18 19:25:28
+1
A:
Well, i found the Homepage of Eric Rollins and his different Implementations (Haskell, Scala, Erlang,...) of a ACO Algorithm helpfull. And also the Book from Enrique Alba, titled "Parallel Metaheuristics: A New Class of Algorithms" where you can find a whole chapter of explanation about ACO Algorithms and their different usages.
Hth
+3
A:
link Wikipedia actually got me started. I read the article and got to coding. I was solving a wicked variation of the traveling salesman problem. It's an amazing meta-heuristic. Basically, any type of search problem that can be put into a graph (nodes & edges, symmetric or not) can be solved with an ACO.
Look out for the difference between global and local pheromone trails. Local pheromones discourage one generation of ants from traversing the same path. They keep the model from converging. Global pheromones are attractors and should snag at least one ant per generation. They encourage optimum paths over several generations.
The best suggestion I have, is simply to play with the algorithm. Setup a basic TSP solver and some basic colony visualization. Then have some fun. Working with ants, conceptually, is way cool. You program their basic behaviors and then set them loose. I even grow fond of them. :)
ACOs are a greedier form of genetic algorithms. Play with them. Alter their communicative behaviors and pack behavior. You'll rapidly begin to see network / graph programming in an entirely different way. That's their biggest benefit, not the recipe that most people see it as.
You just gotta play with it to really understand it. Books & research papers only give a general sky-high understanding. Like a bike, you just gotta start riding. :)
ACOs, by far, are my favorite abstraction for graph problems.
Pestilence
2009-12-10 01:46:26