I think of evolutionary algorithms as optimization methods inspired by one of the most powerful processes I know of: biological evolution. When I need to solve a problem where I don’t have a clean mathematical formula to differentiate, or where the search space is too rugged and complex for classical methods, I reach for an evolutionary algorithm. The core idea is that I maintain a population of candidate solutions, and over successive generations, I let the better solutions survive, combine, and mutate, gradually improving the population’s quality. Its importance comes from its generality — it does not need gradients, does not need the problem to be continuous or differentiable, and can handle noisy, multimodal, or black-box objective functions where I genuinely have no insight into the internal structure of the problem.
History and Background
I see evolutionary computation as having several independent roots that later merged into one field. In the 1960s, Ingo Rechenberg and Hans-Paul Schwefel in Germany developed Evolution Strategies for optimizing aerodynamic shapes. Around the same time, Lawrence J. Fogel developed Evolutionary Programming for evolving finite-state machines. In the 1970s, John Holland at the University of Michigan developed Genetic Algorithms, formalizing much of the theory in his 1975 book “Adaptation in Natural and Artificial Systems.” Later, in the 1990s, John Koza extended these ideas into Genetic Programming, evolving entire computer programs. Over time, these separate strands — Genetic Algorithms, Evolution Strategies, Evolutionary Programming, and Genetic Programming — were recognized as variations on a shared theme, and the umbrella term “Evolutionary Algorithms” came to describe the whole family.
Problem Statement
I use evolutionary algorithms when I face optimization problems that are hard for classical calculus-based or exact methods: the objective function might be non-differentiable, discontinuous, noisy, or evaluated through a simulation rather than a formula; the search space might be enormous, combinatorial, or have many local optima that trap gradient-based methods. The problem, stated generally, is: given a search space and a fitness function that scores any candidate solution, find a candidate (or set of candidates) that maximizes or minimizes that fitness, without relying on derivative information.
Core Concepts
- Individual/Chromosome: A single candidate solution, encoded in some representation (binary string, real-valued vector, tree, permutation).
- Population: A collection of individuals evaluated and evolved together at each generation.
- Fitness function: A function that scores how good a candidate solution is relative to the problem’s objective.
- Selection: The process of choosing which individuals get to reproduce, typically favoring higher-fitness individuals.
- Crossover (recombination): Combining genetic material from two or more parents to produce offspring.
- Mutation: Randomly altering part of an individual’s encoding to introduce variation.
- Generation: One full cycle of evaluation, selection, and reproduction, producing a new population.
- Elitism: Preserving the best individuals unchanged into the next generation to avoid losing good solutions.
How It Works
I always start by encoding the problem into a representation that an evolutionary algorithm can manipulate. From there, the process runs like this:
- I generate an initial population of candidate solutions, usually at random.
- I evaluate the fitness of every individual using the problem’s objective function.
- I select individuals to be parents, biased toward those with higher fitness.
- I apply crossover to pairs of parents to produce offspring that mix their traits.
- I apply mutation to the offspring, introducing small random changes.
- I form the new population, often keeping the best individuals from the previous generation (elitism).
- I repeat steps 2 through 6 for many generations until a stopping condition is met — a fitness target, a generation limit, or stagnation.
Working Principle
The underlying logic mirrors natural selection: variation plus selection, applied repeatedly, drives a population toward higher fitness. Mutation and crossover generate diversity so the algorithm can explore the search space, while selection pressure ensures that useful traits are more likely to be passed on. I think of this as a balance between exploration (searching new areas of the space through mutation and randomness) and exploitation (refining known good areas through selection and crossover of strong individuals). Too much exploration and the algorithm never converges; too much exploitation and it converges prematurely to a mediocre local optimum. Tuning this balance — through mutation rate, selection pressure, and population size — is central to making an evolutionary algorithm work well.
Mathematical Foundation
I can express the selection probability of an individual using fitness-proportionate (roulette wheel) selection as:
$$ P(x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)} $$
where $f(x_i)$ is the fitness of individual $i$ and $N$ is the population size.
The expected number of offspring for a “schema” (a pattern shared by a subset of the population) is described by Holland’s Schema Theorem, which I find is the closest thing evolutionary algorithms have to a formal convergence proof:
$$ E[m(H, t+1)] \geq m(H,t) \cdot \frac{f(H)}{\bar{f}} \cdot \left[1 – p_c \frac{\delta(H)}{l-1} – o(H) p_m\right] $$
where:
- $m(H,t)$ is the number of individuals matching schema $H$ at generation $t$
- $f(H)$ is the average fitness of individuals matching $H$
- $\bar{f}$ is the average fitness of the population
- $p_c$ is the crossover probability, $\delta(H)$ the defining length of the schema, $l$ the chromosome length
- $p_m$ is the mutation probability, $o(H)$ the order (number of fixed positions) of the schema
This theorem tells me that short, low-order, above-average schemata (building blocks) receive exponentially increasing representation in future generations, which is the theoretical basis for why evolutionary search tends to work.
Diagrams
flowchart TD
A[Initialize random population] --> B[Evaluate fitness of each individual]
B --> C[Select parents based on fitness]
C --> D[Apply crossover to create offspring]
D --> E[Apply mutation to offspring]
E --> F[Form new generation]
F --> G{Stopping condition met?}
G -- No --> B
G -- Yes --> H[Return best individual found]Pseudocode
function EvolutionaryAlgorithm(fitness_function, pop_size, max_generations):
population = generate_random_population(pop_size)
for generation in 1 to max_generations:
fitness_values = [fitness_function(ind) for ind in population]
parents = select_parents(population, fitness_values)
offspring = []
for each pair (p1, p2) in parents:
child1, child2 = crossover(p1, p2)
child1 = mutate(child1)
child2 = mutate(child2)
offspring.append(child1, child2)
population = form_new_population(population, offspring) // with elitism
if stopping_condition(population, fitness_values):
break
return best_individual(population)
Step-by-Step Example
I like to demonstrate with a simple example: maximizing $f(x) = x^2$ for integer $x$ in the range 0 to 31, encoded as 5-bit binary strings.
Suppose my initial population of 4 individuals is: 01101 (13), 11000 (24), 01000 (8), 10011 (19).
- Fitness values: $13^2=169$, $24^2=576$, $8^2=64$, $19^2=361$. Total = 1170.
- Selection probabilities favor 24 and 19 heavily (576/1170 ≈ 49%, 361/1170 ≈ 31%).
- Suppose selection picks
11000and10011as parents for crossover at position 3: offspring become11011(27) and10000(16). - I then apply mutation with a small probability, perhaps flipping one bit of
11011to get11111(31) — the maximum possible value in this range. - After forming the next generation with these stronger individuals, the population’s average fitness rises, and I repeat this process until the population converges near $x=31$, the true optimum.
Time Complexity
Each generation requires evaluating the fitness of every individual, which costs $O(N \cdot C)$ where $N$ is population size and $C$ is the cost of a single fitness evaluation. Selection, crossover, and mutation are typically $O(N \cdot L)$ where $L$ is the chromosome length. Across $G$ generations, the total time is $O(G \cdot N \cdot (C + L))$. In practice, the fitness evaluation cost $C$ dominates for real-world problems, since it often involves running a simulation or complex computation per individual.
Space Complexity
I need to store the current population and, typically, the offspring population simultaneously before replacement, giving $O(N \cdot L)$ space where $N$ is population size and $L$ is the length of each individual’s encoding. If I track fitness history or maintain an archive of best solutions, that adds a modest, usually $O(G)$ or $O(N)$, overhead on top.
Correctness Analysis
I want to be upfront that evolutionary algorithms are heuristic methods — I cannot generally prove they will find the global optimum in finite time for arbitrary problems. What I can say, supported by the Schema Theorem and later convergence analyses (such as those using Markov chain models of the algorithm with elitism), is that under certain conditions — nonzero mutation probability on every bit, and elitism preserving the best solution found — the algorithm is guaranteed to converge to the global optimum given unlimited generations, because every point in the search space remains reachable with nonzero probability and the best-found solution is never lost. Without elitism, this guarantee does not hold, since the best solution found can be lost to selection or destroyed by mutation.
Advantages
- It does not require gradient or derivative information, making it applicable to black-box and non-differentiable problems.
- It can escape local optima more easily than purely local search methods, due to its population-based, stochastic nature.
- It is naturally parallelizable since individuals can be evaluated independently.
- It is highly flexible and can be adapted to almost any representation: binary strings, real vectors, trees, graphs, permutations.
- It handles multimodal and noisy objective functions reasonably well.
Disadvantages
- It typically requires many fitness evaluations, which is expensive if each evaluation is costly (e.g., a physics simulation).
- It has no guarantee of finding the exact global optimum in finite time.
- Performance is sensitive to parameter choices like population size, mutation rate, and crossover rate.
- Premature convergence can occur if diversity is lost too early.
- It offers less interpretability than exact or gradient-based methods, since the search process is stochastic.
Applications
- Engineering design optimization, such as optimizing aerodynamic or structural shapes.
- Scheduling and timetabling problems, like job-shop scheduling.
- Neural architecture search and hyperparameter tuning in machine learning.
- Evolving game-playing agents and strategies.
- Genetic programming for automatically generating computer programs or symbolic regression models.
- Robotics, evolving control policies or morphologies.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define POP_SIZE 20
#define GENES 5 // 5-bit chromosome, values 0-31
#define GENERATIONS 50
#define MUTATION_RATE 0.05
typedef struct {
int genes[GENES];
int fitness;
} Individual;
int decode(Individual *ind) {
int value = 0;
for (int i = 0; i < GENES; i++)
value = (value << 1) | ind->genes[i];
return value;
}
void evaluate(Individual *ind) {
int x = decode(ind);
ind->fitness = x * x; // objective: maximize x^2
}
void random_individual(Individual *ind) {
for (int i = 0; i < GENES; i++)
ind->genes[i] = rand() % 2;
evaluate(ind);
}
// tournament selection: pick 3 at random, return the fittest
Individual tournament_select(Individual pop[]) {
Individual best = pop[rand() % POP_SIZE];
for (int i = 0; i < 2; i++) {
Individual challenger = pop[rand() % POP_SIZE];
if (challenger.fitness > best.fitness)
best = challenger;
}
return best;
}
void crossover(Individual *p1, Individual *p2, Individual *c1, Individual *c2) {
int point = 1 + rand() % (GENES - 1);
for (int i = 0; i < GENES; i++) {
if (i < point) {
c1->genes[i] = p1->genes[i];
c2->genes[i] = p2->genes[i];
} else {
c1->genes[i] = p2->genes[i];
c2->genes[i] = p1->genes[i];
}
}
}
void mutate(Individual *ind) {
for (int i = 0; i < GENES; i++) {
double r = (double) rand() / RAND_MAX;
if (r < MUTATION_RATE)
ind->genes[i] = 1 - ind->genes[i]; // flip bit
}
}
int main() {
srand((unsigned) time(NULL));
Individual population[POP_SIZE], new_population[POP_SIZE];
// Step 1: initialize population
for (int i = 0; i < POP_SIZE; i++)
random_individual(&population[i]);
for (int gen = 0; gen < GENERATIONS; gen++) {
// Step 2 (elitism): find and keep the best individual
int best_idx = 0;
for (int i = 1; i < POP_SIZE; i++)
if (population[i].fitness > population[best_idx].fitness)
best_idx = i;
new_population[0] = population[best_idx];
// Step 3: fill the rest of the population with offspring
for (int i = 1; i < POP_SIZE; i += 2) {
Individual p1 = tournament_select(population);
Individual p2 = tournament_select(population);
Individual c1, c2;
crossover(&p1, &p2, &c1, &c2);
mutate(&c1);
mutate(&c2);
evaluate(&c1);
evaluate(&c2);
new_population[i] = c1;
if (i + 1 < POP_SIZE) new_population[i + 1] = c2;
}
for (int i = 0; i < POP_SIZE; i++)
population[i] = new_population[i];
printf("Generation %d: best x = %d, fitness = %d\n",
gen, decode(&population[0]), population[0].fitness);
}
return 0;
}
Sample Input and Output
With the objective of maximizing $f(x) = x^2$ for 5-bit $x$ in [0, 31], a typical run produces output such as:
Generation 0: best x = 24, fitness = 576
Generation 5: best x = 29, fitness = 841
Generation 12: best x = 31, fitness = 961
Generation 13: best x = 31, fitness = 961
...
Generation 49: best x = 31, fitness = 961
The population converges to $x = 31$, the true global maximum in this range, and elitism ensures it does not lose this once found.
Optimization Techniques
- Adaptive mutation rates: I reduce mutation rate as the population converges, and increase it if diversity collapses too early, to balance exploration and exploitation dynamically.
- Elitism: Always carrying the best individual(s) forward unchanged prevents losing good solutions to unlucky crossover or mutation.
- Diverse selection strategies: Tournament selection with adjustable tournament size lets me control selection pressure more precisely than simple roulette-wheel selection.
- Niching and speciation: Techniques that maintain diverse subpopulations to avoid premature convergence on multimodal problems.
- Hybridization with local search (memetic algorithms): Combining evolutionary search with local hill-climbing refines solutions faster once the algorithm finds promising regions.
Common Mistakes
- Setting the mutation rate too high, which turns the search into essentially random search and destroys good building blocks.
- Setting the mutation rate too low or omitting it entirely, causing the population to lose diversity and converge prematurely.
- Using too small a population size, which limits the diversity needed for effective search.
- Forgetting elitism, which can cause the best-found solution to be lost between generations.
- Misdesigning the fitness function so it does not actually reflect the real objective, leading the algorithm to optimize the wrong thing.
Further Reading
- Holland, J. H. “Adaptation in Natural and Artificial Systems.” University of Michigan Press, 1975.
- Goldberg, D. E. “Genetic Algorithms in Search, Optimization, and Machine Learning.” Addison-Wesley, 1989.
- Eiben, A. E., Smith, J. E. “Introduction to Evolutionary Computing.” Springer: https://www.springer.com/gp/book/9783662448731
- Koza, J. R. “Genetic Programming: On the Programming of Computers by Means of Natural Selection.” MIT Press: https://mitpress.mit.edu/9780262111706/genetic-programming/
- Wikipedia overview: https://en.wikipedia.org/wiki/Evolutionary_algorithm
