{"title":"Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA)","authors":"Buthainah Fahran Al-Dulaimi, Hamza A. Ali","volume":14,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":123,"pagesEnd":130,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/6555","abstract":"
The well known NP-complete problem of the Traveling Salesman Problem (TSP) is coded in genetic form. A software system is proposed to determine the optimum route for a Traveling Salesman Problem using Genetic Algorithm technique. The system starts from a matrix of the calculated Euclidean distances between the cities to be visited by the traveling salesman and a randomly chosen city order as the initial population. Then new generations are then created repeatedly until the proper path is reached upon reaching a stopping criterion. This search is guided by a solution evaluation function.<\/p>\r\n","references":"[1] J. H. Holland et. Al., \"Induction: Processes of Inference, Learning, and\r\nDiscovery\", MIT Press, 1989.\r\n[2] M. Melanie, \"An Introduction to Genetic Algorithms\", MIT Press, 1996.\r\n[3] S. Sur-Kolay, S. Banerjee, and C. A. Murthy, \"Flavours of Traveling\r\nSalesman Problem in VLSI Design\", 1st Indian International Conference\r\non Artificial Intelligence, 2003.\r\n[4] E.L. Lawler, J.K. Lenstra, A.H.G Rinnooy Kan, and D. B. Shmoys, \"The\r\nTraveling Salesman Problem: A Guided Tour of Combinatorial\r\nOptimization\", Wiley address Interscience, Chichester, 1985.\r\n[5] Moscato, P. and M.G. Norman, \"A `Memetic', Approach for the Traveling\r\nSalesman Problem. Implementation of a Computational Ecology for\r\nCombinatorial Optimization on Message-Passing a Systems, Parallel\r\nComputing and ransputer Applications\", edited by M. Valero, E. Onate,\r\nM. Jane, J.L. Larriba and B. Suarez, Ed. IOS Press, Amsterdam, 1992. pp:\r\n187 -194.\r\n[6] M. Lalena, \"Traveling Salesman Problem Using Genetic Algorithms.\r\nhttp:\/\/www.lalena.com\/ai\/tsp\/, 2003.\r\n[7] D. Whitley and K. Mathias, \"Genetic Operators, the Fitness Landscape\r\nand the Traveling Salesman Problem\", Parallel Problem Solving from\r\nNature-PPSN 2. R. Manner and B. Mandrake North Holland-Elsevier,\r\neds., 1992, pp: 219 - 228.\r\n[8] S. Kedar, Naphade & Dilek Tuzun, \"Initializing the Hopfield-Tank\r\nNetwork for the TSP using a convex hull: A Computational Study.\r\nProceedings of the Artificial Neural Networks in Engineering (ANNIE'95)\r\nConference, 1995, PP399 - 404.\r\n[9] D. E. Goldberg, \"Genetic Algorithm in Search, Optimization and Machine\r\nLearning\", Machine Learning. Addison-Wesley, New York, 1989.\r\n[10] P. Larranaga, C. M. H. Kuijpers, R. H. Murga, I. Inza and S. Dizdarevic,\r\n\"Genetic Algorithms for the Travelling Salesman Problem: A Review of\r\nRepresentations and Operators\", Artificial Intelligence Review. 13, 1999,\r\nPP129-170.\r\n[11] S. R. Shubhra, B. Sanghamitra and K. Pal. Sankar, \"New Operators of\r\nGenetic Algorithms for Traveling Salesman Problem\", IEEE, 0-7695-\r\n2128-2\/04, 2004.\r\n[12] Ji. Ping and Ho. William, \"The Traveling Salesman and the Quadratic\r\nAssignment Proble: Integration, Modeling and Genetic Algorithm\", Int.\r\nSymposium on OR and its Applications, 2005, PP198-205.\r\n[13] C. Ding, Ye. Cheng and M. He, \"Two-Level Genetic Algorithm for\r\nClustered Traveling Salesman Problem with Application in Large-Scale\r\nTSPs\", Tsinghua Science and Technology, Vol.12, No.4, 2007, PP459-\r\n465.\r\n[14] P. Borovska, T. Ivanova and H. Salem, \"Efficient Parallel Computation of\r\nthe Traveling Salesman Problem on Multicomputer Platform\",\r\nProceedings of the International Scientific Conference \u00d4\u00c7\u00ffComputer Science-\r\n2004, Sofia, Bulgaria, Dec. 2004, PP74-79.\r\n[15] R. Gremlich, A. Hamfelt, H. de Pereda and V. Valkovsky, \"Genetic\r\nAlgorithms with Oracle for the Traveling Salesman Problem\", proceedings\r\nof world academy of science, Engineering and Technology, Vol. , Aug\r\n2005, PP1307-6884.\r\n[16] Q. Jiang, R. Sarker and H. Abbass, \"Tracking moving targets in the nonstationary\r\ntravelling salesman problem,\" Complexity International, Vol.11,\r\n2005, PP171-179.\r\n[17] V. Lawrence, A. Snyder and M. S. Daskin, \"A random-key genetic\r\nalgorithm for the generalized traveling salesman problem\", Available\r\nonline since 17 May 2005, www.sciencedirect.com\r\n[18] M. Bakhouya and J. Gaber, \"An Immune Inspired-based Optimization\r\nAlgorithm: Application to the Traveling Salesman Problem, AMO\",\r\nAdvanced Modeling and Optimization, Vol. 9, No. 1, 2007.\r\n[19] B. P. Buckles, P. E. Petry and R. I. Kuester, \"Schema Survival Rates\r\nand Heuristic Search in Genetic Algorithms\", IEEE, 1990, PP 86-91.\r\n[20] D. T. Phillips, A. Rarindran and J. J. Solberg, \"Operations Research:\r\nPrinciples and Practice\", John Wiely and Sons Inc, 1976.\r\n[21] D. E. Goldberg, \"Genetic Algorithms in Search, Optimization, and\r\nMachine Learning\", Addison Wesley Publishing Company Inc. 1989.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 14, 2008"}