Holland’s book is the mathematical theory of evolution as computation. It proved that Darwinian selection isn’t just a biological accident — it’s an algorithm with computable guarantees on performance, extractable from biology and applicable to arbitrary optimization problems.
The genetic algorithm
The GA is deliberately minimal: a population of bit strings (candidate solutions) evolves through three operators:
- Selection: copy strings with probability proportional to fitness
- Crossover: pair two strings, cut both at the same random point, swap the halves
- Mutation: flip each bit with small probability p_m
That’s it. No gradient information, no second derivatives, no domain knowledge beyond the fitness function. The question is: why does this work?
The schema theorem — why GAs aren’t random search
A schema is a template over bit strings: 1##0##1 specifies the first, fourth, and seventh positions; # is a wildcard. Each n-bit string matches 2^k schemata (one for each subset of positions). A population of m strings therefore implicitly represents O(m·2^n) schemata simultaneously.
Holland’s theorem: the expected number of instances of schema H in generation t+1 is:
m(H, t+1) ≥ m(H, t) · f(H)/f̄ · [1 - p_c·δ(H)/(n-1) - o(H)·p_m]
Where:
f(H)/f̄= schema’s fitness relative to population average (selection)p_c·δ(H)/(n-1)= probability crossover disrupts H (lower for compact schemata)o(H)·p_m= probability mutation disrupts H (lower for low-order schemata)
Short, compact, above-average schemata grow exponentially. This is the building block hypothesis: GAs work by discovering short high-fitness building blocks and combining them into increasingly fit solutions.
The implicit parallelism insight
The practical consequence is combinatorial leverage. While explicitly testing m strings per generation, the GA is effectively evaluating O(m^3) schemata (Holland’s “implicit parallelism” estimate). This is the mathematical argument that GAs exploit structure in fitness landscapes that local search (hill climbing, simulated annealing) cannot.
Connection to evolution and ALife
Holland’s formalism strips evolution down to its computational essence: variation + selection + heredity. The biological substrate (DNA, proteins, cells) is irrelevant to this abstraction. This is the foundational move of artificial life: if evolution is substrate-independent, then it can run in silicon. Ray’s Tierra (ray-1992-an-approach-to-the-synthesis) is the direct experimental test.
The GA also connects to reinforcement learning: Holland’s classifier systems (rule sets evolved by GAs) used a “bucket brigade” credit assignment algorithm that anticipates Q-learning (watkins-1992-q-learning). The credit assignment problem — how to assign blame/credit to past actions for delayed rewards — appears in both fields.
Limits
The schema theorem is a lower bound, not a complete explanation. The no free lunch theorem (1997) established that no algorithm beats random search averaged over all fitness landscapes — GAs’ advantage is specific to landscapes with exploitable, compositional structure. When the building blocks don’t combine well (high epistasis), GAs struggle. Real fitness landscapes are usually somewhere between these extremes.