Fonte: http://www.santafe.edu/projects/evca/

Title: Evolving Cellular Automata to Perform Computations: Mechanisms and Impediments

Reference: Physica D, 75:361-391, 1994.

SFI working paper: 93-11-071

LANL archive:

Abstract: We present results from experiments in which a genetic algorithm was used to evolve cellular automata (CAs) to perform a particular computational task---one-dimensional density classification. We look in detail at the evolutionary mechanisms producing the GA's behavior on this task and the impediments faced by the GA. In particular, we identify four ``epochs of innovation'' in which new CA strategies for solving the problem are discovered by the GA, describe how these strategies are implemented in CA rule tables, and identify the GA mechanisms underlying their discovery. The epochs are characterized by a breaking of the task's symmetries on the part of the GA. The symmetry breaking results in a short-term fitness gain but ultimately prevents the discovery of the most highly fit strategies. We discuss the extent to which symmetry breaking and other impediments are general phenomena in any GA earch.

Title: Genetic Algorithm Discovers Particle-Based Computation in Cellular Automata

Reference: In Y. Davidor, H.-P. Schwefel, and R. Männer (eds.), Parallel Problem Solving from Nature-III, 344-353, Springer-Verlag, 1994.

SFI working paper: 94-03-015

LANL archive:

Abstract: How does evolution produce sophisticated emergent computation in systems composed of simple components limited to local interactions? To model such a process, we used a genetic algorithm (GA) to evolve cellular automata to perform a computational 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 sophisticated 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.

Title: Evolving Globally Synchronized Cellular Automata

Reference: In L. J. Eshelman (ed.), Proceedings of the Sixth International Conference on Genetic Algorithms, 336-343, Morgan Kaufmann, 1995.

SFI working paper: 95-01-005

LANL archive:

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.

Title: Evolving Cellular Automata to Perform Computations

Reference: In T. Bäck, D. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation, Oxford University Press.

SFI working paper:

LANL archive:

Abstract: We describe an application of genetic algorithms (GAs) to the design of cellular automata (CAs) that can perform computations requiring global coordination. A GA was used to evolve CAs for two computational tasks: density classification and synchronization. In both cases, the GA discovered rules that gave rise to sophisticated emergent computational strategies. These strategies can be analyzed using a ``computational mechanics'' framework in which ``particles'' carry information and interaction between particles effects information processing. This framework can also be used to explain the process by which the strategies are designed by the GA. This work is a first step in employing GAs to engineer useful emergent computation in decentralized multi-processor systems.