The University of Sussex

A cellular automaton to embed genetic search

Pedro Paulo Balbi de Oliveira

To appear in: D.L.Stein & L.Nadel, editors. "1991 Lectures in Complex Systems". Santa Fe Institute Series in the Sciences of Complexity, Addison-Wesley, 1992. A non-deterministic cellular automaton with periodic boundary conditions, whose temporal evolution resembles an artificial-life world, is presented. This artificial-life activity takes place in a 2D-world, where worm-like organisms roam around mating, reproducing, and being selected. Since the motivation for this work has been to embed some form of genetic search in cellular automata, the automaton is described in terms of its general capabilities to act as a framework within which genetic search problems can be defined. However, it is not an aim of the paper to discuss in detail any particular application. Although the concept of search has been traditionally associated with function optimisation and with strategies for solving prespecified problems, these are not the connotations of search we mean here; rather, we refer to the process of exploring the space of possible genomes in particular universes, without any concern for optimization or preconceived evolutionary paths to be followed. Because of this, and also because the built-in selection process can be better seen as preserving the non-deleterious features of the organisms (in contrast to selecting for the most adapted ones), the nature of the evolutionary process eventually achieved should be seen as an instance of the exaptationist standpoint in evolutionary theory. The bridge between the activity of the organisms and the genetic search process is made by allowing that the main constituent of the organisms' bodies be the genomes that define the points in the search space under question. The fact that the cellular automaton relies upon only four states per cell allows for its use in a number of ways, some of which are discussed; indeed, the actual cellular automaton described is just one possible example of a large family. This flexibility opens up the possibility of the development of a new class of models to study emergence and self-organisation in evolutionary processes, mainly from the standpoint of artificial life.


This paper is not available online