GA: Genetic Operators

Source: Unit 5 §5

Operator	Purpose
Crossover (recombination)	Exchange genetic material between individuals.
Mutation	Maintain genetic diversity from one generation to the next.

✓Best practiceChoose the operator for the problem, not by habit

An operator that works well on one problem may work badly on another. There is no universally best crossover, which is why the encoding and the operator have to be chosen together.

Crossover types

Single-point

Pick one random crossover point and swap the tails.

Single-point crossover at position 3. Blue genes come from P1, green from P2.

Double-point

Two random sites; the middle segment is swapped.

Two-point crossover: only the middle segment changes hands.

≡FactsThe remaining variants

• Multi-point - the generalisation: alternating segments are swapped. One-point and N-point crossover both exhibit positional bias.
• Uniform - each gene is swapped with probability 0.5. No positional bias, but it has distributional bias, since it tends to transmit about half the genes from each parent.
• Matrix - for matrix chromosomes: choose random row or column cross-sites and exchange a vertical or horizontal region between the mated matrices.
• Order crossover (permutations) - copy a random gene segment from P1 into C1 at the same positions, then fill the remaining slots from P2 in P2's order, skipping genes already used.
• Position-based crossover (permutations) - copy genes at random positions from P1 into C1, then fill the rest from P2, again deleting genes already selected.

The source's order-crossover example works on a 9-city tour:

P1: 4 5 [2 1 3 7] 8 6 9 keep the bracketed segment in place in C1,

then delete those genes from P2 and fill

C1's blanks with P2's remaining order.

⚠GotchaThe slides' segment does not match their own brackets

The bracketed segment reads 2 1 3 7, but the worked result keeps 1-3-7-8. Reproduce whichever the question gives you and state the rule you applied; the mechanism, not the segment, is what is being examined.

Masking-based uniform crossover

A mask decides, position by position, which parent each child gene comes from.

With mask bit 1, C1 takes P1 and C2 takes P2. With mask bit 0, they swap sources.

Mutation

Mutation alters one or more gene values. It maintains genetic diversity, stops chromosomes becoming too similar (which stalls evolution), and helps the search escape local optima and avoid premature convergence. It is applied after crossover.

Mutation type	How it works
Uniform	Pick a random position k and replace the gene with a uniformly random value in [Xₖᴸ, Xₖᵁ].
Boundary	Replace the gene with either Xₖᴸ or Xₖᵁ, with equal probability.
One's complement	Flip all bits: [01101011] → [10010100].
Inversion	Pick two positions and reverse the substring between them.
Insertion	Randomly select a node and insert it at a random position.
Heuristic	Neighbourhood-based: form the neighbours, evaluate them all, keep the best.

→StepsInversion, worked

1. Start from PX = [2 5 4 9 6 8 1 3 7].
2. Choose the substring 4 9 6 8.
3. Reverse it to 8 6 9 4.
4. The child is CX = [2 5 8 6 9 4 1 3 7].

Probability versus rate

Term	Meaning
Crossover probability	The likelihood that the selected chromosomes undergo crossover.
Crossover rate	The total number of crossovers performed.
Mutation probability	The likelihood that random elements are changed.
Mutation rate	The number of chromosomes in the population that undergo mutation.

⚠GotchaProbability and rate are different quantities

One is per-individual chance, the other is a count over the population. A question that gives you "mutation rate 0.1, population 10" wants one mutation, not a 10% chance per chromosome.

GA versus genetic programming

⇄CompareTwo related but distinct techniques

Genetic algorithmEach individual is a candidate solution, a quantity. A probabilistic search mimicking natural evolution. The output is a solution.

Genetic programmingEach individual is a computer program. A special case of a GA that evolves programs to perform a task. The output is another program.