Information Technology Reference
In-Depth Information
Remark2.
One of the main problems for introducing a control term is how to
combine
u
with
F
in order to have a well-defined global CA function. Another
problem concerns the definition of a suitable topology for these models. In this
context, additive CA's defined on a finite state set with a group structure form
an interesting class in which topological properties have been widely explored
by many authors.
It should be finally stressed that formula (8) is not the only way to introduce
control, it may be expressed by various forms of disturbance of the CA's dynam-
ics.
4.2RegionalControllabilityProblem
For an initial configuration
s
0
, the configuration at time
T
is obtained by
s
T
=
F
T
u
(
s
0
). Let
s
d
be a given desired configuration defined on a subregion
ω
of
L
.
Let
d
be a distance defined on the configuration space
S
L
by :
∀
(
s
1
,s
2
)
∈S
L
×S
L
d
(
s
1
,s
2
)=card
{c∈L|s
1
(
c
)
'
=
s
2
(
c
)
}
(9)
It is easy to verify that (9) is a well defined distance on
S
L
.
Definition3.
TheCAAissaidtoberegionallycontrollablefors
d
∈S
ω
if
thereexistsacontroluinanappropriateway((8)forinstance)suchthat
s
T
=
s
d
onω
(10)
To solve this problem by a theoretical approach is still very hard owing to the
fully discrete nature of the CA's models. One of their main deficiencies is the lack
of structural spaces. This work is intended to be an attempt to formulate and
solve numerically the regional controllability problem using genetic algorithms.
The first problem concerns an unknown local CA dynamics which steers the
system from an appropriate initial configuration to a desired one within a finite
time
T
. The second problem is a properly control one in which we try to find
an additional term to a given local dynamics in order to achieve the same goal.
The one and two-dimensional cases are both considered and the expressions of
CA's rules and controls are obtained.
5SimulationExamples
5.1ExtractingLocalRules
Exampleof1-DCellularAutomaton.
Consider a one-dimensional CA
which consists of a lattice of cells
c
i
,
i
=1
,···,N
arranged in a line. Each cell
takes its value in a discrete set
S
=
{
0
,
1
,
2
}
. The cell states evolve synchronously
in discrete time steps according to the states of their neighbours
{c
i−
1
,c
i
,c
i
+1
}
subject to a local transition function to be determined. With
N
= 40, we consider
a subregion
ω
=
{c
11
,···,c
20
}
and a prescribed state
s
d
defined by
s
d
(
c
i
)=
