GA: A Full Worked Example

Source: Unit 5 §6

≡FactsThe problem

• Minimise $f(x) = x \sin(10\pi x) + 1.0$.
• Subject to $-1 \le x \le 2$.
• Crossover rate 0.5, mutation rate 0.1, population 10 chromosomes.
• One generation, worked end to end.

Step 1: initialisation and evaluation

Ten values of $x$ are drawn, and $f(x)$ is computed for each.

x = −0.4691, 0.1572, −0.5914, 0.6454, 0.7796,

1.0580, 0.0991, 0.2772, 0.5605, 1.6327

 

min f(x) = 0.4697 at x = 0.5605 ← the best of this generation

Step 2: selection, with normalisation

Sort $f(x)$ ascending, then normalise the costs between 0.1 and 0.9:

$$f'(x) = \frac{(\text{max}_{range} - \text{min}_{range})\,(f(x) - \min f(x))}{\max f(x) - \min f(x)} + \text{min}_{range}$$

Here $\text{min}_{range} = 0.1$, $\text{max}_{range} = 0.9$, $\min f = 0.4697$ and $\max f = 2.3962$.

→StepsTurning costs into selection probabilities

1. Normalise every cost into [0.1, 0.9] with the formula above.
2. Divide each normalised cost by the sum of all of them to get a probability.
3. Flip the probabilities, so the lowest-cost chromosome ends up with the highest selection probability.
4. Spin the roulette wheel 10 times to fill the mating pool. A random draw of 0.6777 falls in the interval [0.6508, 0.7458], which selects the 5th chromosome, $x = 0.0991$.

⚠GotchaThe slides' "5th chromosome" is 5th after sorting

$x = 0.0991$ is the 7th entry in the initial list above, but the 5th once step 1 sorts the population by cost: the ascending order runs 0.5605 ($f = 0.4697$), 0.7796, −0.5914, 0.1572, then 0.0991 at $f = 1.0028$. The ordinal refers to the sorted population. Say which ordering you are counting in and the discrepancy disappears.

⚠GotchaThis is a minimisation problem, so raw cost is not fitness

Feeding cost straight into a roulette wheel would give the worst chromosomes the biggest arcs. Step 3 is not decoration; it is what converts a cost into a fitness. Any minimisation GA needs an equivalent flip.

Step 3: directional crossover

A crossover rate of 0.5 over 10 chromosomes means 5 crossovers; a mutation rate of 0.1 means 1 mutation.

$$C_1 = P_1 + R(P_2 - P_1) \qquad C_2 = P_2 + R(P_1 - P_2)$$

→StepsOne crossover, computed

1. Take $P_1 = 0.0991$, $P_2 = 0.5605$, and a random $R = 0.3451$.
2. $C_1 = 0.0991 + 0.3451(0.5605 - 0.0991) = 0.0991 + 0.1592 = \mathbf{0.2583}$.
3. $C_2 = 0.5605 + 0.3451(0.0991 - 0.5605) = 0.5605 - 0.1592 = \mathbf{0.4013}$.

Directional crossover on real-valued genes: both children land on the line between the parents, at mirrored fractions R of the gap.

⚠GotchaCheck the boundary before replacing a parent

Every new offspring must lie within $[-1, 2]$. If it does not, the parent is not replaced. Skipping this check is how a real-coded GA quietly starts evaluating points outside its own domain.

Step 4: mutation

Randomly select an offspring - say the third - and replace it with a new random number drawn from $[-1, 2]$.

Step 5: termination

Stop after a set number of generations, or on another criterion. Otherwise loop back to the evaluation in step 1 and run the next generation.