Geology Reference
In-Depth Information
first algorithm was aiming to search for an optimal
path in a graph. The original idea has since diversi-
fied to solve a wider class of numerical problems
and, as a result, several problems have emerged,
drawing on various aspects of the behaviour of
ants. The initial applications of ACO were in the
domain of NP-hard combinatorial optimization
problems, while it was soon also applied to rout-
ing in telecommunication networks.
In ACO, a set of software agents called
artificial
ants
search for good solutions to the optimization
problem of finding the best path on a weighted
graph. The ants incrementally build solutions by
moving on the graph. The solution construction
process is stochastic and it is biased on a
phero-
mone model
, that is, a set of parameters associated
with graph components (either nodes or edges)
whose values are modified at runtime by the ants.
To apply ACO to the TSP, the
construction
graph
is considered, defined by associating the
set of cities with the set of vertices on the graph.
The construction graph is fully connected and
the number of vertices is equal to the number of
cities, since in the TSP it is possible to move from
any given city to any other city. The length of the
edges (connections) between the vertices are set to
be equal to the corresponding distances between
the nodes (cities) and the pheromone values and
heuristic values are set for the edges of the graph.
Pheromone values are modified during iterations at
runtime and represent the cumulated experience of
the ant colony, while heuristic values are problem
dependent values that, in the case of the TSP, are
set to be the inverse of the lengths of the edges.
During an ACO iteration, each ant starts from
a randomly chosen vertex of the construction
graph. Then, it moves along the edges of the
graph keeping a memory of its path. In order to
move from one node to another it probabilisti-
cally chooses the edge to follow among those
that lead to yet unvisited nodes. Once an ant has
visited all the nodes of the graph, a solution has
been constructed. The probabilistic rule is biased
by pheromone values and heuristic information:
the higher the pheromone and the heuristic value
associated to an edge, the higher the probability
the ant will choose that particular edge. Once all
the ants have completed their tour, the iteration is
complete and pheromone values on the connec-
tions are updated: each of the pheromone values
is initially decreased by a certain percentage and
then it receives an amount of additional phero-
mone proportional to the quality of the solutions
to which it belongs.
Ant Colony Optimization Algorithm
Consider a population of
m
ants where at each
iteration of the algorithm every ant constructs a
“route” by visiting every node sequentially. Ini-
tially, ants are put on randomly chosen nodes. At
each construction step during an iteration, ant
k
applies a probabilistic action choice rule, called
random proportional rule, to decide which node to
visit next. While constructing the route, an ant
k
currently at node
i
, maintains a memory M
k
which
contains the nodes already visited, in the order
they were visited. This memory is used in order
to define the feasible neighbourhood N
k
i
that is
the set of nodes that have not yet been visited by
ant
k
. In particular, the probability with which ant
k
, currently at node
i
, chooses to go to node
j
is
(
)
α
(
)
β
τ
⋅
η
k
i j
,
i j
,
k
p
=
,
if
j
∈
N
(
)
i j
,
∑
i
α
β
(
τ
)
⋅
(
η
)
i
,
i
,
k
N
∈
i
(12)
where
τ
i
,
j
is the amount of pheromone on con-
nection between
i
and
j
nodes,
α
is a parameter
to control the influence of
τ
i
,
j
,
β
is a parameter to
control the influence of
η
i
,
j
and
η
i
,
j
is a heuristic
information that is available a priori, denoting the
desirability of connection
i
,
j
, given by
=
1
η
i j
(13)
,
d
i j
,
Search WWH ::
Custom Search