Intelligent Systems II · M2 · mocks

Q2 · GA through two generations [3]

M2 mock 3 · 10 marks

Q1(a)+Q1(b) compulsory; any two of Q2–Q4. Answers immediately below each question.

Confirmed M2 pattern: Q1(a) [2] and Q1(b) [2] are compulsory. Attempt any two of Q2, Q3 and Q4, each worth 3 marks. The paper offers 13 marks; you attempt 10. These are newly written practice questions, not claims about the exact upcoming paper. Solutions are directly below each question; the teaching working is deliberately longer than a concise exam answer.

Q2. Maximise $f(x)=x^2$ over unsigned 4-bit integers using the supplied GA settings. Perform two complete generations and compare the population fitness. [3 marks · Practice; complete two-generation solution]

Given

Initial ordered population: [2, 7, 8, 13]. Use 4 bits, crossover after bit 2, pair mating-pool slots 1–2 and 3–4. Flip bit 4 of children [1, 2, 3, 4] in every generation. Replace the whole population with the four children; no elitism.

Generation	Selection instruction
1	Current individual row numbers [3, 4, 4, 3]
2	Current individual row numbers [2, 3, 2, 3]

To find

Both generations: evaluation, selection, crossover, mutation, decoding and comparison.

Formula and why it applies

Encoding represents x; it does not change the objective. Crossover exchanges tails. Mutation flips specified bits. Fitness must be recomputed after mutation. Use exactly the supplied selection rule; replacing the weakest by the strongest is not a universal GA step.

Solution

Step 1. Generation 1: evaluate and encode the current population

Individual	x	Binary	Objective calculation
1	2	0010	2 × 2 = 4
2	7	0111	7 × 7 = 49
3	8	1000	8 × 8 = 64
4	13	1101	13 × 13 = 169

Step 2. Generation 1: apply the supplied selection order

The question directly supplies individual numbers [3, 4, 4, 3]. These refer to the current generation’s row numbers, not their x values.

Mating-pool slot	Chosen individual	x	Chromosome
1	3	8	1000
2	4	13	1101
3	4	13	1101
4	3	8	1000

Step 3. Generation 1: crossover after bit 2

Keep each prefix and exchange the suffixes. Bit positions are counted from the left starting at 1.

Pool slots paired	Parent A	Parent B	Child A	Child B
1 & 2	10 \| 00	11 \| 01	1001	1100
3 & 4	11 \| 01	10 \| 00	1100	1001

Step 4. Generation 1: mutate only the specified bits

Child	Before mutation	Instruction	After mutation
1	1001	Flip bit 4	1000
2	1100	Flip bit 4	1101
3	1100	Flip bit 4	1101
4	1001	Flip bit 4	1000

Step 5. Generation 1: decode and evaluate every child

Chromosome	Decode using place values	Objective
1000	8 + 0 + 0 + 0 = 8	8² = 64
1101	8 + 4 + 0 + 1 = 13	13² = 169
1101	8 + 4 + 0 + 1 = 13	13² = 169
1000	8 + 0 + 0 + 0 = 8	8² = 64

Step 6. Generation 1: compare and form the next population

Add the objective scores in each population, then divide by its number of individuals.

\overline f_{old}=\frac{4+49+64+169}{4}=\frac{286}{4}=71.5

\overline f_{new}=\frac{64+169+169+64}{4}=\frac{466}{4}=116.5

Best objective: 169 → 169. Higher is better. The next population is [8, 13, 13, 8]. No elitism is imposed, so the best previous individual is not automatically protected.

Step 7. Generation 2: evaluate and encode the current population

Individual	x	Binary	Objective calculation
1	8	1000	8 × 8 = 64
2	13	1101	13 × 13 = 169
3	13	1101	13 × 13 = 169
4	8	1000	8 × 8 = 64

Step 8. Generation 2: apply the supplied selection order

The question directly supplies individual numbers [2, 3, 2, 3]. These refer to the current generation’s row numbers, not their x values.

Mating-pool slot	Chosen individual	x	Chromosome
1	2	13	1101
2	3	13	1101
3	2	13	1101
4	3	13	1101

Step 9. Generation 2: crossover after bit 2

Keep each prefix and exchange the suffixes. Bit positions are counted from the left starting at 1.

Pool slots paired	Parent A	Parent B	Child A	Child B
1 & 2	11 \| 01	11 \| 01	1101	1101
3 & 4	11 \| 01	11 \| 01	1101	1101

Step 10. Generation 2: mutate only the specified bits

Child	Before mutation	Instruction	After mutation
1	1101	Flip bit 4	1100
2	1101	Flip bit 4	1100
3	1101	Flip bit 4	1100
4	1101	Flip bit 4	1100

Step 11. Generation 2: decode and evaluate every child

Chromosome	Decode using place values	Objective
1100	8 + 4 + 0 + 0 = 12	12² = 144
1100	8 + 4 + 0 + 0 = 12	12² = 144
1100	8 + 4 + 0 + 0 = 12	12² = 144
1100	8 + 4 + 0 + 0 = 12	12² = 144

Step 12. Generation 2: compare and form the next population

Add the objective scores in each population, then divide by its number of individuals.

\overline f_{old}=\frac{64+169+169+64}{4}=\frac{466}{4}=116.5

\overline f_{new}=\frac{144+144+144+144}{4}=\frac{576}{4}=144

Best objective: 169 → 144. Higher is better. The next population is [12, 12, 12, 12]. No elitism is imposed, so the best previous individual is not automatically protected.

Final answer. After two generations the ordered population is [12, 12, 12, 12]. Best final objective = 144 at x = [12].