Sponsor
This research was supported by the Santa Fe Institute, under the Adaptive Computation and External Faculty Programs (supported by ONR grant N00014-95-1-0975) and under NSF grant IRI-9320200 and DOE grant DE-FG03-94ER25231. It was supported by the University of California, Berkeley, under ONR grant N00014-95-1-0524.
Published In
Proceedings of the Conference on Physics and Computation---PhysComp96
Document Type
Conference Proceeding
Publication Date
1996
Subjects
Genetic algorithms, Computational complexity, Cellular automata -- Evolution
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 [3].
In previous work [4, 5], 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 [2, 6], 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.
Persistent Identifier
http://archives.pdx.edu/ds/psu/12303
Citation Details
Hordijk, W., Crutchfield, J. P., and Mitchell, M. (1996). "Embedded particle computation in evolved cellular automata." Santa Fe Institute, Santa Fe, NM.
Description
Paper presented at the Conference on Physics and Computation---PhysComp96, Boston, MA. and subsequently included in its proceedings..