Genetic algorithms

A genetic algorithm knows nothing about the problem it solves. It does not compute derivatives, it does not know the shape of the landscape and it has no plan. It just keeps a population of candidates, evaluates them, and lets the best ones have more offspring. The hope is that selection accumulates the correct pieces before the population becomes uniform.

The idea

The inspiration is biological evolution, but the algorithm is a stochastic search technique, not a biology simulation. Each individual represents a possible solution. A fitness function assigns it a number. Each generation selects parents, recombines their genomes and introduces mutations. The children replace the population and the process repeats.

The central piece is the representation. A genome can be a bit string, a vector of real numbers, a permutation or a tree. The choice is not neutral: it determines which solutions are reachable and which operators make sense.

The pieces

piece	role
representation	encodes a solution as a genome
fitness	measures how good a solution is
selection	favors individuals with better fitness
crossover	combines genetic material from two parents
mutation	introduces small random changes
elitism	preserves the best individuals unchanged

Tournament selection is one of the simplest: pick k individuals at random and the one with the highest fitness wins. With k = 3 the selective pressure is moderate. Single-point crossover cuts two genomes at the same position and swaps them. Mutation flips bits with low probability. Elitism avoids losing the best solution found so far.

A concrete example

We want to maximize a multimodal function on the interval [0, 32]:

The genome is a 16-bit string. It is read as an integer between 0 and 65,535, which is scaled linearly to [0, 32]. The population has 30 individuals; tournaments of size 3, single-point crossover with probability 0.9, per-bit mutation of 0.01 and two-individual elitism are used. Over 100 generations the best fitness and the mean are recorded.

In this run the best individual landed at x ≈ 26.741, with f(x) ≈ 36.722. The maximum of the function is at x ≈ 26.741, so the algorithm found the correct region. What matters is not the exact number but the shape of the curves: best fitness climbs fast and plateaus, while the mean takes longer to approach it.

The gap between the two curves is useful information. If the mean sticks to the best too early, the population lost diversity and the search can get trapped in a local optimum. If the mean never rises, selective pressure is too weak or the representation cannot build better solutions.

Why it works, and when it doesn't

The classic explanation is the schemata theorem: selection increases the representation of blocks that are above average, and crossover can recombine good blocks from different parents. It is a useful justification, not a guarantee. The theorem describes the expected effect of selection on patterns, but it does not promise that the algorithm finds the global optimum.

The landscape matters. If fitness is noisy, if the variables interact hostilely, or if the global optimum is surrounded by deep valleys, the population can converge to a mediocre solution. The phenomenon is called premature convergence, and it is fought with more diversity, adaptive mutation, restarts or structured populations. There is no universal recipe.

Nor is there a genetic algorithm that is “better” for every problem. The no free lunch theorem says that, averaged over all possible landscapes, no search algorithm beats another. A genetic algorithm bakes in assumptions: that the space can be represented, that good solutions share blocks, and that selection can exploit them. If those assumptions don't hold, the method loses its edge.

That's why a GA is rarely the first choice when gradients are available, constraints are smooth, or the problem is convex. It makes more sense when fitness is a black box, when the space is discrete or combinatorial, when there are multiple optima, or when evaluating a solution is expensive but parallelizable.

A minimal implementation

The following code reproduces the experiment. It is not a framework: it is the skeleton to understand where each decision lives.

import math
import random

BITS, POP, GENS = 16, 30, 100
TOUR, PC, PM = 3, 0.9, 0.01
random.seed(20261024)


def fitness(bits):
    x = int("".join(map(str, bits)), 2) / (2**BITS - 1) * 32
    return x * math.sin(x) + 10


def tournament(population, fits):
    contenders = random.sample(range(len(population)), TOUR)
    return population[max(contenders, key=lambda i: fits[i])]


population = [[random.randint(0, 1) for _ in range(BITS)]
              for _ in range(POP)]

for gen in range(GENS):
    fits = [fitness(g) for g in population]
    elite = sorted(range(POP), key=lambda i: fits[i], reverse=True)[:2]
    next_pop = [population[i][:] for i in elite]

    while len(next_pop) < POP:
        a = tournament(population, fits)[:]
        b = tournament(population, fits)[:]

        if random.random() < PC:
            cut = random.randint(1, BITS - 1)
            a, b = a[:cut] + b[cut:], b[:cut] + a[cut:]

        for g in (a, b):
            for i in range(BITS):
                if random.random() < PM:
                    g[i] ^= 1

        next_pop.extend([a, b])

    population = next_pop[:POP]

best = max(population, key=fitness)
print("".join(map(str, best)), fitness(best))

There are three details that usually get overlooked. First, parents are copied before mutating; otherwise mutation modifies the previous population. Second, elitism is applied before crossover and mutation, so the best individual is not lost. Third, the tournament is held with replacement: the same individual can be selected several times, which increases selective pressure.

Closing

A genetic algorithm is not an intelligence and it does not “discover” the problem. It is a way of biasing a search: keep several answers, punish the bad ones and let variation explore. Its virtue is the same as Langton's ant: simple local rules, global behavior that is not visible at first sight.