Information Technology Reference
In-Depth Information
Table 1.
The best evolved rules, the rule table hexadecimal code, the type of
non-trivial collective behavior and the Langton's parameter. To recover the 128-
bit string giving the output bits of the rule table, expand each hexadecimal digit
to binary. The output bits are then given in lexicographic order. The arrangement
of neighbors for
φ
a
is
|s
i,j
|s
i
−
3
,j
|s
i
+3
,j
|s
i,j
−
2
|s
i,j
+2
|s
i
−
2
,j
|s
i
+2
,j
|
, while for
φ
b
is
|s
i,j
|s
i
−
3
,j
|s
i
+3
,j
|s
i,j
−
1
|s
i,j
+1
|s
i
−
2
,j
|s
i
+2
,j
|
.In
d
= 1 the arrangement of neighbors is
|s
i
−
3
|s
i
−
2
|s
i
−
1
|s
i
|s
i
+1
|s
i
+2
|s
i
+3
|
.
Symbol Rule Table Hexadecimal Code
NTCB
λ
φ
a
10000008-1004000a-10000048-108e0c43
QP3
0.148
d
=2
φ
b
10000008-1000000a-100000cc-10860cc3
QP3
0.156
φ
a
21088418-01091108-41038844-10c18080
P3
0.211
φ
b
ffbe84bc-10874438-c6a08204-9d1b800b
P3
0.414
d
=1
φ
c
146157d1-fbb53fec-7dfbeffc-eaf0fa28 QP3(P3) 0.625
φ
d
f193800-c06b0eb0-e000461c-80659c11
P3
0.336
In each generation: (i)
F
(
φ
) is calculated for each rule
φ
in the population.
(ii) The population is ranked in order of fitness. (iii) A number
E
=5of
the highest fitness (“elite”) rules is copied without modification to the next
generation. (iv) The remaining
P
−
E
= 15 rules for the next generation
are formed by single-point crossover between randomly chosen pairs of elite
rules. The offsprings from each crossover are each mutated with a probability
m
=0
.
05. This defines one generation of the GA; it is repeated
G
=10
3
times
for one run of the GA.
3 Results
We performed more than 500 different runs of the GA each with a different
random-number seed. The dynamics of a typical run is shown in Figure 1 which
plots the fittest rule of each generation and the Langton's parameter
λ
which
is the fraction of 1s in the rule table. Though the study of the generational
progression of the GA can give important information about the design of specific
CA rules, here we focus mainly on the behavior of the last evolved rule. Table
1 shows the best evolved rules in
d
= 2 and
d
= 1, the rule table hexadecimal
code, the kind of collective behavior observed and the
λ
parameter.
3.1
Experiments in d=2
In most runs the GA ends up with rules that show a noisy P1 or a P4 collective
behavior, but in a few cases the GA is able to detect some rules with a QP3
collective behavior. Figure 2 shows the iterative map of the fittest rule in the run
in which
φ
a
was found. In the initial generations, Figure 2a-b, the GA detects
a rule with a cloudy P1 behavior. At generation 253 ( Figure 2c ) the GA finds
a rule for which its iterative map shows a dense triangular object. Finally at
