Genetic Algorithms — Evolution-Based Optimisation
- Five components: representation, fitness function, selection, crossover, mutation. Getting all five right for your problem is the engineering challenge.
- Elitism: always carry the best solution forward — prevents regression.
- For permutation problems (TSP): order crossover or PMX crossover preserves the permutation constraint.
Genetic algorithms (GA) are a class of evolutionary computation algorithms inspired by natural selection. They excel at combinatorial optimisation problems where exact methods are infeasible: travelling salesman, job shop scheduling, neural network architecture search, game-playing strategy design.
GAs do not guarantee finding the global optimum (they are metaheuristics), but they find good solutions to NP-hard problems where exact algorithms would take astronomical time. The travelling salesman problem with 100 cities has 100!/2 ≈ 10^157 possible routes — exhaustive search is impossible, but GAs routinely find solutions within 1-2% of optimal.
Core Components
Every genetic algorithm has five components: representation (how solutions are encoded), fitness function (how good is each solution), selection (which solutions reproduce), crossover (how two parents combine), and mutation (random perturbation to maintain diversity).
import random def genetic_algorithm(target: str, pop_size: int = 200, mutation_rate: float = 0.01, max_generations: int = 1000) -> str: """Classic: evolve a string to match the target.""" chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz !' n = len(target) def fitness(s): return sum(a==b for a,b in zip(s, target)) def random_individual(): return ''.join(random.choice(chars) for _ in range(n)) def crossover(a, b): pt = random.randint(0, n) return a[:pt] + b[pt:] def mutate(s): return ''.join(c if random.random() > mutation_rate else random.choice(chars) for c in s) population = [random_individual() for _ in range(pop_size)] for gen in range(max_generations): population.sort(key=fitness, reverse=True) if fitness(population[0]) == n: print(f'Solved in generation {gen}') return population[0] # Select top 50%, breed next generation survivors = population[:pop_size//2] children = [mutate(crossover(random.choice(survivors), random.choice(survivors))) for _ in range(pop_size//2)] population = survivors + children return population[0] result = genetic_algorithm('Hello World') print(f'Result: {result}')
Result: Hello World
Selection Strategies
Tournament selection: Pick k random individuals, choose the best. Computationally efficient, tunable selection pressure via k.
Roulette wheel (fitness proportionate): Select with probability proportional to fitness. Works poorly if one individual has much higher fitness than others (it dominates).
Rank selection: Sort by fitness, assign probability by rank not absolute fitness. More robust to fitness scale differences.
Elitism: Always copy the best individual(s) to the next generation unchanged. Prevents losing the best solution found.
Travelling Salesman Example
The TSP is the canonical GA benchmark. Chromosome = permutation of cities. Crossover must preserve the permutation property (no city visited twice). Fitness = total route distance.
import random, math def tsp_fitness(route, cities): return 1 / sum(math.dist(cities[route[i]], cities[route[(i+1)%len(route)]]) for i in range(len(route))) def order_crossover(p1, p2): """Order crossover (OX) — preserves relative order, no duplicates.""" n = len(p1) a, b = sorted(random.sample(range(n), 2)) child = [None] * n child[a:b] = p1[a:b] remaining = [x for x in p2 if x not in child] j = 0 for i in range(n): if child[i] is None: child[i] = remaining[j]; j += 1 return child # Quick demo with 5 cities cities = {i: (random.uniform(0,10), random.uniform(0,10)) for i in range(5)} route1 = list(range(5)) random.shuffle(route1) route2 = list(range(5)) random.shuffle(route2) child = order_crossover(route1, route2) print(f'Parent 1: {route1}') print(f'Parent 2: {route2}') print(f'Child: {child} (no duplicates: {len(set(child))==5})')
Parent 2: [1, 3, 0, 2, 4]
Child: [2, 0, 1, 3, 4] (no duplicates: True)
🎯 Key Takeaways
- Five components: representation, fitness function, selection, crossover, mutation. Getting all five right for your problem is the engineering challenge.
- Elitism: always carry the best solution forward — prevents regression.
- For permutation problems (TSP): order crossover or PMX crossover preserves the permutation constraint.
- GAs trade optimality for tractability — good solutions to NP-hard problems without exponential time.
- Hyperparameters: population size (50-500), mutation rate (0.001-0.1), crossover rate (0.6-0.9). Problem-specific tuning required.
Interview Questions on This Topic
- QWhat are the five components of a genetic algorithm?
- QWhy can't you use standard crossover for TSP and what do you use instead?
- QHow does elitism prevent regression in genetic algorithms?
- QWhen would you choose a genetic algorithm over gradient descent?
Frequently Asked Questions
When should I use genetic algorithms vs simulated annealing vs gradient descent?
Gradient descent: differentiable objective, continuous search space, need global optimum (with restarts). Simulated annealing: single solution, continuous or discrete, simple implementation. Genetic algorithms: combinatorial/discrete search space, multi-modal fitness landscape, black-box objective (no gradient available), naturally parallel. TSP/scheduling: GA or SA. Neural network training: gradient descent (Adam, SGD).
Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.