WEEK 10 Genetic Algorithms & Evolutionary Computation – Key Vocabulary
Recap of Previous Material
Course progression before this lecture:
Fundamental concepts of computation & algorithms
Algorithm comparison & computational complexity
O(\cdot) Big-Oh notation
Core data structures
Sorting algorithms
Graph traversal algorithms
Search & fitness concepts
Heuristic search methods
Hill-Climbing and Simulated Annealing
Road-Map for Remainder of Module
Advanced heuristic search & applications to be covered:
Genetic Algorithms (GA) → this lecture
Evolutionary Computation (general family) → this lecture
Ant Colony Optimisation (ACO)
Particle Swarm Optimisation (PSO)
Application case studies: Bin Packing, Data Clustering, Travelling Salesperson Problem (TSP)
Genetic Algorithms – High-Level View
Bio-inspired optimisation & AI search technique
Suited for problems where deterministic solutions are hard or unknown
Typically produces a good / partial answer (no guarantee of global optimum)
Sometimes inferior to domain-specific algorithms, yet more general-purpose
Biological Metaphor: Genes & Chromosomes
Each gene = single binary digit (bit)
Chromosome = ordered string of genes (bit-string)
Encoding a solution = representation; must cover entire search space
Requires a fitness function to evaluate quality of each chromosome
Population & Generations
Population (PS) = number of chromosomes alive simultaneously
Generation = one complete cycle of selection → reproduction (crossover, mutation) → replacement
Worked Scenario: Knapsack Problem (KP)
Given n items with individual weight & value:
Choose subset so that total weight ≤ capacity
Maximise total value
GA representation example (10 items):
Bit-string of length n, 1 = item included, 0 = excluded
Some bit-strings may be invalid if weight constraint violated → must be fixed or discarded during fitness evaluation
GA Life-Cycle (Overview)
Initialise random population
Evaluate fitness of every chromosome
Produce next generation via selection, crossover, mutation
Iterate for predetermined number of generations or convergence criterion
Return best chromosome discovered
Genetic Operators
Crossover (Recombination)
Combines genetic material from 2 parents → 2 offspring
Controlled by crossover probability CP per chromosome
Major variants:
One-Point Crossover
Choose random cut-point p \in [2, n-1]
Child C: first p genes from Parent B, remaining from Parent A
Child D: complement (first part of A, second part of B)
Uniform Crossover
For each gene: 50 % chance child takes gene from parent A, otherwise from parent B
Second child receives opposite gene choice
Mutation
Random bit-flip with mutation probability MP per gene
Ensures exploration, prevents premature convergence to local minima
Example: 01101101 \rightarrow 00101111 where highlighted bits flipped
Selection (Survival of the Fittest)
Goal: build next population same size as current
Probability of survival proportional to relative fitness
Roulette-Wheel selection (fitness-proportionate) illustrated; numerous alternatives exist (tournament, rank, etc.)
Parameter Definitions (Holland’s Notation)
NG : Number of generations
PS : Population size
CP : Crossover probability
MP : Mutation probability
n : Number of genes per chromosome
Canonical GA (Holland, 1975)
Generate PS random chromosomes length n
For i = 1 \rightarrow NG
Apply crossover with chance CP
Apply mutation with chance MP per gene
Fix or discard invalid chromosomes
Apply survival selection (e.g., roulette-wheel)
Return fittest chromosome of final generation
Practical Parameter Ranges (Rule-of-Thumb)
Population size: 10 \text{–} 100 (problem-dependent)
Generations: 100 \text{–} 1000
Chromosome length: problem-specific, kept minimal but expressive
Mutation rate: 0.1\% \text{–} 10\% (often 1/n)
Crossover rate: 50\% \text{–} 100\%
Example Domains Using GA
Numerical optimisation & general search
Economics & resource allocation
Parallel algorithm design
Image processing & computer vision
Vehicle routing & logistics
Aircraft / aerodynamic design
Scheduling (manufacturing, timetabling)
Bioinformatics (e.g.
DNA analysis)Many other real-world optimisation tasks
Evolutionary Computation (EC) – Family Perspective
GA is one member of wider EC techniques inspired by Darwinian evolution
Typical EC loop:
Random initial population
Evaluate fitness
Select best individuals
Generate next generation via variation operators
Other EC paradigms introduced:
Evolutionary Programming (EP)
Genetic Programming (GP)
Evolutionary Strategies (ES) – not covered
Learning Classifier Systems (LCS) – not covered
Estimation of Distribution Algorithms (EDA) – not covered
Evolutionary Programming (EP)
Similar to GA but no crossover, heavy emphasis on mutation
Every individual mutates → population temporarily doubles
Mutation operators often complex/adaptive (not simple bit-flip)
Tournament Selection used for survival:
Each individual compared against a fixed number of opponents
Wins a point per successful comparison
Retain top-scoring individuals until original population size restored
EP Algorithm:
Initialise population
For each generation:
Mutate all individuals
Tournament selection to down-size
Return best individual
Genetic Programming (GP) – Symbolic Regression Focus
Extends GA to evolve programs (typically represented as syntax trees)
Terminal set = constants & variables; function set = operators (+, –, ×, ÷, ln, etc.)
Example expression x^2 + \ln(10) - 7.3x represented as tree:
\begin{array}{c}\text{root: }+\[-0.3em]\begin{array}{cc}\text{subtree 1: }\times(x, x) & \text{subtree 2: }-\big(\ln(10), \times(7.3, x)\big)\end{array}\end{array}
Fitness = error between expression output and observed data (e.g.
least-squares)Crossover & mutation redesigned for trees; examples:
Sub-tree Exchange Crossover: swap random sub-trees between parents
Self Crossover: swap sub-trees within same parent
Point Mutation: change symbol at a node
Permutation Mutation: swap two terminals in same sub-tree
Hoist, Expansion, Prune, Sub-tree mutation (see slide table)
GP algorithm identical template to GA with tree-specific operators
Laboratory Exercise Preview
Apply GA to Scales Problem (Worksheet 9)
Extra Worksheet:
Adapt Lab 10’s simple GA to a new problem instance
Conduct multiple experiments & plot convergence curves
Upcoming Lecture
Ant Colony Optimisation (ACO) & Particle Swarm Optimisation (PSO) presented by Dr Fang Wang
Connections, Implications & Best-Practice Notes
Choice of representation & fitness function critically influences GA success (garbage-in, garbage-out principle)
Parameter tuning often requires empirical experimentation (meta-optimisation possible)
GA & other EC methods lend themselves to parallelisation because fitness evaluations across population are independent
Ethical & practical considerations:
Interpretability: GA may produce opaque solutions
Computational cost vs. benefit (large populations & long generations can be expensive)
When deploying evolved solutions (e.g.
aircraft design, routing) thorough validation is mandatory
The No-Free-Lunch theorem reminds us no single heuristic dominates across all problems; GAs are a versatile but not universally superior tool