Directed Search for Cellular Automata Rules

The purpose of this project is to develop a tool for discovering cellular automata (CA) rules for new computation systems, nanotechnology, and other applications.  Most people are familiar with the “Game of Life,” which is an example of a particular CA; its rich and interesting behavior stems from its computational rule, which was carefully designed by a very clever mathematician (J. H. Conway).  However, because CAs are complex, non-linear, parallel systems, it is difficult to predict their behavior mathematically, and it is difficult to work backwards from a desired behavior to a CA that will produce it.  One way to solve this problem is to use a genetic algorithm (GA), which can search efficiently for a CA rule that maximizes a fitness function, which is programmed to test for how nearly a particular CA’s behavior approaches the desired behavior.  (Classic work in this area was done by Crutchfield, Mitchell, et al.)  Unfortunately, for some very interesting problems it is difficult to program a fitness function, although humans can easily evaluate a CA’s behavior (i.e., we “know it when we see it”).  Therefore, this tool combines human selection of the best-performing CAs with the GA’s mechanism for searching the solution space of possible rules.

The program begins with two randomly-generated or user-provided CA rules (the “parents”), which it treats as “genetic strings.”  From these are generated a small number (a dozen, say) of “offspring” formed by crossover of the parents genetic strings and by random mutation.  The program runs all of these CAs (the two parents and the offspring) in parallel (from a random or user-specified initial state), displaying them like multiple Life games.  After a certain amount of time, the user picks the two CAs that best exhibit the desired behavior, and these become the “parents” of the next generation.  The user continues in this way, selecting the two best from each generation, until they obtain a CA exhibiting the desired behavior.  (If the CAs don’t seem to be converging on the desired behavior, the user might have to start over with different first parents.)  In effect, the tool is an abstract model of the selective breeding of plants or animals (think of dog breeder developing a new breed or a horticulturist breeding a new rose).

The program will have a number of other utility features, including the ability to save CA rules to a file or to reload them, to control the number of offspring and other parameters (e.g., mutation rate, crossover probability), to start, stop, and rerun simulations, etc.

For more information on this project, please send me mail or make an appointment to discuss it.

Return to MacLennan's home page

Send mail to Bruce MacLennan /

Valid HTML 4.01!This page is
Last updated: 2007-05-22.