Evolving Binary Chromosomes with a Genetic Algorithm
Problem Setup
Scenario:Maximize the number of 1s in a binary chromosome using the given initial population and specified evolution rules.
Given:A population of 4 chromosomes, each containing 6 bits. Fitness is determined by the number of 1s in each chromosome. The evolution setup specifies two crossover operations after bit 3 and one mutation on child C3 at bit 3.
Task:Evaluate the initial fitness values, rank the chromosomes by fitness, apply the specified crossover and mutation operations, and calculate the fitness of the resulting generation.
Need a quick refresher? Review Genetic Algorithm theory
Initial Population
| Data Point | Chromosome (Binary String)✎ |
|---|---|
| P1 | 101100 |
| P2 | 011011 |
| P3 | 110001 |
| P4 | 001110 |
Evolution Rules Setup
Step-by-Step Evolution
Step 1: Evaluate Fitness
| ID | Chromosomes | Fitness |
|---|---|---|
| P1 | 101100 | 3 |
| P2 | 011011 | 4 |
| P3 | 110001 | 3 |
| P4 | 001110 | 3 |
Step 2: Rank by Fitness (Descending)
| Rank | Chromosomes | Fitness |
|---|---|---|
| New #1 (P2) | 011011 | 4 |
| New #2 (P1) | 101100 | 3 |
| New #3 (P3) | 110001 | 3 |
| New #4 (P4) | 001110 | 3 |
Step 3: After Crossover
| C1 | 011100 |
| C2 | 101011 |
| C3 | 110110 |
| C4 | 001001 |
Step 4: After Mutation
| C1 | 011100 |
| C2 | 101011 |
| C3 (mutated) | 111110 |
| C4 | 001001 |
Step 5: Final Generation Fitness
| Child ID | New Chromosome | Genetics Status | Final Fitness |
|---|---|---|---|
| C1 | 011100 | Crossover | 3 |
| C2 | 101011 | Crossover | 4 |
| C3 | 111110 | Mutated | 5 |
| C4 | 001001 | Crossover | 2 |
Final Answer
Best chromosome:111110
Final fitness:5
Mutation improves C3's fitness from 4 to 5, making it the strongest chromosome in this generation. However, the One-Max target for six bits is 111111 with fitness 6, so the global optimum has not yet been reached.
Exam Takeaway
- Reorder chromosomes before applying crossover rules: When crossover rules refer to ranked positions, use the population after sorting by fitness, not the original chromosome IDs. Preserve the specified order for tied fitness values.
- Apply crossover at the exact bit boundary: A crossover after bit 3 keeps the first three bits together and exchanges the remaining bits. Mutation is a separate operation performed on the resulting offspring, not on the original parents.
- Recalculate fitness after mutation: In One-Max, flipping a 0 to 1 increases fitness by one, while flipping a 1 to 0 decreases it by one. The best chromosome in a generation is not necessarily the global optimum.