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