Information Technology Reference
In-Depth Information
controllability based on genetic algorithms which have been successfully used
for both uniform and non-uniform CA's [18]. We consider first the problem of
finding a CA rule which performs the task consisting on steering the system at
a given time
T
to a desired configuration on a subregion of the domain. The
exhibited evolution of such CA's rules is given for both one and two dimensional
examples. The control problem is considered then and formulated such an ad-
ditional term which excites a given local CA dynamics. In both cases, explicite
forms of rules and controls are given.
The paper is organized as follows: first, we recall some basic definitions re-
garding CA's and their relation to systems theory. In the third section, we give
some ideas on genetic algorithms. The fourth section states the regional con-
trollability problem by means of CA's models. In the fifth one, we give various
illustrative examples in one and two dimensions. We finish with some concluding
remarks and comments.
2CellularAutomataDefinitions
2.1Introduction
CA's are simple mathematical models which provide a powerful and interesting
tool for describing complex space-time phenomena. They are discrete dynamical
systems which are often delineated as a counterpart to partial differential equa-
tions, as they also demonstrate the capability to describe continuous distributed
dynamic systems. Since their introduction in the late of 1940s by Stanislas Ulam
and the work of John von Neumann (1966), many other scientists have applied
CA's approach to a wide range of problems. We can cite John Horton Conway
(1970) with his famous game of life which constitutes a very good example in
computer science, Stephen Wolfram (1980) who gave a classification of CA's and
developed a very good study establishing that CA's evolution may reproduce be-
haviours of many continuous systems. In recent years, CA's have already become
a very popular tool for simulating the behaviour of complex physical processes
see e.g. [3, 19, 22].
2.2CellularAutomataArchitectureandDynamics
CA's are discrete models whose behaviour is completely specified in terms of
simple local relations. They are constructed as follows: time is discrete and pro-
gresses in steps. A D-dimensional infinite space is partitioned into discrete ele-
ments (the CA's lattice
L
) according to a given geometry. Boundary conditions
can be set to define a finite lattice. Each cell or small region of space takes a
value in a discrete finite state set
S
and updates itself independently basing its
new state on the states and location of a set of cells (the neighbourhood), usu-
ally formed by its immediate surrounding. The neighbourhood of size
n
may be
defined as a mapping
N
:
L−→L
n
where
N
(
c
)=
{c
1
,c
2
,...,c
n
}
. The local dy-
namics can be given in several ways. It is usually expressed as a function which
specifies the transition rule and defined by
