Genetic Algorithm & Evolution

• How genetic algorithms are inspired by natural selection
• Key vocabulary: chromosome, gene, fitness function
• The three genetic operators: selection, crossover, mutation
• How populations evolve over generations
• Real-world applications of genetic algorithms
• How genetic algorithms compare to gradient descent

Inspiration: Natural Selection

Charles Darwin observed that organisms with traits better suited to their environment survive and reproduce more. Over generations, beneficial traits become more common.

Genetic algorithms (GAs) apply this principle to optimisation problems: evolve a population of candidate solutions toward better and better answers.

Key Vocabulary

Example: Optimising a delivery route.

• Chromosome: [3, 1, 4, 2, 5] (order of cities to visit)
• Gene: each city index
• Fitness: total route distance (lower = more fit)

The Fitness Function

The fitness function assigns a numerical score to each chromosome. It is problem-specific.

The GA does not need to know how to solve the problem — it only needs to evaluate how good each solution is.

The Three Genetic Operators

1. Selection

Choose which chromosomes reproduce. More fit solutions get a higher probability of being selected.

Common methods:

• Roulette wheel selection: probability proportional to fitness.
• Tournament selection: pick the best from a random subset.

2. Crossover (Recombination)

Two parent chromosomes exchange segments to create offspring.

| Parent 1 | 1 0 1 1 | 0 0 1 | | Parent 2 | 0 1 0 0 | 1 1 0 | | Child 1 | 1 0 1 1 | 1 1 0 | | Child 2 | 0 1 0 0 | 0 0 1 |

Single-point crossover at position 4.

This combines good traits from both parents.

3. Mutation

Randomly alter one or more genes with a small probability.

1 0 1 1 0 0 1 → 1 0 **0** 1 0 0 1 (gene 3 flipped)

Mutation maintains diversity and prevents the population from getting stuck in a local optimum.

The GA Loop (Generations)

1. Initialise: Create a random population
2. Evaluate: Score each chromosome with the fitness function
3. Select: Choose parents (higher fitness → higher probability)
4. Crossover: Create offspring by combining parents
5. Mutate: Randomly alter some genes in offspring
6. Replace: Form new generation from offspring
7. Repeat steps 2–6 until stopping criterion is met
   (max generations, or fitness threshold reached)

Over many generations, the average fitness of the population increases.

Applications

Genetic Algorithm vs Gradient Descent

1. Explain the analogy between natural selection and a genetic algorithm. What corresponds to "survival of the fittest" in a GA?

2. A GA is used to find the shortest delivery route through 10 cities. Define what the chromosome, gene, and fitness function would be for this problem.

3. After crossover, two offspring are created. Why is mutation also applied, even though the offspring already combine traits from two fit parents?

4. A GA population converges to the same chromosome after 50 generations, but it is not the global optimum. What problem has occurred, and how can it be prevented?

5. A problem has a fitness landscape with many local optima and a discontinuous (non-differentiable) objective function. Why is a genetic algorithm better suited here than gradient descent?