Databases Reference
In-Depth Information
link (
i, j
) after one completed cycle is equal to:
n
∆
τ
ij
(
t
)
∆
τ
ij
(
t
)=
(1.6)
k
=1
where ∆
τ
ij
(
t
) is the quantity of pheromone laid on link(
i, j
)bythe
k
th ant
during the cycle.
The pheromone quantity ∆
τ
ij
(
t
)iscalculatedas∆
τ
ij
=
Q
L
k
(
t
)
,ifthe
k
th ant walks along the link(
i, j
) in its tour during the cycle. Otherwise,
the pheromone quantity equals: ∆
τ
ij
=0,where
Q
is a constant;
L
k
(
t
)
is the tour length developed by the
k
th ant within the cycle. As we
can see, artificial ants collaborate among themselves in order to discover
high-quality solutions. This collaboration is expressed through pheromone
deposition. In order to improve ant system Dorigo
et al.
35
proposed
ant colony optimization (ACO) that represents metaheuristic capable
to discover high-quality solutions of various combinatorial optimization
problems.
The transition probability
p
ij
(
t
) is defined within the ant colony
optimization by the following equation:
j
=
arg max
h∈
Ω
i
(
t
)
{
[
τ
ih
(
t
)][
η
ih
]
β
}
q
≤
q
0
(1.7)
J
q
≤
q
0
where
q
is the random number uniformly distributed in the interval [0, 1],
q
0
is the parameter (0
1), and
J
is the random choice based on the
above relation; one assumes
α
= 1 when using the equation (1.4).
In this way, when calculating transition probability, one uses pseudo-
random-proportional rule (equation (1.8)) instead of random-proportional
rule (equation (1.4)). The trail intensity is updated within the ACO by
using local rules and global rules. Local rule orders each ant to deposit a
specific quantity of pheromone on each arc that it has visited when creating
the traveling salesman tour. This rule reads:
≤
q
0
≤
τ
ij
(
t
)
←
(1
−
ρ
)
τ
ij
(
t
)+
ρτ
0
,
(1.8)
where
ρ
is the parameter (0
<ρ<
1), and
τ
0
is the amount of pheromone
deposited by the ant on the link(
i, j
) when creating the traveling salesman
tour. It has been shown that the best results are obtained when
τ
0
is equal
to the initial amount of pheromone
c
.
