Information Technology Reference
In-Depth Information
3 A Cellular Automata Model
In Deneubourg's model, ants are updated
sequentially
in a given order specified
by some arbitrary (but fixed) numbering of the ants. Here, we propose a
paral lel
synchronous updating scheme. We thus introduce a cellular automaton (CA)
model whose dynamics is based on the diffusion rule of [5].
In our CA model, ants have a local perception of their environment: they can
access any information located in their direct neighborhood. Deneubourg's ants
have an intelligence based on a memory (temporal information), while our ants
behave according to the knowledge of their surroundings (spatial information).
The dynamics consists in alternating a pick-up, deposition and marking rule
with a random walk rule. The CA approach implies dealing with any potential
conflict which arises when several ants simultaneously enter a site.
3.1 The Underlying Space
The cells of our CA are arranged on a regular two-dimensional square lattice.
The local topology around a cell is given by the Moore neighborhood, which
consists of the 8-neighboring cells (above, below, right and left, plus diagonals).
The state of a cell consists of: (1) ants moving in any of the 8 directions, and
(2) a corpse. In our model all ants are identical, but there can be several types
of corpses. A cell can hold at most eight ants, each one traveling in a different
direction, and at most one corpse. If we think of a cell as being connected to its
neighbors by links, then the ants can be thought as traveling along these links.
3.2 The Evolution Rule
The CA rules are described in table 3.1. Let us list some differences with
Deneubourg's model. First, our parallel updating scheme implies some kind of
arbitration to handle conflicts. Second, the pick-up probability is now based on
local spatial information. Third, the deposition phase, which is deterministic,
requires a supplementary stage: the marking of loaded ants. Fourth, the ants
move according to a CA diffusion rule.
Algorithm 3.1:
The cellular ant colony algorithm.
