## Definition **Genetic Algorithms (GA)** are population-based metaheuristics inspired by biological evolution. Maintain a population of candidate solutions ("chromosomes"); produce new solutions via *selection*, *crossover*, and *mutation*; let fitter solutions propagate. Introduced by John Holland (1975). ## The Algorithm ``` initialise population of N random solutions evaluate fitness of each repeat: select parents biased by fitness crossover pairs of parents to produce children mutate children with small probability evaluate children's fitness replace least-fit population members with children until: convergence or budget exhausted return best solution found ``` ## The Three Operations ### Selection Pick parents weighted by fitness. Methods: - **Roulette wheel.** Probability proportional to fitness. - **Tournament.** Pick $k$ candidates; the fittest wins. - **Rank selection.** Probability based on fitness rank, not raw value. ### Crossover Combine two parent chromosomes to produce children. For bit-string encoding: - **One-point crossover.** Split at a random position; swap tails. - **Two-point crossover.** Two split points. - **Uniform crossover.** Each bit independently from one parent. For permutation encoding (TSP, scheduling), specialised crossovers preserve permutation property (OX, PMX, ERX). ### Mutation Random small perturbations. Bit flip; insert/delete; swap positions. Probability typically low (1-5% per gene). Mutation maintains diversity and explores beyond what crossover can reach. ## Population Diversity Premature convergence — when population collapses to similar solutions — is the major failure mode. Mitigations: - **Niching / speciation.** Encourage subpopulations to maintain diversity. - **Elitism + diversity injection.** Keep some best solutions; randomly replace others. - **Restart** if convergence happens too fast. ## Hyperparameters - **Population size** (50-500). - **Crossover rate** (0.6-0.9). - **Mutation rate** (0.01-0.1). - **Selection pressure.** - **Number of generations.** GA performance is highly hyperparameter-sensitive. ## When GA Wins - **No gradient available** (black-box, non-differentiable objectives). - **Combinatorial problems** with rich structure: scheduling, routing, layout. - **Multi-objective problems** (NSGA-II, MOEA/D find Pareto fronts). - **Constraint-satisfaction-like problems.** ## When GA Loses - **Smooth differentiable problems** — gradient methods win easily. - **Well-structured combinatorial problems** with known polynomial-time algorithms. - **Continuous optimisation** at large dimensions — Bayesian optimisation, CMA-ES often beat GAs. ## Variants - **CMA-ES** (Covariance Matrix Adaptation Evolution Strategy). State-of-the-art for continuous black-box optimisation. Adapts the search distribution's covariance. - **NSGA-II** for multi-objective optimisation. - **Genetic Programming** (Koza) — evolve programs / expression trees. - **Differential Evolution.** Population-based, well-suited for continuous problems. ## Why GA Is Often Beaten GAs are general-purpose; specialised algorithms exploiting problem structure usually win on specific problems. The strength is *generality*: minimal assumptions, applies to anything. ## Related - [[Simulated Annealing]] - [[Tabu Search]] - [[Particle Swarm Optimization]] - [[Combinatorial Optimization]]