Genetic Algorithms, in depth: encoding, selection, crossover, mutation and constraint repair, measured against an exact optimum

When a genetic algorithm is the right tool

Use a GA when three conditions hold together. You can score a candidate but not differentiate the score. The search space is discrete, combinatorial or full of constraints. A good answer reached reliably is worth more than a proven optimum. Examples: exam timetables, chip floorplans, antenna shapes, feature subsets, and test-input generation in fuzzing.

Do not use one when a better-informed method applies. If the objective is smooth and differentiable, use gradients (the optimization landscape article explains why they win there). If the problem fits an integer program of moderate size, a MIP solver will usually find better solutions and also prove a bound. If an exact algorithm such as knapsack dynamic programming fits your sizes, use it. The No Free Lunch theorems of Wolpert and Macready make the point formally: averaged over all problems, no black-box optimiser beats another. A GA earns its keep through the problem knowledge you build into its encoding and operators.

The generational loop

Every GA is the same loop. The design work is in the boxes:

population = [random_feasible_candidate() for _ in range(N)]
for generation in range(G):
    scores = [fitness(x) for x in population]          # N evaluations
    next_pop = best_E(population, scores)              # elitism
    while len(next_pop) < N:
        a, b = select(population, scores), select(population, scores)
        child = crossover(a, b) if rand() < p_cross else copy(a)
        child = repair(mutate(child))
        next_pop.append(child)
    population = next_pop
return best(population)

Representation decides everything

Representation decides what crossover and mutation mean, and it matters more than any parameter. A good encoding has locality: a small change to the genome makes a small change to the solution. Bit strings suit subset problems: bit i means "item i is included". Real-valued vectors suit continuous parameters, with Gaussian mutation. Permutations suit ordering problems such as the travelling salesman or job sequencing. They need special operators, because one-point crossover of two tours duplicates some cities and loses others.

Order crossover (OX) is the standard fix for permutations. Copy a slice from parent a, then fill the remaining positions with the missing genes in the order they appear in parent b, starting after the slice and wrapping around. The child is always a valid permutation. It keeps a contiguous run of a, and the relative order of b.

def order_crossover(a, b, rng):
    """OX: keep a slice of parent a, fill the rest in parent b's cyclic order."""
    n = len(a)
    i, j = sorted(rng.sample(range(n), 2))
    child = [None] * n
    child[i:j + 1] = a[i:j + 1]
    kept = set(a[i:j + 1])
    fill = [g for g in b[j + 1:] + b[:j + 1] if g not in kept]
    for pos, g in zip(list(range(j + 1, n)) + list(range(i)), fill):
        child[pos] = g
    return child

That function was checked on 20,000 random parent pairs with between 2 and 15 genes, and every child was a valid permutation. For exact tours on small instances, compare against Held-Karp dynamic programming.

Selection, elitism, crossover and mutation

Selection pressure is how strongly fitness decides who breeds. Tournament selection draws k candidates at random and keeps the best. k = 2 is gentle, k = 7 is aggressive, and it only needs to compare fitness values, so negative scores and rescaling do not affect it. Roulette-wheel selection, with probability proportional to fitness, is the classic textbook version, but it is fragile. One outlier takes over the wheel early. Late in the run, when all scores are close, the pressure disappears. It also fails outright on negative fitness. Prefer tournament or rank selection.

Elitism copies the best E individuals into the next generation unchanged, so the best score never goes down. One or two elites out of a population of 50 to 100 is typical. Many more and the elites take over the population.

Crossover recombines building blocks. Uniform crossover chooses each gene from either parent with probability 0.5. One- and two-point crossover keep neighbouring genes together, which helps only when position carries meaning. Mutation keeps diversity alive. For bit strings, flipping each bit with probability 1/L (L = genome length) changes about one bit per child, and that default is hard to beat.

Constraints: penalty, repair or decoder

Real problems have constraints, and a random child often breaks them. A knapsack child can exceed capacity, and a timetable child can double-book a room. There are three ways to respond:

• Penalty: give infeasible candidates low fitness (zero is the "death penalty"). It is simple, but it throws away evaluations, and on tightly constrained problems most of the population can end up infeasible.
• Repair: map every child to a nearby feasible solution before scoring it. This is where domain knowledge enters, and as the experiment below shows, it is often the biggest single lever.
• Decoders: design the encoding so that every genome decodes to a feasible solution, for example a priority order that a greedy scheduler fills in.

A complete GA for 0/1 knapsack

Here is the whole design applied to 0/1 knapsack: bit-string encoding, tournament selection with k = 3, uniform crossover, 1/L mutation, two elites, and a greedy repair operator. The repair removes the items with the worst value-to-weight ratio until the pack fits, then fills leftover capacity with the best-ratio items.

import random

def make_fitness(values, weights, capacity):
    def fitness(bits):
        w = sum(wi for wi, b in zip(weights, bits) if b)
        v = sum(vi for vi, b in zip(values, bits) if b)
        return v if w <= capacity else 0
    return fitness

def repair(bits, values, weights, capacity):
    """Drop the worst value/weight items until the pack fits, then greedily refill."""
    bits = list(bits)
    order = sorted(range(len(bits)), key=lambda i: values[i] / weights[i])
    w = sum(weights[i] for i in range(len(bits)) if bits[i])
    for i in order:                      # worst ratio first
        if w <= capacity:
            break
        if bits[i]:
            bits[i] = 0
            w -= weights[i]
    for i in reversed(order):            # best ratio first
        if not bits[i] and w + weights[i] <= capacity:
            bits[i] = 1
            w += weights[i]
    return bits

def tournament(pop, fits, k, rng):
    best = max(rng.sample(range(len(pop)), k), key=lambda i: fits[i])
    return pop[best]

def uniform_crossover(a, b, rng):
    return [x if rng.random() < 0.5 else y for x, y in zip(a, b)]

def mutate(bits, rate, rng):
    return [1 - b if rng.random() < rate else b for b in bits]

def ga_knapsack(values, weights, capacity, pop_size=60, generations=200,
                k=3, p_cross=0.9, elite=2, seed=0):
    rng = random.Random(seed)
    n = len(values)
    fit = make_fitness(values, weights, capacity)
    pop = [repair([rng.randint(0, 1) for _ in range(n)], values, weights, capacity)
           for _ in range(pop_size)]
    for gen in range(generations):
        fits = [fit(ind) for ind in pop]
        ranked = sorted(range(pop_size), key=lambda i: fits[i], reverse=True)
        nxt = [pop[i] for i in ranked[:elite]]          # elitism
        while len(nxt) < pop_size:
            a = tournament(pop, fits, k, rng)
            b = tournament(pop, fits, k, rng)
            child = uniform_crossover(a, b, rng) if rng.random() < p_cross else list(a)
            child = mutate(child, 1.0 / n, rng)
            nxt.append(repair(child, values, weights, capacity))
        pop = nxt
    fits = [fit(ind) for ind in pop]
    best = max(range(pop_size), key=lambda i: fits[i])
    return pop[best], fits[best]

Measured: GA versus greedy versus the exact optimum

Test it on 30 random instances of 50 items. Weights are 5 to 60, each value is the weight plus a random amount from -4 to +12 (correlated instances, which are harder for greedy), and capacity is half the total weight. The exact optimum comes from DP. Each configuration ran with population 60 for 200 generations, which is 12,000 evaluations per run:

Three conclusions follow. First, the GA without repair is worse than greedy on average: 12,000 evaluations of blind evolution lost to one sort. Second, adding repair turned the same loop into a method that hit the exact optimum on 27 of 30 instances, usually within the first few generations. The repair is greedy in its own right, and the GA spends its effort exploring near greedy solutions instead of rediscovering feasibility. Third, the comparison only means something because an exact answer existed. On your real problem, find a baseline you can trust, such as greedy, a solver bound or a small exactly solvable version, before you tune anything.

Running and tuning a GA

Budget in evaluations. Population size times generations is the cost. Spend it on evaluations, not on extra hyperparameters. Cache fitness by genome hash, because elites and duplicate children are re-scored constantly. When one evaluation is a simulation or a training run, evaluate the population in parallel. A generation is an embarrassingly parallel map.

Watch diversity, not only the best score. Log the best, median and number of distinct genomes per generation. If distinct genomes collapse while the best score stalls, that is premature convergence. Lower k, raise mutation, or restart from fresh random individuals while keeping the elites.

Seeds and stopping. Run at least five seeds and report the spread. A GA reports one lucky run far too easily. Stop on an evaluation budget or after G generations without improvement, never on "looks converged".

Trade-offs. Simulated annealing keeps one candidate and is simpler to tune. Prefer it when there is no meaningful way to combine two solutions. CMA-ES usually beats a GA on continuous problems with tens to hundreds of dimensions. NSGA-II extends GAs to several objectives at once and returns a Pareto front. For problems like multidimensional knapsack at production scale, benchmark a MIP solver before you commit to any metaheuristic.

Failure modes

• Premature convergence. Too much selection pressure or too little mutation makes the population a set of clones by generation 20, after which crossover does nothing.
• A fitness function that can be gamed. The GA optimises exactly what you wrote. A loophole in the scoring, such as an unpenalised constraint or a simulator bug, will be found and exploited.
• A broken encoding. Standard crossover on permutations produces invalid tours. A low-locality encoding turns mutation into random restarts.
• Penalties that are too weak. If an infeasible candidate outscores feasible ones, the run converges to an answer you cannot use.
• Fitness-proportional selection on raw scores. It stalls when scores are large and close together, and it breaks on negative values.
• No baseline. Without greedy, random search or an exact solution on small instances, you cannot tell whether the GA is helping.

What to do next

1. Type in the knapsack GA and a DP solver, and reproduce the table on your own 30 instances with at least five seeds each.
2. Remove the repair step and watch the gap open up. Then try a penalty proportional to the excess weight and compare.
3. Log distinct genomes per generation, then raise k to 7 and watch premature convergence happen.
4. Port the loop to a permutation problem with order crossover and swap mutation, and check it against Held-Karp on 12 cities.
5. For your real problem, write down the baseline, the evaluation budget and the stopping rule before you write the GA.
6. Keep learning: the knapsack problem, travelling salesman by DP, multidimensional knapsack and optimization landscapes.