Suppose two candidate routes each contain a useful stretch, but neither route is good overall. A genetic algorithm can try to combine those strengths: crossover takes two selected parent solutions and recombines parts of their chromosomes into a child. Unlike a change to one solution, this lets a population search using features already present in different candidates. section 18.1.1 section 18.1.7
Crossover sits between parent selection and mutation when producing a new population. Its exact operation depends on how a solution is encoded: copying a segment is straightforward for a bit string, but a route must remain a permutation with each vertex appearing once. Recombination can improve fitness or make it worse, so the child still needs evaluation. section 18.1.5 section 18.1.7 section 18.2.3
Choose an operator that preserves the chromosome’s requirements:
- For a 0–1 knapsack bit string, choose a random cut between genes. Copy the first parent’s prefix and the second parent’s suffix. The opposite pairing could produce a second child. Two cuts or independent parent choices for each gene are other options. section 18.1.7
- For a traveling-salesperson route, copy a prefix from the first parent, then scan the entire second parent and append only vertices not yet copied. Simply appending its suffix could duplicate vertices and omit others. section 18.2.3
Listing 18.12 TSP: crossover
function tspCossover(chromosome1, chromosome2) #1
i ← randomInt(1, |chromosome1|-1) #2
newChromosome ← chromosome1[0:i] #3
genesFromChromosome1 ← new Set(newChromosome) #4
for j in {0,..,|chromosome2|-1} do #5
if not chromosome2[j] in genesFromChromosome1 then #6
newChromosome.add(chromosome2[j])
return newChromosome
The route implementation makes the validity check explicit: a set records the copied prefix, and a scan of the second parent supplies the remaining vertices in their order there. section 18.2.3
An implementation can keep the recombination method separate from its application probability. When the crossover chance fails, the shown wrapper chooses a parent instead; after a child is produced, mutation is applied separately. For chromosomes of length n, copying knapsack slices takes linear time and output space. The route method also takes linear time and additional linear space if set membership is constant-time on average. section 18.1.7 section 18.2.3 section 18.1.5
Tune crossover alongside mutation and population size rather than treating it as a guaranteed improvement. In the reported TSP experiments, crossover-only evolution plateaued early with a smaller population; a larger population improved its early results, but runs without mutation varied substantially with the initial population. section 18.2.4
