  Crossover is the process of recombining the genetic features of two parents.
For many applications where crossover is applied to permutations, relevant
genetic features are pairs of adjacent elements, also called edges in the
permutation order. Recombination of edges without errors is thought to be an
NP-hard problem, typically approximated by heuristics that either introduce new
edges or are only able to produce a small variety of offspring. Here, we derive
an algorithm for crossover of permutations that achieves perfect transmission
of edges and produces a uniform sampling of all possible offspring, in
quadratic average computation time. The algorithm and its derivation reveal a
link between cycle crossover (CX) and edge assembly crossover (EAX), offering a
new perspective on these well-established algorithms. We also describe a
modification of the algorithm that generates the mathematically optimal
offspring for the asymmetric travelling salesman problem.
