The ant colony algorithm is a clever way of finding a "best path" over a complex graph. It models the living style of ants, mimicking how ants find their way to a food source from their colony and back again.
Ants are a classic example of social insects, meaning that they work together for the good of the colony. An ant colony finds new food sources by sending out foragers who explore the surroundings more or less at random, traveling randomly among the passable paths available to it. If it finds food, a forager will return to the colony, laying a pheromone trail as it goes. Other ants can later follow this pheromone trail back to the food.
This idea is applicable to the study of finding the shortest path in a given graph, one of the fundamental problems of graph theory. Graphs, in this context, are simple models of how things relate to each other, much like a road map. Here's an example of a simple graph, which I'll use in describing the ant colony algorithm.
(safe spot)------(safe spot)
/ | \ 7 \
6 / | \ \ 8
/ | \ \
(colony) | 1 \ 4 (food source)
\ | \ /
8 \ | \ / 9
\ | 2 \ /
(safe spot)------(safe spot)
Ants travel from safe spot to safe spot to reach the food source. They stumble about blindly, randomly choosing paths that they haven't been down before. When an ant reaches a food source, it turns around and follows its own path backwards to the colony, laying a pheromone trail. The ant then goes back to the food colony again and again and again, back and forth, following the pheromone trail.
Whenever an ant, still looking for the food source, has to make a choice, the ant prefers the path with more pheromones and will preferably choose it (not always, but usually in a proportion of pheromone trails. After a given amount of time (usually some multiple of the total of all of the path lengths), the program is stopped, and the strongest trail of pheromones is followed; this is the best path from colony to food source. Why? The shortest path between food source and colony will have the most repeated traversals, meaning that it will have the most pheromone.
Let's see this at work. Let's label each edge and safe spot (i.e., vertex) from the graph above with a letter for easier notation.
( ** B ** )------( ** C ** )
/ | \ l \
g / | \ \ m
/ | \ \
(A) | i \ k (F)
\ | \ /
h \ | \ / n
\ | j \ /
( ** E ** )------( ** D ** )
(safe spot)------(safe spot)
/ | \ 7 \
6 / | \ \ 8
/ | \ \
(colony) | 1 \ 4 (food source)
\ | \ /
8 \ | \ / 9
\ | 2 \ /
(safe spot)------(safe spot)
So let's send some ants through. We send through 100 ants, and at each juncture, an ant chooses a path with the following ratio: path1.pheromone + 1:path2.pheromone + 1, so if there is no pheromone, it is equal, and if there is pheromone, the weaker path won't always be rejected. Here is a runthrough of how the ants are moving, so you can follow along.
At 0 seconds, 50 ants will follow path g and 50 will follow path h right off the bat.
At 6 seconds, 50 ants reach point B from path g.
17 of these follow path i, 17 more follow path k, and the rest follow path l.
At 7 seconds, 17 ants reach point E from path i.
8 of these follow path j and the rest follow path h.
At 8 seconds, 50 ants reach point E from path h.
25 of these follow path i and the rest follow path j.
At 9 seconds, 8 ants reach point D from path j.
4 of these follow path k and the rest follow path n.
At 9 seconds, 25 ants reach point B from path i.
9 of these follow path g, 8 of these follow path k, and the rest follow path l.
At 10 seconds, 25 ants reach point D from path j.
13 of these follow path n and the rest follow path k.
At 10 seconds, 17 ants reach point D from path k.
9 of these follow path n and the rest follow path j.
... ...
At 18 seconds, the first group, numbering 4, following path n, reach the colony.
They start to return, laying pheromone along path n. They took g-i-j-n to arrive.
... ...
At 19 seconds, another group, numbering 9, following path n, reach the colony.
They start to return, laying pheromone along path n. They took g-k-n to arrive.
At 19 seconds, another group, numbering 13, following path n, reach the colony.
They start to return, laying pheromone along path n. They took h-j-n to arrive.
... ... ...
You can see that over time, pheromone will begin to be heavily laid along the shortest path (g-i-j-n). They will build a favortism for the second group to follow their trailblazing path, and the majority of the ants will follow, laying down a continually heavier trail of pheromone, until all ants follow that path almost exclusively. When the algorithm stops and the strongest pheromone path is followed, the shortest path g-i-j-n will quickly be revealed.
This type of solution to the graph problem is very adaptable to threading and parallelized solutions, because each ant can traverse the graph individually. Thus, using a large number of processors, an approximation of the best path from point A to point B on a complex graph can quickly be found.
The ant colony algorithm is very effective for application to "shortest-route" problems, such as the traveling salesman problem (with a few modifications, such as requiring each ant visit each safe spot, and dying if they have to repeat a path) and trip-planning software such as Expedia.