Information Technology Reference
In-Depth Information
2 Synchronous and Asynchronous Cellular Automata
Cellular automata are discrete dynamical systems. A standard cellular automa-
ton consists of an array of cells, eachof whichcan be in one of a finite number
of possible states, updated synchronously in discrete time steps, according to a
local, identical interaction rule. Here we will only consider Boolean automata
for which the cellular state
s ∈{
0
,
1
}
. The state of a cell at the next time step
is determined by the current states of a surrounding neighborhood of cells. The
regular cellular array (grid) is
d
-dimensional, where
d
=1
,
2
,
3 is used in prac-
tice; in this paper we shall concentrate on
d
= 1, i.e. one-dimensional grids. The
identical rule contained in eachcell is usually specified in te form of a rule
table withan entry for every possible neighborhood configuration of states. For
one-dimensional CAs, a cell is connected to
r
local neighbors (cells) on either
side; eachcell thus has 2
r
+1 neighbors. When considering a finite grid, spatially
periodic boundary conditions are frequently applied, resulting in a circular grid
for the one-dimensional case. The term
configuration
refers to an assignment of
ones and zeros to eachcell at a given time step.
There are many ways for sequentially updating the cells of a CA (for an ex-
cellent discussion, see [7]). The most general one is
independent random ordering
of updates in time, which consists in randomly choosing the cell to be updated
next, with replacement. This corresponds to a binomial distribution for the up-
date probability, the limiting case of which for large
n
is the Poisson distribution
(
n
is the number of cells in the grid).
For comparison purposes we also employ two other update methods:
fixed
random sweep
and
random new sweep
([7]). In the fixed random sweep update,
eachcell to be updated next is cosen withuniform probability witout re-
placement; this will produce a certain update sequence (
c
1
,c
2
,...,c
n
), where
c
q
means that cell number
p
is updated at time
q
and (
j,k,...,m
) is a permutation
of the
n
cells. The same permutation is then used for the following update cycles.
The random new sweep method is the same except that each new sweep through
the array is done by picking a different random permutation of the cells. A time
step consists in updating
n
times, which corresponds to updating all the
n
cells
in the grid for fixed random sweep and random new sweep, and possibly less than
n
cells in the binomial method, since some cells might be updated more than
once. It should be noted that our chosen asynchronous updating being non-de-
terministic, the same CA may reach a different configuration after
n
time steps
on the same initial distribution of states, which is not the case for synchronous
CAs, since there is a single possible sequence of configurations for a synchronous
CA for a given initial configuration of states.
3 Evolving 1-D Asynchronous CAs for the Density Task
In this section we define the density task and we describe how asynchronous CAs
for performing this task can be evolved by genetic algorithms (GA).
The density task is a prototypical computational task for CAs that has been
much studied due to its simplicity and richness of behavior. For one-dimensional
