Solution Techniques

Ant Colonies System Description

Ant System (AS) methods are inspired by an analogy with real ant colonies foraging for food. In their search for food, ants mark the paths they travel by laying an aromatic essence called pheromone. The quantity of pheromone laid on a path depends on the length of the path and the quality of the food source. This pheromone provides information to other ants that are attracted to it. With time, paths leading to the most interesting food sources, i.e., close to the nest and with large quantities of food, become more frequented and are marked with larger amounts of pheromone. Overall, this process leads to an efficient procedure for procuring food by ant colonies.

In Figure 1 we explain graphically how ants find the shortest path from the nest to the food source just by leaving pheromone trails. For simplification purposes, let us suppose that there are just two possible paths from the nest of ants (point A of Fig. 1a) to the food (point B of Fig. 1a). Initially, ants start from the nest (Fig. 1b) and when point B is reached, since there is no pheromone trail, they follow either of the two paths with equal probability (Fig. 1c). Ants which followed the shortest path will reach the food earlier than the others (Fig. 1d), and when they return, they find at point E a light pheromone trail on the shortest path, so they follow that route with a higher probability than the other one (Fig. 1e). When the ants that went through the longest path return from the food (point F) and reach point E, the pheromone trail on the shortest path will be more reinforced than that of the longer one, so they will follow that shortest path with higher probability. This way, the probability of following the shortest path will become greater and greater over time, since ants continuously leave pheromones on the shortest path (reinforcing it) while the pheromones on the longest path are evaporating (Figs. 1e–g). Finally, the pheromone trail of the longest route will have evaporated and most ants will follow the shortest path, which will have a great density of pheromones (Fig. 1h).

Nest and food source connected by two possible paths — a)

Ants choosing either path with equal probability — c)

Ants on the shortest path reaching the food earlier — d)

Returning ants preferring the path with more pheromone — e)

The shortest path being progressively reinforced — f)

Pheromone evaporating on the longest path — g)

Most ants finally following the shortest path — h)

Pheromone level on the two paths over time — Figure 1. Ants finding the shortest path from nest -A- to the food source -F-

Dorigo, in his Ph.D. thesis [Dorigo 1992], introduced the concept of AS, a new class of metaheuristics for solving combinatorial problems based on the following correspondences: artificial ants searching the solution space simulate real ants exploring their environment, objective function values are associated with the quality of food sources, and values recorded in an adaptive memory mimic the pheromone trails.