Genetic Algorithm

🔥 Vibe Prompt

"Evolve a bitstring to match '11111111...' (64 bits). Use tournament selection, 1-point crossover, mutation."

import random

def ga(target_len=64, pop_size=100, gens=100):
    target = [1] * target_len
    
    def fitness(ind): return sum(i == t for i, t in zip(ind, target))
    def create(): return [random.randint(0,1) for _ in range(target_len)]
    
    pop = [create() for _ in range(pop_size)]
    
    for gen in range(gens):
        scores = [(fitness(ind), ind) for ind in pop]
        scores.sort(reverse=True)
        
        if scores[0][0] == target_len:
            print(f"Perfect solution at gen {gen}!")
            break
        
        new_pop = [scores[0][1], scores[1][1]]  # Elitism
        
        while len(new_pop) < pop_size:
            parents = random.choices(pop, weights=[f + 1 for f, _ in scores], k=2)
            cross = random.randint(0, target_len)
            child = parents[0][:cross] + parents[1][cross:]
            if random.random() < 0.01:
                child[random.randint(0, target_len-1)] ^= 1
            new_pop.append(child)
        pop = new_pop
        
        if gen % 20 == 0:
            print(f"Gen {gen}: best fitness = {scores[0][0]}/{target_len}")

    return max(fitness(ind) for ind in pop)

result = ga()
print(f"Final fitness: {result}/64")

Applications

Neural architecture search
Financial trading strategies
Robot controller design
Feature selection

Key Points

Understand the core concepts thoroughly
Practice with hands-on code examples
Apply knowledge to real-world problems
Review and reinforce through exercises

Further Learning

Official documentation
Open source projects on GitHub
Community forums and discussions
Related courses and tutorials

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):
        """Tournament selection: pick k random, return the best."""
        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 binary genes."""
        for i in range(len(chrom)):
            if random.random() < self.mutation_rate:
                chrom[i] = 1 - chrom[i]  # Flip 0↔1

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

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"\nBest: {best}")
print(f"Ones: {sum(best)} / 50")
print(f"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: PSO

The next chapter covers Particle Swarm Optimization.