Genetic Algorithms Explained

A beginner-friendly guide to understanding genetic algorithms.

🧬 What is a Genetic Algorithm?

A genetic algorithm (GA) is an optimization technique inspired by natural evolution. Just like species evolve over generations to become better adapted to their environment, a GA evolves solutions to become better at solving a problem.

The Biology Analogy

Biology	Genetic Algorithm
Species	Solutions (tours)
Individual	One solution
DNA	Solution representation
Fitness	Solution quality
Reproduction	Crossover (combining solutions)
Mutation	Random changes
Natural Selection	Selecting better solutions
Evolution	Iterative improvement

🔄 How Does It Work?

The Evolution Cycle

1. CREATE
   ↓
2. EVALUATE
   ↓
3. SELECT
   ↓
4. CROSSOVER
   ↓
5. MUTATE
   ↓
6. REPEAT

Let's understand each step with examples:

Step 1: Create Initial Population

Start with random solutions (tours):

Population of 5 tours visiting 5 cities:

Tour 1: A → B → C → D → E → A (Distance: 1500km)
Tour 2: B → D → A → C → E → B (Distance: 1200km) ← Better!
Tour 3: C → A → D → B → E → C (Distance: 1800km)
Tour 4: E → C → B → A → D → E (Distance: 1350km)
Tour 5: D → E → A → B → C → D (Distance: 1650km)

Step 2: Evaluate Fitness

Measure how good each solution is:

Fitness = 1 / Distance
(Shorter distance = Higher fitness = Better solution)

Tour 1: Fitness = 1/1500 = 0.000667
Tour 2: Fitness = 1/1200 = 0.000833 ← Highest fitness!
Tour 3: Fitness = 1/1800 = 0.000556
Tour 4: Fitness = 1/1350 = 0.000741
Tour 5: Fitness = 1/1650 = 0.000606

Step 3: Select Parents

Choose better solutions more often (like natural selection):

Selection Probability (Roulette Wheel):

Tour 2: 25% chance ████████
Tour 4: 22% chance ███████
Tour 1: 20% chance ██████
Tour 5: 18% chance █████
Tour 3: 15% chance ████

Better tours have higher chance of being selected as parents!

Step 4: Crossover (Reproduction)

Combine two parents to create offspring:

Parent 1: [A → B → C → D → E]
Parent 2: [C → A → E → D → B]

        ↓ Order Crossover ↓

Offspring: [A → B → E → D → C]
(inherits [A,B] from parent1, fills rest with parent2's order)

Why crossover works:

• Offspring inherits good traits from both parents
• Creates new combinations
• Explores solution space efficiently

Step 5: Mutation

Randomly change some solutions to maintain diversity:

Before mutation: [A → B → C → D → E]
↕ Swap
After mutation: [A → D → C → B → E]

Why mutation works:

• Prevents getting stuck in local optima
• Introduces new genetic material
• Helps explore uncharted territory

Step 6: Repeat

Continue for many generations:

Generation 1: Best = 2000km
Generation 10: Best = 1500km ↓ Improving
Generation 20: Best = 1200km ↓
Generation 50: Best = 980km ↓
Generation 100: Best = 975km ↓
Generation 150: Best = 975km ← Converged (no improvement)

🎯 Why Does It Work?

1. Selection Pressure

Better solutions reproduce more → Good traits spread through population

Generation 1: Mix of good and bad tours
↓
Generation 10: More good tours, fewer bad ones
↓
Generation 50: Mostly good tours
↓
Generation 100: Excellent tours dominate

2. Exploration vs Exploitation

• Crossover → Exploits good solutions (combines what works)
• Mutation → Explores new possibilities (tries random changes)
• Balance → Find best solution without getting stuck

3. Population Diversity

Multiple solutions evolving in parallel:

• Different approaches tried simultaneously
• Best ideas naturally rise to the top
• Maintains backup options

📊 Visual Example: Evolution in Action

Generation 0 (Random)

Cost Distribution:
1000-1500km: ▓▓▓
1500-2000km: ▓▓▓▓▓▓
2000-2500km: ▓▓▓▓
2500-3000km: ▓▓

Average: 1800km
Best: 1200km

Generation 50 (Evolved)

Cost Distribution:
1000-1500km: ▓▓▓▓▓▓▓▓
1500-2000km: ▓▓
2000-2500km:
2500-3000km:

Average: 1100km ← Much better!
Best: 985km

🔧 Key Parameters

Population Size

Small (10): Fast but limited exploration
Medium (50): Good balance
Large (200): Thorough but slow

For TSP: Population = 1-2× number of cities

Mutation Rate

Low (1%): Stable, exploits current solutions
Medium (5%): Good balance
High (20%): Chaotic, lots of exploration

For TSP: 2-5% works well

Generations

Few (100): Quick but rough solution
Many (5000): Better solution, slower

Rule: Run until convergence (no improvement for N generations)

🎓 Learning Exercise

Try to predict what happens:

Scenario 1: Very high mutation rate (50%)

Answer: Population becomes random again!
Mutation destroys good solutions.

Scenario 2: No mutation at all (0%)

Answer: Gets stuck!
Can't explore new possibilities, misses better solutions.

Scenario 3: Only keep best solution (no diversity)

Answer: Converges too fast to local optimum!
Needs population diversity to escape.

🆚 GA vs Other Approaches

Genetic Algorithm

✅ Pros:

• Finds good solutions for complex problems
• Doesn't need problem-specific knowledge
• Naturally parallel
• Handles large search spaces

❌ Cons:

• No guarantee of optimal solution
• Slower than specialized algorithms
• Requires parameter tuning

Brute Force (Try all combinations)

✅ Pros: Guaranteed optimal ❌ Cons: Impossible for 500 cities (500! combinations)

Greedy (Nearest neighbor)

✅ Pros: Very fast ❌ Cons: Often poor quality

GA Sweet Spot

Best for problems that are:

• Too complex for brute force
• Where approximation is acceptable
• No known efficient exact algorithm

🔍 Real-World Applications

Genetic algorithms are used in:

• Route Optimization (TSP, vehicle routing)
• Scheduling (job shop, timetabling)
• Design (aircraft, antennas, circuits)
• Machine Learning (hyperparameter tuning)
• Game AI (evolving strategies)
• Art (evolutionary art, music composition)

📚 Further Reading

• TSP Overview - Learn about the specific problem
• Architecture Deep Dive - See how it's implemented
• Custom Operators Tutorial - Create your own
• Performance Tuning - Optimize your GA

🧪 Try It Yourself

Run the algorithm and watch the cost decrease:

python main.py

Notice how:

1. Initial solutions are random and poor
2. Cost steadily decreases
3. Improvement slows as it converges
4. Eventually stabilizes (converged)

This is evolution in action! 🧬

---

Next: Understand the specific problem → TSP Overview