EVOLVING CELLULAR-AUTOMATA TO PERFORM COMPUTATIONS - MECHANISMS AND IMPEDIMENTS

We present results from experiments in which a genetic algorithm (GA) was used to evolve cellular automata (CAs) to perform a particular com putational task - one-dimensional density classification. We look in d etail at the evolutionary mechanisms producing the GA's behavior on th is task and the impediments faced by the GA. In particular, we identif y four ''epochs of innovation'' in which new CA strategies for solving the problem are discovered by the GA, describe how these strategies a re implemented in CA rule tables, and identify the GA mechanisms under lying their discovery. The epochs are characterized by a breaking of t he task's symmetries on the part of the GA. The symmetry breaking resu lts in a short-term fitness gain but ultimately prevents the discovery of the most highly fit strategies. We discuss the extent to which sym metry breaking and other impediments are general phenomena in any GA s earch.