Genetic algorithms (GAs) are optimization and search algorithms inspired by biological evolution, introduced by John Holland in the 1970s. A population of candidate solutions (individuals) is encoded as chromosomes—strings of bits, numbers, or other representations—and evolved through generations using operators that mimic selection, crossover (recombination), and mutation. At each generation, individuals are evaluated by a fitness function, and those with higher fitness are more likely to reproduce and pass their "genes" to the next generation.
The three core operators drive evolution: Selection preferentially copies high-fitness individuals (using methods like tournament selection, roulette wheel, or rank-based selection). Crossover combines segments of two parent chromosomes to produce offspring, analogous to sexual recombination, allowing good building blocks (schemata) to combine. Mutation randomly alters individual genes with a small probability, preventing premature convergence to local optima and maintaining genetic diversity. The interplay of these operators allows GAs to search complex, discontinuous, multi-modal fitness landscapes that gradient-based optimizers cannot navigate.
This simulator evolves a population of solutions toward a target, showing fitness progression over generations, genetic diversity metrics, and the fitness landscape. You can tune population size, crossover rate, mutation rate, and selection pressure to observe phase transitions between diversity-preserving exploration and fitness-maximizing exploitation—the central tension in evolutionary computation. GAs have solved scheduling problems, designed antennas, evolved neural network architectures, and optimized drug molecules.
How is a genetic algorithm different from gradient descent?
Gradient descent requires the fitness (loss) function to be differentiable and navigates toward local optima by following the gradient direction. It struggles with discontinuous functions, functions with many local minima, and problems where solutions cannot be naturally represented as continuous vectors. Genetic algorithms make no assumptions about the fitness landscape: they can handle discrete representations, discontinuous and noisy functions, and multi-modal landscapes with many local optima. GAs explore many regions of the search space simultaneously through their population, trading the efficiency of gradient descent for greater robustness to complex landscapes.
What is the schema theorem and why does it matter?
Holland's schema theorem provides a theoretical explanation for why GAs work. A schema is a pattern that matches a subset of chromosomes (e.g., 1**0* matches all 5-bit strings starting with 1 and having 0 in position 4). The theorem states that schemata with above-average fitness, short defining length (bits close together), and low order (few fixed bits) receive exponentially increasing representation over generations. This Building Block Hypothesis suggests GAs implicitly search for and combine short, low-order, high-fitness patterns—the building blocks of good solutions—even though no explicit search for building blocks is coded.
What is the exploration-exploitation trade-off in genetic algorithms?
Exploration means searching new, unvisited regions of the solution space (maintaining diversity); exploitation means refining the best solutions found so far (converging). High mutation rate and low selection pressure increase exploration; low mutation and high selection pressure increase exploitation. Too much exploitation causes premature convergence—the population converges on a local optimum before the global optimum is found. Too much exploration prevents convergence to any good solution. Adaptive GAs adjust mutation rate based on diversity metrics, and niching techniques (fitness sharing, crowding) maintain multiple diverse subpopulations simultaneously exploring different fitness peaks.
Crossover combines segments of two parent chromosomes, potentially creating offspring with a combination of good features from each parent that neither possessed alone. In a multi-modal landscape, two individuals on different local optima may produce offspring near a better optimum neither parent could reach by mutation alone. This is analogous to sexual reproduction in biology: recombination shuffles genetic material, allowing beneficial mutations from separate lineages to be combined into a single individual—a process far faster than waiting for all mutations to occur in a single lineage. Crossover's effectiveness depends on the encoding representing problem structure (linkage learning).
GAs and related evolutionary algorithms have achieved notable engineering successes: NASA's ST5 spacecraft antenna was evolved by a GA, producing a bent-wire shape that no human designer would have conceived but outperformed conventional designs. GAs have optimized protein folding, drug molecule design, VLSI circuit layouts, financial trading strategies, and airfoil shapes. Google's AutoML uses evolutionary methods to search neural network architectures. In operations research, GAs solve vehicle routing, job scheduling, and timetabling problems that are NP-hard and intractable for exact methods at real-world scale.