Intelligent Systems II · TEE · papers
Q5(a) GA selection, crossover and survivor replacement [10]
Re-examination · 25 Jun 2024
Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.
Use the population table. (1) Rank-select the best two, then one-point crossover in the middle. (2) A three-way tournament on individuals 1,3,5 selects parent 1; a two-way tournament on 2,4 selects parent 2. Again crossover in the middle. (3) Replace using fitness-based survivor selection and compute the new average. (4) Repeat replacement from the original population using age-based survivor selection and compute its average.
| No. | Chromosome | Fitness | Age |
|---|---|---|---|
| 1 | 01000000 | 64 | 8 |
| 2 | 01011111 | 95 | 2 |
| 3 | 01010000 | 80 | 13 |
| 4 | 01011001 | 89 | 9 |
| 5 | 01011110 | 94 | 4 |
| 6 | 01001111 | 79 | 10 |
| 7 | 01010001 | 81 | 12 |
| 8 | 01000001 | 65 | 15 |
| 9 | 01011000 | 88 | 10 |
| 10 | 01000000 | 64 | 20 |
Answer
Given
Ten 8-bit chromosomes with supplied fitness and ages; larger fitness is better.
To find
Four offspring and two independent survivor-selection outcomes.
Formula and why it applies
Rank or tournament selection chooses parents. Crossover exchanges suffixes after bit 4. Fitness-based replacement removes the weakest; age-based replacement removes the oldest. Treat the two requested replacements as separate experiments starting from the same initial population.
Solution
Step 1. Rank and choose the top two
| Fitness rank | Individual | Fitness |
|---|---|---|
| 1 | 2 | 95 |
| 2 | 5 | 94 |
| 3 | 4 | 89 |
| 4 | 9 | 88 |
| 5 | 7 | 81 |
| 6 | 3 | 80 |
| 7 | 6 | 79 |
| 8 | 8 | 65 |
| 9 | 1 | 64 |
| 10 | 10 | 64 |
Select 2(95) and 5(94). Split 0101|1111 and 0101|1110. Swapping suffixes gives 01011110(94) and 01011111(95).
Step 2. Conduct the specified tournaments
Tournament{1,3,5}: fitness 64,80,94 → choose 5. Tournament{2,4}:95,89 → choose 2. Split 0101|1110 and 0101|1111. Children are 01011111(95) and 01011110(94). No mutation is specified.
The four child fitnesses are 94,95,95,94, sum 378. Their strings already exist in the supplied table, so their supplied fitness values can be used directly; no new fitness function is invented.
Step 3. Fitness-based survivor replacement
Remove the four lowest-fitness originals:1(64),10(64),8(65),6(79). Keep 2,3,4,5,7,9 with fitness 95,80,89,94,81,88. Keep duplicates because the question does not impose uniqueness.
LaTeX: \text{retained sum}=95+80+89+94+81+88=527
LaTeX: \bar f_{fitness}=\frac{527+378}{10}=90.5Step 4. Age-based replacement, reset to the original table first
Remove the oldest four:10(age 20),8(age 15),3(age 13),7(age 12). Keep 1,2,4,5,6,9 with fitness 64,95,89,94,79,88. Add the same four offspring.
LaTeX: \text{retained sum}=64+95+89+94+79+88=509
LaTeX: \bar f_{age}=\frac{509+378}{10}=88.7Step 5. Explain the difference
LaTeX: \bar f_{original}=799/10=79.9Fitness-based replacement improves the average more in this example because it directly removes weaker individuals. Age-based replacement promotes turnover, but age is not the same as quality. “Rank-based” selection is usually probabilistic; here the question explicitly says choose the best two, so that deterministic instruction is followed.