A Genetic Algorithm with Priority Selection for the Traveling Salesman Problem

Authors: Cha-Hwa Lin, Je-Wei Hu

Abstract:

The conventional GA combined with a local search algorithm, such as the 2-OPT, forms a hybrid genetic algorithm(HGA) for the traveling salesman problem (TSP). However, the geometric properties which are problem specific knowledge can be used to improve the search process of the HGA. Some tour segments (edges) of TSPs are fine while some maybe too long to appear in a short tour. This knowledge could constrain GAs to work out with fine tour segments without considering long tour segments as often. Consequently, a new algorithm is proposed, called intelligent-OPT hybrid genetic algorithm (IOHGA), to improve the GA and the 2-OPT algorithm in order to reduce the search time for the optimal solution. Based on the geometric properties, all the tour segments are assigned 2-level priorities to distinguish between good and bad genes. A simulation study was conducted to evaluate the performance of the IOHGA. The experimental results indicate that in general the IOHGA could obtain near-optimal solutions with less time and better accuracy than the hybrid genetic algorithm with simulated annealing algorithm (HGA(SA)).

Keywords: Traveling salesman problem, hybrid geneticalgorithm, priority selection, 2-OPT.

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

References:

[1] W. Banzaf, "The "Molecular" Traveling Salesman" Biological Cybernetics, 1990, 64: 7-14.
[2] Burkowski, F.J., "Proximity and priority: applying a gene expression algorithm to the Traveling Salesperson Problem," Parallel Computing, Vol. 30, pp. 803-816, May 2004.
[3] G.A. Croes, "A Method for Solving Traveling Salesman Problems," Operations Research, 1958, Vol. 6, No. 6, pp. 791-812.
[4] M.R. Garey, D.D. Johnson, and R.E. Trajan, "The Planar Hamiltonian Circuit Problem is NP-complete," SIAM Journal of Computing, 1976, 5:704-714.
[5] Grefenstette, J.J., "Incorporating Problem Specific Knowledge into Genetic Algorithms," in Genetic Algorithms and Simulated Annealing, L. Davi, edtor, pp. 42-60, Morgan Kaufmann Publishers, 1987.
[6] Kido, T. "Hybrid Searches Using Genetic Algorithm," in: Genetic algorithm, H. Kitano, editor, Sangyo Tosho, pp. 61-88, 1993.
[7] K. Katayama, H. Sakamoto, and H. Narihisa,, "An Efficiency of Hybrid Mutation Genetic Algorithm for Traveling Salesman Problem," In Proceedings of the Second Australia-Japan Workshop on Stochastic Models in Engineering, Technique & Management, Gold Coast, Australia, 1996, pp. 294-301.
[8] K. Katayama and H. Narihisa,"An Efficient Hybrid Genetic Algorithm for the Traveling Salesman Problem," Electronics and Communications in Japan, Part 3, 2001, Vol. 84, No. 2, pp. 76-83.
[9] S. Lin and B.W. Kernighan,"An Effective Heuristic Algortihm for the Traveling Salesman Problem", Operations Research, 1973, Vol. 21, No. 2, pp. 498-516.
[10] G. Reinelt, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/in dex.html.