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