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:

    1. 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)

    1. 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)

  1. Generate PS random chromosomes length n

  2. 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)

  3. 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:

    1. Random initial population

    2. Evaluate fitness

    3. Select best individuals

    4. 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:

    1. Initialise population

    2. For each generation:

    • Mutate all individuals

    • Tournament selection to down-size

    1. 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