Genetic Algorithm

🔥 Vibe Prompt

"Use Genetic Algorithm to solve TSP with 20 cities. Population 100, 200 generations. Show the best route evolution."

import random, math

def genetic_algorithm(cities, pop_size=100, generations=200, mutation_rate=0.01):
    n = len(cities)
    def dist(i, j): return math.sqrt((cities[i][0]-cities[j][0])**2 + (cities[i][1]-cities[j][1])**2)
    def fitness(route): return -sum(dist(route[i], route[(i+1)%n]) for i in range(n))
    
    pop = [random.sample(range(n), n) for _ in range(pop_size)]
    
    for gen in range(generations):
        scored = [(fitness(ind), ind) for ind in pop]
        scored.sort(reverse=True)
        pop = [ind for _, ind in scored]
        
        next_pop = pop[:2]  # Elitism
        while len(next_pop) < pop_size:
            p1, p2 = random.choices(pop[:pop_size//2], k=2)
            a, b = sorted(random.sample(range(n), 2))
            child = [-1] * n
            child[a:b] = p1[a:b]
            remaining = [x for x in p2 if x not in child]
            for i in range(n):
                if child[i] == -1:
                    child[i] = remaining.pop(0)
            if random.random() < mutation_rate:
                i, j = random.sample(range(n), 2)
                child[i], child[j] = child[j], child[i]
            next_pop.append(child)
        pop = next_pop
    
    return pop[0], -fitness(pop[0])

Chapter Summary

Understand core concepts and principles
Master implementation methods and techniques
Familiar with common issues and solutions
Able to apply in real projects

Implementation Example

Basic Example

# This section provides a complete implementation example

Steps

Setup: Configure development environment
Data: Prepare required data
Implementation: Build core functionality
Testing: Verify correctness
Optimization: Improve performance

Common Errors

| Error Type | Cause | Solution | |------------|-------|----------| | Compilation | Syntax | Check code syntax | | Runtime | Environment | Verify dependencies installed | | Logic | Algorithm | Step-by-step debugging | | Performance | Efficiency | Use profilers |

Code Example

import sys

def main():
    print("Hello, World!")

if __name__ == "__main__":
    main()

References

Official documentation
API reference
Open source examples
Community discussions

What Is a Genetic Algorithm?

Genetic Algorithms (GA) are inspired by natural selection — the fittest individuals survive and reproduce.

The GA Cycle

1. INITIALIZE → Create random population
       ↓
2. EVALUATE → Calculate fitness for each individual
       ↓
3. SELECT → Choose parents based on fitness
       ↓
4. CROSSOVER → Combine parents to create offspring
       ↓
5. MUTATE → Randomly modify offspring
       ↓
6. REPLACE → New generation replaces old
       ↓
   (repeat from step 2 until convergence)

Key Components

| Component | What It Does | Example | |-----------|-------------|---------| | Chromosome | Represents a solution | Binary string, permutation, real vector | | Gene | A single parameter | Bit, city index, weight value | | Fitness | How good the solution is | Cost function (lower = better) | | Population | Set of candidate solutions | 100 chromosomes | | Selection | Picks parents for breeding | Tournament, roulette wheel | | Crossover | Combines two parents | Single-point, uniform, PMX | | Mutation | Random changes to offspring | Bit flip, swap, Gaussian noise |

Python Implementation

import random

class GeneticAlgorithm:
    def __init__(self, pop_size=100, mutation_rate=0.01, crossover_rate=0.8):
        self.pop_size = pop_size
        self.mutation_rate = mutation_rate
        self.crossover_rate = crossover_rate
    
    def evolve(self, fitness_func, gene_pool, chrom_length, generations=100):
        """Evolve a population over multiple generations."""
        # Initialize random population
        population = [
            [random.choice(gene_pool) for _ in range(chrom_length)]
            for _ in range(self.pop_size)
        ]
        
        for gen in range(generations):
            # Evaluate fitness
            fitness = [fitness_func(ind) for ind in population]
            
            # Track best
            best_idx = fitness.index(min(fitness))
            best_fitness = fitness[best_idx]
            best_individual = population[best_idx].copy()
            
            if gen % 20 == 0:
                print(f"Generation {gen}: best fitness = {best_fitness:.4f}")
            
            # Create next generation
            new_population = []
            
            # Elitism: keep the best
            new_population.append(best_individual)
            
            while len(new_population) < self.pop_size:
                # Selection (tournament)
                parent1 = self._tournament_select(population, fitness)
                parent2 = self._tournament_select(population, fitness)
                
                # Crossover
                if random.random() < self.crossover_rate:
                    child1, child2 = self._crossover(parent1, parent2)
                else:
                    child1, child2 = parent1.copy(), parent2.copy()
                
                # Mutation
                self._mutate(child1)
                self._mutate(child2)
                
                new_population.extend([child1, child2])
            
            population = new_population[:self.pop_size]
        
        return best_individual, best_fitness
    
    def _tournament_select(self, pop, fitness, k=3):
        idx = random.sample(range(len(pop)), k)
        best = min(idx, key=lambda i: fitness[i])
        return pop[best].copy()
    
    def _crossover(self, p1, p2):
        """Single-point crossover."""
        point = random.randint(1, len(p1) - 1)
        c1 = p1[:point] + p2[point:]
        c2 = p2[:point] + p1[point:]
        return c1, c2
    
    def _mutate(self, chrom):
        """Bit-flip mutation."""
        for i in range(len(chrom)):
            if random.random() < self.mutation_rate:
                chrom[i] = 1 - chrom[i]

# Example: Maximize sum of bits (MAX-ONE problem)
def fitness_max_one(chrom):
    return -sum(chrom)

ga = GeneticAlgorithm(pop_size=100, mutation_rate=0.01)
best, best_fit = ga.evolve(
    fitness_func=fitness_max_one,
    gene_pool=[0, 1],
    chrom_length=50,
    generations=200
)

print(f"Best: {sum(best)} / 50 ones, Fitness: {best_fit}")

Selection Methods

| Method | How It Works | Best For | |--------|-------------|----------| | Tournament | Pick k random, keep the best | Simple, prevents premature convergence | | Roulette wheel | Probability proportional to fitness | When fitness is clearly ranked | | Rank-based | Probability based on rank, not raw fitness | Avoids domination by outliers |

Summary

Genetic Algorithms evolve solutions through selection, crossover, and mutation — mimicking natural evolution.

Key takeaways: | GA cycle: initialize → evaluate → select → crossover → mutate → replace | | Chromosome = candidate solution; Fitness = how good it is | | Selection: tournament (k=3) is simple and effective | | Crossover (80% rate): combines two parents into two children | | Mutation (1% rate): random bit flips prevent premature convergence | | Elitism: keep the best individual from each generation | | MAX-ONE: maximize the number of 1s in a binary string | | GA works for any problem with a fitness function |

Next Chapter: Simulated Annealing

The next chapter covers Simulated Annealing for optimization.