Preprint --- Evolving Globally Synchronized Cellular Automata

[Jim Crutchfield]

The following paper is now available on the Web and via anonymous FTP.
Access instructions follow.


             Evolving Globally Synchronized Cellular Automata

Rajarshi Das, James P. Crutchfield, Melanie Mitchell, and James E. Hanson

              Santa Fe Institute Working Paper 95-01-005

                              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.


World Wide Web URL:

     http://www.santafe.edu/projects/evca/evabstracts.html

Anonymous FTP:

    To obtain an electronic copy of this paper (12 pages):

        ftp ftp.santafe.edu
        login: anonymous
        password: <your email address>
        cd /pub/EvCA
        binary
        get EGSCA.ps.Z
        quit
 
    Then at your system:

        uncompress EGSCA.ps.Z
        lpr -P<printer-name> EGSCA.ps.Z

If you have trouble getting this paper electronically, you can request
a hard copy from Deborah Smith (drs at santafe.edu), Santa Fe Institute, 
1399 Hyde Park Road, Santa Fe, NM, USA, 87501.