Offensive Security Researcher & Quantum Cryptography Analyst

Evolutionary Algorithm: Working, Explanation, and Optimization Techniques

Abdul Wahab Junaid
evolutionary algorithm and working of this algorithm.

evolutionary algorithm and working of this algorithm.

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

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:

  1. I generate an initial population of candidate solutions, usually at random.
  2. I evaluate the fitness of every individual using the problem’s objective function.
  3. I select individuals to be parents, biased toward those with higher fitness.
  4. I apply crossover to pairs of parents to produce offspring that mix their traits.
  5. I apply mutation to the offspring, introducing small random changes.
  6. I form the new population, often keeping the best individuals from the previous generation (elitism).
  7. 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:

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).

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version