New operator for the Traveling Salesman Problem

As announced, Darrell Whitley gave a talk on the new operator his team has designed for the classic TSP.

After doing a review of all the classical techniques and operators used to solve this problem, he introduces his new crossover operator that tries not to introduce new edges in the offspring, acting thus as a pure recombination operator, instead of a crossover+mutation. This new operator is called perfect crossover, and is first respectful, and then it transmits alleles. It’s not always possible to apply it, but in samples studied it works 95% of the time. When used in combination with other mutation operators in an evolutionary algorithm, it yields very good results; not completely competitive with the best results known, but almost there.
It’s been great to have such a great talker in our weekly seminars. You can also check out his paper Tunneling between optima: partition crossover for the traveling salesman problem online