Sponsor
This research was supported by the Santa Fe Institute, under the Adaptive Computation and External Faculty Programs and under NSF grant IRI-9320200 and DOE grant DE-FG03-94ER25231. It was supported by the University of California, Berkeley, under the ONR Dynamical Neural Systems Program and AFOSR grant 91-0293.
Document Type
Working Paper
Publication Date
4-1995
Subjects
Genetic algorithms, Computational complexity, Cellular automata -- Evolution
Abstract
How does an evolutionary process interact with a decentralized, distributed system in order to produce globally coordinated behavior? Using a genetic algorithm (GA) to evolve cellular automata (CAs), we show that the evolution of spontaneous synchronization, one type of emergent coordination, takes advantage of the underlying medium's potential to form embedded particles. The particles, typically phase defects between synchronous regions, are designed by the evolutionary process to resolve frustrations in the global phase. We describe in detail one typical solution discovered by the GA, delineating the discovered synchronization algorithm in terms of embedded particles and their interactions. We also use the particle-level description to analyze the evolutionary sequence by which this solution was discovered. Our results have implications both for understanding emergent collective behavior in natural systems and for the automatic programming of decentralized spatially extended multiprocessor systems.
Persistent Identifier
http://archives.pdx.edu/ds/psu/12381
Citation Details
Das, Rajarshi, P. James, Melanie Mitchell, and James E. Hanson. "Evolving Globally Synchronized Cellular Automata." SFI Working Paper 1995-01-005 (1995)
Description
Santa Fe Institute Working Paper 1995-01-005. Subsequently published in Proceedings of the 6th International Conference on Genetic Algorithms, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©1995.