Information Technology Reference
In-Depth Information
10
3
100 ants
200 ants
400 ants
800 ants
1600 ants
10
2
10
1
10
0
10
3
10
4
10
5
10
6
10
7
iteration
Fig. 4.
Time evolution of the numbers of clusters.The domain size is 290
×
200 and
there are 1500 corpses. The algorithm uses probabilistic pick-up.
than a simple diffusion process. We also want to emphasize that our CA model,
as opposed to [4], is not plagued by noise at the end of the clustering process.
Finally, we remark that the curves of figure 4 can be approximately super-
imposed by linearly rescaling time by a factor
M
. This result indicates that a
single ant can also produce the single cluster alone. Adding more ants just im-
proves linearly the formation speed. This is the most basic form of cooperation:
more workers do more work in the same amount of time. The global task is thus
equally divided among the ants which perform their job independently. There
is no collective effect requiring, for example, a minimal number of workers to
achieve the global task. Similarly, we also observed that the density
d
(
t
)ofthe
largest cluster follows some kind of universal behavior under time rescaling. This
can be summarized by the formulae
N
(
t
)=
C ·
(
Mt
)
−
0
.
75
1
−
exp(
−ν
(
Mt
)
γ
)
d
(
t
)=0
.
92
·
(3)
where
C
,
ν
,
γ
are constants depending on the details of the model, 0
.
75 the
power-law exponent and 0
.
92the maximum cluster density. As a matter-of-
fact, these results are not really surprising, since the ants in our model have no
added-in intelligence. However, it was not completely obvious that some ants
would not undo the job done by others, thus yielding a factor smaller than
M
for the formation speed.
5Conclusion and Further Work
We proposed a new parallel CA ant colony algorithm which performs clustering
and sorting of corpses, initially randomly distributed in a two dimensional arena.
