No Access

A Genetic Algorithm with the Mixed Heuristics for Traveling Salesman Problem

Yong Wang

School of Renewable Energy, North China Electric Power University, No. 2 Beinong Road, Beijing 102206, China

https://doi.org/10.1142/S1469026815500030Cited by:4 (Source: Crossref)

Abstract

Traveling salesman problem (TSP) is one of well-known discrete optimization problems. The genetic algorithm is improved with the mixed heuristics to resolve TSP. The first heuristics is the four vertices and three lines inequality, which is applied to the 4-vertex paths to generate the shorter Hamiltonian cycles (HC). The second local heuristics is executed to reverse the i-vertex paths with more than two vertices, which also generates the shorter HCs. It is necessary that the two heuristics coordinate with each other in the optimization process. The time complexity of the first and second heuristics are O(n) and O(n³), respectively. The two heuristics are merged into the original genetic algorithm. The computation results show that the improved genetic algorithm with the mixed heuristics can find better solutions than the original GA does under the same conditions.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in artificial intelligence!

References

W. X. Zhang and R. E. Korf , Artificial Intelligence 81 , 223 ( 1996 ) . Crossref, Google Scholar
A. Rodríguez and R. Ruiz , Comput. & Oper. Res. 39 , 1566 ( 2012 ) . Crossref, Google Scholar
Y. Wang and J. H. Liu , Robot. Com.-Int. Manuf. 26 , 212 ( 2010 ) . Crossref, Google Scholar
P. Berman and M. Karpinski, 8/7-Approximation Algorithm for (1,2)-TSP, SODA'06 (Miami, FL, 2006) pp. 641–648. Google Scholar
B. W. Douglas , Introduction to graph theory , 2nd edn. ( Pearson Education Asia Limited and China Machine Press , Beijing , 2006 ) . Google Scholar
S. Climer and W. X. Zhang , Artificial Intelligence 170 , 714 ( 2006 ) . Crossref, Google Scholar
M. G. A. Verhoeven , E. H. L. Aarts and P. C. J. Swinkels , Future Gener. Comput. Syst. 11 , 175 ( 1995 ) . Crossref, Google Scholar
K. Helsgaun, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Available at www2.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/ (2014) . Google Scholar
A. Fischer et al. , Discrete Applied Mathematics 166 , 97 ( 2014 ) . Crossref, Google Scholar
J. M. Kan and Y. Zhang , Energy Procedia 17 , 319 ( 2012 ) . Crossref, Google Scholar
W. N. Chen et al. , IEEE T. Evolut. Comput. 14 , 278 ( 2010 ) . Crossref, Google Scholar
G. Carlos , S. Antonio and H. V. Xosé , Computers & Operations Research 56 , 22 ( 2015 ) . Crossref, Google Scholar
Y. H. Liu , Appl. Math. Comput. 216 , 125 ( 2010 ) . Crossref, Google Scholar
C. Changdar , G. S. Mahapatra and R. K. Pal , Swarm and Evolutionary Computation 15 , 27 ( 2014 ) . Crossref, Google Scholar
B. Bontoux , C. Artigues and D. Feillet , Computers & Operations Research 37 , 1844 ( 2010 ) . Crossref, Google Scholar
C. Ding , Y. Cheng and M. He , Tsinghua Science and Technology 12 , 459 ( 2007 ) . Crossref, Google Scholar
L. N. Xing et al. , Eng. Appl. Artif. Intell. 21 , 1370 ( 2008 ) . Crossref, Google Scholar
F. Liu and G. Z. Zeng , Expert System with Applications 36 , 6995 ( 2009 ) . Crossref, Google Scholar
M. Chen and C. Y. Chien , Expert Syst. Appl. 38 , 14439 ( 2011 ) . Crossref, Google Scholar
Y. A. Wang, Representation model for TSP, in 2013 IEEE Int. Conf. High Performance Computing and Communications & 2013 IEEE Int. Conf. Embedded and Ubiquitous Computing (Zhangjiajie, Hunan, 2013), pp. 204–209 . Google Scholar
J. H. Holland , Adaptation in Nature and Artificial System ( MIT Press , Cambridge, MA , 1975 ) . Google Scholar
T. D. G. Wiazda , Genetic Algorithms Reference: Crossover for Single-Objective Numerical Optimization Problems ( Springer Press , Berlin , 2006 ) . Google Scholar
J. Majumdar and A. K. Bhunia , J. Comput. Appl. Math. 235 , 3063 ( 2011 ) . Crossref, Google Scholar
T. Saenphon , S. Phimoltares and C. Lursinsap , Eng. Appl. Artif. Intell. 35 , 324 ( 2014 ) . Crossref, Google Scholar