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.