Evolution: Natural Selection on the Grid
In May 2003, a paper appeared in Nature that drew a sharp line between what evolutionary theory could prove and what it could only assert.
The question was one of the oldest in biology: can natural selection produce genuinely complex features — the kind that require multiple coordinated mutations and cannot arise in a single step? Critics of Darwinian gradualism had long argued that complex biological structures were too improbable to emerge through random variation filtered by selection. Proponents of gradualism replied that the mathematics worked, given enough time. Both sides were largely arguing from principle.
Richard Lenski, Charles Ofria, Robert Pennock, and Christoph Adami settled the argument in a grid. Using Avida, a digital evolution platform they had developed at Caltech, they ran populations of self-replicating computer programs through millions of generations and watched a complex function — the ability to execute a specific logical operation requiring nine distinct genomic steps — evolve from scratch. They then ran a control population in which the intermediate steps conferred no fitness benefit. The complex function never evolved. The conclusion was direct: complex features emerge through a sequence of simpler features, each of which must be selectively useful on its own. Complexity is not mysterious; it is accumulated gradualism, and you can watch it happen.
The significance of this result extends beyond biology. It means that evolution — the most powerful known process for generating functional complexity — is, at its core, a cellular automaton.
Fitness as a Local Rule
In classical population genetics, fitness is a number assigned to a genotype. The fitness landscape — a concept introduced by Sewall Wright in 1932 — maps each possible genotype to a fitness value and asks how populations move through this abstract space under selection and mutation.
The model is powerful but globally defined: every genotype has a fitness value regardless of where the organism is or who its neighbors are. Real evolution is not like this. A predator’s fitness depends on whether prey are nearby. A plant’s fitness depends on the density of competing plants around it. Pathogen fitness depends on the local density and immune history of hosts. Fitness is relational and spatial.
This is the structure of a cellular automaton. In a CA model of evolution, the “fitness” of a cell-organism is a function of its local neighborhood: which types of organisms occupy nearby cells, how many, and in what pattern. The birth and survival rules — the B/S parameters in Life-like notation — are the fitness function. A cell is born if the local conditions for reproduction are met; it survives if the local conditions for persistence are met. The population dynamics that emerge from these rules are the evolutionary dynamics of the system.
This mapping has a specific consequence: spatial structure matters. In a well-mixed population (the classical assumption of most evolutionary models), every organism interacts with every other organism with equal probability. In a spatial CA, organisms interact only with their spatial neighbors. These two assumptions predict different evolutionary outcomes, and the differences are not subtle.
The Tierra System: Evolution in a Digital Biosphere
Thomas S. Ray, an ecologist at the University of Oklahoma, built Tierra in 1991 not as a simulation of biology but as a digital instantiation of it. His insight was radical: he would not write organisms that evolved. He would create the conditions under which evolution would occur and let organisms emerge.
Tierra is a virtual computer — a custom virtual machine with its own instruction set — inside which self-replicating machine-code programs compete for two resources: memory (space) and CPU time (energy). Ray wrote a single ancestral organism, 80 instructions long, capable of copying itself into adjacent memory. Then he let it run.
Within a few thousand generations, the descendants of that 80-instruction ancestor had produced parasites: shorter programs that could not copy themselves but hijacked the copying machinery of their hosts. The hosts then evolved resistance. The parasites evolved counter-resistance. Hyperparasites emerged — programs that could turn the parasites’ own hijacking mechanism against them. Ray had not programmed any of this. He had set up initial conditions, imposed resource constraints, and allowed mutation; the rest was evolution.
The connection to Conway’s Life is more than analogy. Tierra is a CA in the sense that all meaningful processing is local: each instruction in a Tierra organism modifies only local state, and the “interaction” between organisms is mediated through the adjacency of memory locations. The emergent ecology — parasites, hyperparasites, coevolutionary arms races — is a consequence of local rules propagating through a structured space, exactly as Life’s gliders and eaters are consequences of four birth-and-survival rules propagating through a grid.
Ray’s result established a principle that has guided artificial life research ever since: if you want complex behavior to evolve, build the environment, not the organisms.
Avida: Putting Evolution Under the Microscope
Avida, developed at Caltech in 1993 by Christoph Adami, Charles Ofria, and C. Titus Brown, took Ray’s insight and added scientific instrumentation. Where Tierra was designed to let evolution run and observe what happened, Avida was designed to let evolution run and measure it.
An Avida organism is a self-replicating program, like Tierra’s, but Avida adds a precise fitness function: programs earn CPU cycles (the currency of reproduction speed) by executing specific logical operations on input numbers. Simple operations — copying a bit, flipping a bit — earn small rewards. Complex operations — the logical EQU function, which requires correctly implementing nine interacting steps — earn large rewards. This creates a defined fitness landscape on which the researchers can watch populations navigate.
The 2003 Lenski et al. result, published as “The evolutionary origin of complex features” in Nature 423:139–145, used this framework to address the irreducible complexity argument directly. They found that complex logical functions evolved repeatedly when intermediate steps were rewarded, but essentially never when they were not. More remarkably, they found that mutations that were deleterious when they first appeared sometimes served as stepping-stones — they reduced fitness in the short term but enabled complex functions to evolve later. This is something that is nearly impossible to observe in natural populations over human timescales; in Avida, it was a routine experimental result.
The CA connection is precise: each Avida organism occupies a location in a spatial grid, reproduces into adjacent locations, and interacts primarily with its spatial neighbors for resources. The spatial structure is not incidental — it is what makes Avida an evolutionary model rather than a genetic algorithm, because spatial structure creates the local competition and local coevolution that drives Darwinian dynamics.
Coevolution on the Grid: The Red Queen in a CA
One of the most important phenomena in evolutionary biology is coevolution — the mutual evolutionary response of interacting species to each other. The most dramatic form is the Red Queen dynamic: hosts and parasites (or predators and prey) evolve adaptations and counter-adaptations in a cycle that never stabilizes, each side perpetually running to stay in place.
In well-mixed models of coevolution, the Red Queen tends to produce cycling dynamics: parasite frequency rises, host resistance spreads, parasite fitness drops, and the cycle repeats. This is what classical mathematical models predict.
Spatial CA models predict something different. In a spatial coevolution model — where hosts and parasites interact only locally and offspring disperse locally — the dynamics produce traveling waves. Waves of parasite adaptation sweep through the host population spatially, not temporally. A region of space that has just been hit by a wave of parasites evolves rapid resistance; by the time the next wave arrives, resistance has spread to neighboring cells. The spatial structure creates refugia — pockets of susceptible hosts that persist long enough to be recolonized — and these refugia maintain the evolutionary cycle rather than allowing either side to win.
This spatial version of the Red Queen, studied in CA models by researchers including Paulien Hogeweg and colleagues, produces richer and more stable coevolutionary dynamics than the well-mixed versions. The result is not merely academic: it may explain why sexual reproduction — which the Red Queen hypothesis was originally invoked to explain — is maintained in spatially structured natural populations even when asexual reproduction is more efficient in isolation.
Evolutionary Computation: Evolving the Rules Themselves
The relationship between evolution and CA runs in both directions. CA models are used to study evolution, but evolutionary algorithms are also used to find interesting CA rules.
The space of Life-like rules contains 262,144 members. Most are boring — everything either dies immediately or immediately solidifies. Finding rules with interesting dynamics (gliders, oscillators, complex behavior) by hand is laborious. Genetic algorithms — computational methods that evolve solutions by selection and mutation — can search this space efficiently, and have been used to find rules with specific properties: rules that maximize entropy over time, rules that produce specific pattern types, rules that are maximally unpredictable.
The deeper insight from this work is about the structure of rule space itself. The interesting rules — the ones that support complex dynamics — are not scattered randomly through the 262,144-point space. They cluster near a small number of attractors, and the clusters are roughly contiguous. Rules near Conway’s Life (B3/S23) tend to produce Life-like behavior. The interesting region of rule space has a topology that evolutionary search can navigate efficiently.
This parallels a key finding from fitness landscape theory in biology: real fitness landscapes are not random but structured, with accessible routes from simple genotypes to complex ones. The ruggedness of the landscape — the density of local optima — determines how well evolution can work. Both digital evolution platforms and evolutionary searches of CA rule space suggest that, at least in the right regime, landscapes are navigable.
What Evolution in a Grid Tells Us
The larger point that emerges from fifty years of evolutionary CA modeling is not technical — it is philosophical.
Evolution was for most of its history a narrative science: it described what must have happened, given the evidence, but could not run the experiment. The fossil record told you that complex features had evolved; it could not show you how, step by step, in real time, under controlled conditions.
Tierra and Avida changed this. They made evolution an experimental science. You could now control the fitness landscape, measure mutation rates, replay evolutionary history with different starting conditions, and watch the emergence of parasites, the spread of resistance, and the accumulation of complexity at a speed that compressed geological time into hours.
The reason this works — the reason digital organisms in a grid can be genuinely evolutionary — is that Conway’s 1970 insight was right. Local rules are sufficient to produce global complexity. You do not need to encode the complexity; you need to create the conditions for complexity to evolve. The Game of Life proved this for physics. Tierra and Avida proved it for biology.
The grid is not a metaphor for evolution. It is evolution’s native habitat.