WEEK 10 Genetic Algorithms & Evolutionary Computation – Key Vocabulary

Vocabulary flashcards summarising key terms from the CS2004 lecture on Genetic Algorithms, Evolutionary Programming, and Genetic Programming.

Genetic Algorithm (GA)

A search and optimisation technique inspired by evolutionary biology that uses selection, crossover, and mutation to evolve solutions.

Gene

A single binary digit within a chromosome representing part of a solution.

Chromosome

A string of genes encoding a candidate solution to a problem.

Representation

The chosen encoding scheme that maps problem solutions to chromosomes, covering the full search space.

Fitness Function

A quantitative measure used to evaluate how good a chromosome’s solution is.

Population

The set of chromosomes that exist simultaneously during one generation of a GA run.

Generation

One complete cycle of evaluating, selecting, and creating a new population in a GA.

Crossover

A genetic operator that combines genes from two parent chromosomes to produce offspring.

One-Point Crossover

A crossover method where parents exchange segments of genes after a randomly chosen single cut point.

Uniform Crossover

A crossover method where each gene is independently chosen from either parent with equal probability.

Mutation

A genetic operator that randomly inverts bits in a chromosome to introduce new genetic material and maintain diversity.

Selection Operator

The process that chooses which chromosomes survive to the next generation based on fitness.

Roulette Wheel Selection

A probabilistic selection method where the chance of survival is proportional to a chromosome’s fitness.

Crossover Probability (CP)

The likelihood that a chromosome will undergo crossover during reproduction.

Mutation Probability (MP)

The probability that a given gene will mutate during reproduction.

Population Size (PS)

The number of chromosomes maintained in each generation of a GA.

Number of Generations (NG)

The total iterations the GA executes before termination.

Knapsack Problem

An optimisation problem of selecting items with weights and values to maximise value while staying under a weight limit.

Holland’s GA Algorithm

A canonical GA procedure involving random initialization, crossover, mutation, invalid repair, and fitness-based survival across NG generations.

Evolutionary Computation

A family of optimisation techniques inspired by natural evolution, including GAs, EP, and GP.

Evolutionary Programming (EP)

An evolutionary method focused on mutation (no crossover) and tournament selection for survival.

Tournament Selection

A selection strategy where individuals compete in small groups, earning points for superior fitness, with top scorers surviving.

Genetic Programming (GP)

An evolutionary technique that evolves computer programs, often represented as tree structures, to solve problems like symbolic regression.

Symbolic Regression

A GP task that discovers mathematical expressions fitting data, represented as expression trees.

Sub-tree Exchange Crossover

A GP operator that swaps entire sub-trees between parent program trees.

Point Mutation (GP)

A GP mutation changing a single node (operator or operand) within a program tree.

Hoist Mutation

A GP mutation that promotes a sub-tree to become a new individual, effectively simplifying the program.

Prune Mutation

A GP operator that removes a sub-tree to reduce program size.

Optimisation

The process of finding the best solution under given constraints, a primary application area for GAs.

Parameter Tuning

Adjusting GA variables—PS, NG, CP, MP, chromosome length—to improve performance for a specific problem.