Melanie Mitchell, Recent Publications
13/09/94
-----------------------------------------------------
The following is a list of my recent papers related to evolving
cellular automata with genetic algorithms and to computation in
spatially extended systems:
To obtain an electronic copy of a paper:
ftp ftp.santafe.edu
login: anonymous
password:
cd /pub/Users/mm
binary
get
quit
Then at your system:
uncompress
lpr -P (without the .Z)
If you have trouble getting any of these papers electronically, you can
request a hard copy from Deborah Smith (drs@santafe.edu), Santa Fe
Institute, 1399 Hyde Park Road, Santa Fe, NM, USA, 87501.
Melanie Mitchell
mm@santafe.edu
P.S. For a complete list of my recent papers, see the README file in the
/pub/Users/mm directory.
-------------------------------------------------------------
ftp-file-name: rev-edge-part1.ps.Z
rev-edge-part2.ps.Z
rev-edge-part3.ps.Z
rev-edge-part4.ps.Z
Revisiting the Edge of Chaos:
Evolving Cellular Automata to Perform Computations
Melanie Mitchell, Peter T. Hraber, and James P. Crutchfield
Complex Systems, 7, 89--130, 1993.
(SFI-93-03-014)
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.
-------------------------------------------------------------
ftp-file-name: DynCompEdge.ps.Z
Dynamics, Computation, and the ``Edge of Chaos'': A Re-Examination
Melanie Mitchell, James P. Crutchfield, and Peter T. Hraber
To appear in G. Cowan, D. Pines, and D. Melzner (editors),
_Complexity: Metaphors, Models, and Reality_.
Santa Fe Institute Stuides in the
Sciences of Complexity, Proceedings Volume 19.
Reading, MA: Addison-Wesley.
(SFI-93-06-040)
Abstract
In this paper we review previous work and present new work
concerning the relationship between dynamical systems theory and computation.
In particular, we review work by Langton (1990) and Packard (1988) on the
relationship between dynamical behavior and computational capability in
cellular automata (CA). We present results from an experiment similar to
the one described in Packard (1988), that was cited there as evidence for
the hypothesis that rules capable of performing complex computations are most
likely to be found at a phase transition between ordered and chaotic behavioral
regimes for CA (the "edge of chaos").
Our experiment produced very different results from the original
experiment, and we suggest that the interpretation of the original results is
not correct. We conclude by discussing general issues related to dynamics,
computation, and the "edge of chaos" in cellular automata.
-------------------------------------------------------------
ftp-file-name: MechImped.part1.ps.Z
MechImped.part2.ps.Z
Evolving Cellular Automata to Perform Computations:
Mechanisms and Impediments
Melanie Mitchell James P. Crutchfield Peter T. Hraber
Santa Fe Institute UC Berkeley Santa Fe Institute
Physica D, 75, 361-391, 1994
(SFI 93-11-071)
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 search.
Note that the paper (44 pages) is broken up into two halves that must be
retrieved separately.
-------------------------------------------------------------
ftp-file-name: EvEmComp.ps.Z
The Evolution of Emergent Computation
James P. Crutchfield Melanie Mitchell
UC Berkeley Santa Fe Institute
(SFI 94-03-012)
March, 1994
Abstract
A simple evolutionary process can discover sophisticated methods
for emergent information processing in decentralized spatially-extended
systems. The mechanisms underlying the resulting emergent computation
are explicated by a novel technique for analyzing particle-based
logic embedded in pattern-forming systems. Understanding how
globally-coordinated computation can emerge in evolution is relevant
both for the scientific understanding of natural information processing
and for engineering new forms of parallel computing systems.
-------------------------------------------------------------
ftp-file-name: GA-Particle.part1.ps.Z
GA-Particle.part2.ps.Z
GA-Particle.part3.ps.Z
GA-Particle.part4.ps.Z
A Genetic Algorithm Discovers Particle-Based Computation
in Cellular Automata
Rajarshi Das Melanie Mitchell James P. Crutchfield
Santa Fe Institute Santa Fe Institute UC Berkeley
Santa Fe Institute Working Paper 94-03-015
To appear in Proceedings of the Third Parallel Problem-Solving
From Nature Conference March, 1994
(SFI 94-03-015)
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.