Information Technology Reference
In-Depth Information
In some sense, it is more realistic to use a CA, since the problem of clus-
tering in ant colonies is parallel by nature. Indeed, the ants perform their task
simultaneously and may actually compete for a given corpse. Furthermore, ant
colony algorithms achieve a global task in a distributed way without the need
of central control. Hence, they are local by essence. Current applications include
robust distributed sorting and graph partitioning [1,2].
In this work, we show that the clustering process resulting from our CA,
produces a single cluster in the long run. We observe the effect on the density
of this cluster of probabilistic versus deterministic pick-up. If there are different
types of corpses, our algorithm sorts them into distinct clusters, one per type.
In addition to observing clustering and sorting from a qualitative point of view,
we study the number of clusters and their density as a function of time. It seems
that both functions are invariant under a time rescaling by a factor equal to the
number of ants. This indicates that the clustering process does not result from
a collaboration between the ants.
2 The Deneubourg Model
The model of Deneubourg [3] defines a discrete dynamics on a square lattice,
whose sites are occupied by ants and corpses. The motion of the ants is sequential
in the sense that ants are visited according to an initial, arbitrary numbering.
At each time step, ants move randomly from their present position to one of the
four neighboring sites (left, right, above or below), provided it is not occupied by
another ant. The displacement of the corpses is totally dependent on the ants.
An ant encountering a corpse on its path, picks it up with probability
p
p
unless it is already loaded with a corpse. Then the ant moves again randomly
and, at each step, may deposit the body with probability
p
d
on the new site it
stands on. The probabilities
p
p
and
p
d
are computed as
2
2
k
1
k
1
+
f
f
k
2
+
f
p
p
=
p
d
=
(1)
where
k
1
,
k
2
are parameters and
f
is the proportion of corpses encountered by
the ant during its last
T
steps. This quantity
f
represents the ant's memory.
If
f
is small compared to
k
1
(i.e. the ant is in the vicinity of a small cluster),
p
p
is close to one and it is very likely that the ant will take the corpse. If
f
is
large with respect to
k
2
(i.e. the ant has come across many dead bodies), then
so is the probability
p
d
of depositing the corpse. Clearly, this rule biases the
dynamics towards emptying small existing clusters and augmenting larger ones,
thus favoring the formation of a single cluster of corpses.
Note that the current occupation state of the cell on which the ant lies is
taken into account only after the pick-up or drop down decision is made.
In this implementation, ants are authorized to move onto sites occupied by
corpses. This allows the memory update as well as the picking up of corpses to
take place. Likewise, ants drop the corpse they carry on the site they stand on.
