SFI Working Paper Abstract
1994
| Title: | A Genetic Algorithm Discovers Particle-Based Computation in Cellular Automata |
| Author(s): | Rajarshi Das, Melanie Mitchell, and James P. Crutchfield |
| Files: | [pdf] |
| Paper #: | 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 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. |