The Genetic Algorithm with Two Heuristic Rules for TSP

Abstract:

Many complex discrete manufacturing problems, such as manufacturing sequencing problem or machine scheduling problem etc, can be converted into a general traveling salesman problem (TSP). TSP has been proven to be NP-complete. The genetic algorithm is improved with two heuristic rules for TSP. The first heuristic rule is the four vertices and three lines inequality. It is applied to the local Hamiltonian paths to generate the better solutions. The second heuristic rule is executed to reverse the local Hamiltonian paths, which generates new better solutions. The two heuristic rules coordinate with each other and they are merged into the optimization process of genetic algorithm to improve its performance. The computation results show that the improved genetic algorithm can find the near optimal solutions for most of the TSP instances.

• Periodical: Advanced Materials Research (Volumes 694-697)
• Pages: 2787-2793
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.694-697.2787
• Online since: May 2013
• Authors: Yong Wang
• Keywords: Genetic Algorithm (GA), Heuristic Rule, Traveling Salesman Problem (TSP)

References

[1] Y.Wang and J.H. Liu. Chaotic particle swarm optimization for assembly sequence planning. Robotics and Computer-Integrated Manufacturing,Vol.26(2010), pp.212-222.

DOI: 10.1016/j.rcim.2009.05.003

[2] S.J. Hu, J. Ko, L. Weyand, et, al. Assembly System Design and Operations for Product Variety. CIRP Annals-Manufacturing Technology Vol.60(2011), pp.715-733.

DOI: 10.1016/j.cirp.2011.05.004

[3] K.N. McKay. Unifying the theory and practice of production scheduling. Journal of Manufacturing Systems Vol.18(1999), pp.241-255.

[4] W.X. Zhang, R.E. Korf. A study of complexity transitions on the asymmkric traveling salesman problem, Artificial Intelligence Vol.81(1996), pp.223-239.

DOI: 10.1016/0004-3702(95)00054-2

[5] P. Berman,M. Karpinski. 8/7-Approximation Algorithm for (1,2)-TSP. In: SODA'06, Miami, FL (2006) 641-648.

[6] B.W. Douglas: Introduction to graph theory (Pearson Education Asia Limited and China Machine Press, Bei Jing 2006)

[7] S. Climer, W.X. Zhang. Cut-and-solve: An iterative search strategy for combinatorial optimization problems. Artificial Intelligence, Vol.170 (2006), pp.714-738.

DOI: 10.1016/j.artint.2006.02.005

[8] D.S. Johnson, L.A. McGeoch: The Traveling Salesman Problem and Its Variations, Combinatorial Optimization (Springer Press, London 2004).

[9] K. Helsgaun. An effective implementation of the Lin-Kernighan traveling salesman heuristic. In: www2.iwr.uni-heidelberg.de/groups/comopt/ software/TSPLIB95/tsp/.

[10] H. Ghaziri, I.H. Osman. A neural network algorithm for the traveling salesman problem with backhauls. Computers & Industrial Engineering, Vol.44(2003), pp.267-281.

DOI: 10.1016/s0360-8352(02)00179-1

[11] W.N. Chen, J. Zhang, et, al. A novel set-based particle swarm optimization method for discrete optimization problems. IEEE Trans. Evolutionary Computation, Vol.14(2010), pp.278-300.

DOI: 10.1109/tevc.2009.2030331

[12] L.J. Schmitt, M.M. Amini. Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study. European Journal of Operational Research, Vol.108 (1998), pp.551-570.

DOI: 10.1016/s0377-2217(97)00206-3

[13] Y.H. Liu. Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem. Applied Mathematics and Computation, Vol.216 (2010), pp.125-137.

DOI: 10.1016/j.amc.2010.01.021

[14] B. Bontoux, C. Artigues, D. Feillet. A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem. Computers & Operations Research, Vol.37(2010), pp.1844-1852.

DOI: 10.1016/j.cor.2009.05.004

[15] F. Liu, G.Z. Zeng. Study of genetic algorithm with reinforcement learning to solve the TSP. Expert System with Applications, Vol.39(2009), pp.6995-7001.

DOI: 10.1016/j.eswa.2008.08.026

[16] S.M. Chen, C.Y. Chien. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert System with Applications, Vol.38(2011), pp.14439-14450.

DOI: 10.1016/j.eswa.2011.04.163

[17] V. Deineko, B. Klinz, G. Woeginger, Four point conditions and exponential neighborhoods for symmetric TSP. In: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, SODA'06, Miami, FL (2006) 544-553.

DOI: 10.1145/1109557.1109617

[18] J.H. Holland: Adaptation in nature and artificial system (MIT Press, Cambridge 1975).

[19] T.D.G wiazda. Genetic algorithms reference. Vol1: Crossover for single-objective numerical optimization problems (Springer Press, 2006).

[20] J. Majumdar, A.K. Bhunia. Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times. Journal of Computational and Applied Mathematics, Vol.235 (2011), pp.3063-3078.

DOI: 10.1016/j.cam.2010.12.027