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 / MacLennan@utk.edu This
page is www.cs.utk.edu/~mclennan/RO/DSCAR.html