CI Chapter 5 — Evolutionary Computation and Genetic Algorithms.

This chapter is where Darwin becomes a computing primitive. If Chapter 1 was the big worldview chapter, Chapter 5 is the first time you can really feel the CI style under your hands. Instead of one perfectly logical solver, you get a population. Instead of a proof, you get selection pressure. Instead of one path through the search space, you get many partial attempts evolving together. It is messy, probabilistic, and weirdly elegant.

01 Why natural evolution is such a compelling optimisation metaphor

Darwin's theory of evolution by natural selection rests on three simple ingredients: variation, heredity, and selection. Members of a population vary. Some of their traits are inherited. And some variants survive and reproduce better than others. Over time, those tiny biased survival events shift the population.

Computational intelligence notices something beautiful in that story: evolution is solving an optimisation problem without ever writing down a gradient or a full global model. It does not know the final answer in advance. It does not reason symbolically about the “best species.” It just keeps a population under pressure, creates variation, preserves useful information, and lets good structure accumulate.

That makes evolution a powerful metaphor for AI because many real problems look like this: the search space is massive, the surface is rugged, the variables are mixed or discrete, and no derivative exists. In such cases, insisting on a gradient-based or exact solver can be unrealistic. Evolutionary search does not need a symbolic proof of optimality to start getting traction.

Evolutionary algorithms do not literally reproduce biology. They abstract the computational essence: populations, inherited structure, stochastic variation, biased survival, and cumulative improvement. That is enough to turn Darwin into an optimiser.

02 The evolutionary vocabulary you must not mix up

Chapter 5 introduces a cluster of biological words that become algorithmic words. The best way to survive them is to keep the computational meaning attached from the beginning.

A chromosome is the encoded form of a candidate solution. A gene is one position or component in that chromosome. An allele is the value stored at that gene position. The genotype is the encoded representation itself. The phenotype is the actual interpreted solution in the problem domain.

For example, in an 8-queens GA, the chromosome might be an 8-length vector where index \(i\) is the column and value \(x_i\) is the row position of the queen in that column. That encoded vector is the genotype. The actual board layout it represents is the phenotype. In a binary feature-selection problem, the genotype might be a 0/1 string. In a TSP solver, the genotype might be a permutation of cities.

The population is the set of candidate solutions currently alive. The fitness function is the scoring rule telling us how well a candidate performs. Better fitness usually means a better chance to become a parent or survive. And the fitness landscape is the conceptual surface where every possible candidate has a height equal to its fitness.

It helps to treat these terms as a translation dictionary: biology gives the metaphor, optimisation gives the purpose.

03 Fitness landscapes: the mental picture behind evolutionary search

The phrase fitness landscape is one of the most useful visual ideas in all of optimisation. Imagine every possible solution as a point in a landscape. The height of that point is its fitness. High peaks are good solutions. Low valleys are bad ones. Evolution is trying to move populations toward the higher regions.

Some landscapes are friendly: one broad hill, no traps, smooth improvement directions. Others are nasty: many local peaks, sharp cliffs, plateaus, ridges, noisy measurements, disconnected regions. Real-world optimisation often looks like the second kind.

Why does this picture matter? Because it explains why a population-based approach helps. A single-solution method like naive hill climbing may get stuck on the first decent hill it reaches. A population can occupy many regions simultaneously. Mutation can jump away from traps. Recombination can combine useful substructures discovered in different areas. Diversity is not an aesthetic bonus; it is a survival mechanism against premature convergence.

04 Why evolution works when gradients and exact methods fail

Gradient-based optimisation is wonderful when you have a differentiable objective, a smooth surface, and variables that live in a nice continuous space. But a lot of practical AI problems do not cooperate.

Some problems are discrete, like permutations of cities in a TSP tour. Some are multimodal, with many local optima. Some are noisy, where evaluating the same candidate twice gives slightly different results. Some are black-box, where you can score a candidate but cannot inspect the objective internally. Some are non-differentiable or combinatorial. And some have weird mixed encodings where half the variables are binary choices and half are continuous parameters.

Evolutionary algorithms are useful exactly because they are gradient free. If you can answer “how good is this candidate?” they can proceed. That is a low requirement compared with demanding analytical derivatives or exact dynamic programming structure.

That trade-off is worth understanding. Evolution trades mathematical neatness for flexibility. It often pays for that flexibility with more evaluations, stochastic behaviour, and tuning effort. But for many hard optimisation problems, that is still a very good bargain.

05 The genetic algorithm loop, end to end

The canonical GA loop is short enough to memorise and deep enough to spend a whole chapter on:

Initialisation creates the first generation. Evaluation gives every individual a fitness. Selection picks which individuals get reproductive opportunity. Crossover combines parts of parents. Mutation perturbs offspring. Replacement decides what the next generation looks like. And termination stops the process when your budget or target is met.

Each component sounds harmless until you realise every one of them changes the search dynamics. Representation changes what crossover even means. Selection changes selection pressure. Mutation rate changes whether the algorithm explores or just jitters. Replacement changes how quickly diversity disappears. That is why GAs feel simple on slides and subtle in practice.

06 Representation: the encoding quietly controls everything

The first design choice is the chromosome representation. This sounds like a data-structure question, but it is really a search-dynamics question because crossover and mutation act on the encoding.

Binary strings are the classic representation: lots of 0s and 1s, convenient for theory, mutation by bit flip, crossover by swapping substrings. But binary can be unnatural when the problem variables are really real numbers, permutations, or trees.

Integer and real-valued vectors are much more natural for parameter optimisation. If you are tuning controller gains or continuous coefficients, representing them directly as real values avoids awkward binary decoding.

Permutation encodings are essential for ordering problems such as the travelling salesman problem. Here the chromosome is an ordering of cities. Standard bit-string crossover can break validity by duplicating or omitting cities, so special operators are needed.

Tree or graph encodings appear in genetic programming, where the chromosome is itself a program structure or expression tree.

This is why people say representation is half the battle. A brilliant selection scheme cannot rescue an encoding that makes valid partial solutions hard to preserve.

07 Initialisation and fitness evaluation

Most GAs start with a random population of size \(N\). Typical sizes like 50–200 are common because they offer a compromise: enough diversity to cover multiple regions, but not so many individuals that evaluation becomes too expensive. If the search space is huge or the encoding is brittle, you may want more. If each evaluation is very costly, you may want fewer.

The point of random initialisation is not to guarantee a good starting solution. It is to guarantee diversity of starting hypotheses. You want many different attempts in play before selection begins to concentrate the population.

Fitness evaluation is where the problem gets translated into GA language. For 8-queens, one natural fitness is the number of non-attacking queen pairs, with a maximum of 28. For a TSP, since we want shorter tours, a common fitness is something inversely related to length such as \(f = 1/L\). For a regression problem, fitness might be negative error or a transformed reward.

The main rule is simple: the fitness function is the lens through which the algorithm sees the world. If you define it poorly, the algorithm becomes brilliantly wrong.

08 Selection: deciding who gets to become a parent

Selection is where “survival of the fittest” enters the algorithm, but notice the phrase carefully. In GAs, the fittest usually do not reproduce deterministically. They reproduce probabilistically. Better individuals get a higher chance, not an absolute monopoly. That stochasticity is healthy because it preserves some diversity and prevents one early champion from freezing the whole search.

Roulette-wheel selection, also called fitness-proportionate selection, is the textbook starting point. If individual \(i\) has fitness \(f_i\), then

The metaphor is a roulette wheel where each individual owns a slice proportional to its fitness. Spin the wheel, and better individuals are more likely to be chosen. The weakness is obvious: if one individual's fitness dwarfs the rest, its slice becomes enormous and convergence can happen too fast.

Tournament selection is often more robust. Pick \(k\) individuals at random, compare them, and the fittest wins the tournament. Then repeat as needed. With \(k=2\), you already get moderate pressure. Larger \(k\) means stronger pressure. The appeal is simplicity, stability, and easy control.

Rank selection sorts the population by fitness and assigns selection probability by rank rather than raw score. That means an extreme outlier cannot dominate purely because its numerical fitness is huge. You care about relative ordering, not absolute magnitude.

Elitism is a safety device: copy the best \(n\)% or best \(k\) individuals directly into the next generation. This prevents the bizarre but very real possibility that the current best solution disappears because of unlucky selection, crossover, and mutation.

09 Crossover: where the algorithm bets on reusable building blocks

Crossover, or recombination, is the GA's signature move. Two parents exchange material to produce children. The intuition is that good partial structures found in different individuals can be combined into a better whole.

Single-point crossover picks one cut point and swaps the tails. Two-point crossover picks two cut points and swaps the middle segment. Uniform crossover treats each gene position independently, choosing from parent 1 or parent 2 according to random masks.

For real-valued vectors, a very natural variant is arithmetic crossover:

where \(\alpha\) is some mixing coefficient, often between 0 and 1.

The crossover probability \(P_c\) is usually high, around 0.6–0.9. The reason is philosophical as much as empirical: GAs are betting that mixing existing good material is one of the main engines of improvement.

10 Mutation: the small random shock that keeps evolution alive

If crossover is the GA's headline act, mutation is its insurance policy. Mutation introduces new variation that selection and crossover alone cannot guarantee. Without mutation, once an allele disappears from the population, it is gone forever. That is dangerous because populations can converge too early around mediocre regions.

For binary strings, the classical mutation is bit flip: each bit flips with small probability \(P_m\), often in the rough range 0.001–0.01 per bit. For real-valued vectors, a common choice is Gaussian mutation, where you add noise like \(x' = x + \mathcal{N}(0,\sigma)\).

Mutation does two things at once. First, it helps explore new regions by generating values not present in the current population. Second, it repairs over-concentrated populations by reintroducing lost diversity.

I like to think of mutation as the algorithm's way of admitting that inheritance is not enough. Sometimes genuinely new information must enter the search.

11 Replacement, survival, and when the run should stop

Once offspring are created and evaluated, you must decide how the next generation is formed. In a generational GA, the whole population is replaced each generation, possibly with elitism preserving the best few. In a steady-state GA, only one or a few individuals are replaced at a time, which can create smoother evolution and more persistent continuity.

Elitism plus generational replacement is common because it gives a simple rhythm while protecting the best solutions found so far.

Termination criteria are practical rather than theoretical. Common choices include:

• a fixed maximum number of generations,
• a fitness threshold such as “stop once fitness \(\geq\) target,”
• no improvement for \(G\) generations,
• or an external time or evaluation budget.

Because evolutionary algorithms are stochastic, “best possible proof of optimality” is usually not the stopping mindset. The mindset is: have we reached a sufficiently good answer for the available budget?

12 The schema theorem and the building-block hypothesis

This is the most theory-heavy part of the chapter, but the intuition is manageable if you slow it down.

A schema is a pattern over chromosomes using fixed symbols plus wildcards. For a binary string, the schema \(1*01*\) means: first bit must be 1, third bit must be 0, fourth bit must be 1, while the second and fifth bits can be anything. The order of a schema is the number of fixed positions. Here the order is 3. The defining length is the distance between the first and last fixed positions. Here it spans from position 1 to position 4, so the defining length is 3.

Holland's schema theorem says, roughly, that short, low-order, above-average schemata receive exponentially increasing trials over generations. In plainer English: if a small pattern tends to occur in fitter individuals, the GA will tend to preserve and sample it more often.

This supports the building-block hypothesis. The claim is that GAs work well because they discover useful short subpatterns — building blocks — and recombine them into larger high-quality solutions. That is why contiguous and meaningful encodings matter so much. If the building blocks are easy to preserve, crossover can assemble them. If they are fragmented awkwardly across the chromosome, crossover may keep smashing them apart.

This is also why people call some problems deceptive. In deceptive problems, locally attractive building blocks can mislead the search away from the global optimum. The GA still relies on structure, but the structure can lie to it.

13 A worked 8-queens GA example, one generation at a time

Let us use a simplified 8-queens representation where each chromosome is an 8-digit string and each digit gives the row position of the queen in that column. So the chromosome 15863724 means: in column 1 place a queen in row 1, in column 2 place one in row 5, and so on.

The maximum number of non-attacking queen pairs is \(\binom{8}{2} = 28\). So a natural fitness is:

Suppose our tiny population has four individuals:

Individual	Chromosome	Fitness
A	15863724	24
B	16837425	20
C	24683175	26
D	25713864	18

Total fitness is 88, so roulette-wheel selection probabilities are approximately:

• \(P(A) = 24/88 \approx 0.273\)
• \(P(B) = 20/88 \approx 0.227\)
• \(P(C) = 26/88 \approx 0.295\)
• \(P(D) = 18/88 \approx 0.205\)

Suppose selection chooses parents \(C\) and \(A\). Using single-point crossover after the fourth position:

Now mutate child 1 with a low-probability random event, say position 7 changes from 2 to 5, giving 24683754. Then evaluate both children. Maybe child 1 scores 25 and child 2 scores 22. With generational replacement plus elitism, the best old individual 24683175 may survive automatically, and the new population is formed from the best combination of elite survivors and offspring.

This tiny example hides a lot of complexity, but it shows the loop concretely: score, bias reproduction toward the better individuals, mix them, perturb them, rescore, repeat. Over many generations, the population tends to accumulate more non-attacking structures until a valid 28-fitness arrangement appears.

14 Beyond the basic GA: GP, ES, and DE

Genetic algorithms are the celebrity of the family, but they are not the whole family.

Genetic programming (GP) evolves programs rather than fixed-length strings. The chromosome is often a tree representing an expression or program. Crossover swaps subtrees. Mutation may replace a node or subtree. GP is famous for symbolic regression, automatic formula discovery, and evolving rule structures.

Evolutionary strategies (ES) focus more naturally on real-valued optimisation. They are mutation-heavy and often self-adapt their own mutation step sizes \(\sigma\). The rough message of ES is: if your problem is continuous, stop pretending everything should be a bit string. Use an algorithm built for real vectors.

Differential evolution (DE) is a modern favourite for continuous optimisation because it is simple and effective. It creates a trial vector by adding a weighted difference of two individuals to a third, then compares the trial with the current target. Very few parameters, very competitive performance.

Method	Typical representation	Main variation mechanism	Good fit
GA	Binary, symbolic, permutations, general encodings	Crossover-heavy plus mutation	Combinatorial and general-purpose search
ES	Real-valued vectors	Mutation-heavy, self-adaptive step sizes	Continuous optimisation
GP	Trees / programs	Subtree crossover and mutation	Symbolic regression, program search
DE	Real-valued vectors	Differential mutation and greedy selection	Strong practical continuous optimisation

The big lesson is that “evolutionary computation” is the umbrella; “genetic algorithm” is one well-known member under that umbrella.

15 No Free Lunch, and where GAs actually shine

The No Free Lunch theorem is the sober reminder that no optimiser is best on all possible problems. If one algorithm performs amazingly on one class of landscapes, there must be other classes where it performs worse, averaged over all possible problems.

So the case for GAs is not “GAs beat everything.” The case is narrower and more realistic: they are very useful when you cannot compute good gradients, when the search space is huge and multimodal, when representations are discrete or structured, and when approximate high-quality solutions are acceptable.

GAs are especially natural for feature selection, combinatorial design, scheduling, routing with custom encodings, hyperparameter search, and hybrid problems with odd constraints. They are often weaker when a smooth differentiable objective exists and a strong gradient-based optimiser can exploit that structure directly.

16 Practical tuning instincts and beginner mistakes

People often ask for the best population size, crossover rate, and mutation rate as if there is a hidden sacred table. There isn't. But there are good instincts.

If the population is too small, diversity collapses early. If it is too large, evaluation cost explodes. If selection pressure is too strong, mediocre early winners dominate. If it is too weak, the algorithm drifts. If crossover is too destructive for your representation, children are mostly garbage. If mutation is too tiny, exploration disappears; too large, and selection cannot accumulate gains.

In practice, good GA work often means spending serious thought on representation, fitness shaping, and diversity preservation. The loop is simple; the craft is in the design.

17 Why operator design matters so much for permutations and structured problems

One lesson that beginners usually learn the hard way is that a GA is not just “take any encoding, then blindly single-point crossover and bit-flip mutation.” That works tolerably for simple bit strings, but many real problems have structure that standard operators can destroy. The travelling salesman problem is the classic warning sign. If parent 1 is 1 2 3 4 5 and parent 2 is 3 5 4 1 2, then a naive single-point crossover can easily create a child with duplicate cities and missing cities. That child is not just suboptimal; it is invalid.

This is why specialised representations demand specialised operators. Permutation problems often need order crossover, partially matched crossover, cycle crossover, swap mutation, insertion mutation, or inversion mutation. The goal is to keep the child inside the space of valid tours while still mixing parental structure. If your operator constantly creates illegal children and then relies on ad-hoc repair, the algorithm spends too much effort recovering from its own representation mistakes.

The same principle appears in other domains. In genetic programming, subtree crossover makes sense because the chromosome is a tree. In real-valued optimisation, Gaussian mutation and arithmetic crossover are natural because the search space is continuous. In feature selection, bit flips make intuitive sense because each position literally means include or exclude.

This also explains why comparing “GA” to another method can be unfair unless you specify the encoding and operators. A badly matched GA can look terrible, while a well-encoded GA with domain-aware operators can look surprisingly smart. The algorithmic idea is only half the story; the engineering of the representation is the other half.

18 A concrete schema intuition example

The schema theorem can feel abstract until you see one tiny example. Suppose we are using 5-bit chromosomes and we notice that individuals matching the schema 1*01* often have above-average fitness. That schema fixes bit 1 as 1, bit 3 as 0, and bit 4 as 1, while bits 2 and 5 can vary. Its order is 3 because three positions are fixed. Its defining length is 3 because the first fixed position is bit 1 and the last fixed position is bit 4.

Now imagine a population where many high-fitness strings look like 10010, 11011, and 10110. They all share the same hidden building block: first bit 1, third bit 0, fourth bit 1. Selection will tend to copy these individuals more often because they are fit. That automatically increases the number of samples of the schema in the next generation. If crossover points usually happen outside the schema's small defining length, the pattern survives recombination fairly often. If mutation rates are low, the fixed bits are not frequently destroyed. So the schema grows in the population.

That is the core intuition behind “short, low-order, above-average schemata get exponentially increasing trials.” The GA is not explicitly reasoning, “Ah yes, bits 1, 3, and 4 form a useful concept.” It just ends up sampling that pattern more because fit individuals carrying it survive and reproduce. Over time, other useful schemata from other parents can be combined with it.

This is also why long fragile schemata are harder to preserve. The more spread out a pattern is, the more likely crossover cuts through it. The more fixed positions it has, the more likely mutation damages one of them. So the theorem rewards compact reusable patterns. That is a beautiful piece of theory because it links the operator mechanics directly to the idea of evolutionary reuse.

19 When a GA is the right hammer, and when it really is not

I think the most mature way to respect Chapter 5 is not to turn GAs into a religion. They are excellent when you have a huge search space, awkward structure, no reliable derivative, and a willingness to spend many evaluations for a good approximate answer. They are also great when you suspect the solution has reusable substructure that crossover can exploit.

But if your objective is smooth, differentiable, and well behaved, gradient-based optimisation can be dramatically more efficient. If your state space is tiny, exhaustive search or dynamic programming can be better. If your constraints are rigid and symbolic, a CSP or SAT formulation may crush a GA. The wisdom is in fit, not hype.

So the exam takeaway is not “GA beats local search” or “GA beats exact search.” The right statement is: GAs are robust, population-based, derivative-free optimisers that are particularly appealing for multimodal, discrete, combinatorial, and awkward black-box problems. That is already a powerful and respectable claim.

Why is crossover treated as central in a GA?

Because the GA bets that useful substructures can be recombined from different parents. Mutation alone can search, but crossover allows the algorithm to combine already-good pieces rather than rediscovering them independently.

Why is tournament selection so popular?

It is simple, efficient, and robust. You can control selection pressure through the tournament size \(k\), and it is less sensitive than roulette-wheel selection to extreme raw fitness values.

Does the schema theorem prove GAs always work?

No. It gives intuition about why above-average short schemata can proliferate, but it does not guarantee success on every landscape. Deceptive problems, poor encodings, and excessive convergence can still hurt badly.

When should I reach for ES or DE instead of a classical GA?

If the variables are naturally real-valued and the main task is continuous optimisation, ES and DE are often more natural and more competitive than forcing a binary GA formulation.

• Evolutionary computation turns variation, heredity, and selection into a population-based search process.
• Genetic algorithms work through representation, fitness evaluation, selection, crossover, mutation, replacement, and termination.
• Representation is crucial because operators act on encodings, not on abstract problem meaning.
• The schema theorem and building-block hypothesis explain why short reusable patterns matter.
• GA is only one member of EC; GP, ES, and DE cover other structures and problem types.