Holland's Genetic Algorithm

A search and optimisation method inspired by Darwinian evolution. Populations of candidate solutions compete, recombine, and mutate across generations — discovering structure in complex search spaces that purely random or greedy methods cannot navigate.

"The power of a genetic algorithm comes from crossover, not mutation." — John Holland

1. Introduction

In 1975, cognitive scientist and computer scientist John Henry Holland published Adaptation in Natural and Artificial Systems, introducing the Genetic Algorithm (GA) as a rigorous framework for understanding and engineering adaptive behaviour. Holland's goal was not merely to solve optimisation problems — he wanted to understand the abstract mechanisms underlying adaptation in any complex system, from immune cells to economies.

The core insight is that biological evolution is an extraordinarily effective search algorithm. Natural selection, recombination, and mutation have been exploring the space of possible proteins, body plans, and behaviours for 3.8 billion years. Holland asked: can we bottle that process and apply it to engineering problems?

Connections to other complex systems

Like Kauffman NK networks and the logistic map, genetic algorithms live at the boundary between order and chaos. Too much selection pressure → the population converges prematurely (ordered). Too much mutation → random walk (chaotic). The best performance sits at a critical balance — exploration vs exploitation.

2. The Biological Analogy

Biology	Genetic Algorithm
Organism / individual	Candidate solution (chromosome)
Gene	Single variable or bit position
Allele	Value at a gene position (0 or 1)
Genotype	Encoded chromosome (bit string)
Phenotype	Decoded solution (real number, schedule, etc.)
Population	Set of candidate solutions
Fitness	Objective function value — quality of solution
Natural selection	Fitness-proportionate or tournament selection
Sexual recombination	Crossover: exchanging segments between two parents
Point mutation	Random bit flip
Generation	One full cycle of selection → crossover → mutation

The analogy is deliberate and tight. Holland was influenced by geneticist R.A. Fisher's Fundamental Theorem of Natural Selection and sought a computational equivalent that could be proven theoretically — which led to the Schema Theorem (see §7).

3. Binary Encoding

The Chromosome

Holland's original GA encodes candidate solutions as fixed-length binary strings. A chromosome of length L can represent 2^L distinct values. To search for a real number x in [0, 1], decode the L-bit binary string as an integer and divide by 2^L − 1:

x = (b₀·2^L-1 + b₁·2^L-2 + … + b_L-1·2⁰) / (2^L − 1)

Example: L = 8 chromosome 10110100 decodes to 180 / 255 ≈ 0.706.

Chromosome

10 11 01 00

→ x ≈ 0.706

Why Binary?

Holland chose binary encoding for a theoretical reason: it maximises the number of schemata (templates) implicit in each chromosome — a key factor in the Schema Theorem. A chromosome of length L simultaneously represents 3^L schemata (each position is 0, 1, or * wildcard). Longer chromosomes = finer resolution and more implicit parallelism.

Implicit parallelism

A population of n chromosomes processes an estimated O(n³) schemata simultaneously. Holland called this implicit parallelism — the GA's most powerful property, and the source of its efficiency.

4. The Algorithm

1. Initialise   Generate a random population of n chromosomes
2. Evaluate    Compute fitness f(i) for each chromosome i
3. Select      Choose parent pairs proportional to fitness
4. Crossover   Swap chromosome segments at a random cut point
5. Mutate      Flip each bit with small probability p_m
6. Replace     New population replaces the old
7. Repeat      Go to 2 until termination criterion is met

Each pass through steps 2–6 is one generation. The fitness function is the only problem-specific component — the rest of the algorithm is domain-independent. This generality is what makes GAs powerful: you only need to define what "good" means.

The fitness function is everything

The GA is only as smart as the signal it receives from the fitness function. A poorly designed fitness function — one that is flat, deceptive, or noisy — will prevent the GA from making progress regardless of other parameter choices.

5. Selection

Fitness-Proportionate Selection (Roulette Wheel)

Holland's original method assigns each individual a selection probability equal to its fitness divided by the total population fitness. Imagine a roulette wheel where each individual owns a slice proportional to its fitness — fitter individuals are selected more often, but no individual is guaranteed or excluded.

P(select i) = f(i) / Σ_j f(j)

Advantage: directly reflects Holland's Schema Theorem. Weakness: if one super-individual dominates early, it crowds out diversity — premature convergence.

Tournament Selection

Pick k individuals at random; the one with the highest fitness wins. Repeat to fill the mating pool. Larger k = stronger selection pressure. More robust than roulette wheel and widely used in practice.

Elitism

A simple but powerful addition: always copy the single best individual into the next generation unchanged. This ensures the best discovered solution is never lost. The demo uses elitism of size 1.

6. Crossover and Mutation

Single-Point Crossover

Choose a random cut point. The two children inherit complementary segments from each parent. Applied with probability p_c (typically 0.6–0.9).

Parent 1

10 10 10 10

Parent 2

01 01 01 01

Child 1

10 10 01 01

← segments swapped after cut

Child 2

01 01 10 10

Red bar = cut point. Green bits = inherited from opposite parent.

Uniform Crossover

Each bit position is inherited independently from either parent with equal probability. Higher disruption of schemata but more thorough mixing. Generally preferred for higher-dimensional problems.

Mutation

Each bit is independently flipped with a small probability p_m. Holland recommended p_m ≈ 1/L (one expected flip per chromosome). Mutation's role is to prevent permanent loss of genetic material — it is a background operator, not the primary search mechanism.

Before

10 11 01 00

After (p_m)

10 11 1 10 0

← bit 5 flipped

The mutation rate sweet spot

Too low (p_m → 0): alleles that happen to be lost from the population can never return — genetic drift leads to premature convergence. Too high (p_m → 0.5): the algorithm degrades to random search; good schemata are destroyed as fast as selection creates them. The optimal sits near 1/L.

7. The Schema Theorem

Schemata

A schema H is a template over the alphabet {0, 1, *} where * matches either 0 or 1. A chromosome of length L implicitly belongs to 2^k schemata, where k is the number of defined (non-*) positions.

Chromosome

10 11 01 00

H₁ = 1 * * 1 * * * *

1* *1 ** **

H₂ = * * * * * 1 * 0

** ** *1 *0

H₃ = * 1 * * * * 1 * ✗

*1 ** ** 1*

H₁: order=2, defining length=3 · H₂: order=2, defining length=7 · H₃: does not match this chromosome (bit 2 is 0, not 1)

Two properties of a schema determine its fate:

Order o(H): number of fixed (non-*) positions — higher order schemata are more fragile
Defining length δ(H): distance between first and last fixed position — longer schemata are more likely to be disrupted by crossover

The Theorem

Holland proved that the expected number of representatives of schema H in generation t+1 satisfies:

m(H, t+1) ≥ m(H, t) · [f̄(H) / f̄] · [1 − p_c · δ(H)/(L−1) − o(H) · p_m]

where f̄(H) is the average fitness of chromosomes matching H and f̄ is the population mean. The conclusion: short, low-order, above-average schemata receive exponentially increasing trials over generations.

The Building Block Hypothesis

Holland proposed that GAs work by identifying, amplifying and recombining building blocks — short, low-order, high-fitness schemata. Just as organisms evolve by combining successful sub-structures (eyes, limbs), GAs evolve solutions by combining successful sub-strings.

A note on the theorem's limitations

The Schema Theorem is a lower bound and does not account for "hitchhiking" (neutral bits riding on fit schemata) or the deceptive case where building blocks of locally good schemata combine to form globally poor solutions. Real GA behaviour is richer than the theorem suggests.

8. Live Demo

The GA below evolves a population of binary chromosomes to maximise the chosen fitness function. Watch the population converge on peaks of the fitness landscape while mutation maintains diversity.

Population 40

Chr. length 16

Mutation 0.020

Crossover 0.80

Gen 0 Best — Avg — Diversity — Best x —

Fitness landscape — population as dots

Population chromosomes (sorted by fitness, best at top)

Evolution — best fitness (orange) and average fitness (blue) per generation

9. Parameters and Tuning

Parameter	Typical range	Too low	Too high
Population size n	30–200	Poor diversity, early convergence, high variance	Slow per-generation progress; diminishing returns
Chromosome length L	Depends on precision needed	Coarse solution space, limited search	Large schema space slows convergence; harder to evolve
Crossover rate p_c	0.6–0.9	Insufficient recombination; slow mixing	Good building blocks destroyed too quickly
Mutation rate p_m	1/L – 0.05	Lost alleles never recovered; premature convergence	Random walk; schemata cannot stabilise

The Exploration–Exploitation Trade-off

Every adaptive system faces this tension: exploit known good solutions (converge) vs explore unseen parts of the space (diversify). In a GA:

High selection pressure, low mutation → exploitation dominates → premature convergence
Low selection pressure, high mutation → exploration dominates → random walk
The optimal balance changes over time — early exploration, later exploitation — which is why some advanced GAs use adaptive parameter control

Population Diversity

When most chromosomes become identical, crossover produces only copies of the same individual — no new search. Diversity can be measured as the fraction of unique chromosomes or the average Hamming distance between pairs. The demo shows diversity live; watch it collapse under high selection pressure and recover under high mutation.

10. Guided Experiments

Experiment 1 — Premature Convergence

Click Low mutation preset (p_m = 0.001). Run for ~50 generations. Watch the diversity metric plummet to near zero as all chromosomes converge to the same (possibly sub-optimal) value. The evolution chart shows best fitness plateau well below the true optimum. Now click Default and compare — mutation at 0.02 allows continual exploration.

Experiment 2 — Mutation as Random Walk

Click High mutation (p_m = 0.15, about 2–3 flips per chromosome per generation). The population never converges; the average fitness oscillates wildly. The best fitness found is lower than with default settings because good schemata are destroyed as fast as selection builds them. This is the chaotic end of the GA parameter space.

Experiment 3 — Crossover vs Mutation Alone

Click No crossover (p_c = 0.0). The GA now operates purely by selection and mutation — essentially a parallel hillclimber. Compare convergence speed and final quality against the default. Holland's thesis was that crossover, not mutation, drives the GA's power; this experiment tests that claim directly.

Experiment 4 — Population Size and Diversity

Try Tiny population (n = 10) and then Large population (n = 80), running each to 100 generations. With n = 10, high variance means you sometimes find the optimum quickly (lucky) but often get stuck. With n = 80, progress is steadier. Notice that large population runs are slower per generation but more reliable overall.

Experiment 5 — Needle in a Haystack

Click the Needle in haystack preset. The fitness function is almost zero everywhere except for a tiny spike near x ≈ 0.73. Selection pressure is nearly useless because almost all chromosomes have equal (near-zero) fitness. The GA effectively random-walks until mutation or lucky crossover hits the needle. Watch how long it takes compared to the multimodal function — flat fitness landscapes defeat GAs.

Experiment 6 — OneMax: Pure Building Blocks

Click the OneMax preset. Every 1-bit contributes equally to fitness — there are no interactions between positions. This is the easiest possible problem for a GA because every schema of all-1 bits is a perfect building block. The population should reach close to maximum fitness (all 1s) within 20–40 generations, demonstrating the Schema Theorem's exponential growth of above-average schemata.

Experiment 7 — Long Chromosomes and Resolution

On the multimodal function, increase chromosome length from 8 to 24 using the slider. Longer chromosomes give finer resolution (more peaks become distinguishable) but take more generations to converge because the schema space is much larger. The best fitness ceiling rises, but early generations make slower progress.

Experiment 8 — Watching Schema Growth

On the default multimodal setup, pause after 5 generations and examine the population grid carefully. Notice that most chromosomes in the top half share common bit patterns (building blocks) that are absent in the bottom half. These are the above-average schemata Holland predicted would proliferate. Continue stepping slowly and watch those shared patterns spread through the whole population.

Holland's Genetic Algorithm

1. Introduction

2. The Biological Analogy

3. Binary Encoding

The Chromosome

Why Binary?

4. The Algorithm

5. Selection

Fitness-Proportionate Selection (Roulette Wheel)

Tournament Selection

Elitism

6. Crossover and Mutation

Single-Point Crossover

Uniform Crossover

Mutation

7. The Schema Theorem

Schemata

The Theorem

The Building Block Hypothesis

8. Live Demo

9. Parameters and Tuning

The Exploration–Exploitation Trade-off

Population Diversity

10. Guided Experiments

Experiment 1 — Premature Convergence

Experiment 2 — Mutation as Random Walk

Experiment 3 — Crossover vs Mutation Alone

Experiment 4 — Population Size and Diversity

Experiment 5 — Needle in a Haystack

Experiment 6 — OneMax: Pure Building Blocks

Experiment 7 — Long Chromosomes and Resolution

Experiment 8 — Watching Schema Growth

Further Reading