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.
L. Darrell Whitley mostrando el recorrido del viajante de comercio (by jmerelo)
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

3 thoughts on “New operator for the Traveling Salesman Problem

  1. 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.

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s