Genetic Algorithms with Oracle for the Traveling Salesman Problem

By introducing the concept of Oracle we propose an approach for improving the performance of genetic algorithms for large-scale asymmetric Traveling Salesman Problems. The results have shown that the proposed approach allows overcoming some traditional problems for creating efficient genetic algorithms.

• Robin Gremlich
• Andreas Hamfelt
• Héctor de Pereda
• Vladislav Valkovsky

• Genetic algorithms
• Traveling Salesman Problem
• optimal decision distribution
• oracle.

[1] Robin Gremlich, Andreas Hamfelt, and Vladislav Valkovsky,
"Prediction of the Optimal Decision Distribution for the Traveling
Salesman Problem", Proceedings of IPSI International Conf., Sveti
Stefan, Montenegro, 2004.
[2] Papadimitriou C.H., Steiglitz K. Combinatorial Optimization:
Algorithms and Complexity. Englewood Cliffs, NJ: Prentice Hall, 1982.
[3] http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95/
[4] Gutin, Punnen (eds.), The Travelling Salesman Problem and its
Variations, Kluwer Academic Publishers, 2002.
[5] http://www.tsp.gatech.edu/
[6] http://en.wikipedia.org/wiki/Genetic_algorithm
[7] http://tracer.ull.es/academic/Travelling_Salesman_Problem.html
[8] http://en.wikipedia.org/wiki/Local_optimum
[9] http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm