Contents
• People involved
• About Ant Colony Optimization
• References
• Links
COMP^{2}SYS people involved in evolutionary
computation research are:
 Max Manfrin
 Prasanna Balaprakash
Senior scientists involved in evolutionary computation research
are:
 Marco Dorigo
 Mauro Birattari
 Thomas Stützle
About Ant Colony Optimization
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.
Framework for Ant Colony Optimization
while termination conditions not met do
ScheduleActivities
ConstructAntsSolutions
UpdatePheromones
DaemonActions % optional
endScheduleActivities
endwhile

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_{1}, ··· , 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 socalled 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 suboptimal
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.
References
[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):2941, 1996.
[3] M. Dorigo, G. Di Caro, and L. M. Gambardella.
Ant algorithms for discrete optimization. Artificial Life,
5(2):137172, 1999.
[4] M. Dorigo and T. Stützle. Ant Colony
Optimization. MIT Press, Cambridge, MA, 2004.
Links
• The Ant Colony Optimization website
