Title:
   Embedded-Particle Computation in Evolved Cellular Automata

Author(s):
   Wim Hordijk, James P. Crutchfield, and Melanie Mitchell

Reference:
   PhysComp96, T. Toffoli, M. Biafore, and J. Leao (eds.), New England Complex Systems Institute, pp. 153-158, 1996

Abstract:
   In our work we are studying how genetic algorithms (GAs) can evolve cellular automata (CAs) to perform computations that require global coordination. The ``evolving cellular automata'' framework is an idealized means for studying how evolution (natural or computational) can create systems that perform emergent computation, in which the actions of simple components with local information and communication give rise to coordinated global information processing.

   In previous work, we analyzed the process by which a genetic algorithm designed CAs to perform particular tasks. In this paper we focus on how these CAs implement the emergent computational strategies for performing a task. In particular, we develop a class of embedded-particle models to describe the computational strategies implemented by particular CAs. To do this, we use the computational mechanics framework of Crutchfield and Hanson, in which a CA's information processing is described in terms of regular domains, embedded particles, and their interactions. We then evaluate this class of models by comparing their computational performance to that of the CAs they model. The results demonstrate, via a generally close quantitative agreement between the CAs and the embedded particle models, that this new model class captures the significant functional features in the CAs' space-time behavior that underlie the CAs' computational capability and evolutionary fitness.

Download:
   PostScript (gzip'ed; 87K)
   PDF (190K)

Other URLs:
   SFI working paper 96-08-073