Evolving Cellular Automata to Perform Computations: Mechanisms and Impediments

Melanie Mitchell, James P. Crutchfield, and Peter T. Hraber

93-11-071

We present results from experiments in which a genetic algorithms was used to evolve cellular automata (CAs) to perform a particular computational task--one-dimensional density classification. We look in detail at the evolutionary mechanisms producing the GA’s behavior on this task and the impediments faced by the GA. In particular, we identify four “epochs of innovation” in which new CA strategies for solving the problem are discovered by the GA, describe how these strategies are implemented in CA rule tables, and identify the GA mechanisms underlying their discovery. The epochs are characterized by a breaking of the task’s symmetries on the part of the GA. The symmetry breaking results in a short-term fitness gain but ultimately prevents the discovery of the most highly fit strategies. We discuss the extent to which symmetry breaking and other impediments are general phenomena in any GA search.