Information Technology Reference
In-Depth Information
A Parallel Cellular Ant Colony Algorithm for
Clustering and Sorting
Paul Albuquerque
1
,
2
and Alexandre Dupuis
1
1
Computer Science Department, University of Geneva, 1211 Geneva 4, Switzerland
2
LII, Ecole d'ingenieurs de Geneve, HES-SO, 1202 Geneva, Switzerland
Abstract.
Some ant species are known to gather and sort corpses in
an auto-organized way. In this contribution, we propose a new cellular
ant colony algorithm for sorting and clustering. This algorithm mimics
the behavior of real ants. The cellular automata nature of our algorithm
implies a straightforward parallelization. The rule consists of a pick-up, a
depositionandadiffusion.Ourprobabilisticpick-upruleisbasedonsome
spatial neighborhood information. We observe that probabilistic pick-up
yields compact clusters and also speeds up the clustering process. In the
long run, a single cluster emerges. Moreover, in the presence of several
corpse species, our algorithm sorts the corpses into distinct clusters. Thus
our model reproduces realistic results, but however we do not observe any
collective effect.
1 Introduction
Some ant species are capable of clustering corpses or sorting their brood without
any of the working ants having a global perception of the overall task [1,2]. It thus
seems that the building of a single cluster emerges as the result of a collaboration
between the ants. Ant colony algorithms try to mimic this behavior.
The famous forerunner model proposed by Deneubourg [3] for clustering and
sorting is the following. Ants move randomly in some arena containing corpses,
which they can load and deposit later. They are endowed with some form of
intelligence: (i) picking up a corpse occurs preferentially in a small cluster of
dead bodies and (ii) the probability to deposit the corpse in a cluster increases
with its size. With both these hypotheses, it is clear that smaller clusters should
disappear to the benefit of larger ones. The ants estimate a cluster size from a
memory of their past steps, and act probabilistically according to this estimate.
In this contribution, we define a new cellular automaton (CA) which mod-
els an ant colony. Our CA model performs clustering and sorting similarly to
Deneubourg's model. However, we use a deterministic deposition rule and a
probabilistic pick-up rule based on the ants' local spatial perception of their
environment. The motion of the ants is related to a CA diffusion rule [5]. To
our knowledge, the effect of a parallel synchronous updating scheme has not yet
been explored in much detail. Here, we only address the parallelization and not
the performance issue, even though we give some timing indications.
