Genetic Algorithms

Population-based optimization through representation, fitness, selection, crossover, mutation, elitism, diversity, and reproducible evaluation.

A genetic algorithm (GA) searches with a population rather than one current state. New candidates are produced by selecting, recombining, and mutating existing ones. The biological language is a metaphor; the method works only when its representation and operators preserve useful problem structure.

Core Cycle

Each generation performs:

encode candidate solutions;
evaluate fitness;
select parents;
apply crossover;
apply mutation;
form the next population;
test the stopping rule.

from random import Random

def calculate_fitness(genes):
    # More 1s means better fitness.
    return sum(genes)

def tournament_selection(population, size, rng):
    candidates = rng.sample(population, size)

    best = candidates[0]
    for candidate in candidates[1:]:
        if calculate_fitness(candidate) > calculate_fitness(best):
            best = candidate

    return best

def one_point_crossover(first, second, rng):
    point = rng.randrange(1, len(first))
    child_one = first[:point] + second[point:]
    child_two = second[:point] + first[point:]
    return child_one, child_two

def mutate(genes, mutation_rate, rng):
    mutated = genes.copy()

    for index in range(len(mutated)):
        if rng.random() < mutation_rate:
            mutated[index] = 1 - mutated[index]

    return mutated

def genetic_algorithm(
    gene_length,
    population_size=40,
    max_generations=200,
    mutation_rate=0.02,
    seed=0,
):
    rng = Random(seed)
    population = []

    for _ in range(population_size):
        genes = []
        for _ in range(gene_length):
            genes.append(rng.randint(0, 1))
        population.append(genes)

    history = []

    for generation in range(max_generations + 1):
        population.sort(key=calculate_fitness, reverse=True)
        best = population[0]
        best_fitness = calculate_fitness(best)
        history.append(best_fitness)

        if best_fitness == gene_length:
            return {
                "best": best,
                "fitness": best_fitness,
                "history": history,
                "generations": generation,
            }

        # Keep copies of the best two individuals.
        new_population = [
            population[0].copy(),
            population[1].copy(),
        ]

        while len(new_population) < population_size:
            first = tournament_selection(
                population, size=3, rng=rng
            )
            second = tournament_selection(
                population, size=3, rng=rng
            )

            child_one, child_two = one_point_crossover(
                first, second, rng
            )
            new_population.append(
                mutate(child_one, mutation_rate, rng)
            )

            if len(new_population) < population_size:
                new_population.append(
                    mutate(child_two, mutation_rate, rng)
                )

        population = new_population

    population.sort(key=calculate_fitness, reverse=True)
    return {
        "best": population[0],
        "fitness": calculate_fitness(population[0]),
        "history": history,
        "generations": max_generations,
    }

run = genetic_algorithm(gene_length=20, seed=7)
print("generation:", run["generations"])
print("fitness:", run["fitness"])
print("genes:", run["best"])

The implementation is complete for bit-string chromosomes. Each operation has its own short function, every source of randomness uses one seeded generator, elites are copied before mutation, and the result keeps a fitness history for analysis.

The stopping rule has two safeguards: a target when the optimum is known and a generation budget when it is not. Reaching the budget still returns the best candidate found; it does not report that candidate as globally optimal.

Representation

A chromosome may be:

a bit string;
an integer or real vector;
a permutation;
a tree;
a structured record.

The encoding should make useful solution features inheritable. Ordinary crossover on a route permutation can duplicate cities and omit others. Permutation problems need order-preserving operators or repair.

Representing N-Queens as one row per column guarantees one queen in each column. Using a permutation also guarantees unique rows, leaving diagonal conflicts for fitness.

Fitness

Fitness should:

correlate with real quality;
distinguish progress;
be cheap enough for repeated evaluation;
handle invalid candidates explicitly;
resist exploitable shortcuts.

For N-Queens:

def queen_fitness(rows):
    n = len(rows)
    conflicts = 0

    for left in range(n):
        for right in range(left + 1, n):
            same_row = rows[left] == rows[right]
            same_diagonal = (
                abs(rows[left] - rows[right]) == right - left
            )
            conflicts += same_row or same_diagonal

    pairs = n * (n - 1) // 2
    return pairs - conflicts

The maximum equals the number of queen pairs, meaning no pair attacks.

Penalty functions can rank infeasible candidates, but a weak penalty may reward invalid shortcuts and a severe penalty may provide no gradient toward feasibility. Constraint-preserving operators are often preferable.

The bit-string implementation above cannot be applied unchanged to a permutation encoding. For N-Queens with one unique row per column, use permutation-safe crossover and swap mutation. This is a central lesson: the outer evolutionary cycle is reusable, but representation and variation operators form one coherent design.

Selection

Selection allocates reproduction opportunities.

Roulette selection samples in proportion to adjusted fitness.
Tournament selection chooses the best among a random subset.
Rank selection uses order rather than raw values.

Selection pressure controls exploitation. Weak pressure produces drift. Strong pressure copies early winners too aggressively and destroys diversity.

Tournament size offers a simple pressure control: larger tournaments make high-fitness parents more likely.

Crossover

Common operators include:

one-point crossover;
two-point crossover;
uniform crossover;
ordered crossover for permutations;
subtree crossover for tree structures.

Crossover is useful only when combining partial structures from good parents tends to produce useful children. If variables interact globally, arbitrary recombination may be destructive.

Mutation

Mutation introduces variation:

flip a bit;
perturb a real value;
swap two permutation positions;
replace a subtree;
move one scheduled item.

Too little mutation allows convergence to one mediocre family. Too much reduces evolution to random search. Mutation rate should be interpreted relative to chromosome length and operator magnitude.

Operator Examples

Suppose the parents are:

Parent A: 1 1 0 0 1 0
Parent B: 0 0 1 1 0 1

A one-point crossover after position 3 keeps one prefix and takes the other suffix:

Child:    1 1 0 | 1 0 1

A two-point crossover chooses two boundaries and exchanges only the middle segment:

Parent A: 1 | 1 0 0 | 1 0
Parent B: 0 | 0 1 1 | 0 1
Child:    1 | 0 1 1 | 1 0

A uniform crossover independently chooses the source parent at every position. A mask such as A B A B B A produces:

Child:    1 0 0 1 0 0

Mutation must also match the representation:

bit flip: 110010 → 111010;
swap: [1, 4, 3, 2] → [1, 2, 3, 4] by exchanging positions 2 and 4;
reversal: [1, 4, 3, 2] → [1, 2, 3, 4] by reversing positions 2 through 4.

Swap and reversal preserve a permutation: no item is duplicated or lost. A bit flip does not. Conversely, reversal may be meaningful for a route but arbitrary for a bit mask. Operators are part of the problem representation, not interchangeable decorations.

Elitism

Elitism copies a small number of best candidates unchanged. It prevents losing the best solution through unlucky variation. Excessive elitism accelerates premature convergence.

Always track the best-ever candidate separately even if the population replacement policy is non-elitist.

Diversity

A population can contain many copies of the same poor solution. Monitor:

distinct chromosome count;
average pairwise distance;
per-gene variance or entropy;
gap between best and median fitness;
generations since improvement.

Possible interventions:

increase mutation;
reduce selection pressure;
restart part of the population;
penalize duplicates;
maintain niches;
change the representation.

Population size also trades computation for coverage. A large population explores more candidates per generation but consumes more evaluations.

Building Blocks

The usual intuition is that selection preserves useful partial patterns and crossover combines them. This works only when the encoding places interacting genes where an operator can preserve them. One-point crossover has a positional bias: adjacent genes are more likely to travel together than distant genes.

Epistasis describes interaction among genes. If the contribution of one gene depends strongly on many others, evaluating and recombining partial patterns becomes difficult. Deceptive landscapes can even reward short-term patterns that lead away from the global optimum.

Operator design should follow problem structure:

group tightly interacting variables;
preserve feasibility when possible;
use repair only when its bias is understood;
measure whether children outperform random candidates with similar cost.

Crossover is not mandatory. Mutation-only evolutionary search can be a stronger baseline when useful components do not recombine cleanly.

Constraint Handling

Common strategies include:

feasibility-preserving encodings;
repair after variation;
penalties for violations;
ranking feasible solutions before infeasible ones;
multi-objective treatment of quality and violation.

Penalty coefficients silently define trade-offs. If a schedule may violate room capacity to gain preference score, the penalty determines how much illegality the optimizer is willing to buy. Hard requirements are safer as representation or operator constraints when feasible.

Repair also changes the search distribution. If many children repair to the same candidate, diversity collapses even when crossover appears varied. Record pre-repair and post-repair diversity separately.

Stopping Rules

Stop after:

a target fitness;
a fixed evaluation budget;
a maximum generation count;
no improvement for a patience window;
diversity collapse.

“Converged” means the search stopped changing, not that it reached a global optimum.

Experimental Design

Evaluate a GA across many seeds. Report:

success rate;
solution-quality distribution;
evaluations to target;
best and median fitness curves;
parameter settings;
diversity measures;
runtime.

Compare equal numbers of fitness evaluations, not equal generations. A population of 500 performs much more work per generation than one of 50.

Ablation helps explain performance: remove crossover, mutation, or elitism one at a time and observe what changes.

Worked Example

The all-ones problem verifies mechanics because its target fitness is known, but it is too simple to demonstrate why a GA is useful. Use it first to test invariants:

population size remains constant;
every bit stays in {0,1};
best fitness never decreases under elitism;
the same seed reproduces the same history;
mutation rates zero and one behave as expected.

Then compare at least three settings over multiple seeds. For example, vary mutation rate while holding population size, evaluation budget, tournament size, and elitism constant. Report median curves and success rates instead of selecting the most favorable run.

For a problem without a known optimum, compare against random search using the same number of fitness evaluations. A GA earns its additional structure only if recombination and selection exploit regularity in the landscape.

Applications

scheduling;
engineering design;
route optimization;
feature selection;
controller parameters;
test generation;
layout;
symbolic expression search.

Common Mistakes

Applying an operator incompatible with the encoding.
Assuming biological inspiration guarantees effectiveness.
Hiding invalid candidates behind an arbitrary penalty.
Using one run as evidence.
Losing diversity through excessive elitism.
Comparing generations rather than evaluations.
Declaring population convergence to be optimality.

Exercises

Design bit, integer, and permutation encodings for three optimization problems.
Implement tournament selection and vary tournament size.
Build permutation-safe crossover for route planning.
Compare swap and inversion mutation on the same route problem.
Plot best, median, and diversity curves across generations.
Run an ablation study for crossover, mutation, and elitism.
Explain when random-restart hill climbing is a better choice than a GA.
Implement permutation-safe crossover and swap mutation for N-Queens.
Compare the GA with random search under an equal evaluation budget.
Add diversity history and trigger a partial restart after stagnation.