Intelligent Systems II · M2 · read

Two generations including roulette selection

3. Genetic algorithms

Candidate → fitness → encoding → selection → crossover → mutation → two complete generations.

Maximise $f(x)=x(15-x)+1$ 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, 5, 9, 12]. Use 4 bits, crossover after bit 2, pair mating-pool slots 1–2 and 3–4. Flip bit 4 of children [2, 4] in every generation. Replace the whole population with the four children; no elitism.

Generation	Selection instruction
1	Random draws [0.1, 0.4, 0.65, 0.9]
2	Random draws [0.2, 0.4, 0.6, 0.95]

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 × (15 − 2) + 1 = 27
2	5	0101	5 × (15 − 5) + 1 = 51
3	9	1001	9 × (15 − 9) + 1 = 55
4	12	1100	12 × (15 − 12) + 1 = 37

Step 2. Generation 1: calculate roulette intervals

Fitness weights are nonnegative. The nonnegative objective itself is the fitness in this maximisation example.

\sum F=27+51+55+37\approx170

Individual	Probability: weight ÷ total	Cumulative: old boundary + probability
1	27 ÷ 170 ≈ 0.158823529	0 + 0.158823529 ≈ 0.158823529
2	51 ÷ 170 ≈ 0.3	0.158823529 + 0.3 ≈ 0.458823529
3	55 ÷ 170 ≈ 0.323529412	0.458823529 + 0.323529412 ≈ 0.782352941
4	37 ÷ 170 ≈ 0.217647059	0.782352941 + 0.217647059 ≈ 1

Step 3. Generation 1: use the supplied random draws

Random draw	Interval containing it	Selected individual	Selected x
0.1	0 ≤ 0.1 < 0.158823529	1	2
0.4	0.158823529 ≤ 0.4 < 0.458823529	2	5
0.65	0.458823529 ≤ 0.65 < 0.782352941	3	9
0.9	0.782352941 ≤ 0.9 < 1	4	12

Intervals are left-closed and right-open, except that a draw of exactly 1 selects the last interval. No draw here is on a boundary. Draws select parents with replacement: selecting a parent once does not remove it. Calculations use unrounded weights; the table displays rounded numbers.

Step 4. 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	00 \| 10	01 \| 01	0001	0110
3 & 4	10 \| 01	11 \| 00	1000	1101

Step 5. Generation 1: mutate only the specified bits

Child	Before mutation	Instruction	After mutation
1	0001	No mutation	0001
2	0110	Flip bit 4	0111
3	1000	No mutation	1000
4	1101	Flip bit 4	1100

Step 6. Generation 1: decode and evaluate every child

Chromosome	Decode using place values	Objective
0001	0 + 0 + 0 + 1 = 1	1(15−1)+1 = 15
0111	0 + 4 + 2 + 1 = 7	7(15−7)+1 = 57
1000	8 + 0 + 0 + 0 = 8	8(15−8)+1 = 57
1100	8 + 4 + 0 + 0 = 12	12(15−12)+1 = 37

Step 7. 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{27+51+55+37}{4}=\frac{170}{4}=42.5

\overline f_{new}=\frac{15+57+57+37}{4}=\frac{166}{4}=41.5

Best objective: 55 → 57. Higher is better. The next population is [1, 7, 8, 12]. No elitism is imposed, so the best previous individual is not automatically protected.

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

Individual	x	Binary	Objective calculation
1	1	0001	1 × (15 − 1) + 1 = 15
2	7	0111	7 × (15 − 7) + 1 = 57
3	8	1000	8 × (15 − 8) + 1 = 57
4	12	1100	12 × (15 − 12) + 1 = 37

Step 9. Generation 2: calculate roulette intervals

Fitness weights are nonnegative. The nonnegative objective itself is the fitness in this maximisation example.

\sum F=15+57+57+37\approx166

Individual	Probability: weight ÷ total	Cumulative: old boundary + probability
1	15 ÷ 166 ≈ 0.090361446	0 + 0.090361446 ≈ 0.090361446
2	57 ÷ 166 ≈ 0.343373494	0.090361446 + 0.343373494 ≈ 0.43373494
3	57 ÷ 166 ≈ 0.343373494	0.43373494 + 0.343373494 ≈ 0.777108434
4	37 ÷ 166 ≈ 0.222891566	0.777108434 + 0.222891566 ≈ 1

Step 10. Generation 2: use the supplied random draws

Random draw	Interval containing it	Selected individual	Selected x
0.2	0.090361446 ≤ 0.2 < 0.43373494	2	7
0.4	0.090361446 ≤ 0.4 < 0.43373494	2	7
0.6	0.43373494 ≤ 0.6 < 0.777108434	3	8
0.95	0.777108434 ≤ 0.95 < 1	4	12

Step 11. 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	01 \| 11	01 \| 11	0111	0111
3 & 4	10 \| 00	11 \| 00	1000	1100

Step 12. Generation 2: mutate only the specified bits

Child	Before mutation	Instruction	After mutation
1	0111	No mutation	0111
2	0111	Flip bit 4	0110
3	1000	No mutation	1000
4	1100	Flip bit 4	1101

Step 13. Generation 2: decode and evaluate every child

Chromosome	Decode using place values	Objective
0111	0 + 4 + 2 + 1 = 7	7(15−7)+1 = 57
0110	0 + 4 + 2 + 0 = 6	6(15−6)+1 = 55
1000	8 + 0 + 0 + 0 = 8	8(15−8)+1 = 57
1101	8 + 4 + 0 + 1 = 13	13(15−13)+1 = 27

Step 14. 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{15+57+57+37}{4}=\frac{166}{4}=41.5

\overline f_{new}=\frac{57+55+57+27}{4}=\frac{196}{4}=49

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

Final answer. After two generations the ordered population is [7, 6, 8, 13]. Best final objective = 57 at x = [7, 8].