Information Technology Reference
In-Depth Information
An Evolutionary Approach to the Study of
Non-trivial Collective Behavior in Cellular
Automata
Francisco Jimenez-Morales
Departamento de Fısica de la Materia Condensada. Universidad de Sevilla.
P. O. Box 1065, 41080-Sevilla, Spain.
jimenez@us.es
Abstract.
A genetic algorithm (GA) is used to evolve two and one
dimensional cellular automata (CA) to perform a non-trivial collective
behavior task. Using as fitness function the average area in the iterative
map, the GA is able to discover several rules with the desired behavior.
In
d
= 2 we study the scaling of the attractor versus lattice size and
noise. In
d
= 1, using the tools of the computational mechanics, the
structural organization of the CA dynamics is uncovered.
1 Introduction
Cellular Automata (CA) are fully discrete dynamical systems, where the states
are chosen in a finite set and distributed on a discrete grid, the time evolution
is run synchronously in all the sites of a regular lattice and each site changes
its state
s
i
(
t
) (0 or 1) according to a local rule
φ
that only depends upon its
neighbor values. Despite the simplicity of their construction CA are found to be
capable of diverse and complex behavior and are often used as a prototype for
the analysis of spontaneous emergence of ordered behavior in spatially extended
systems that are locally coupled.
As CA are governed by local interactions and subjected to noise, it was ex-
pected that any globally observable, such as the concentration of activated cells
c
(
t
)=
N
i
s
i
(
t
) would show a trivial time dependence in the limit of infinite
size [1]. But several exceptions to this have been found. The most remarkable
one is a quasiperiod three behavior (QP3) that exhibits the concentration of
rule-33 automaton in d=3 [7] and other CA in high space dimensions [3]. This
behavior is neither transient nor due to the finite size of the lattice and has
been obtained for deterministic and probabilistic rules [9]. Several attempts
have been made to understand its phenomenology and have addressed the
possible mechanisms by which this puzzling collective behavior emerges [2] but
at the moment there is not any answer to the question of how this non-trivial
collective behavior can be predicted from the local rule.
