文档介绍：A ic Algorithm Discovers Particle-Based
Computation in Cellular Automata
Rajarshi Das1, Melanie Mitchell1, and James P. Crutchfield2
1 Santa Fe Institute, 1660 Old Pecos Trail, Suite A, Santa Fe, New Mexico, . 87501.
2 Physics Department, University of California, Berkeley, CA, . 94720.
In Y. Davidor, H.-P. Schwefel, and R. M¨anner (editors), Parallel Problem Solving from
Nature—PPSN III. Berlin: Springer-Verlag.
Abstract. How does evolution produce sophisticated putation in systems
composed of ponents limited to local interactions? To model such a process, we
used a ic algorithm (GA) to evolve cellular automata to perform putational task
requiring globally-coordinated information processing. On most runs a class of relatively
unsophisticated strategies was evolved, but on a subset of runs a number of quite sophisti-
cated strategies was discovered. We analyze the emergent logic underlying these strategies in
terms of information processing performed by “particles” in space-time, and we describe in
detail the generational progression of the GA evolution of these strategies. Our analysis is a
preliminary step in understanding the general mechanisms by which sophisticated emergent
computational capabilities can be automatically produced in decentralized multiprocessor
systems.
1. Introduction
Natural evolution has created many systems