Information Technology Reference
In-Depth Information
1
,∀
11
≤i≤
20. Denote by
N
s
d
(
t
) the value of
d
(
s
t
,s
d
)where
s
t
is the obtained
CA configuration at time
t
. The goal is to investigate the suitable transition rule
capable of steering the system from a given initial state to a prescribed final
configuration within some number of time steps
T
. This can be formulated by
N
s
d
(
T
)=0on
ω
.
Within an arbitrary initial population of individuals (rules in this case),
we simulate for each rule the CA evolution and we keep the best fitness value
v
f
=
−N
s
d
(
t
). The implementation of the genetic algorithm provides at each
generation a rule which gives the best fitness value. The presented results are
obtained with the two following parameters : 0.6 for crossover probability and
which belongs to the interval [0
.
6
,
1] and 0.003 for mutation probability which
must be in [0
.
001
,
0
.
005]. The extracting rule has the form :
s
t
+1
(
c
i
)=[
s
t
(
c
i−
1
)
⊕
2]
⊗
[
s
t
(
c
i
)
⊕
2]
⊗
[
s
t
(
c
i
+1
)
⊕
2]
(11)
where
⊕
and
⊗
indicate addition and multiplication modulo 3, respectively.
Starting with an arbitrary initial configuration, the simulation results give the
following evolution with rule (11)
Time
w
t=12
t=9
t=6
t=3
t=0
11
w
20
Sites
Fig.1.
Evolutionofthe1-DCAruleachievingregionalcontrollabilityin
ω
at
T
=
12.Cellswithstate0,1and2arerepresentedbythewhite,grayandblackregions
respectively.
ω
isrepresentedbygraysquares.
2-DCellularAutomatonExample.
Consider a square lattice composed of
cells
c
i,j
,
i,j
=1
,···,
10 that evolve in a discrete state set
S
=
{
0
,
1
,
2
}
. The cell
state at time
t
,
s
t
(
c
i,j
) is updated according to the states of its surrounding von
Neumann neighbourhood. The subregion is given by
ω
=
{c
i,j
|
4
≤i,j≤
6
}
and the problem is to find a local rule which allows the system to reach at time
T
the configuration defined by
s
d
(
c
i,j
)=1
∀c
i,j
∈ω
. A genetic algorithm as for
1-D CA's is implemented and the obtained result gives