Genetic Algorithms Explained: Optimization Inspired by Natural Evolution

How Genetic Algorithms Work

A genetic algorithm follows a cycle that mirrors biological evolution. Initialization creates a random population of candidate solutions, each encoded as a chromosome (typically a string of bits, numbers, or symbols). Fitness evaluation scores each individual using a fitness function that measures how well the solution solves the problem. Selection chooses individuals for reproduction, with fitter individuals having a higher probability of being selected. Crossover combines two parent chromosomes to produce offspring that inherit traits from both parents. Mutation randomly alters individual genes with a small probability, introducing new genetic material. The offspring form the next generation, and the cycle repeats.

The population size, number of generations, crossover rate, and mutation rate are parameters that significantly affect performance. Typical populations contain 50 to 500 individuals, crossover rates range from 0.6 to 0.9, and mutation rates range from 0.001 to 0.05. Too much mutation disrupts good solutions; too little leads to premature convergence on suboptimal solutions. Tuning these parameters is both an art and an ongoing area of research.

Key Components in Detail

Representation

The choice of chromosome encoding significantly impacts performance. Binary encoding represents solutions as strings of 0s and 1s, which is simple and works well for problems with discrete variables. Real-valued encoding uses floating-point numbers, which is natural for continuous optimization problems. Permutation encoding represents solutions as orderings, which is appropriate for scheduling and routing problems like the traveling salesman problem. The encoding must allow meaningful crossover and mutation operations that produce valid offspring.

Selection Methods

Tournament selection randomly picks a small group (typically 2 to 7 individuals) and selects the fittest from that group. It is simple, efficient, and allows tuning selection pressure by adjusting the tournament size. Roulette wheel selection assigns each individual a slice of a roulette wheel proportional to its fitness; spinning the wheel selects individuals probabilistically. Rank-based selection ranks individuals by fitness and assigns selection probability based on rank rather than raw fitness, avoiding problems when fitness values have extreme ranges.

Crossover Operators

Single-point crossover picks a random position and swaps the segments after that point between two parents. Two-point crossover picks two positions and swaps the segment between them. Uniform crossover independently decides for each gene position whether to take the gene from parent A or parent B. For permutation problems, specialized crossover operators like order crossover (OX) and partially matched crossover (PMX) preserve the validity of orderings.

Mutation Operators

For binary encoding, bit flip mutation toggles a random bit. For real-valued encoding, Gaussian mutation adds a small random value drawn from a normal distribution. For permutation encoding, swap mutation exchanges two randomly chosen positions, and inversion mutation reverses a random segment. Mutation prevents the population from losing genetic diversity and getting stuck at local optima.

Advantages and Limitations

Genetic algorithms have several compelling advantages. They require no gradient information, making them applicable to problems with discontinuous, noisy, or non-differentiable fitness landscapes. They naturally explore multiple regions of the search space simultaneously through the population, reducing the risk of getting trapped in local optima. They are highly parallelizable, since fitness evaluations for different individuals are independent. They can handle mixed types of variables (continuous, discrete, categorical) within the same framework.

The limitations are also significant. GAs provide no guarantee of finding the global optimum. They require many fitness evaluations, which can be expensive if each evaluation involves running a complex simulation. They can converge prematurely if the population loses diversity. The choice of encoding, operators, and parameters significantly affects performance, and there is no universal set of good choices. For problems where gradient-based optimization is applicable, methods like gradient descent are typically much faster and more reliable.

Real-World Applications

Engineering design uses GAs to optimize complex structures. Antenna designs evolved by NASA for the ST5 spacecraft mission outperformed human-designed antennas because the GA explored unconventional shapes that engineers would not have considered. Automotive companies use GAs to optimize crash structures, aerodynamic profiles, and engine timing parameters.

Scheduling problems, from university timetabling to airline crew scheduling to manufacturing job shop scheduling, are natural GA applications. These problems involve many constraints and a vast number of possible arrangements, making exhaustive search impossible and greedy heuristics unreliable.

Machine learning uses GAs for feature selection (choosing which input variables to include in a model), hyperparameter tuning (finding optimal learning rates, layer sizes, and other settings), and neural architecture search (designing the structure of neural networks). These applications leverage the GA ability to navigate large, discrete search spaces where gradient information is unavailable.

Financial modeling applies GAs to portfolio optimization, trading strategy development, and risk management. The ability to optimize over complex, noisy objective functions with multiple competing objectives makes GAs well-suited for financial applications where traditional optimization may fail.

Evolutionary Computing Beyond GAs

Genetic algorithms are part of a broader family of evolutionary computing methods. Evolution strategies focus on continuous optimization using self-adaptive mutation step sizes. Genetic programming evolves entire programs or mathematical expressions rather than fixed-length chromosomes, enabling automatic program synthesis. Differential evolution uses vector differences between population members to drive mutation, excelling on continuous optimization benchmarks. Particle swarm optimization, inspired by bird flocking behavior rather than evolution, maintains a swarm of candidate solutions that move through the search space guided by personal and collective best positions.