Where can I learn more about “ant colony” optimizations?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

National Geographic wrote an interesting article awhile back talking about some of the theories.

Answer 4

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.

Answer 5

I am surprised nobody has mentioned the bible of ACO:

Marco Dorigo & Thomas Stützle: Ant Colony Optimization

This book is written by the author of ACO and it is highly readable. You can take it to the beach and have fun reading it. But it is also the most complete resource of all, great as a reference when implementing the thing.

You can read some excerpts on Google Books

Another great source of wisdom is the ACO Homepage

Answer 6

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.

Answer 7

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.

Answer 8

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