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

# New operator for the Traveling Salesman Problem

Advertisements

Very interesting!

I am curious to know which operators yield the best results for various problem types. Do you know of a good reference for this?

I am not that familiar with the whole literature; as for the TSP the best result is not an evolutionary algorithm, although it uses some stochastic techniques, as far as I remember.

Pingback: Genetic Algorithms: Links And Resources (2) « Angel ”Java” Lopez on Blog