Information Technology Reference
In-Depth Information
0.9
0.8
0.7
0.6
Probabilistic pick−up
Deterministic pick−up
0.5
0.4
0.3
0.2
0.1
0
1
2
3
4
5
6
7
8
9
10
x 10
5
iteration
Fig. 3.
Time evolution of the density of the largest cluster. Squares (resp. circles)
correspond to the model with probabilistic (resp. deterministic) pick-up.
Figure 4 shows, for probabilistic pick-up, the number
N
(
t
) of clusters as a
function of time (in Log-Log scale) and the density of the largest cluster for
different numbers
M
of ants. Here
M
takes the values 100, 200, 400, 800 and
1600. At
t
=0,
N
(
t
) is of the order of
N
0
. After between 400
000 and 2
000
000
iterations, depending on
M
, there remains only one large cluster, hence
N
(
t
)=1.
With respect to performance, we wish to point out that the CPU-time of an
iteration depends little on
M
. Indeed, most of the simulation time is devoted
to the domain traversal, which occurs at each update of the CA. Therefore,
there should be an optimal
M
, depending on the other fixed parameters, which
produces the best performances.
In figure 4,
N
(
t
) appears as a stair function. The increasing length steps
indicate a slowing down of the clustering process. Indeed, large compact clusters
are more robust, requiring thus on average more time to vanish.
After an initial start-up of a few thousand iterations in which small clusters
appear,
N
(
t
) enters a power-law regime. Here, the clustering activity has reached
its normal level and
N
(
t
) gradually decreases towards 1. The power-law expo-
nent is approximately
−
3
/
4. It is interesting to compare this exponent with the
exponents
−
1
/
2of a diffusion process and
−
1 of a global pick up and deposit
anywhere algorithm. An exponent of 3 was measured in [4] for Deneubourg's
model, but however for a relatively short intermediate power-law regime. The
final regime leading from a dozen of clusters to a single one, was very noisy and
rather slow. In our CA model, the power-law regime survives until the end. In
the deterministic case, the exponent is
−
1
/
2. Therefore, adding in some intelli-
gence, via probabilistic pick-up, shows that our algorithm actually does better
