Genetic Algorithms

In the preceding chapter we compared nearest-neighbour construction, best-improvement hill climbing with restarts, and simulated annealing on a small vehicle-routing instance. Those searches maintain one current candidate at a time. The hill climber can stop improving in its current neighbourhood, while annealing can accept a worse move under its temperature rule; neither finite-budget run guarantees that it visits every promising region.

A genetic algorithm attacks the same problem from a different angle. Instead of one candidate solution, it maintains a population of them. Instead of perturbing and accepting, it selects promising parents, builds new candidates by combining parts of two parents (crossover) and by perturbing the result (mutation), and then lets the better candidates survive (selection with elitism). The hope is that recombination assembles partial solutions that neither parent contains, so the population can improve faster than a single trajectory.

For that hope to pay off, the encoding has to cooperate. Our decision variable is the visiting order of eight customers, so a candidate is a permutation and every child of crossover or mutation must remain a permutation: no duplicated customers, no missing ones. The order-preserving crossover we build below guarantees this by construction, and the decoder turns any permutation into two feasible depot tours, so no repair step is needed for this instance.

Our aim in this chapter is to build the mechanism from primitives, count every objective evaluation, and compare it with NN-seeded random search, best-improvement segment-reversal hill climbing, and simulated annealing under the same 300-evaluation budget on exactly the same routing instance. Nearest-neighbour construction supplies the common starting permutation and is also reported separately as a one-evaluation baseline. Because the instance has only eight customers, we can enumerate all $8! = 40320$ permutations and report gaps to that reference. The worked parents are chosen to illustrate crossover; the repeated-run comparison will tell us how the actual search performs under its budget.