Selection Methods

How a Genetic Algorithm picks parents — biased toward the fittest, but not deterministic.

Why we need them

In a GA we need to pick which individuals reproduce. If we always pick the very best, we lose diversity instantly. If we pick uniformly at random, fitness doesn't matter. We want something in between — fitter individuals get picked more often, but everyone has a chance.

Roulette wheel selection

The picture

Imagine a roulette wheel where each individual gets a slice proportional to its fitness. Higher fitness → bigger slice → more likely to be picked.

Five steps:

Compute total fitness F = Σ fitness(i).
Compute relative fitness for each: fitness(i) / F.
Compute cumulative probabilities (running sum).
Draw a random number r in [0, 1].
Pick the first individual whose cumulative probability ≥ r.

Example 1: Graph coloring (maximization)

4 individuals, fitness = # of satisfied constraints:

Ind.	Fitness	Relative	Cumulative
A	12	12/30 = 0.400	0.400
B	8	8/30 = 0.267	0.667
C	6	6/30 = 0.200	0.867
D	4	4/30 = 0.133	1.000

Total = 30. Draw r = 0.52: 0.52 falls between A's cumulative (0.400) and B's (0.667) → select B.

Example 2: TSP (minimization)

For minimization (smaller distance = better), invert: fitness = 1 / distance.

Tour	Distance	Fitness = 1/d	P(select)	Cumulative
A	300	0.0033	0.067	0.067
B	250	0.0040	0.089	0.156
C	80	0.0125	0.281	0.436
D	40	0.0250	0.562	1.000

Total fitness = 0.0445. Draw r = 0.35 → falls between B (0.156) and C (0.436) → select C.

Tournament selection

Even simpler: pick K random individuals from the population, return the best of those.

K-way tournament:
    pick K random individuals
    return argmax_fitness among them

Tuning K:

K = 2 — gentle selection pressure (more diversity).
K = population_size — always pick the best (no diversity).
K = 3 or 5 is common in practice.

Tournament selection is popular because it:

Has no need to compute cumulative probabilities.
Works equally well for minimization or maximization (just compare).
Has tunable pressure via K.
Avoids issues when fitness has huge range (where roulette over-favors the best).

Interactive demo

Spin the wheel several times — count how often each is picked. Try changing fitness values.

Click spin

Exam tips

Frequently asked

"Apply roulette wheel selection with these fitness values and r = 0.X" — compute total, relative, cumulative, find which slice r falls in.
"What if it's a minimization problem?" — use 1/cost as fitness, OR subtract each cost from max_cost + 1.
"What is K in tournament selection?" — number of competitors. Higher K = stronger selection pressure.
"Which has more diversity, tournament with K=2 or roulette wheel?" — usually tournament with K=2; less greedy than roulette wheel when one individual has much higher fitness.