Evolving Cellular Automata with Genetic Algorithms

8 Evolving Cellular Automata with Genetic Algorithms 

In previous sections, I have described several projects in which cellular automata are cleverly (and sometimes with considerable difficulty) hand-designed to perform computations. The work of myself and my colleagues James Crutchfield, Rajarshi Das, James Hanson, and Peter Hraber takes a different approach, that of automatically designing CAs with genetic algorithms (GAs). 

Some early work on evolving CAs with GAs was done by Packard and colleagues (Packard, 1988 Richards, Meyer, and Packard, 1990). Koza (1992) also applied genetic programming to evolve CAs for simple random-number generation. Our work builds on that of Packard (1988), described in Section 4.4. We have used a form of the GA to evolve CAs to perform two computational tasks. The first is a density-classification task (Mitchell, Hraber, and Crutchfield, 1993 Mitchell, Crutchfield, and Hraber, 1994b Crutchfield and Mitchell, 1995 and Das, Mitchell, and Crutchfield, 1994.) (Subsequent work on evolving CAs and related architectures to perform density classification was done by Sipper, 1996, and by Andre, Bennett, and Koza, 1996.) The second is a synchronization task (Das, Crutchfield, Mitchell, and Hanson, 1995). All the work described here uses one-dimensional, k = 2,r = 3 CAs with periodic boundary conditions. 

Instead, more sophisticated coordination and information transfer must be achieved. This coordination must, of course, happen in the absence of any central processor or central memory directing the coordination. 

Our version of the GA worked as follows. First, a population of 100 chromosomes was chosen at random from a distribution that was flat over the density of Is in the output bits. (This uniform distribution differs from the more commonly used unbiased distribution in which each bit in the chromosome is independently randomly chosen. We found that using a uniform distribution considerably improved the GA s performance on this task—see Mitchell, Crutchfield, and Hraber, 1994b, for details). The fitness of a rule in the population was computed by (1) randomly choosing 100 ICs that are uniformly distributed over p G [0.0,1.0], with exactly half with p Pc and half with p Pc, (2) iterating the rule on each IC until it arrives at a fixed point or for a maximum of M 2N time steps, and (3) determining 

---