A genetic algorithm (GA) searches for good solutions by simulating evolution: a population of encoded candidates ("chromosomes") is scored by a fitness function, the fitter ones are selected as parents, and their genes are recombined (crossover) and randomly perturbed (mutation) to form the next generation. Introduced by John Holland in the 1970s, GAs are the best-known member of evolutionary computation. They need no gradients — only a way to score a candidate — which makes them a general tool for combinatorial and black-box optimization.
The encoding is the most important design decision; it determines which operators make sense and whether small genetic changes produce small changes in the solution. Binary strings suit yes/no decisions (feature selection, knapsack). Real-valued vectors suit continuous parameters. Permutations encode orderings (traveling salesman, scheduling) and need special operators so children remain valid permutations. Trees are used in genetic programming. Constraints are handled by penalty terms in the fitness, repair functions that fix invalid children, or encodings that cannot express invalid solutions.
fi / Σfj. Needs positive fitness and is distorted when one individual dominates early.Too much selection pressure causes premature convergence — the population becomes clones of one early good solution. Too little turns the GA into random search.
Crossover combines building blocks from two parents. Variants: single-point (shown), two-point, uniform (each gene from either parent with probability 0.5), blend / SBX for real values, and order crossover (OX) or PMX for permutations. Crossover rate is typically 0.6–0.9.
Mutation maintains diversity and lets the search reach genes absent from the population: bit flips with probability around 1/L for a length-L chromosome, Gaussian noise for real values, swap or inversion for permutations. Holland's schema theorem gives the intuition: short, fit gene patterns (schemata) tend to increase in frequency, as long as crossover and mutation do not break them too often.
import numpy as np
rng = np.random.default_rng(42)
n_items = 40
weights = rng.integers(1, 30, n_items)
values = rng.integers(1, 60, n_items)
capacity = weights.sum() // 3
def fitness(pop):
w = pop @ weights
v = pop @ values
return np.where(w <= capacity, v, v - 10 * (w - capacity)) # penalty for overweight
def tournament(pop, fit, k=3):
idx = rng.integers(0, len(pop), (len(pop), k))
winners = idx[np.arange(len(pop)), fit[idx].argmax(axis=1)]
return pop[winners]
def crossover(parents, rate=0.9):
kids = parents.copy()
for i in range(0, len(parents) - 1, 2):
if rng.random() < rate:
mask = rng.random(n_items) < 0.5 # uniform crossover
kids[i, mask], kids[i + 1, mask] = parents[i + 1, mask], parents[i, mask]
return kids
def mutate(pop, pm=1 / n_items):
flips = rng.random(pop.shape) < pm
return np.where(flips, 1 - pop, pop)
pop_size, generations, n_elite = 100, 200, 2
pop = (rng.random((pop_size, n_items)) < 0.3).astype(int)
for g in range(generations):
fit = fitness(pop)
elite = pop[np.argsort(fit)[-n_elite:]]
kids = mutate(crossover(tournament(pop, fit)))
pop = np.vstack([elite, kids[: pop_size - n_elite]])
if g % 40 == 0:
print(f"gen {g:3d} best={fit.max():.0f} mean={fit.mean():.1f}")
best = pop[fitness(pop).argmax()]
print("value:", best @ values, "weight:", best @ weights, "/", capacity)
For real projects, libraries such as DEAP, PyGAD, or pymoo (multi-objective, NSGA-II/III) provide tested operators, parallel evaluation, and logging.
Track best and mean fitness and a diversity measure (e.g. mean pairwise Hamming distance). A collapsing diversity curve while fitness has plateaued signals premature convergence; respond by raising mutation, lowering tournament size, injecting random immigrants, or using an island model (several sub-populations with occasional migration). Stop on a fixed evaluation budget or when the best fitness has not improved for N generations. Because GAs are stochastic, compare settings over multiple seeds.
Consider four individuals with fitness 40, 30, 20 and 10. Under roulette selection their selection probabilities are 0.40, 0.30, 0.20 and 0.10. Now add 1,000 to every fitness value, which does not change which solution is best: the probabilities become 1040/4100 ≈ 0.254 down to 1010/4100 ≈ 0.246, almost uniform, and selection pressure has nearly vanished. Subtract 9 instead and the last individual's share falls to 1/64 while the first takes nearly half. Raw fitness-proportionate selection is therefore sensitive to an arbitrary offset, which is why scaling (windowing or sigma scaling) or rank-based selection is used with it.
Under binary tournament with replacement, the best individual wins whenever it is drawn at least once in two draws, giving probabilities 0.4375, 0.3125, 0.1875 and 0.0625. These depend only on rank, so the offset problem disappears. Larger tournaments increase pressure: with k = 4 the best individual's probability rises to 1 − (3/4)4 ≈ 0.68. A useful way to think about tuning is the takeover time, the number of generations selection alone would need to fill the population with copies of the best individual; strong pressure shortens it and risks premature convergence, while mutation and crossover work against it.
For continuous parameters, real-valued encodings with simulated binary crossover (SBX) and polynomial mutation (both from Deb and colleagues) are standard; their distribution indices control how far children land from parents. Mutation step size can be adapted: evolution strategies self-adapt per-gene step sizes, and CMA-ES (Hansen & Ostermeier, 2001) adapts a full covariance matrix, which is usually stronger than a plain GA on continuous problems of up to a few hundred dimensions.
The classic generational GA replaces the whole population each generation; a steady-state GA replaces one or two individuals at a time, which keeps good solutions longer and suits asynchronous parallel evaluation. Memetic algorithms add a local search (such as 2-opt for routing) to each child; on many combinatorial problems this hybrid is far more effective than either part alone, because the GA explores between basins and the local search descends within them.
Many design problems trade off objectives that cannot be combined into one number honestly: cost versus weight, accuracy versus latency, return versus risk. A solution dominates another if it is no worse on every objective and strictly better on at least one. The set of non-dominated solutions is the Pareto front, and a population-based method is well suited to approximating the whole front in one run. NSGA-II (Deb et al., 2002) ranks the population into successive non-dominated fronts and breaks ties within a front by crowding distance, preferring isolated points so the front stays evenly covered. NSGA-III extends this with reference directions for many (roughly four or more) objectives. Evaluate a multi-objective run with the hypervolume indicator, the area or volume dominated by the front relative to a reference point.
| Problem shape | Usually better first choice | Where a GA still helps |
|---|---|---|
| Smooth, differentiable objective | Gradient descent, L-BFGS | Rarely |
| Continuous, black-box, moderate dimension | CMA-ES, Bayesian optimisation for very expensive evaluations | Mixed discrete and continuous variables |
| Linear constraints, integer decisions | Integer linear programming (OR-Tools, Gurobi, HiGHS) | Non-linear or simulated objectives that a solver cannot express |
| Routing, scheduling at scale | Problem-specific heuristics, constraint programming | As a memetic layer over those heuristics |
| Several conflicting objectives | NSGA-II / NSGA-III | This is a GA |
Documented applications include the evolved X-band antenna for NASA's Space Technology 5 mission (Hornby et al., 2006), timetabling and crew scheduling, structural and aerodynamic shape design with simulators, feature selection for predictive models, and neural architecture search, where regularized evolution (Real et al., 2019) was competitive with reinforcement-learning search. See swarm intelligence for related population methods and constraint satisfaction for exact alternatives.
Further reading: Holland, Adaptation in Natural and Artificial Systems (1975); Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning (1989); Eiben & Smith, Introduction to Evolutionary Computing (2nd ed., 2015); Deb et al., "A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II" (IEEE TEC, 2002); Hansen, "The CMA Evolution Strategy: A Tutorial" (arXiv:1604.00772).