GA: Terminology & Structure

Source: Unit 5 §2

The vocabulary

Term	Meaning
Population	A subset of all possible (encoded) solutions.
Chromosome	One solution to the problem.
Gene	One element or position of a chromosome.
Allele	The value a gene takes in a particular chromosome.
Genotype	The chromosome as represented in computation space, i.e. encoded.
Phenotype	The solution in the real-world solution space.
Encoding / decoding	Encoding is phenotype → genotype; decoding is genotype → phenotype.
Fitness function	Takes a solution, returns its suitability.
Genetic operators	Alter the genetics of offspring: crossover, mutation, selection.

One chromosome is one candidate solution. A gene is a position in it; an allele is the value sitting in that position.

⚠GotchaGenotype and phenotype are not interchangeable

The GA operates entirely on genotypes: crossover and mutation cut and flip bits without knowing what they mean. The fitness function is the only place the genotype is decoded back into a phenotype and judged as a real solution. Mixing the two up is what makes an encoding scheme fail.

The generalised pseudo-code

GA():

initialize population

find fitness of population

while (termination criterion not reached):

parent selection

crossover with probability p_c

mutation with probability p_m

decode and calculate fitness

survivor selection

find best

return best

The structure as a loop

The GA loop. Everything between fitness evaluation and survivor selection repeats once per generation.

In words: a pool of candidate solutions undergoes recombination and mutation to produce offspring, repeated over generations, with fitter individuals given a higher chance to mate. The population evolves until a stopping criterion is met.