paper available

[Melanie Mitchell]

The following paper (available via anonymous ftp) may be of interest to some
on this list: 

		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  

	            Santa Fe Institute Working Paper 93-11-071

	     	              Submitted to Physica D
	    	                 October 18, 1993 

			  	     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.

To obtain an electronic copy of this paper:

Note that the paper (44 pages) is broken up into two halves that must be 
retrieved separately.   

	ftp ftp.santafe.edu
	login: anonymous
	password: <your email address>
	cd /pub/Users/mm
	binary
	get sfi-93-11-071.part1.ps.Z
	get sfi-93-11-071.part2.ps.Z
	quit

Then at your system:

	uncompress sfi-93-11-071.part1.ps.Z
	uncompress sfi-93-11-071.part2.ps.Z
	lpr -P<printer-name> sfi-93-11-071.part1.ps
	lpr -P<printer-name> sfi-93-11-071.part2.ps

If you cannot obtain an electronic copy, send a request for a hard copy to
dlu at santafe.edu.