Intelligent Systems II · TEE · papers
Q6(a) GA ranking and three crossover methods [10]
Final examination · 17 Apr 2024
Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.
A chromosome x=abcdefghij has ten genes, each a digit 0–9. Fitness f (x)=(a+b)−(c+d)+(e+f)+(g+h)−(i+j). Initial chromosomes: x₁=6541353253; x₂=8712660124; x₃=2392128546; x₄=4185209426. (1) Evaluate and rank fitness. (2) Cross the fittest two at the midpoint. (3) Cross second and third fittest using two points b and f. (4) Cross first and third using arithmetic crossover α=.5. (5) Evaluate all six offspring. (6) Has overall fitness improved?
Answer
Given
Four ten-gene parents and a signed linear fitness function.
To find
Ranking, two children per crossover, child fitness and fair population comparison.
Formula and why it applies
One-point crossover swaps suffixes. Two-point crossover swaps the middle block. Arithmetic crossover takes weighted gene values.
LaTeX: child_1=\alpha P+(1-\alpha)Q,\quad child_2=(1-\alpha)P+\alpha QSolution
Step 1. Evaluate each signed pair sum
| Parent | (a+b)−(c+d)+(e+f)+(g+h)−(i+j) | Fitness |
|---|---|---|
| x1 | 11−5+8+5−8 | 11 |
| x2 | 15−3+12+1−6 | 19 |
| x3 | 5−11+3+13−10 | 0 |
| x4 | 5−13+2+13−8 | -1 |
Descending order: x₂ (19), x₁ (11), x₃ (0), x₄ (−1).
Step 2. One-point crossover after gene 5
x₂=87126 | 60124; x₁=65413 | 53253. Exchange the right blocks.
| Child | Genes | Fitness |
|---|---|---|
| C1 | 8712653253 | 20 |
| C2 | 6541360124 | 10 |
Step 3. Two-point crossover after b and after f
State cuts explicitly: positions 2 and 6. The parents are x₁=65 | 4135 | 3253 and x₃=23 | 9212 | 8546. Swap only the four-gene middle blocks.
| Child | Genes | Fitness |
|---|---|---|
| C3 | 6592123253 | 0 |
| C4 | 2341358546 | 11 |
Step 4. Arithmetic crossover of x₂ and x₃
| Position | x₂ | x₃ | 0.5x₂+0.5x₃ |
|---|---|---|---|
| 1 | 8 | 2 | 5.0 |
| 2 | 7 | 3 | 5.0 |
| 3 | 1 | 9 | 5.0 |
| 4 | 2 | 2 | 2.0 |
| 5 | 6 | 1 | 3.5 |
| 6 | 6 | 2 | 4.0 |
| 7 | 0 | 8 | 4.0 |
| 8 | 1 | 5 | 3.0 |
| 9 | 2 | 4 | 3.0 |
| 10 | 4 | 6 | 5.0 |
At α=0.5 both children are identical. C5=C6=[5.0, 5.0, 5.0, 2.0, 3.5, 4.0, 4.0, 3.0, 3.0, 5.0]. Their fitness is 9.5.
Step 5. Show every offspring fitness calculation
| Child | Pair sums with signs | Fitness |
|---|---|---|
| C1 | 15−3+11+5−8 | 20 |
| C2 | 11−5+9+1−6 | 10 |
| C3 | 11−11+3+5−8 | 0 |
| C4 | 5−5+8+13−10 | 11 |
| C5 | 10−7+7.5+7−8 | 9.5 |
| C6 | 10−7+7.5+7−8 | 9.5 |
Step 6. Compare averages, not totals from different population sizes
LaTeX: \bar f_{old}=(11+19+0-1)/4=7.25
LaTeX: \bar f_{new}=((20)+(10)+(0)+(11)+(9.5)+(9.5))/6=10Best old fitness is 19; best new fitness is 20. The mean improves, but the best individual may not. A larger total alone is not proof of improvement because six children replace four parents.