Intelligent Systems II · TEE · papers
Q5(a) Binary GA crossover, one-bit mutation and fitness [10]
Final / re-examination · 28 Apr 2025
Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.
Implement genetic algorithm to maximize the function f (x)=x³−4x²+6x with x in the range [0,15]. Take 4 bit representation of 10,12,7 and 3 as the parent chromosomes. Crossover is after 2 nd bit and mutation is by flipping any one bit. Repeat the process for 2 offspring also comment on the fitness of the offspring.
Answer
Given
Parents 10,12,7,3; unsigned 4-bit encoding; crossover after the second bit; one bit may be flipped. Pairing and mutation positions are not specified.
To find
Crossover children, explicit mutated chromosomes and objective comparison.
Formula and why
LaTeX: x=8b_1+4b_2+2b_3+b_4,\qquad f(x)=x^3-4x^2+6xSplit after the second bit, swap the right halves, then flip exactly the declared mutation bit. Fitness is the stated objective; maximize it.
Step 1. Encode and evaluate the four parents
| Parent x | 4-bit code | Fitness calculation | f (x) |
|---|---|---|---|
| 10 | 1010 | 10³−4(10²)+6(10) | 660 |
| 12 | 1100 | 12³−4(12²)+6(12) | 1224 |
| 7 | 0111 | 7³−4(7²)+6(7) | 189 |
| 3 | 0011 | 3³−4(3²)+6(3) | 9 |
Step 2. Declare pairing and form children
Pair the parents in their listed order: (10,12) and(7,3). Each pair produces two reciprocal children. This uses all four supplied parents; “2 offspring” is interpreted as the two children from a crossover pair, not as two complete generations.
| Pair | Split parents | Child 1 | Child 2 |
|---|---|---|---|
| 10 with 12 | 10|10 and 11|00 | 10|00=1000₂=8 | 11|10=1110₂=14 |
| 7 with 3 | 01|11 and 00|11 | 01|11=0111₂=7 | 00|11=0011₂=3 |
Step 3. Perform one explicitly chosen bit flip per child
Choose the rightmost bit (bit 4 from the left, weight 1) for every child. This is allowed by “any one bit”; it is not the only possible mutation outcome.
| Before mutation | Flip bit 4 | After mutation | Decimal |
|---|---|---|---|
| 1000 | 0→1 | 1001 | 9 |
| 1110 | 0→1 | 1111 | 15 |
| 0111 | 1→0 | 0110 | 6 |
| 0011 | 1→0 | 0010 | 2 |
Step 4. Evaluate every offspring and compare
| Child x before mutation | f (x) before | Child x after mutation | f (x) after |
|---|---|---|---|
| 8 | 304 | 9 | 459 |
| 14 | 2044 | 15 | 2565 |
| 7 | 189 | 6 | 108 |
| 3 | 9 | 2 | 4 |
LaTeX: f(15)=15^3-4(15^2)+6(15)=3375-900+90=2565The best supplied parent is 12 with 1224. The best mutated child is 15 with 2565, an improvement. Mutation did not help every child:7→6 lowers 189 to 108, and 3→2 lowers 9 to 4. Crossover/mutation generate candidates; fitness evaluation decides which are retained.
Step 5. State the result without hiding stochastic choices
For these declared pairings and mutations, offspring are 9,15,6,2 and the best is 15. Different allowed mutation positions can give different offspring. If only two children are requested in a short answer, the fully worked first pair supplies 9 and 15; the second pair shows how the remaining supplied parents are handled. On the finite integer domain 0…15, direct evaluation confirms 15 gives the largest objective, but one generic GA generation is not a proof of global optimality for arbitrary problems.