Genetic Algorithms

Genetic Algorithms

You are an expert in genetic algorithms (GAs) for combinatorial optimization. This skill covers the canonical generational GA loop, encoding selection, the selection/crossover/mutation operator triad, elitism, population sizing, selection-pressure analysis, and the diagnosis and prevention of premature convergence, with a reusable numpy-vectorized implementation. Use the framework below to take a user from "I want to try a GA" to a calibrated, reproducible implementation that is honest about when a GA is the right tool — and when it is not.

Initial Assessment

Establish these facts before writing any GA code:

• Decision variable and natural encoding. Is a solution a binary vector, a permutation, an integer assignment, or mixed? The encoding fixes which operators are legal; choose it first (see solution-encodings). Both worked examples below — permutation TSP and binary knapsack — exist because this choice changes everything downstream.
• Problem size and scaling. How many genes n, and how does one evaluation scale in n? Population memory is $O(Nn)$ and vectorized operators cost $O(Nn)$ per generation, so the genome length rarely limits a GA — the evaluation usually does.
• Exact alternative check. Estimate whether a MIP solver or dynamic program reaches optimality within the time budget; many "GA problems" with a few hundred variables are exactly solvable. Even when they are not, solve small instances exactly anyway: a GA that cannot match brute force on 15 items is broken, not unlucky.
• Why a GA at all. A GA earns its complexity only when recombining two good solutions tends to produce another good solution, i.e., the problem has building blocks that crossover can exchange. If the problem rewards pure intensification, iterated local search or tabu search with a strong neighborhood usually wins. Insist on a simple baseline.
• Constraint structure. For each constraint, decide: satisfied by encoding (a permutation always visits each city once), restored by a repair operator, or penalized in the fitness. This decision shapes the operator set; see constraint-handling-techniques for the full menu.
• Evaluation cost and vectorizability. A GA spends almost all time in fitness evaluation. Can the whole population be evaluated as one (N, n) array operation? If a single evaluation takes seconds (simulation, solver call), the affordable population and generation counts shrink drastically and surrogate or cached evaluation becomes relevant.
• Evaluation budget. Total evaluations = population size × generations (plus initialization). Fix the budget from the wall-clock limit and measured evaluations per second, then split it between N and generations — do not pick both independently.
• Local search availability. If a cheap improvement procedure exists (2-opt for tours, greedy add/drop for subsets), plan for a memetic algorithm from the start; pure GAs are rarely competitive on classic permutation benchmarks (see memetic-algorithms).
• Quality requirement. A 2-5% gap from best-known is the realistic target for a plain, well-tuned GA on hard combinatorial problems. Matching best-known typically requires hybridization.
• Multi-objective? If yes, the replacement scheme changes fundamentally (non-dominated sorting, crowding); the single-objective loop here is the wrong skeleton.
• Instance source and format. Standard benchmark sets (TSPLIB, OR-Library, QAPLIB) or synthetic generators? Generated instances need their own recorded seeds so that every reported number can be regenerated bit-for-bit.
• Reporting protocol. Number of seeds per instance, instances, fixed budget per run, statistics to report (best/mean/std). A GA result from one seed is an anecdote.
• Parameter-tuning budget. Will parameters be tuned systematically (Optuna, irace) or set from the guidance table below? Reserve separate tuning instances to avoid overfitting.

Algorithm Anatomy

The canonical loop and its six design decisions

A generational GA maintains a population of N encoded solutions and repeats: select parents biased toward quality, recombine them, mutate the offspring, and replace the population while preserving the best individuals. Holland (1975), "Adaptation in Natural and Artificial Systems," introduced the framework; Goldberg (1989), "Genetic Algorithms in Search, Optimization and Machine Learning," fixed the canonical form used here. Every GA is fully specified by six decisions:

| Component | Decision | Robust default | Detail skill | |---|---|---|---| | Encoding | genotype structure | match the natural decision variable | solution-encodings | | Fitness | objective + constraint handling | minimize cost; repair > penalty when cheap | constraint-handling-techniques | | Selection | how parents are chosen | tournament, k = 2-4 | selection-and-replacement-strategies | | Crossover | how parents recombine | encoding-specific (uniform / OX) at rate 0.6-0.95 | crossover-operators | | Mutation | background variation | per-gene 1/n (binary); one move per individual (permutation) | mutation-and-perturbation-operators | | Replacement | how generations turn over | generational + 1-5% elitism | selection-and-replacement-strategies |

When a GA is the right tool

• Use a GA when solutions decompose into parts worth mixing (subsets, assignments with weak interactions, sequencing with reusable sub-orders), when no strong single-solution neighborhood with cheap delta evaluation is known, or when the objective is a black box that vectorizes well over a whole population.
• Prefer iterated local search or tabu search when a powerful neighborhood with $O(1)$/$O(n)$ delta evaluation exists and intensification drives quality — or keep the GA but make it memetic from the start (memetic-algorithms).
• Prefer an estimation-of-distribution algorithm when variables have strong, learnable dependencies that pairwise recombination scrambles; prefer BRKGA when a natural decoder exists and a problem-independent framework is wanted.
• Prefer an exact solver outright when instances are small or the formulation is tight; the GA then serves at most as a warm-start provider.

A GA chosen by default, without this comparison, is the most common design error in metaheuristic practice.

Selection pressure, formally

Under fitness-proportionate (roulette) selection the expected copy count of individual $i$ is

$$ E[mi] = N \,\frac{fi}{\sum{j} fj}, $$

which collapses to near-uniform sampling once fitness values cluster — the standard failure of roulette late in a run. Tournament selection depends only on ranks: with tournament size $k$ and rank $r$ (1 = best of N),

$$ P(\text{rank } r \text{ wins a tournament}) = \frac{(N-r+1)^k - (N-r)^k}{N^k}. $$

Goldberg & Deb (1991), "A Comparative Analysis of Selection Schemes Used in Genetic Algorithms," show the takeover time — generations until the best individual fills the population under selection alone — is approximately $\ln N / \ln k$ for tournament selection. For N = 100: about 6.6 generations at k = 2 and 4.2 at k = 3. Crossover and mutation push back against takeover; if observed convergence is much faster than these numbers suggest, selection pressure or elitism is too high.

What crossover is supposed to do

The schema theorem (Holland 1975) bounds the growth of a pattern $H$ with order $o(H)$ (fixed positions) and defining length $\delta(H)$ (span):

$$ E[m(H, t+1)] \;\ge\; m(H,t)\,\frac{f(H)}{\bar f}\left(1 - pc\,\frac{\delta(H)}{n-1} - o(H)\,pm\right). $$

The practical reading, independent of the debated building-block hypothesis: selection amplifies above-average patterns, while crossover and mutation destroy them at a rate growing with their span and order. Operators must therefore respect the structure that carries fitness — adjacency for tours (hence order/edge-preserving crossovers), subset membership for knapsacks (hence uniform crossover). An encoding-operator mismatch makes crossover a noise generator; the crossover-operators skill catalogs which operator preserves which property.

Population sizing and budget split

Theory (Goldberg, Deb & Clark 1992, "Genetic Algorithms, Noise, and the Sizing of Populations"; Harik, Cantú-Paz, Goldberg & Miller 1999, the gambler's-ruin model) sizes N by the signal-to-noise ratio of competing building blocks — informative but not directly computable for a new problem. Practical protocol: under a fixed evaluation budget, run N ∈ {50, 100, 200, 400} with proportionally fewer generations and keep the best mean. Small N converges fast and stalls; large N explores but may not converge within budget. Per-generation work is $O(N \cdot c_{\text{eval}} + N \log N)$ with $O(N n)$ memory — almost always dominated by evaluation.

Parameter guidance

| Parameter | Typical range | Increasing it buys | At the cost of | |---|---|---|---| | Population size N | 50-200 (binary), 100-400 (permutation) | Diversity, better final quality | Fewer generations per budget | | Crossover rate $pc$ | 0.6-0.95 | More recombination of building blocks | Disruption when operators mismatch the encoding | | Mutation rate $pm$ | 1/n per gene (binary); 0.1-0.4 per individual (permutation) | Diversity, escape from stalls | Random-walk behavior, destroyed offspring | | Tournament size k | 2-5 | Faster convergence to good regions | Premature convergence, lost diversity | | Elite count e | 1-5% of N | Monotone best-so-far, no regression | Diversity loss when overdone | | Generations | budget / N | Deeper convergence | Nothing, if budget is truly fixed |

Tune N and k first — they control the explore/exploit balance; $pc$ and $pm$ are secondary once the defaults above are in place (De Jong 1975 and Grefenstette 1986 remain the classic parameter studies; Eiben & Smith 2015, "Introduction to Evolutionary Computing," is the modern reference).

Reusable GA Framework

The engine below is problem-independent. It sees the population as one (N, n) numpy array and receives four callables: init_population, batch evaluate (minimization), batch crossover, and batch mutate. All problem knowledge lives in those hooks, so the TSP and knapsack examples reuse the loop unchanged. Selection is vectorized tournament; replacement is generational with elitism.

GENETIC-ALGORITHM(instance, budget)
  P  Array:
    """Return indices of n_parents tournament winners (minimization).

    Draws an (n_parents, k) matrix of entrants in one call and picks the
    lowest-cost entrant per row -- no Python loop over tournaments.
    """
    entrants = rng.integers(0, cost.shape[0], size=(n_parents, k))
    return entrants[np.arange(n_parents), np.argmin(cost[entrants], axis=1)]

def run_ga(
    init_population: Callable[[np.random.Generator], Array],
    evaluate: Callable[[Array], Array],
    crossover: Callable[[Array, Array, np.random.Generator], Array],
    mutate: Callable[[Array, np.random.Generator], Array],
    *,
    n_generations: int = 200,
    tournament_k: int = 3,
    crossover_rate: float = 0.9,
    n_elites: int = 2,
    seed: int = 0,
) -> tuple[Array, float, Array]:
    """Generational GA with tournament selection and elitism.

    evaluate maps an (N, n) population to an (N,) cost vector (minimize).
    crossover maps two (M, n) parent arrays to one (M, n) child array.
    mutate maps an (M, n) child array to an (M, n) mutated array.
    Returns (best solution, best cost, best-cost-per-generation history).
    """
    rng = np.random.default_rng(seed)
    pop = init_population(rng)
    cost = evaluate(pop)
    n_pop = pop.shape[0]
    n_children = n_pop - n_elites
    history = np.empty(n_generations)
    for gen in range(n_generations):
        order = np.argsort(cost)
        elites, elite_cost = pop[order[:n_elites]], cost[order[:n_elites]]
        pa = pop[tournament_selection(cost, n_children, tournament_k, rng)]
        pb = pop[tournament_selection(cost, n_children, tournament_k, rng)]
        children = crossover(pa, pb, rng)
        skip = rng.random(n_children) > crossover_rate
        children[skip] = pa[skip]                 # pairs that skip crossover
        children = mutate(children, rng)
        pop = np.vstack([elites, children])
        cost = np.concatenate([elite_cost, evaluate(children)])
        history[gen] = cost.min()
    best = int(np.argmin(cost))
    return pop[best].copy(), float(cost[best]), history

def demo_onemax(n_bits: int = 60, pop_size: int = 80) -> None:
    """Sanity check on OneMax, stated as minimizing the count of zero bits."""

    def init(rng: np.random.Generator) -> Array:
        return rng.integers(0, 2, size=(pop_size, n_bits), dtype=np.int8)

    def evaluate(pop: Array) -> Array:
        return (pop == 0).sum(axis=1).astype(float)

    def uniform_crossover(pa: Array, pb: Array, rng: np.random.Generator) -> Array:
        mask = rng.random(pa.shape)  Array:
        flip = rng.random(children.shape)  Array:
    """Distance matrix for n cities on the unit circle (indices sorted by angle).

    Points in convex position make the optimum known: the tour that visits
    cities in angular order, i.e., the identity permutation here.
    """
    rng = np.random.default_rng(seed)
    angles = np.sort(rng.uniform(0.0, 2.0 * np.pi, size=n))
    pts = np.column_stack([np.cos(angles), np.sin(angles)])
    return np.linalg.norm(pts[:, None, :] - pts[None, :, :], axis=2)

def tour_lengths(tours: Array, dist: Array) -> Array:
    """Vectorized closed-tour length of every row in an (N, n) permutation array."""
    nxt = np.roll(tours, -1, axis=1)
    return dist[tours, nxt].sum(axis=1)

def order_crossover(pa: Array, pb: Array, rng: np.random.Generator) -> Array:
    """OX: copy a random slice from parent A, fill the rest in parent-B order.

    The fill step is inherently sequential per pair (it depends on which
    cities the slice already used), so the loop runs over pairs while the
    membership test inside is vectorized over genes.
    """
    n_pairs, n = pa.shape
    cuts = np.sort(rng.integers(0, n + 1, size=(n_pairs, 2)), axis=1)
    children = np.empty_like(pa)
    for i in range(n_pairs):
        lo, hi = cuts[i]
        segment = pa[i, lo:hi]
        rest = pb[i][~np.isin(pb[i], segment)]
        children[i, lo:hi] = segment
        children[i, :lo] = rest[:lo]
        children[i, hi:] = rest[lo:]
    return children

def inversion_mutation(
    children: Array, rng: np.random.Generator, p: float = 0.3
) -> Array:
    """Reverse one random segment of each child with probability p.

    Segment reversal changes only two tour edges -- the gentlest useful
    permutation mutation for adjacency-driven objectives like the TSP.
    """
    n_children, n = children.shape
    out = children.copy()
    cuts = np.sort(rng.integers(0, n, size=(n_children, 2)), axis=1)
    for i in np.flatnonzero(rng.random(n_children)  Array:
    """Greedy nearest-neighbor tour, used to seed a few individuals."""
    n = dist.shape[0]
    unvisited = np.ones(n, dtype=bool)
    tour = np.empty(n, dtype=np.int64)
    tour[0] = start
    unvisited[start] = False
    for i in range(1, n):
        row = np.where(unvisited, dist[tour[i - 1]], np.inf)
        tour[i] = int(np.argmin(row))
        unvisited[tour[i]] = False
    return tour

Before wiring anything into the loop, verify the operator's contract in isolation — a recombination bug that silently produces invalid permutations is the most expensive GA bug to find later, because the run "works" and merely returns garbage tours:

import numpy as np

# Uses order_crossover from the operator block above.

def ox_demo() -> None:
    """Show that OX output is a valid permutation and what it inherits."""
    pa = np.array([[3, 0, 6, 2, 5, 1, 4, 7]])
    pb = np.array([[2, 7, 5, 0, 3, 4, 1, 6]])
    child = order_crossover(pa, pb, np.random.default_rng(8))[0]
    assert sorted(child.tolist()) == l

…

## Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

- **Author:** [hajibabaie](https://github.com/hajibabaie)
- **Source:** [hajibabaie/combinatorial-optimization-skills](https://github.com/hajibabaie/combinatorial-optimization-skills)
- **License:** MIT

Install and usage instructions live in the source repository linked above.