Chapter 4: Ant Algorithms

 Download CD Content

In this chapter, we'll look into an interesting multi-agent simulation that's useful in solving a wide variety of problems. Ant algorithms, or Ant Colony Optimization (the name coined by its inventor Marco Dorigo), uses the natural metaphor of ants and stigmergy to solve problems over a physical space [Dorigo 1996]. Nature has provided a number of different methods and ideas in the space of optimization (as illustrated by other chapters in this book such as "Simulated Annealing" and "Introduction to Genetic Algorithms"). Ant algorithms are particularly interesting in that they can be used to solve not only static problems, but also highly dynamic problems such as routing problems in changing networks.

Natural Motivation

Although ants are blind, they navigate complex environments and can find food some distance from their nest and return to their nest successfully. They do this by laying pheromones while they navigate their environment. This process, known as stigmergy, modifies their environment to permit communication between the ants and the colony as well as memory for the return trip to the nest.

What is most surprising about this process is that ants tend to take the best route between their nest and some external landmark. This natural optimization is again part of stigmergy. As more ants use a particular trail to an external landmark, the trail becomes higher in pheromone concentration. The closer the landmark is to the nest, the higher the number of round-trips made by each ant. For a landmark that's farther away, a lesser number of round-trips are made, and a higher concentration of pheromones is applied. The higher the concentration of pheromones, the more ants will choose this route over others that might be available. This iterative process achieves sub-optimal to optimal trails between the endpoints.

Ant algorithms are interesting because they share some of the fundamental qualities of ants themselves . Ants are altruistic, cooperative, and work collectively toward a common goal. Ant algorithms share these traits in that the simulated ants within the environment work in parallel to solve a problem, and through stigmergy, help others to further optimize the solution.

Consider the example in Figure 4.1. Two ants at their nest must reach the food on the other side of the obstacle . While the ants travel, each ant deposits a small amount of pheromone along the route as a marker.

Figure 4.1: Initial configuration (T ).

With equal probability, each ant takes a different route. One ant takes the upper route and the other the lower route. Since the lower route is half the distance to the food, the lower ant has reached the destination at time T ₁ . The ant taking the higher route has only reached the halfway mark (see Figure 4.2).

Figure 4.2: One unit of time has passed (T ₁ ).

Once an ant reaches the food, it takes one of the objects and returns back to the nest using the same path . At time T ₂ , the lower ant has returned to the nest with the food while the upper ant has finally reached the food landmark (see Figure 4.3).

Figure 4.3: Two units of time have passed (T ₂ ).

Recall that as each ant travels , a small amount of pheromone is deposited along the trail. In the case of the upper ant, the trail has been covered only once during the period T -T ₂ . The lower ant has covered its trail twice during the same period. Therefore, twice the amount of pheromone has been deposited along the lower trail compared to the upper trail. At time T ₄ , the upper ant will have returned to the nest while the lower ant will have completed another run to the food landmark and back. At this point, the concentration of pheromone on the lower trail will be twice that of the upper trail. The upper ant will then likely decide to use the lower trail, based solely on the concentration of pheromone detected .

This is the basic idea behind ant algorithms ”optimization through indirect communication between autonomous agents .