Genetic Algorithms with Oracle for the Traveling Salesman Problem

Authors: Robin Gremlich, Andreas Hamfelt, Héctor de Pereda, Vladislav Valkovsky

Abstract:

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.

Keywords: Genetic algorithms, Traveling Salesman Problem, optimal decision distribution, oracle.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060054

References:

[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