Ant Colony Optimisation (ACO) studies artificial systems that take inspiration from the behaviour of real ant colonies and which are used to solve discrete optimisation problems.
Ant algorithms were first proposed by Dorigo and colleagues [Dorigo et al., 1991] as a multi-agent approach to difficult combinatorial optimisation problems like the travelling salesman problem (TSP) and the quadratic assignment problem (QAP), and later introduced the ACO meta-heuristic [Dorigo and Di Caro, 1999]. There is currently a lot of ongoing activity in the scientific community to extend/apply ant-based algorithms to many different discrete optimisation problems. Recent applications cover problems like vehicle routing [Bullnheimer et al., 1999], graph colouring [Costa and Hertz, 1997], and routing in communications networks [Di Caro and Dorigo, 1998][Varela and Sinclair, 1999].
Ant algorithms were inspired by the observation of real ant colonies. Ants are social insects, that is, insects that live in colonies and whose behaviour is directed more to the survival of the colony as a whole than to that of a single individual component of the colony. Social insects have captured the attention of many scientists because of the high level of structure their colonies can achieve, especially when compared to the relative simplicity of the colony's individuals. An important and interesting behaviour of ant colonies is their foraging behaviour, and, in particular, how ants can find shortest paths between food sources and their nest. While walking from food sources to the nest and vice versa, ants deposit on the ground a substance called pheromone, forming in this way a pheromone trail. Ants can smell pheromone and, when choosing their way, they tend to choose, in probability, paths marked by strong pheromone concentrations. The pheromone trail allows the ants to find their way back to the food source (or to the nest). It can also be used by other ants to find the location of the food sources found by their nest-mates. It has been shown experimentally that this pheromone trail following behaviour can give rise, once employed by a colony of ants, to the emergence of shortest paths. That is, when more paths are available from the nest to a food source, a colony of ants may be able to exploit the pheromone trails left by the individual ants to discover the shortest path from the nest to the food source and back.
The Ant Colony Optimisation meta-heuristic employs a co-operating colony of ants in an attempt to find good solutions to difficult discrete optimisation problems. Cooperation is a key design component of ACO algorithms: The choice is to allocate the computational resources to a set of relatively simple agents (artificial ants) that communicate indirectly by stigmergy. Good solutions are an emergent property of the agents' cooperative interaction.
Artificial ants have a double nature. First, they are an abstraction of real ants found in nature and of their behaviour. On the other hand, artificial ants have also been enriched with some capabilities which are not found among their natural counterparts. Since the artificial ants are employed in software to solve difficult discrete optimisation problems, it is reasonable to give the ants some capabilities, which while not found in real ant behaviour, make them more efficient and effective.
Similarities and Differences with Real Ants
Most of the ideas of ACO stem from real ants and their behaviour. In particular, the use of: (i) a colony of cooperating individuals, (ii) an (artificial) pheromone trail for local stigmergic communication, (iii) a sequence of local moves to find shortest paths, and (iv) a stochastic decision policy using local information and no lookahead. [Dorigo et al., 1999].
Colony of cooperating individuals: As with real ant colonies, ant algorithms comprise of a population, or colony, of concurrent and asynchronous entities cooperating at a global level in order to find an optimal solution to the problem at hand. Although each individual ant is given the task of building a feasible solution, high quality solutions are the result of the cooperation of the individuals among the entire population. Ants within the population communicate among themselves by means of the information they read/write on the problems states that they visit. This is explained in more detail in the next item.
Pheromone trail and stigmergy: As real ants move about, they deposit a chemical substance, called pheromone, on the areas they visit. Artificial ants also modify some aspects of their environments, by mimicking this pheromone depositing behaviour. This artificial pheromone trail changes some numeric information locally stored in the problem's state they visit. This information takes into account the ant's current history/performance and can be read /written by any ant accessing the state. In ACO algorithms local pheromone trails are the only communication channels among the ants.
This stigmergic form of communication plays a major role in the utilization of collective knowledge. Its main effect is to change the way the environment (the problem landscape) is locally perceived by the ants as a function of all the past history of the whole ant colony. Just as real pheromone would evaporate over time, so do the artificial pheromone trails. Pheromone evaporation helps prevent the ant colony from prematurely converging upon a sub optimal solution, by allowing the ant colony to slowly forget its past history so that it can search in new directions without being over-constrained by its past decisions.
Shortest path searching and local moves: Both real and artificial ants share a common goal; to find a shortest (minimum cost) path from an origin to a destination (nest to food source). Both ant types move simply through their environment, going from one problem state to another, adjacent problem state. These steps and states are, of course, problem specific.
As was mentioned above, in order to help increase the efficiency and effectiveness of the solution, artificial ants have some characteristics that are not apparent in their real ant counterparts. [Dorigo et al., 1999]
- Artificial ants live in a discrete world, and their moves are from one discrete state to the next.
- Artificial ants keep an internal state, which contains the memory of the past actions of the ant.
- Artificial ants deposit an amount of pheromone that is a function of the quality of solution found.
- Artificial ants timing in laying pheromone is problem dependent. In some cases, pheromone trails are only updated after a solution is found. In other cases, high quality solutions are given pheromone reinforcement.