Crossover Operators

Crossover Operators

You are an expert in recombination operators for evolutionary and population-based metaheuristics. This skill is the reference catalog: for every standard crossover — one-point, two-point, uniform (binary/integer); arithmetic, BLX-alpha, SBX (real-valued); OX, PMX, CX, ERX, AEX, position-based (permutation) — it gives when to use it, a numpy implementation, a complexity note, and the problems and algorithms it fits. Use the preservation-property framework below to match operator to encoding to problem, and the measurement harness to verify the match empirically instead of trusting folklore.

Initial Assessment

Establish these facts before recommending or writing any crossover code:

• Fix the encoding first. Binary vector, integer vector, real vector, permutation, or something indirect (random keys, decoder)? The encoding determines which operators are even legal — k-point crossover on a permutation produces duplicates, period. If the encoding is still negotiable, settle it before the operator (see solution-encodings).
• Identify which structural property carries fitness. Absolute position (QAP-style slot assignment), relative order (sequencing, scheduling with precedence), adjacency (tours, routing), or set membership (knapsack, covering)? This single question selects the operator family; the anatomy section formalizes the three permutation properties.
• Check what crossover does to feasibility. Permutation operators preserve the permutation invariant but nothing else. Side constraints (capacities, time windows, budgets) are violated freely by every standard operator — decide up front: repair, penalty, or decoder.
• Ask whether recombination earns its place at all. If two good parents rarely share exploitable structure (low fitness-distance correlation, highly epistatic objective), crossover degenerates to macro-mutation. Plan the headless-chicken control experiment (Advanced Techniques) before investing in an exotic operator.
• Establish the algorithmic context. Which algorithm consumes the operator — a canonical GA, a memetic algorithm with local search on offspring, scatter search? With strong local search after crossover, disruption matters less and cheaper operators (OX instead of ERX) often win on time-adjusted quality.
• Determine the per-child cost tolerance. All operators here are O(n) per child, but constants differ by an order of magnitude: np.where masking vs. Python-level adjacency bookkeeping (ERX). Measure evaluations per second first; the operator should stay well under ~20% of generation wall time.
• Determine batch shape and vectorizability. Binary and real operators vectorize fully over an (N, n) population array. Permutation operators are inherently per-pair (the fill step depends on which genes are already used), so the loop runs over pairs with vectorized inner steps.
• One child or two per pair? Symmetric operators (k-point, uniform, SBX, arithmetic) produce two children for free; most permutation operators produce one child per parent ordering — call them twice with swapped arguments if the budget wants two.
• Real-valued specifics. Bounds and their enforcement (clip, reflect, resample), the spread parameter (SBX eta, BLX alpha), and whether crossover applies per gene or per vector.
• Reproducibility. Every stochastic operator takes an explicit np.random.Generator; seeds are recorded per run. An operator comparison without fixed seeds and repeated runs is noise.

Operator Anatomy: What Crossover Must Preserve

The contract of recombination

A crossover operator takes two parent genotypes and must produce a child that (a) is a valid genotype and (b) inherits the structure that made the parents good. Radcliffe (1991), "Forma Analysis and Random Respectful Recombination," makes this precise with two properties worth checking for any operator: respect (features common to both parents appear in the child) and transmission (every child feature comes from at least one parent). Uniform crossover respects and transmits gene values; CX respects and transmits absolute positions; ERX transmits edges with rare exceptions. An operator that transmits the wrong feature class — PMX transmitting positions on a problem where fitness lives in edges — is technically correct and practically useless.

The three permutation properties, formally

For parents $P^1, P^2$ and child $C$, all permutations of $\{0,\dots,n-1\}$, with $\piX(v)$ the index of value $v$ in $X$ and $E(X)$ the undirected cyclic edge set $\{\{Xk, X_{k+1 \bmod n}\}\}$:

$$ \mathrm{pos}(C) = \frac{1}{n}\,\bigl|\{\, i : Ci \in \{P^1i,\, P^2_i\} \,\}\bigr| \qquad\text{(position preservation)} $$

$$ \mathrm{ord}(C \mid P) = \binom{n}{2}^{-1} \,\bigl|\{\, \{a,b\} : \operatorname{sgn}(\piC(a)-\piC(b)) = \operatorname{sgn}(\piP(a)-\piP(b)) \,\}\bigr| \qquad\text{(order agreement)} $$

$$ \mathrm{adj}(C) = \frac{1}{n}\,\bigl|E(C) \cap \bigl(E(P^1) \cup E(P^2)\bigr)\bigr| \qquad\text{(edge preservation)} $$

CX achieves $\mathrm{pos}(C) = 1$ by construction. ERX typically achieves $\mathrm{adj}(C) \ge 0.95$ (Whitley, Starkweather & Fuquay 1989 report ~95-99% parental edges). OX keeps one parent's segment in place and the rest in the other parent's relative order, so it scores high on $\mathrm{ord}$ and middling on the rest. The measurement harness below computes all three for any operator on any parent pair — run it on representative parents from your population rather than arguing from the table alone.

Master catalog

| Operator | Encoding | Primarily preserves | Per-child cost | Source | |---|---|---|---|---| | One-point | binary / integer / real | contiguous blocks; strong positional bias | O(n) | Holland (1975) | | Two-point / k-point | binary / integer / real | blocks, weaker endpoint bias | O(n) | De Jong (1975) | | Uniform | binary / integer | per-gene values; no positional bias | O(n) | Syswerda (1989) | | Whole/per-gene arithmetic | real | convexity — children on the parent segment | O(n) | Michalewicz (1992) | | BLX-alpha | real | interval schemata; allows expansion beyond parents | O(n) | Eshelman & Schaffer (1993) | | SBX | real | parent-centric spread, tunable via eta | O(n) | Deb & Agrawal (1995) | | OX (order) | permutation | relative order + one parent's segment | O(n) | Davis (1985) | | POS (position-based) | permutation | a random position subset + other parent's order | O(n) | Syswerda (1991) | | PMX (partially mapped) | permutation | absolute positions, segment-anchored | O(n) | Goldberg & Lingle (1985) | | CX (cycle) | permutation | absolute positions, fully ($\mathrm{pos}=1$) | O(n) | Oliver, Smith & Holland (1987) | | ERX (edge recombination) | permutation | undirected adjacency | O(n), heavy constant | Whitley et al. (1989) | | AEX (alternating edges) | permutation | directed adjacency, alternating parents | O(n) | Grefenstette et al. (1985) |

Operator × problem-type fit

| Problem type | Fitness lives in | First choice | Also reasonable | Avoid | |---|---|---|---|---| | Knapsack, subset selection, set covering | membership | uniform | two-point | one-point on long genomes | | TSP, routing | adjacency | ERX (EAX at the high end) | OX, AEX | PMX, CX | | Flow-shop, sequencing, priority lists | relative order | OX | POS, PMX | CX | | QAP, slot assignment, keyboard layout | absolute position | CX | PMX | OX, ERX | | Continuous parameters | coordinates | SBX (eta 10-20) | BLX-0.5, arithmetic | one-point on correlated genes | | Bounded integer vectors | per-slot values | uniform | two-point; arithmetic + rounding | — |

Larrañaga et al. (1999), "Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators," is the standard empirical backing for the permutation rows: edge-preserving operators dominate on the TSP, order-preserving operators on sequencing objectives, and the ranking inverts between those two problem classes — there is no best permutation crossover, only a best property match.

Bias: how operators explore differently at the same fitness

Eshelman, Caruana & Schaffer (1989), "Biases in the Crossover Landscape," separate two axes. Positional bias: one-point crossover separates two genes with probability proportional to their distance on the string — a schema of defining length $\delta$ survives with probability about $1 - \delta/(n-1)$ — so gene ordering on the genome silently matters. Distributional bias: uniform crossover exchanges $\mathrm{Binomial}(n, 0.5)$ genes, never few, so it is maximally mixing; an order-$o$ schema survives intact with probability $2^{1-o}$ regardless of its span. Practical reading: tightly linked building blocks → two-point; independent genes or unknown linkage → uniform; and if you find yourself reordering the genome to protect one-point crossover, switch operators instead.

Binary and Integer Crossovers

All three operators below are fully vectorized over an (N, n) parent batch: each is one mask construction plus two np.where calls, O(Nn) total and allocation-bound rather than compute-bound. They apply unchanged to integer and real genomes (any dtype np.where supports); only their bias profiles differ.

One-point — use when genes are ordered so that physical adjacency on the string reflects real linkage (rare in OR practice); otherwise its positional bias is a liability. Two-point — the default block-preserving choice; treats the genome as a ring, removing one-point's endpoint asymmetry. Uniform — the default when linkage is unknown or genes are independent (knapsack, feature selection); p_swap tunes mixing strength (0.5 = maximal, Syswerda 1989; 0.1-0.2 behaves like a multi-gene macro-mutation that preserves more parent structure).

import numpy as np

Array = np.ndarray

def one_point_crossover(
    pa: Array, pb: Array, rng: np.random.Generator
) -> tuple[Array, Array]:
    """Batch one-point crossover on (N, n) parent arrays; returns two children.

    Cut position is drawn in [1, n-1] so both children mix both parents.
    """
    n_pairs, n = pa.shape
    cuts = rng.integers(1, n, size=(n_pairs, 1))
    mask = np.arange(n)[None, :]  gene taken from first parent
    return np.where(mask, pa, pb), np.where(mask, pb, pa)

def two_point_crossover(
    pa: Array, pb: Array, rng: np.random.Generator
) -> tuple[Array, Array]:
    """Batch two-point crossover: the segment [lo, hi) is swapped between parents."""
    n_pairs, n = pa.shape
    lo = rng.integers(0, n - 1, size=(n_pairs, 1))
    hi = rng.integers(lo + 1, n)                 # broadcast: hi in [lo+1, n-1] per pair
    idx = np.arange(n)[None, :]
    mid = (idx >= lo) & (idx  tuple[Array, Array]:
    """Batch uniform crossover: each gene swaps between parents with prob p_swap."""
    mask = rng.random(pa.shape)  np.ndarray:
    """Batch total value per row; infeasible rows are reported as -1."""
    v = pop @ values
    w = pop @ weights
    return np.where(w  None:
    """Recombine two feasible knapsack parents with each binary operator."""
    values = np.array([8.0, 11.0, 6.0, 4.0, 12.0, 3.0, 5.0, 7.0])
    weights = np.array([5.0, 7.0, 4.0, 3.0, 8.0, 2.0, 3.0, 5.0])
    capacity = 20.0
    pa = np.array([[1, 1, 0, 0, 0, 0, 1, 1]])   # value 31, weight 20
    pb = np.array([[0, 0, 1, 1, 1, 1, 0, 0]])   # value 25, weight 17
    for name, op in [
        ("one-point", one_point_crossover),
        ("two-point", two_point_crossover),
        ("uniform  ", uniform_crossover),
    ]:
        rng = np.random.default_rng(7)           # fresh rng per operator
        c1, c2 = op(pa, pb, rng)
        vals = knapsack_eval(np.vstack([c1, c2]), values, weights, capacity)
        print(f"{name}  child values: {vals[0]:5.1f} {vals[1]:5.1f}")

if __name__ == "__main__":
    knapsack_demo()
# Expected (seed 7): one-point -> 24.0 and -1.0; two-point -> 26.0 and 30.0;
# uniform -> -1.0 and 14.0. Recombination works (two-point built two feasible
# children mixing both parents' items), yet one-point and uniform each
# produced an infeasible child from two feasible parents: standard binary
# crossovers transmit gene values, not constraint satisfaction.

Real-Valued Crossovers

Real-coded GAs and memetic continuous searches recombine coordinates, not bits. The design axis is the spread of children around the parents: arithmetic crossover is purely contractive (children lie on the segment between parents, so the population's bounding box can only shrink — pair it with a mutation that can expand), BLX-alpha extends the sampling interval beyond the parents by a fraction alpha per side, and SBX shapes a parent-centric distribution whose concentration is tuned by eta.

Arithmetic — use for convex feasible regions where any point between two feasible parents is feasible (linear constraints); also the natural operator when genes are weights or probabilities. BLX-alpha — use when the population must be able to expand; alpha = 0.5 makes the children's expected variance equal the parents' (Eshelman & Schaffer 1993, interval-schemata argument), the standard balanced setting. SBX — the default in modern real-coded evolutionary algorithms and NSGA-II; eta in [10, 20] for exploitation-leaning search, [2, 5] for exploration (Deb & Agrawal 1995).

import numpy as np

Array = np.ndarray

def arithmetic_crossover(
    pa: Array, pb: Array, rng: np.random.Generator, per_gene: bool = False
) -> tuple[Array, Array]:
    """Batch arithmetic crossover: complementary convex combinations of parents.

    per_gene=False draws one lambda per pair (children on the line segment);
    per_gene=True draws one lambda per coordinate (children in the box).
    """
    n_pairs, n = pa.shape
    lam = rng.random((n_pairs, n) if per_gene else (n_pairs, 1))
    return lam * pa + (1.0 - lam) * pb, (1.0 - lam) * pa + lam * pb

def blx_alpha(
    pa: Array,
    pb: Array,
    rng: np.random.Generator,
    alpha: float = 0.5,
    lower: float = 0.0,
    upper: float = 1.0,
) -> Array:
    """Batch BLX-alpha: per gene, sample uniformly from the parent interval
    extended by alpha times its width on each side, then clip to bounds."""
    lo = np.minimum(pa, pb)
    hi = np.maximum(pa, pb)
    width = hi - lo
    child = rng.uniform(lo - alpha * width, hi + alpha * width)
    return np.clip(child, lower, upper)

SBX deserves its own block: it was designed so that, on unbounded reals, the child spread imitates the one-point binary crossover it replaces, with the spread factor $\beta$ drawn from a polynomial density $p(\beta) \propto \beta^{\eta}$ for $\beta \le 1$ and $\beta^{-(\eta+2)}$ for $\beta > 1$. The implementation below includes the two standard practical details that naive versions miss: per-gene application probability (typically 0.5, so children keep some coordinates exactly) and bound handling by clipping.

import numpy as np

Array = np.ndarray

def sbx_crossover(
    pa: Array,
    pb: Array,
    rng: np.random.Generator,
    eta: float = 15.0,
    p_gene: float = 0.5,
    lower: float = 0.0,
    upper: float = 1.0,
) -> tuple[Array, Array]:
    """Batch simulated binary crossover (Deb & Agrawal 1995) with clipping.

    Large eta concentrates children near the parents; small eta spreads them.
    Each gene recombines with probability p_gene, else it is copied through.
    """
    u = rng.random(pa.shape)
    beta = np.where(
        u  None:
    """Measure child spread around the parent pair (0.3, 0.7) per gene."""
    rng = np.random.default_rng(11)
    n_samples, n = 20_000, 1
    pa = np.full((n_samples, n), 0.3)
    pb = np.full((n_samples, n), 0.7)
    c_sbx20, _ = sbx_crossover(pa, pb, rng, eta=20.0, p_gene=1.0)
    c_sbx2, _ = sbx_crossover(pa, pb, rng, eta=2.0, p_gene=1.0)
    c_blx = blx_alpha(pa, pb, rng, alpha=0.5)
    for name, c in [("SBX eta=20", c_sbx20), ("SBX eta=2 ", c_sbx2),
                    ("BLX-0

…

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