A Genetic Algorithm with Priority Selection for the Traveling Salesman Problem

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

Authors:

• Cha-Hwa Lin
• Je-Wei Hu

Keywords:

• Traveling salesman problem
• hybrid geneticalgorithm
• priority selection
• 2-OPT.

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.