Information Technology Reference
In-Depth Information
(Coevolution 1 and Coevolution 2 ) significantly better than all the previous rules.
Their performances are also shown in Table 4.18.
Cellular automata (CA) have been studied widely as they are idealized
versions of massively parallel, decentralized computing systems capable of
emergent behaviors (for overviews of CA theory and applications see, e.g.,
Toffoli and Margolus 1987 and Wolfram 1986). These complex behaviors
result from the simultaneous execution of simple rules at multiple local sites.
In the density-classification task, a simple rule involving a small neighborhood
and operating simultaneously in all the cells of a one-dimensional cellular
automaton, should be capable of making the CA converge into a state of all
1's if the initial configuration (IC) has a higher density of 1's, or into a state
of all 0's if the IC has a higher density of 0's.
4.4.1 The Density-classification Task
The simplest CA is a wrap-around array of N binary-state cells, where each
cell is connected to r neighbors from both sides. The state of each cell is
updated by a defined rule. The rule is applied simultaneously in all the cells,
and the process is iterated for t time steps.
In the most frequently studied version of this problem, N= 149 and the
neighborhood is 7 (the central cell is represented by “u”; the r = 3 cells to the
left are represented by “c”, “b”, and “a”; the r = 3 cells to the right are
represented by “1”, “2”, and “3”). Figure 4.11 shows a CA with N = 11 in
which the updated state for the cellular automaton “u” is shown.
c
b
a
u
12 3
000
t = 0
11
0
1
0
1
1
1
t = 1
1
Figure 4.11. A one-dimensional, binary-state, r = 3 cellular automaton with N = 11.
The arrows represent the periodic boundary conditions. The updated state is shown
only for the central cell.
The task of density-classification consists of correctly determining whether
ICs contain a majority of 1's or a majority of 0's, by making the system
converge, respectively, to an all 1's state (black or “on” cells in a space-time
diagram), or to a state of all 0's (white or “off” cells). As the density of an IC
Search WWH ::




Custom Search