Simple Genetic Algorithm Numerical Example
Problem Setup
Objective: Find the maximum value of f(x) = x² where x ∈ [0, 31] Encoding: 5-bit binary
strings (can represent 0-31) Population Size: 4 Generations: 3
Generation 0 (Initial Population)
Step 1: Initialize Random Population
Individual Binary Decimal (x) Fitness f(x) = x²
1 01101 13 169
2 11000 24 576
3 01000 8 64
4 10110 22 484
Total Fitness: 169 + 576 + 64 + 484 = 1293
Check for binary conversion:
01101 → 13:
(i) 0×2⁴ + 1×2³ + 1×2² + 0×2¹ + 1×2⁰
(ii) 0×16 + 1×8 + 1×4 + 0×2 + 1×1
(iii) 0 + 8 + 4 + 0 + 1 = 13 ✓
11010 → 26:
(i) 1×2⁴ + 1×2³ + 0×2² + 1×2¹ + 0×2⁰
(ii) 1×16 + 1×8 + 0×4 + 1×2 + 0×1
(iii) 16 + 8 + 0 + 2 + 0 = 26 ✓
To convert 13 into binary:
1. Divide 13 by 2:
o 13 ÷ 2 = 6 remainder 1
2. Divide 6 by 2:
o 6 ÷ 2 = 3 remainder 0
3. Divide 3 by 2:
o 3 ÷ 2 = 1 remainder 1
4. Divide 1 by 2:
o 1 ÷ 2 = 0 remainder 1
Now read the remainders from bottom to top:
13 in binary = 1101
Step 2: Selection (Roulette Wheel)
Calculate selection probabilities:
• Individual 1: 169/1293 = 0.131 (13.1%)
• Individual 2: 576/1293 = 0.445 (44.5%)
• Individual 3: 64/1293 = 0.049 (4.9%)
• Individual 4: 484/1293 = 0.374 (37.4%)
Cumulative Probabilities:
• Individual 1: 0.131
• Individual 2: 0.131 + 0.445 = 0.576
• Individual 3: 0.576 + 0.049 = 0.625
• Individual 4: 0.625 + 0.374 = 1.000
Random Numbers for Selection: [0.25, 0.80, 0.15, 0.60]
Selection Results:
• Random 0.25 → falls in [0, 0.576] → Select Individual 2 (11000)
• Random 0.80 → falls in [0.625, 1.000] → Select Individual 4 (10110)
• Random 0.15 → falls in [0, 0.576] → Select Individual 2 (11000)
• Random 0.60 → falls in [0.576, 0.625] → Select Individual 3 (01000)
Selected Parents: [11000, 10110, 11000, 01000]
Step 3: Crossover (Single-point, Rate = 0.7)
Random Numbers: [0.4, 0.9] (for pairs 1-2 and 3-4)
Pair 1: 11000 × 10110
• Random 0.4 < 0.7 → Crossover occurs
• Crossover point: position 3
• Parent 1: 110|00 → Child 1: 110|10 = 11010
• Parent 2: 101|10 → Child 2: 101|00 = 10100
Pair 2: 11000 × 01000
• Random 0.9 > 0.7 → No crossover
• Child 3: 11000 (unchanged)
• Child 4: 01000 (unchanged)
After Crossover: [11010, 10100, 11000, 01000]
Step 4: Mutation (Rate = 0.01)
Random Numbers for each bit:
• Individual 1 (11010): [0.005, 0.02, 0.15, 0.008, 0.25]
• Individual 2 (10100): [0.03, 0.12, 0.45, 0.08, 0.19]
• Individual 3 (11000): [0.07, 0.22, 0.33, 0.14, 0.09]
• Individual 4 (01000): [0.11, 0.06, 0.28, 0.04, 0.17]
Mutation Check (bit-by-bit):
• Individual 1 (11010):
o Bit 0: 0.005 < 0.01 → Mutate! 1→0
o Bit 1: 0.02 > 0.01 → No mutation
o Bit 2: 0.15 > 0.01 → No mutation
o Bit 3: 0.008 < 0.01 → Mutate! 1→0
o Bit 4: 0.25 > 0.01 → No mutation
o Result: 11010 → 01000
• Individual 2 (10100): All random numbers > 0.01 → No mutations
o Result: 10100 (unchanged)
• Individual 3 (11000): All random numbers > 0.01 → No mutations
o Result: 11000 (unchanged)
• Individual 4 (01000): All random numbers > 0.01 → No mutations
o Result: 01000 (unchanged)
Generation 1 Population: [01000, 10100, 11000, 01000]
Generation 1 Population Evaluation
Individual Binary Decimal (x) Fitness f(x) = x²
1 01000 8 64
2 10100 20 400
3 11000 24 576
4 01000 8 64
Total Fitness: 64 + 400 + 576 + 64 = 1104
Selection Probabilities
• Individual 1: 64/1104 = 0.058 (5.8%)
• Individual 2: 400/1104 = 0.362 (36.2%)
• Individual 3: 576/1104 = 0.522 (52.2%)
• Individual 4: 64/1104 = 0.058 (5.8%)
Cumulative Probabilities:
• Individual 1: 0.058
• Individual 2: 0.058 + 0.362 = 0.420
• Individual 3: 0.420 + 0.522 = 0.942
• Individual 4: 0.942 + 0.058 = 1.000
Random Numbers: [0.60, 0.30, 0.85, 0.45] Selected:
• 0.60 → falls in [0.420, 0.942] → Select Individual 3 (11000)
• 0.30 → falls in [0.058, 0.420] → Select Individual 2 (10100)
• 0.85 → falls in [0.420, 0.942] → Select Individual 3 (11000)
• 0.45 → falls in [0.420, 0.942] → Select Individual 3 (11000)
Selected: [11000, 10100, 11000, 11000]
Crossover
Pair 1: 11000 × 10100 (crossover at position 2)
• Child 1: 11|100 = 11100
• Child 2: 10|000 = 10000
Pair 2: 11000 × 11000 (no crossover)
• Child 3: 11000
• Child 4: 11000
After Operations: [11100, 10000, 11000, 11000]
Generation 2 Population Evaluation
Individual Binary Decimal (x) Fitness f(x) = x²
1 11100 28 784
2 10000 16 256
3 11000 24 576
4 11000 24 576
Total Fitness: 784 + 256 + 576 + 576 = 2192
Analysis of Results
Best Individual: 11100 (x = 28, f(x) = 784)
Convergence Progress:
• Generation 0: Best fitness = 576 (x = 24)
• Generation 1: Best fitness = 576 (x = 24)
• Generation 2: Best fitness = 784 (x = 28)
Key Observations:
1. The population is converging toward higher values of x
2. Individual 11100 (x = 28) represents significant improvement
3. The algorithm is successfully exploring the search space
4. Multiple copies of good solutions (11000) show convergence
Optimal Solution: The true maximum is at x = 31, f(31) = 961 Current Best: x = 28, f(28) =
784 (80% of optimal)
Mutation Process in Above Example
Overview
Mutation is the final genetic operator applied after crossover to introduce random variations and
maintain genetic diversity in the population. It prevents premature convergence and helps explore
new regions of the search space. The mutation condition uses random < mutation_rate rather than
random > mutation_rate based on fundamental probability theory and practical implementation
considerations. When we generate a random number uniformly distributed between 0 and 1, we
want exactly 1% of all generated numbers to trigger mutations. Since the random number generator
produces values in the range [0, 1), the interval [0, 0.01) represents exactly 1% of this range.
Therefore, the condition random < 0.01 correctly captures this 1% probability space. If we used
random > 0.01 instead, we would be selecting the interval (0.01, 1], which represents 99% of the
range, causing mutations to occur 99% of the time rather than the desired 1%.
Mutation Configuration
• Type: Bit-flip mutation
• Rate: 0.01 (1% probability per bit)
• Application: Applied to every bit of every individual independently
Step-by-Step Mutation Process
Input Population (After Crossover)
Individual 1: 11010
Individual 2: 10100
Individual 3: 11000
Individual 4: 01000
Mutation Algorithm
For each individual in the population:
1. Iterate through each bit position (0 to 4 for 5-bit strings)
2. Generate a random number between 0 and 1 for each bit
3. Compare with mutation rate: If random < 0.01, mutate the bit
4. Apply bit-flip: Change 0→1 or 1→0 if mutation occurs
Detailed Bit-by-Bit Analysis
Individual 1: 11010
Original bits: [1] [1] [0] [1] [0]
Bit positions: 0 1 2 3 4
Random numbers: 0.005 0.02 0.15 0.008 0.25
Mutation check: ✓ ✗ ✗ ✓ ✗
