Title: Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work

Title: Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work

Reference: Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96), Russian Academy of Sciences, 1996.

SFI working paper:

LANL archive:

Abstract: We review recent work done by our group on applying 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 interactions between particles effects information processing. This framework can also be used to explain the process by which the strategies were designed by the GA. The work described here is a first step in employing GAs to engineer useful emergent computation in decentralized multi-processor systems. It is also a first step in understanding how an evolutionary process can produce complex systems with sophisticated collective computational abilities.

Title: The Evolutionary Design of Collective Computation in Cellular Automata

Reference:Machine Learning Journal. Submitted.

SFI working paper: 98-09-080

LANL archive: adap-org/9809001

Abstract: We investigate the ability of a genetic algorithm to design cellular automata that perform computations. The computational strategies of the resulting cellular automata can be understood using a framework in which ``particles'' embedded in space-time configurations carry information and interactions between particles effect information processing. This structural analysis can also be used to explain the evolutionary process by which the strategies were designed by the genetic algorithm. More generally, our goals are to understand how machine-learning processes can design complex decentralized systems with sophisticated collective computational abilities and to develop rigorous frameworks for understanding how the resulting dynamical systems perform computation.

Fonte: http://www.santafe.edu/~shalizi/notebooks/cellular-automata.html

• Serial and Parallel Genetic Algorithms as Function Optimizers - Gordon, Whitley (1993)  

• Evolving Globally Synchronized Cellular Automata - Rajarshi Das (1995)  

• Discovery of Rewrite Rules in Lindenmayer Systems and State.. - Koza (1993)  

9.2) Autômatos Celulares e Redes Neurais

The genotype-phenotype relation for the 256 elementary cellular automata is studied using neural networks. Neural network are trained to learn the mapping from each genotype rule to its corresponding Li-Packard phenotype class. By investigating learning curves and networks pruned with Optimal Brain Damage on all 256 rules, we find that there is a correspondence between the complexity of the phenotype class and the complexity (net size needed and test error) of the net trained on the class. For Li-Packard Class A (null rules) it is possible to extract a simple logical relation from the pruned network. The observation that some rules are harder for the networks to classify leads to an investigation of rule 73 and its conjugate rule 109. Experiments reveal 3-cycles in magnetization in agreement with observations in higher dimensional cellular automata system.

Cellular Automata (CA) are dynamical system discrete in space, time, and state variables, and characterized by possession of exclusively local mechanisms of interaction. They constitute good models for the study of non-linear complex systems and Artificial Life systems, the Navier-Stokes equation of hydrodynamics, random number generators and speculative models of everything, i.e., the whole universe being modeled in the form of one single cellular automaton. The popularity of CA stems from their simplicity and transparency in definition; being discrete in all respects they are well suited for computer experiments. But in spite of the simplicity in definition, the set of CA (e.g., the set of one-dimensional CA) contains many rules with very complicated behavior.

It is of interest to characterize, within the set of all CA rules, the location of rules with a certain behavior. The set of rules of a certain behavior- for example, chaotic, constitutes a subset in the set of all CA rules. This subset usually presents a rather non-trivial structure. One way to characterize the structure is through neural networks.

The 256 elementary CAs provide an extremely simple example of a CA system, but there are still a number of unsolved problems. Using neural networks, we study the relation between the genotypes that correspond to the same phenotype class. For each phenotype a network learns to divide the 256 CA rules into two categories: the ones that belong to the phenotype, and the ones that do not. This application of neural networks leads to a further investigation of individual rules and phenotype classes using mean field theory.