Genetic Algorithm: Complete Guide
Summary
The Genetic Algorithm (GA) is an optimization metaheuristic inspired by the mechanisms of natural evolution. Conceived by John Holland in the 1970s and popularized by David Goldberg in the 1980s, it relies on four fundamental operators: selection, crossover, mutation, and elitism. By maintaining a population of candidate solutions and evolving them generation after generation, the Genetic Algorithm efficiently explores vast, multimodal, and non-differentiable search spaces. Unlike deterministic methods such as gradient descent, it does not require derivative computation and is remarkably resilient to local minima. This guide covers the mathematical principle, intuition, a complete Python implementation, hyperparameters, advantages and limitations, as well as four concrete use cases.
Mathematical Principle
The functioning of a genetic algorithm is based on rigorous probabilistic concepts. Here are the essential components formulated mathematically.
Population Representation
A population of size $N$ is a set of $N$ individuals (candidate solutions):
$$P^{(t)} = {x_1^{(t)}, x_2^{(t)}, \dots, x_N^{(t)}}$$
where each individual $x_i^{(t)}$ at generation $t$ is represented by a chromosome — a vector of genes:
$$x_i^{(t)} = [g_{i,1}^{(t)}, g_{i,2}^{(t)}, \dots, g_{i,L}^{(t)}]$$
with $L$ the number of genes (chromosome length). Genes can be binary ($g \in {0, 1}$), real-valued ($g \in \mathbb{R}$), integer, or permutation-based, depending on the nature of the problem.
Fitness Function
The fitness function $f: \mathbb{R}^L \rightarrow \mathbb{R}$ evaluates the quality of each individual. For a maximization problem, we seek to find:
$$x^* = \arg\max_{x \in P^{(t)}} f(x)$$
For a minimization problem, the fitness function is generally transformed:
$$f_{adapted}(x) = -f_{original}(x) \quad \text{or} \quad f_{adapted}(x) = \frac{1}{1 + f_{original}(x)}$$
Fitness determines the probability that an individual survives and reproduces. It is the engine of artificial natural selection.
Tournament Selection
Tournament selection is one of the most widely used methods. The principle is as follows:
- Randomly choose $k$ individuals from the current population (with replacement).
- Compare their fitness values.
- Keep the individual with the best fitness.
Formally, for a tournament of size $k$, the probability that an individual of rank $r$ (ranked by decreasing fitness) is selected is:
$$P(\text{selected}) = 1 – \left(\frac{r-1}{N}\right)^k$$
The larger $k$ is, the stronger the selection pressure. A tournament of size $k=2$ is the most common choice, offering a good balance between exploitation and exploration.
Crossover
Crossover combines the genetic information of two parents to produce one or two offspring. Several variants exist:
One-point crossover: A crossover point $c$ is chosen randomly with $1 \leq c < L$. The two offspring are constructed as follows:
$$child_1 = [p_{1,1}, \dots, p_{1,c}, p_{2,c+1}, \dots, p_{2,L}]$$
$$child_2 = [p_{2,1}, \dots, p_{2,c}, p_{1,c+1}, \dots, p_{1,L}]$$
Two-point crossover: Two points $c_1 < c_2$ are chosen. The segment between $c_1$ and $c_2$ is swapped, thus preserving more of the parents’ genetic structure.
Uniform crossover: Each gene of the child comes from either parent 1 or parent 2 with probability $0.5$. This is the most disruptive form but also the most exploratory type of crossover.
The probability of applying crossover is controlled by the parameter $crossover_rate$ ($p_c$), typically between $0.6$ and $0.9$. If crossover is not applied, the offspring are exact copies of the parents.
Mutation
Mutation introduces genetic diversity by randomly modifying one or more genes. For a real-valued representation, Gaussian mutation is written:
$$g’ = g + \epsilon \quad \text{where} \quad \epsilon \sim \mathcal{N}(0, \sigma^2)$$
For a binary representation, the bit is flipped with probability $mutation_rate$ ($p_m$), generally very low ($0.001$ to $0.05$) so as not to overly disrupt the acquired genetic information.
The parameter $p_m$ controls the probability that a given gene is mutated. For a chromosome of length $L$, the expected number of mutations per individual is $L \times p_m$.
Elitism
Elitism ensures that the best individuals of the current generation are transferred intact to the next generation, without modification by crossover or mutation. If the $E$ best individuals are preserved:
$$P^{(t+1)}_{elite} = \text{top}_E(P^{(t)})$$
This ensures monotonic convergence: the best fitness can never decrease from one generation to the next. Without elitism, an unfortunate crossover operator or a mutation could destroy the best solution found. Elitism is generally applied with $E = 1$ or $E = 2$.
Global Cycle Schema
Initialize population P(0) randomly
Evaluate fitness of each individual
For t = 0 to n_generations - 1:
Select parents by tournament
Apply crossover with probability p_c
Apply mutation with probability p_m
Copy the E best individuals (elitism)
Form P(t+1)
Evaluate new solutions
Return the best individual found
Intuition
Imagine a shepherd dog breeder who wants to obtain the best possible dog, capable of herding sheep with maximum efficiency. How does they proceed?
First, they gather a group of varied dogs — this is the initial population. Some are naturally talented, others less so, but all have different potential.
Then, they identify the best dogs in the group, those that best succeed at gathering the flocks — this is fitness evaluation.
Next, they breed the best dogs with each other, hoping that their puppies will inherit the good qualities of both parents — this is crossover. But the result is not guaranteed: sometimes a puppy is better than both parents, sometimes it is worse.
From time to time, a puppy is born with a new, unexpected characteristic — this is mutation. Most of the time, this novelty is harmful or neutral. But sometimes, it brings an unexpected advantage: better peripheral vision, greater endurance, or superior intelligence for anticipating the movements of the flock.
And the breeder takes care to keep their best breeding dogs year after year — this is elitism.
After several generations, if the process is well managed, one obtains shepherd dogs of exceptional quality, far superior to any individual of the first generation. This is exactly the principle of the genetic algorithm, applied not to dogs, but to numerical solutions.
The genetic algorithm does the same thing with solutions: we take the best ones, cross them to produce new combinations, introduce slight random variations, and after several generations, we converge toward solutions of remarkable quality.
Python Implementation
Here is a complete implementation of a Genetic Algorithm from scratch in Python, applied to optimizing the Rastrigin function, a classic multimodal benchmark problem:
import numpy as np
from typing import List, Tuple
# Rastrigin function (minimization problem)
def rastrigin(x: np.ndarray) -> float:
"""
D-dimensional Rastrigin function.
Global minimum: f(0) = 0.
Strong multimodality: many local minima.
"""
D = len(x)
return 10 * D + np.sum(x**2 - 10 * np.cos(2 * np.pi * x))
class Individual:
"""Represents an individual (candidate solution)."""
def __init__(self, genes: np.ndarray, fitness: float = None):
self.genes = genes
self.fitness = fitness # None = not evaluated
class Population:
"""Manages a population of individuals."""
def __init__(
self,
size: int,
gene_dim: int,
bounds: Tuple[float, float],
fitness_fn,
rng: np.random.Generator = None
):
self.size = size
self.gene_dim = gene_dim
self.bounds = bounds
self.fitness_fn = fitness_fn
self.rng = rng or np.random.default_rng()
self.individuals = self._initialize()
def _initialize(self) -> List[Individual]:
"""Random uniform initialization within bounds."""
individuals = []
low, high = self.bounds
genes = self.rng.uniform(low, high, size=(self.size, self.gene_dim))
for g in genes:
ind = Individual(genes=g.copy())
ind.fitness = self.fitness_fn(g)
individuals.append(ind)
return individuals
def evaluate_all(self) -> None:
"""Evaluates the fitness of all unevaluated individuals."""
for ind in self.individuals:
if ind.fitness is None:
ind.fitness = self.fitness_fn(ind.genes)
def best(self) -> Individual:
"""Returns the best individual (minimum fitness)."""
return min(self.individuals, key=lambda ind: ind.fitness)
def tournament_selection(self, k: int = 2) -> Individual:
"""Tournament selection of size k."""
indices = self.rng.choice(len(self.individuals), size=k, replace=False)
candidates = [self.individuals[i] for i in indices]
return min(candidates, key=lambda ind: ind.fitness)
@staticmethod
def one_point_crossover(
parent1: Individual,
parent2: Individual,
rng: np.random.Generator
) -> Tuple[np.ndarray, np.ndarray]:
"""One-point crossover."""
L = len(parent1.genes)
point = rng.integers(1, L) # in [1, L-1]
child1 = np.concatenate([parent1.genes[:point], parent2.genes[point:]])
child2 = np.concatenate([parent2.genes[:point], parent1.genes[point:]])
return child1, child2
@staticmethod
def gaussian_mutation(
genes: np.ndarray,
rate: float,
sigma: float,
bounds: Tuple[float, float],
rng: np.random.Generator
) -> np.ndarray:
"""Gaussian mutation with clipping to bounds."""
mutated = genes.copy()
mask = rng.random(len(mutated)) < rate
noise = rng.normal(0, sigma, size=len(mutated))
mutated[mask] += noise[mask]
low, high = bounds
mutated = np.clip(mutated, low, high)
return mutated
class GeneticAlgorithm:
"""Complete genetic algorithm for minimization."""
def __init__(
self,
population_size: int = 80,
gene_dim: int = 5,
bounds: Tuple[float, float] = (-5.12, 5.12),
fitness_fn=rastrigin,
crossover_rate: float = 0.85,
mutation_rate: float = 0.15,
mutation_sigma: float = 0.5,
n_generations: int = 200,
tournament_k: int = 3,
elitism_count: int = 2,
seed: int = 42
):
self.pop_size = population_size
self.bounds = bounds
self.crossover_rate = crossover_rate
self.mutation_rate = mutation_rate
self.mutation_sigma = mutation_sigma
self.n_generations = n_generations
self.tournament_k = tournament_k
self.elitism_count = elitism_count
rng = np.random.default_rng(seed)
self.population = Population(
size=population_size,
gene_dim=gene_dim,
bounds=bounds,
fitness_fn=fitness_fn,
rng=rng
)
self.rng = rng
self.history = []
def run(self, verbose: bool = True) -> Individual:
"""Runs the genetic algorithm for n_generations."""
self.population.evaluate_all()
for gen in range(self.n_generations):
elite = sorted(
self.population.individuals,
key=lambda ind: ind.fitness
)[:self.elitism_count]
new_individuals = []
for copy in elite:
new_individuals.append(
Individual(genes=copy.genes.copy(), fitness=copy.fitness)
)
while len(new_individuals) < self.pop_size:
p1 = self.population.tournament_selection(self.tournament_k)
p2 = self.population.tournament_selection(self.tournament_k)
if self.rng.random() < self.crossover_rate:
g1, g2 = self.population.one_point_crossover(p1, p2, self.rng)
else:
g1, g2 = p1.genes.copy(), p2.genes.copy()
g1 = self.population.gaussian_mutation(
g1, self.mutation_rate, self.mutation_sigma,
self.bounds, self.rng
)
g2 = self.population.gaussian_mutation(
g2, self.mutation_rate, self.mutation_sigma,
self.bounds, self.rng
)
child1 = Individual(genes=g1)
child1.fitness = self.population.fitness_fn(g1)
new_individuals.append(child1)
if len(new_individuals) < self.pop_size:
child2 = Individual(genes=g2)
child2.fitness = self.population.fitness_fn(g2)
new_individuals.append(child2)
self.population.individuals = new_individuals
best = self.population.best()
self.history.append(best.fitness)
if verbose and (gen % 20 == 0 or gen == self.n_generations - 1):
print(f"Generation {gen:4d} | "
f"Best fitness: {best.fitness:.6f} | "
f"Best individual: {best.genes.round(4)}")
return self.population.best()
# ─── Usage example ───
if __name__ == "__main__":
print("=" * 60)
print("Optimizing the Rastrigin function (D=5)")
print("Known global minimum: f(0,0,0,0,0) = 0")
print("=" * 60)
ga = GeneticAlgorithm(
population_size=80,
gene_dim=5,
bounds=(-5.12, 5.12),
fitness_fn=rastrigin,
crossover_rate=0.85,
mutation_rate=0.15,
mutation_sigma=0.5,
n_generations=200,
tournament_k=3,
elitism_count=2,
seed=42
)
best_solution = ga.run(verbose=True)
print("\n" + "=" * 60)
print("FINAL RESULT")
print(f"Best fitness: {best_solution.fitness:.8f}")
print(f"Best solution: {best_solution.genes.round(6)}")
print(f"Number of evaluations: {ga.pop_size * (ga.n_generations + 1)}")
print("=" * 60)
Code Explanation
Individual class: Each individual is a simple object containing a vector of genes (real-valued representation) and its fitness value. Fitness is computed lazily to avoid unnecessary evaluations.
Population class: Manages the set of all individuals. Initialization creates a random uniform population within the specified bounds. Tournament selection (tournament_selection) picks $k$ individuals at random and returns the best. Crossover (one_point_crossover) swaps gene segments after a random crossover point. Gaussian mutation adds normal noise $\mathcal{N}(0, \sigma^2)$ to selected genes.
GeneticAlgorithm class: Orchestrates the complete cycle: evaluation, selection, crossover, mutation, elitism. The history of best fitness values allows tracking algorithm convergence generation after generation.
The Rastrigin function is an excellent benchmark because it has a global minimum at $f(0, \dots, 0) = 0$ but contains $10^D$ local minima, thus testing the algorithm’s ability to escape local traps.
Hyperparameters
The choice of hyperparameters profoundly influences search quality. Here are the five key parameters:
population_size (100–500)
Population size determines the initial diversity and exploration capacity. A small population (30–50) converges quickly but risks premature convergence. A large population (200–500) explores more space but increases computational cost. For most practical problems, 100 to 200 individuals provide a good compromise.
crossover_rate (0.6–0.95)
The probability of applying crossover to a pair of parents. A high value (≥ 0.8) favors exploitation by actively combining the parents’ genetic information. A value that is too low leaves individuals unchanged, reducing the algorithm’s ability to combine good solutions.
mutation_rate (0.005–0.15)
The probability that a given gene is mutated. This is the most sensitive parameter: a mutation that is too high transforms the genetic algorithm into a random search; a mutation that is too low can lead to genetic impoverishment and premature stagnation. For real-world problems, one often starts with 0.05–0.15 and adjusts based on observed performance.
n_generations (50–2000)
The number of generations determines the search duration. You can set a fixed number or use an adaptive stopping criterion: stop when the best fitness has not improved for $N$ consecutive generations (patience criterion).
tournament_k (2–5)
The tournament size controls selection pressure. With $k=2$, selection is mild and preserves diversity. With $k=5$, only high-quality individuals are selected, which accelerates convergence but reduces diversity. The classic choice is $k=3$, offering a good balance.
Advantages and Limitations
Advantages
- No gradient required: The Genetic Algorithm requires no derivative of the objective function. It works with discontinuous, non-differentiable, noisy, or even externally simulated functions.
- Resistance to local minima: Thanks to population diversity and mutation, the algorithm explores multiple regions simultaneously and avoids the classic gradient descent trap of getting stuck in local minima.
- Broad applicability: It applies to discrete, continuous, mixed, combinatorial, and multi-objective problems with minimal adaptations.
- Natural parallelization: The fitness evaluation of each individual is independent, enabling embarrassing parallelization on GPU, clusters, or distributed computing.
Limitations
- Computational cost: Each generation requires evaluating $N$ fitness functions. For expensive simulations (CFD, financial simulations), the total cost can become prohibitive.
- No optimality guarantee: The Genetic Algorithm does not guarantee convergence to the global minimum. It provides a good approximation within a reasonable time, but no proof of optimality.
- Hyperparameter tuning: Performance depends heavily on hyperparameter choices. Poor tuning can lead to premature convergence or inefficient search.
- Sensitivity to representation: The choice of representation (binary, real-valued, permutation-based) considerably influences the effectiveness of crossover and mutation. A poor representation can prevent the algorithm from finding good solutions.
Concrete Use Cases
1. Hyperparameter optimization of neural networks
A Genetic Algorithm can automatically search for the best neural network architecture — number of layers, number of neurons, learning rate, activation functions. Each individual encodes a complete configuration. Fitness is the network’s performance on the validation set. Work such as that by Real et al. (2019) showed that genetic algorithms can rival Bayesian Optimization for neural architecture search, particularly on discrete architecture spaces.
2. Industrial production scheduling
In factories, scheduling tasks on several machines with complex constraints (deadlines, priorities, resource availability) is an NP-hard problem. A genetic algorithm with permutation-based representation encodes the execution order of tasks. OX (Order Crossover) crossover and inversion mutation preserve feasibility constraints. Companies like Siemens and Airbus use these approaches to optimize their production lines.
3. Aerodynamic design
Optimizing the shape of an airplane wing to minimize drag while maximizing lift is a complex multi-objective problem. The fitness function is evaluated by CFD (Computational Fluid Dynamics) simulation, extremely computationally expensive. A genetic algorithm coupled with a surrogate model can reduce the number of required CFD evaluations by about 80 to 90% compared to direct evaluation.
4. Portfolio planning
The selection and optimal weighting of financial assets to maximize expected return while minimizing risk is a continuous combinatorial optimization problem. A genetic algorithm can encode both the selected assets (binary part of the chromosome) and their allocation weights (real-valued part). This hybrid approach allows handling both the asset selection problem and the weighting problem simultaneously, which is difficult with classical Markowitz methods.
See also
- Explorez la Conjecture de Goldbach en Python : Guide Pratique pour les Passionnés de Programmation
- Résolution des Équations Diophantiennes III avec Python : Guide Complet et Astuces
