Contents

• Max Manfrin
• Prasanna Balaprakash

• Marco Dorigo
• Mauro Birattari
• Thomas Stützle

Ant Colony Optimization (ACO) is a metaheuristic for the approximate solution of difficult optimization problems. The basic ideas of ACO were introduced in Dorigo [1] and Dorigo et al. [2, 3]. A complete overview of the field can be found in Dorigo and Stützle [4].

ACO was inspired by the foraging behavior of real ants. This behavior enables ants to find shortest paths between food sources and their nest. Initially, ants explore the area surrounding their nest in a random manner. As soon as an ant finds a source of food, it evaluates quantity and quality of the food and carries some of this food to the nest. During the return trip, the ant deposits a pheromone trail on the ground. The quantity of pheromone deposited, which may depend on the quantity and quality of the food, will guide other ants to the food source. The indirect communication between the ants via the pheromone trails allows them to find the shortest path between their nest and food sources. This functionality of real ant colonies is exploited in artificial ant colonies in order to solve optimization problems. In ACO algorithms the pheromone trails are simulated via a parametrized probabilistic model that is called the pheromone model. The pheromone model consists of a set of model parameters whose values are called the pheromone values. The basic ingredient of ACO algorithms is a constructive heuristic that is used for probabilistically constructing solutions using the pheromone values. In general, the ACO approach attempts to solve an optimization problem by iterating the following two steps:

• Solutions are constructed using a pheromone model, that is, a parametrized probability distribution over the solution space.
• The solutions that were constructed in earlier iterations are used to modify the pheromone values in a way that is deemed to bias the search toward high quality solutions.

while termination conditions not met do
   ScheduleActivities
      ConstructAntsSolutions
      UpdatePheromones
      DaemonActions      % optional
   end-ScheduleActivities
end-while

The ACO metaheuristic framework (as given in Dorigo and Stützle [4]) consists of three algorithmic components that are gathered in the ScheduleActivities construct. The ScheduleActivities construct does not specify how these three activities are scheduled and synchronized. This is up to the algorithm designer. In the following we explain these three algorithm components in more detail.

ConstructAntsSolutions: As mentioned above, the basic ingredient of ACO algorithm is a constructive heuristic for probabilistically constructing solutions. A constructive heuristic assembles solutions as sequences of solution components taken from a finite set of solution components C = {c₁, ··· , c_n}. A solution construction starts with an empty partial solution s^p =<>. Then, at each construction step the current partial solution s^p is extended by adding a feasible solution component from the set N(s^p) ? C \ s^p, which is defined by the solution construction mechanism. The process of constructing solutions can be regarded as a walk (or a path) on the so-called construction graph G_C =(C, L) whose vertexes are the solution components C and the set L are the connections. Once an ant has built a solution, or while the solution is being built, the ant evaluates the (partial) solution that will be used by the UpdatePheromones procedure to decide how much pheromone to deposit.

UpdatePheromones: This is the process by which the pheromone trails are modified. The trails value can either increase, as ants deposit pheromone on the components or connections they use, or decrease, due to pheromone evaporation. In ACO algorithms we can find different types of pheromone updates. We outline a pheromone update that is used by basically every ACO algorithm. This pheromone update consist of two parts. First, a pheromone evaporation, which uniformly decreases all the pheromone evaporation is needed to avoid a too rapid convergence of the algorithm toward a sub-optimal region. It implements a useful form of forgetting, favoring the exploration of new areas in the search space. Then, one or more solutions form the current and/or from earlier iterations are used to increase the values of pheromone trail parameters on solution components that are part of the solutions.

DaemonActions: This procedure is used to implement centralized actions which cannot be performed by single ants. Examples of daemon actions are the activation of a local optimization procedure, or the collection of global information that can be used to decide whether it is useful or not to deposit additional pheromone to bias the search process from a nonlocal perspective. As a practical example, the daemon can observe the path found by each ant in the colony and select one or a few ants (e.g., those that built the best solutions in the algorithm iteration) which are then allowed to deposit additional pheromone on the components/connections they used.

[1] M. Dorigo. Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale. Ph.D. thesis, Politecnico di Milano, Milan, Italy, 1992.

[2] M. Dorigo, V. Maniezzo, and A. Colorni. Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics - Part B, 26(1):29-41, 1996.

[3] M. Dorigo, G. Di Caro, and L. M. Gambardella. Ant algorithms for discrete optimization. Artificial Life, 5(2):137-172, 1999.

[4] M. Dorigo and T. Stützle. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.

• The Ant Colony Optimization website