Information Technology Reference
In-Depth Information
Handling Corpses. As in Deneubourg's implementation of his model, our ants
are allowed to enter the site of a body. Many ants are allowed onto the same
site as long as they are traveling along different directions. The probability of
picking up a corpse is given by
1
1 + exp( α p · ( f − β p ))
(2)
where f is the proportion of bodies in the neighborhood and α p , β p parameters.
The marking is a kind of memory, which tells the loaded ant to deposit as soon
as possible after being marked
Random Walk. The ant motion rule considered by Deneubourg also differs
from ours. Each step of our random walk consists in successively applying a
diffusion followed by a propagation. The ants move one cell at a time. We use
the diffusion rule of [5]. At each site, an angle kπ/ 4( k ∈ [0; 7]) is chosen with
probability r k . All ants on that site are then rotated by this angle. Since r 0 is
the zero angle probability, ants entering a given site are deflected from their
trajectory with probability 1 − r 0 . An ant moving in direction k is transfered
to the corresponding neighbor. This step does obviously not alter its direction
of motion. The propagation achieves the update of the cells. In the current
implementation, the mean free path is given by r 0 / (1 − r 0 ) independently for
each ant [5]. The quantity r 0 determines the diffusion coe A cient of the random
walk. For example, r 0 =0 . 98 yields a mean free path of 50. This yields a diffusion
coe A cient much larger than in Deneubourg's original implementation. At each
time step, the ants move to the nearest cell along their direction of motion and
check for the possibility to pick up, deposit a corpse or mark themselves. The
ant motion is decoupled from the handling of the corpses.
3.3 Parallelization
A common way for speeding up a computation is to use more than one processor
to achieve the given job. This procedure is called a parallelization. It implies
decomposing a task into several sub-tasks which are equitably assigned to the
available processors.
In the present context, the lattice is partitioned into several domains, one
per processor. An extra layer, called the boundary, is actually added to each
domain. It contains the cell-neighborhood information that is not local to the
processor. At each time step, boundaries are exchanged between processors man-
aging adjacent domains, so as to maintain the cell-neighborhood information up
to date. Note that the partitioning of the lattice is optimized in order to mini-
mize communications. These are overlapped with the propagation phase to save
time.
Our CA algorithm was implemented using PELABS (Parallel Environment
for LAttice Based Simulations) [6]. PELABS is a library developed at the Uni-
versity of Geneva, which offers many functionalities for designing parallel CAs.
 
Search WWH ::




Custom Search