Swarm Intelligence Techniques and Their Adaptive Nature with Applications - Complex System Modelling and Control Through Intelligent Soft Computations - page 255

3.2 Ant Colony Optimization

Ant colony optimization (ACO) is inspired by foraging behavior of ants. Ants
deposit pheromone to mark the favorable path and that path is followed by other
member of the colony to collect foods. Over the time pheromone evaporates and
hence, relative attraction to that speci c path decreases. As much time an ant takes

to travel to and fro from source to destination, proportionate amount of pheromone
evaporates by that time. Summarily smaller path takes less time, which implies less
evaporation, so density of pheromone becomes higher. Therefore, if one ant

nds a
good (i.e., short) path from the source to destination, other ants are more likely to
follow that path. Arti cial ant system has to do two main tasks: updating phero-

mone and selection of path with maximum pheromone densities to reach destina-
tion. To acquire ACO method, solution space is represented with graph. The
pheromone

τ ij , associated with the edge joining nodes i and j, is updated as follows:

X

m
k¼1 Ds ij

s ij ð qÞs ij þ ð 3 Þ

1

where, ˁ is the evaporation rate, m is the number of ants, and Ds ij is the quantity of

pheromone deposited on edge (i, j) by ant k. L k if

ant k used edge (i, j) in its tour, if not considered 0 value, where Q is a constant, and
L k is the cost of the tour constructed by ant k.
ACO adopts probabilistic approach to select path. This probability depends on
priori desirability represented by attractiveness

Ds ij is measured with a ratio Q =

τ ij of
the move, indicating how desirable it has been in the past to make that particular
move. When an ant k is at node i then the probability of going to node j is given by
the equation below:

ʷ ij of the move and posteriori

s ij s ij
P j 2 allowed j s ij g ij

p ij ¼ ð 4 Þ

Here, τ ij is the amount of pheromone deposited for moving from node i to j, ʱ is a

τ ij which takes greater than equal to 0 value, ʲ

parameter to control the in fl uence of

is another parameter to control the in ʷ ij which takes value greater than

equal to 1. ʷ ij is the attractiveness of edge (i, j) which is considered as inverse of
cost of the edge (i, j).
In each iteration ants add new transition to construct

fl uence of

final solution and update
pheromone level in the path. Once solutions are represented with graph and ini-
tialize ants accordingly, ACO can be fitted in general framework.