Information Technology Reference
In-Depth Information
0.12
0.2
0.10
0.18
0.08
0.16
λ
0.06
0.14
0.04
0.12
0.02
100
0.1
0
0
500
500
1000
generation
Fig.1.
Best fitness rule and
λ
-parameter versus generation in the run in which rule
φ
a
was discovered in generation 590. Lattice size of 32
2
cells.
In this work we use a Genetic Algorithm to evolve a population of two and
one dimensional CA. The survival of an individual CA rule is determined by
its ability to perform a “P3 task”. The goal is to find a CA that starting from
a random initial configuration reaches one in which the concentration oscillates
among three different values, i.e. the GA will select rules with P3 or QP3 col-
lective behavior.
2 The Genetic Algorithm
Our GA begins with a population of
P
= 20 randomly generated chromosomes,
listing the rule-table output bits in lexicographic order of neighborhood pat-
terns [8]. We consider binary CA with periodic boundary conditions. Each CA
is represented by a bit string delineating its rule table
φ
, containing the out-
put bits for all possible neighborhood configurations. The bit string is of size
2
7
= 128, resulting in a huge space of 2
128
possible rules. The fitness evaluation
for each CA rule is carried out on a lattice of
N
=
L
d
cells starting from a ran-
dom initial condition of concentration 0
.
5. After a transient time of
N/
2 time
steps, we allow each rule to run for a maximum number of
N/
2 iterations. The
values of concentration are assembled in groups of 4 consecutive values and the
fitness function
F
(
φ
) is defined by:
M/
4
F
(
φ
)=
4
M
1
2
abs
[(
c
2
−
c
1
)(
c
4
−
c
2
)
−
(
c
3
−
c
2
)(
c
3
−
c
1
)]
i
i
The rule's fitness
F
(
φ
) is taken from a geometrical point of view and it is an
average area in the iterative map, i.e. the graph of
c
(
t
+ 1) versus
c
(
t
). In this
iterative map the area of a period-2 behavior is too small, almost 0, the area of
a noisy period-1 and the area of an intermittent P2 is higher than that of a P2
and finally QP3 and P3 behaviors have the highest values.
