GA: Fitness Function & Selection

Source: Unit 5 §4

The fitness function defines the criterion both for ranking hypotheses and for probabilistically selecting them for the next generation. Everything on this page is about turning a fitness number into a parent.

The four selection methods

Method	How it works
Roulette wheel (fitness proportionate)	Selection probability is proportional to fitness / total fitness.
Tournament	Pick 2 chromosomes at random; with probability p, the fitter one wins.
Rank	Sort by fitness, then make selection probability proportional to rank rather than raw fitness.
Elitism	Always retain the best chromosomes into the next generation, untouched.

?DECISIONWhich selection method?

Fitness values are well spread and comparable→Roulette wheelthe simple default

One super-fit chromosome would take over the pool→Rank selectionranks ignore the size of the gap

Fitness is expensive or noisy to compute exactly→Tournamentonly needs pairwise comparisons

The best solution must never be lost→Elitismlayered on top of any other method

Pick this when: one chromosome's fitness dwarfs the rest, or the population has gone flat

Roulette wheel selection in detail

Imagine a wheel whose circumference is $\sum f(c_i)$, the sum of all fitnesses. Each chromosome occupies an arc proportional to its fitness. Spin the wheel, and whichever arc lands at the fixed pointer is selected. Repeat $n$ times.

Illustrative wheel, not the worked example below: each chromosome owns an arc proportional to its fitness. One spin selects one parent; n spins fill the mating pool.

The worked 5-city TSP example

Ten chromosomes with $\sum f(c_i) = 1869$:

#	Chromosome	Fitness	Cumulative
1	d-e-a-b-c	193	193
…	…	…	…
6	c-e-d-a-b	197	1089
7	e-a-d-b-c	222	1311
…	…	…	…

→StepsSelecting with a random number of 1279

1. Draw a random number in $(0, 1869)$; here it is 1279.
2. Walk the cumulative column until the running total first exceeds it.
3. $1089 < 1279 < 1311$, so the walk stops at chromosome 7.
4. Chromosome 7, e-a-d-b-c, is selected.

⚠GotchaFitness proportionate selection has two failure modes

Early on, one lucky chromosome with a huge fitness eats most of the wheel and the population converges prematurely. Late on, when everything has similar fitness, the arcs are nearly equal and selection degenerates into a random choice, so evolution stalls. Rank selection is the standard fix for both.