The Biological Insight
Hill climbing fails at local optima because it only ever looks at its immediate neighbors and only ever moves uphill. It commits to one path and follows it. The moment that path leads to a local peak, the search is over.
Biological evolution does not work this way. Evolution maintains a diverse population of organisms, all slightly different from one another. When two organisms reproduce, their offspring inherit a mixture of traits from both parents — plus occasional random mutations. Organisms better suited to the environment survive and reproduce more often; organisms less suited reproduce less and eventually disappear. Over many generations, the population shifts toward better and better fitness.
Crucially, evolution does not commit to a single path. It explores many parts of the fitness landscape simultaneously, through the diversity of the population. A feature that is mediocre in one organism might combine with a feature from another organism to produce something excellent in their offspring. Local optima are not traps because the population is spread across the landscape — different individuals are exploring different peaks, and crossover between them can produce offspring that reach higher ground than either parent.
Genetic algorithms formalize this biological process and apply it to optimization problems. The result is a search strategy that is slower and more complex than hill climbing, but dramatically better at exploring rugged, complex fitness landscapes.
The Vocabulary
Genetic algorithms borrow their terminology directly from biology. Understanding the vocabulary makes the algorithm much easier to follow:
- A chromosome is one candidate solution — one complete description of how the problem might be solved. In the scheduling problem, a chromosome is one specific ordering of all the subjects.
- A gene is one component of a chromosome — one piece of the solution. In a scheduling chromosome, each gene might be the subject assigned to one particular period.
- The population is the collection of all current candidate solutions — typically several dozen to several hundred chromosomes.
- The fitness function is the scoring rule that evaluates how good any given chromosome is. This is identical to the fitness function from Reading 1: it is how the algorithm knows which solutions are better.
- Selection is the process of choosing which chromosomes will serve as parents for the next generation. Better-scoring chromosomes are more likely to be selected, but lower-scoring ones are not eliminated outright — they still have a chance.
- Crossover is the process of combining two parent chromosomes to produce offspring. A common method: split each parent at a randomly chosen point and swap the segments, producing two new chromosomes that each contain parts of both parents.
- Mutation is a small random change to an offspring chromosome — flipping one gene, swapping two components, or making some other minor alteration. Mutation happens rarely and randomly, but it is essential: without it, the population can converge prematurely and lose diversity.
The Full Cycle
A genetic algorithm proceeds through these steps repeatedly:
Each pass through steps 2-6 is one generation. A genetic algorithm typically runs for hundreds or thousands of generations. With each generation, the average fitness of the population tends to increase as better solutions are preserved and combined.
Back to the Scheduling Problem
Let us see how a genetic algorithm would approach the same scheduling problem from Reading 2. Recall that hill climbing got stuck at fitness 7, missing the optimal solution [Math, Science, English, History] with fitness 10.
A genetic algorithm starts with a population of, say, eight random schedules. Let us trace two of them through one generation:
| Chromosome | Schedule | Fitness |
|---|---|---|
| Parent A | [Math, English, History, Science] | 7 |
| Parent B | [Science, Math, English, History] | 8 |
These two are selected as parents based on their fitness scores. A crossover point is chosen after position 2. The front half of Parent A combines with the back half of Parent B, and vice versa:
| Offspring | Front (from…) | Back (from…) | Result |
|---|---|---|---|
| Offspring 1 | Math, English (A) | English, History (B) | [Math, English, English, History] — invalid* |
| Offspring 2 | Science, Math (B) | History, Science (A) | [Science, Math, History, Science] — invalid* |
*Simple crossover on ordered sequences like schedules often produces invalid offspring (duplicates, missing items). Real genetic algorithms for ordering problems use a smarter crossover method that preserves validity. For our purposes, imagine the algorithm repairs the offspring: it keeps the front segment and fills the remaining positions with the subjects not yet included, in the order they appear in the other parent.
After repair: Offspring 1 becomes [Math, English, Science, History] (fitness 8). A mutation randomly swaps positions 2 and 3: [Math, Science, English, History] — fitness 10. The global optimum, discovered through crossover and mutation rather than by the hill climber's steady uphill trudge.
Why Randomness Helps
Randomness appears in genetic algorithms at three points: the initial population, the selection process (fitter chromosomes are more likely to be chosen, but it is probabilistic rather than deterministic), and mutation. Each role is distinct.
The random initial population seeds diversity across the landscape. Rather than starting from one point like hill climbing, the algorithm starts with many points spread across the solution space. Different individuals occupy different regions, including regions that might be far from any locally obvious solution.
Probabilistic selection preserves diversity. If only the top-performing chromosomes were ever selected, the population would quickly converge to a narrow region of the landscape and lose the diversity that makes crossover powerful. By giving lower-fitness chromosomes a small chance of selection, the algorithm keeps exploring.
Mutation prevents stagnation. Once the population converges, crossover alone cannot generate novelty — combining two nearly identical chromosomes produces nearly identical offspring. Mutation introduces new genetic material that was not present in either parent, allowing the algorithm to escape regions it has thoroughly explored.
Together, these three sources of randomness make genetic algorithms fundamentally different from hill climbing: they are exploratory rather than exploitative. Hill climbing exploits local information to climb quickly. Genetic algorithms balance exploitation (selecting the fittest) with exploration (maintaining diversity and introducing mutation) to search the landscape more broadly.
Where Genetic Algorithms Are Used
Genetic algorithms have been applied to an impressive range of real problems where the solution space is too large and complex for exhaustive search or hill climbing alone:
- Antenna design. NASA's ST5 spacecraft used a genetic algorithm to evolve a novel antenna shape that outperformed all human-designed alternatives. The resulting shape looked nothing like a conventional antenna but performed better by the fitness measure that mattered.
- Drug discovery. Pharmaceutical researchers use genetic algorithms to search the enormous space of possible molecular structures for candidates with desired properties — binding to a target protein, low toxicity, good bioavailability.
- Game playing and strategy. Early video game AI used genetic algorithms to evolve controller strategies. Modern game development still uses them for procedural content generation — evolving level designs, enemy behaviors, and game balance parameters.
- School and hospital scheduling. Complex scheduling problems with many constraints are a natural fit. The fitness function encodes the constraints and preferences; the genetic algorithm searches for a schedule that satisfies as many as possible.
The textbook mentions two scientific discovery systems worth knowing: BACON, which rediscovered Ohm's law, Kepler's third law, and the conservation of momentum from raw data; and AUTOCLASS, which used unsupervised clustering on infrared spectral data to discover new classes of stars that human astronomers had not previously identified. These are striking examples of AI genuinely producing new knowledge rather than just classifying known inputs.
Connecting Back: The Reinforcement Learning Family
Topic 6c introduced reinforcement learning as learning through interaction, reward, and penalty — with no labeled training data. Hill climbing and genetic algorithms both fit within this broader category:
- Neither requires labeled examples of correct solutions. There is no training set with known answers.
- Both use a fitness or reward signal to evaluate solutions and improve over time.
- Both learn through experience — by trying solutions, observing their quality, and using that feedback to generate better candidates.
They are classical optimization techniques rather than modern machine learning methods, and they do not involve the neural network machinery that most people associate with reinforcement learning today. But they embody the same fundamental principle: improve through feedback without being told explicitly what the right answer is.
In Topic 6e, we covered artificial neural networks — a supervised learning approach that is structurally different from everything we have studied so far. Where hill climbing and genetic algorithms search through a space of candidate solutions, neural networks learn by adjusting internal parameters in response to prediction errors. The mechanism is different. The ambition — to learn from experience and improve — is the same.