Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations

Abstract

We present results from an experiment similar to one performed by Packard (1988), in which a genetic algorithm is used to evolve cellular automata (CA) to perform a particular computational task. Packard examined the frequency of evolved CA rules as a function of Langton's lambda parameter (Langton, 1990), and interpreted the results of his experiment as giving evidence for the following two hypotheses: (1) CA rules able to perform complex computations are most likely to be found near ``critical'' lambda values, which have been claimed to correlate with a phase transition between ordered and chaotic behavioral regimes for CA; (2) When CA rules are evolved to perform a complex computation, evolution will tend to select rules with lambda values close to the critical values. Our experiment produced very different results, and we suggest that the interpretation of the original results is not correct. We also review and discuss issues related to lambda, dynamical-behavior classes, and computation in CA. The main constructive results of our study are identifying the emergence and competition of computational strategies and analyzing the central role of symmetries in an evolutionary system. In particular, we demonstrate how symmetry breaking can impede the evolution toward higher computational capability.

38 pages, compressed .ps files (780Kb) available ONLY thru anonymous ftp. (Instructions available via `get 9303003' .)

Cited by in corpus (33)

• Gene Expression Programming: a New Adaptive Algorithm for Solving Problems
• A Survey of Cellular Automata: Types, Dynamics, Non-uniformity and Applications
• Computational Capabilities of Random Automata Networks for Reservoir Computing
• Chaotic Gene Regulatory Networks Can Be Robust Against Mutations and Noise
• A novel procedure for the identification of chaos in complex biological systems
• Fitness landscape of the cellular automata majority problem: View from the Olympus
• Dimension of Reservoir Computers
• Optimal Channel Efficiency in a Sensory Network
• Computation and Universality: Class IV versus Class III Cellular Automata
• Accessibility Measure for Eternal Inflation: Dynamical Criticality and Higgs Metastability
• Epidemiology Through Cellular Automata: Case of Study Avian Influenza in Indonesia
• The window at the edge of chaos in a simple model of gene interaction networks
• A self-organized model for cell-differentiation based on variations of molecular decay rates
• Discrete Dynamical Genetic Programming in XCS
• Error threshold in optimal coding, numerical criteria and classes of universalities for complexity
• Guided Self-Organization of Input-Driven Recurrent Neural Networks
• Topological field theory of dynamical systems. II
• Living on the edge of chaos: minimally nonlinear models of genetic regulatory dynamics
• Coevolving Cellular Automata with Memory for Chemical Computing: Boolean Logic Gates in the B-Z Reaction
• Computational capabilities at the edge of chaos for one dimensional system undergoing continuous transitions
• Semipredictable dynamical systems
• A comparison of evaluation methods in coevolution
• Phase transitions in swarm optimization algorithms
• A synthesis and a practical approach to complex systems
• Density classification performance and ergodicity of the Gacs-Kurdyumov-Levin cellular automaton model IV
• Examples of Synchronization in Discrete Chaotic Systems
• The conduciveness of CA-rule graphs
• Artificial life: sustainable self-replicating systems
• Simply modified GKL density classifiers that reach consensus faster
• The Search for Computational Intelligence
• Deducing Local Rules for Solving Global Tasks with Random Boolean Networks
• Finding The Sign Of A Function Value By Binary Cellular Automaton
• Symptoms of complexity in a tourism system