Genetic Algorithms › Summary

A genetic algorithm is population-based black-box search. A candidate solution is an encoding that must survive variation: here a permutation, cut into two blocks of four by a decoder that turns it into two feasible depot tours. Selection applies pressure through tournaments, whose selection probability for an individual of rank $r$ is $\binom{N-r}{k-1}/\binom{N}{k}$; order crossover recombines two permutations without duplicating a customer within the child, because the copied block and the filtered cyclic listing of the second parent partition the value set; swap mutation can propose a different permutation; and $(\mu+\lambda)$ survival with elitism makes the best-so-far curve non-increasing at the price of a population that can collapse onto near-copies.

The mechanism is built from primitives, and the worked example illustrates recombination of two supplied parents: two mediocre parents of cost $38.2665$ and $39.1233$ produced a child of cost approximately $37.3560$, which enumeration confirms is optimal for this instance, because one contributed a good left block and the other a good right block. The one illustrated swap is worse, and its score still costs an evaluation. Neither that example nor the selected optimal crossover estimates how often arbitrary children improve.

Held to the same 300-evaluation budget as NN-seeded random search, 2-opt hill climbing, and simulated annealing, and repeated over 20 seeds against an exact enumeration of all 40320 permutations, the genetic algorithm's standing on this instance is a measured outcome, not a foregone conclusion: the multi-method figures and the summary table report the observed distributions, exact hits, and gaps without presupposing which method wins. That is the honest conclusion for a problem this small, and it is the right frame for using the method in practice: count every evaluation, repeat the runs, report distributions, validate the final solutions independently, and never call the best result found under a stopping budget optimal without an independent optimality certificate.

In the next chapter we look at differential evolution, a related population method whose variation operator is designed for continuous vectors rather than permutations, and which constructs a mutant from one donor plus a scaled difference of two others, then chooses mutant or target coordinates with a crossover mask.