Genetic algorithms (GAs) are population-based metaheuristics inspired by the process of natural selection and biological evolution. First formalized by John Holland in his 1975 book Adaptation in Natural and Artificial Systems, GAs maintain a population of candidate solutions (“individuals”) that evolve over generations through selection, crossover (recombination), and mutation. Over many generations, the population converges toward high-quality solutions — just as a species adapts to its environment through differential survival and reproduction.
GAs are the most widely known and widely applied evolutionary algorithm. They are the default choice for combinatorial optimization problems with complex, multimodal fitness landscapes — scheduling, routing, timetabling, circuit design, and neural architecture search. Their strength lies in the population mechanism: by maintaining diverse candidates simultaneously, GAs explore multiple regions of the search space in parallel and can recombine building blocks from different good solutions via crossover.
In AI engineering, GAs are used for hyperparameter tuning, neural architecture search (Google’s AmoebaNet used regularized evolution), feature selection, and any setting where the search space is large, discrete or mixed, and the objective function is expensive or non-differentiable. Frameworks like DEAP (Distributed Evolutionary Algorithms in Python) make GAs accessible for rapid prototyping.
A genetic algorithm repeats a cycle of evaluation → selection → crossover → mutation → replacement until a termination condition is met (generation limit, fitness target, or convergence):
# Genetic Algorithm pseudocode using DEAP concepts
import random
def genetic_algorithm(pop_size, n_gens, crossover_prob, mutation_prob,
create_individual, evaluate, select, crossover, mutate):
# 1. Initialize population
population = [create_individual() for _ in range(pop_size)]
for ind in population:
ind.fitness = evaluate(ind)
for gen in range(n_gens):
# 2. Selection — pick parents
parents = select(population, k=pop_size)
# 3. Crossover — recombine pairs
offspring = []
for i in range(0, len(parents), 2):
p1, p2 = parents[i], parents[i+1]
if random.random() < crossover_prob:
c1, c2 = crossover(p1, p2)
else:
c1, c2 = p1.copy(), p2.copy()
offspring.extend([c1, c2])
# 4. Mutation — perturb individuals
for ind in offspring:
if random.random() < mutation_prob:
mutate(ind)
# 5. Evaluate new individuals
for ind in offspring:
ind.fitness = evaluate(ind)
# 6. Replacement — new generation
population = offspring
return max(population, key=lambda ind: ind.fitness)The first design choice is how to encode candidate solutions as “chromosomes.” Common representations:
Holland’s Schema Theorem (the “fundamental theorem of genetic algorithms”) shows that short, low-order schemata (patterns of bits) with above-average fitness increase exponentially in frequency across generations. The Building Block Hypothesis extends this: crossover assembles these short, high-fitness building blocks into complete, high-quality solutions. While the hypothesis has been debated and refined over decades, it remains the primary theoretical justification for why crossover (not just mutation) is essential in GAs.
Selection determines which individuals contribute genetic material to the next generation. Higher-fitness individuals should reproduce more, but maintaining diversity prevents premature convergence:
k = 2 or k = 3 is typical. This is the most commonly used method in practice due to its simplicity and tunable pressure.Crossover is the primary intensification operator — it combines genetic material from two parents to produce offspring that inherit traits from both. Common operators:
Mutation is the primary diversification operator — it introduces random variation to maintain genetic diversity and prevent the population from converging to a single genotype:
1/L where L is chromosome length).N(0, σ) noise to each gene. σ may adapt over time (self-adaptive mutation).Typical crossover probability: 0.6–0.9. Typical mutation probability: 0.01–0.1 per individual (or 1/L per gene). The ratio matters: high crossover + low mutation favors exploitation; the reverse favors exploration.
The biggest failure mode of GAs is premature convergence — the population collapses to a single genotype before finding the global optimum. Countermeasures include: maintaining a diverse initial population, using tournament selection instead of roulette wheel, applying niching/crowding mechanisms, using island models with migration (see Parallel Metaheuristics), and monitoring population diversity metrics. If diversity drops below a threshold, increase mutation rate or inject random individuals.
Google Brain’s AmoebaNet (Real et al., 2019) used regularized evolution — a simple GA with tournament selection and aging — to discover image classification architectures that matched or exceeded those found by reinforcement learning (NASNet). Each individual encodes a neural network cell structure; fitness is validation accuracy on CIFAR-10. The key insight: a simple GA with pop_size = 100 and tournament_size = 5 was sufficient, with no fancy operators needed.
Binary-encoded GAs naturally model subset selection: each bit indicates whether a feature is included. The fitness function evaluates a model trained on the selected feature subset. This is widely used in bioinformatics (selecting genes from thousands of candidates) and in production ML pipelines where reducing feature count cuts inference latency and data pipeline cost.
GAs are the backbone of many commercial scheduling tools. Job-shop scheduling (assigning operations to machines and time slots) and vehicle routing (finding optimal delivery routes for a fleet) are classic GA applications. Permutation encoding with PMX crossover is standard for these problems. Modern solvers typically wrap the GA in a hybrid framework with domain-specific local search.
DEAP (Distributed Evolutionary Algorithms in Python) is the most popular GA framework for research and prototyping. It provides modular building blocks — creators, toolboxes, selection operators, crossover operators, and mutation operators — that snap together to build custom evolutionary algorithms in ~50 lines:
from deap import base, creator, tools, algorithms
import random
# Define fitness and individual types
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat,
creator.Individual, toolbox.attr_bool, n=100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
def eval_func(individual):
return (sum(individual),) # Maximize number of 1s (OneMax)
toolbox.register("evaluate", eval_func)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.01)
toolbox.register("select", tools.selTournament, tournsize=3)
pop = toolbox.population(n=300)
result, log = algorithms.eaSimple(pop, toolbox,
cxpb=0.7, mutpb=0.2, ngen=40)