Title: A HYBRID GENETIC ALGORITHM — A NEW APPROACH TO SOLVE TRAVELING SALESMAN PROBLEM
Abstract: International Journal of Computational Engineering ScienceVol. 02, No. 02, pp. 339-355 (2001) No AccessA HYBRID GENETIC ALGORITHM — A NEW APPROACH TO SOLVE TRAVELING SALESMAN PROBLEMG. ANDAL JAYALAKSHMI, S. SATHIAMOORTHY, and R. RAJARAMG. ANDAL JAYALAKSHMIComputer Science and Engineering Department, Thiagarajar College of Engineering, Madurai, Tamilnadu, India, S. SATHIAMOORTHYComputer Science and Engineering Department, Thiagarajar College of Engineering, Madurai, Tamilnadu, India, and R. RAJARAMInformation Technology Department, Thiagarajar College of Engineering, Madurai, Tamilnadu, Indiahttps://doi.org/10.1142/S1465876301000350Cited by:34 Previous AboutSectionsPDF/EPUB ToolsAdd to favoritesDownload CitationsTrack CitationsRecommend to Library ShareShare onFacebookTwitterLinked InRedditEmail AbstractThis paper introduces three new heuristics for the Euclidean Traveling Salesman Problem (TSP). One of the heuristics called Initialization Heuristics (IH) is applicatbe only to the Euclidean TSP, while other two heuristics RemoveSharp and LocalOpt can be applied to all forms of symmetric and asymmetric TSPs. A Hybrid Genetic Algorithm (HGA) has been designed by combining a variant of an already existing crossover operator with these heuristics. One of the heuristics is for generating initial population, other two are applied to the offspring either obtained by crossover or by shuffling. The last two heuristics applied to offspring are greedy in nature, hence to prevent getting struct up at local optimum we have included proper amount of randomness by using the shuffling operator. We studied the effect of these heuristics by conducting experiments, which show that the results obtained by our Hybrid GA outperformed the results obtained by existing GA in certain problems. These heuristics matched "Best Known" solutions in most cases. In others it produced results with one% tolerance, when compared with those of nature-inspired algorithms such as Simulated Annealing (SA), Evolutionary Computation (EP) and Ant Colony System (ACS). Implementation of these heuristics is simple. Our convergence rate is found to be high and the optimal solution is obtained in a fewer number of iterations.Keywords:Initialization HeuristicsRemoveSharpLocalOptHybrid Genetic Algorithm FiguresReferencesRelatedDetailsCited By 34Route Planning of Helicopters Spraying Operations in Multiple Forest AreasShuping Fang, Yu Ru, Yangyang Liu, Chenming Hu and Xuyang Chen et al.29 November 2021 | Forests, Vol. 12, No. 12Performance Evaluation of Population Seeding Techniques of Permutation-Coded GA Traveling Salesman Problems Based AssessmentVicter Paul, Ganeshkumar C and Jayakumar L1 Jan 2021Structural optimization of stiffener layout for stiffened plate using hybrid GAGerry Liston Putra, Mitsuru Kitamura and Akihiro Takezawa1 Jul 2019 | International Journal of Naval Architecture and Ocean Engineering, Vol. 11, No. 2Hybrid optimizer for the travelling salesman problemSudip Kumar Sahana19 February 2019 | Evolutionary Intelligence, Vol. 12, No. 2Performance Evaluation of Population Seeding Techniques of Permutation-Coded GA Traveling Salesman Problems Based AssessmentVicter Paul, Ganeshkumar C and Jayakumar L1 Apr 2019 | International Journal of Applied Metaheuristic Computing, Vol. 10, No. 2An Improved Ant Colony optimization Algorithm: Minion Ant(MAnt) and its Application on TSPAkshat Shetty, Adhrit Shetty, Kevin Sijo Puthusseri and Radha Shankaramani1 Nov 2018An Improved Genetic Algorithm with a New Initialization Mechanism Based on Regression TechniquesAhmad Hassanat, V. Prasath, Mohammed Abbadi, Salam Abu-Qdari and Hossam Faris7 July 2018 | Information, Vol. 9, No. 7Time-Optimal Path Planning for Dual-Welding Robots Based on Intelligent Optimization StrategyXuewu Wang, Bin Tang, Yixin Yan and Xingsheng Gu2 December 2017A dual local search framework for combinatorial optimization problems with TSP applicationJamal Ouenniche, Prasanna K. Ramaswamy and Michel Gendreau21 December 2017 | Journal of the Operational Research Society, Vol. 68, No. 11Scheduling Optimization of Home Health Care Service Considering Patients' Priorities and Time WindowsGang Du, Xi Liang and Chuanwang Sun10 February 2017 | Sustainability, Vol. 9, No. 2Performance analyses over population seeding techniques of the permutation-coded genetic algorithm: An empirical study based on traveling salesman problemsP. Victer Paul, N. Moganarangan, S. Sampath Kumar, R. Raju and T. Vengattaraman et al.1 Jul 2015 | Applied Soft Computing, Vol. 32A new population seeding technique for permutation-coded Genetic Algorithm: Service transfer approachP. Victer Paul, A. Ramalingam, R. Baskaran, P. Dhavachelvan and K. Vivekanandan et al.1 Mar 2014 | Journal of Computational Science, Vol. 5, No. 2Survey of Methodologies for TSP and VRPS. P. Anbuudayasankar, K. Ganesh and Sanjay Mohapatra20 February 2014High Performance Ant Colony Optimizer (HPACO) for Travelling Salesman Problem (TSP)Sudip Kumar Sahana and Aruna Jain1 Jan 2014Modeling and Simulation about TSP Based on Simulated Annealing AlgorithmJian Zhuang Zhi, Gui Bo Yu, Shi Jie Deng, Zhi Ling Chen and Wen Ya Bai30 August 2013 | Applied Mechanics and Materials, Vol. 380-384Recentering, reanchoring & restarting an evolutionary algorithmJames Hughes, Sheridan Houghten and Daniel Ashlock1 Aug 2013A python-based design-by-contract evolutionary algorithm framework with augmented diagnostic capabilitiesAshwin Panchapakesan, Rami Abielmona and Emil Petriu1 Jun 2013A novel population initialization technique for Genetic AlgorithmP. V. Paul, P. Dhavachelvan and R. Baskaran1 Mar 2013A Populated Iterated Greedy Algorithm with Inver-Over Operator for Traveling Salesman ProblemM. Fatih Tasgetiren, Ozge Buyukdagli, Damla Kızılay and Korhan Karabulut1 Jan 2013Solving the traveling salesman problem using cooperative genetic ant systemsGaifang Dong, William W. Guo and Kevin Tickle1 Apr 2012 | Expert Systems with Applications, Vol. 39, No. 5Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic AlgorithmsMurat Albayrak and Novruz Allahverdi1 Mar 2011 | Expert Systems with Applications, Vol. 38, No. 3A Cooperative Ant Colony System and Genetic Algorithm for TSPsGaifang Dong and William W. Guo1 Jan 2010Neurodynamic programming: a case study of the traveling salesman problemJia Ma, Tao Yang, Zeng-Guang Hou, Min Tan and Derong Liu31 May 2007 | Neural Computing and Applications, Vol. 17, No. 4Bi-distinctive-population co-evolutionary genetic algorithm for traveling salesman problem Dong-Mei Lin and Dong Wang1 Jul 2008Self-adaptive hyperheuristic and greedy searchRobert E. Keller and Riccardo Poli1 Jun 2008Performance enhancement in solving Traveling Salesman Problem using hybrid genetic algorithmD. Kaur and M. M. Murugappan1 May 2008Linear genetic programming of parsimonious metaheuristicsR. E. Keller and R. Poli1 Sep 2007Two-dimensional phase unwrapping using a hybrid genetic algorithmSalah A. Karout, Munther A. Gdeisat, David R. Burton and Michael J. Lalor25 January 2007 | Applied Optics, Vol. 46, No. 5Parallel Search Strategies for TSPs Using a Greedy Genetic AlgorithmYingzi Wei, Yulan Hu and Kanfeng Gu1 Jan 2007Hybrid Intelligent Systems: Evolving Intelligence in Hierarchical LayersA. Abraham1 Jan 2005Designing Multiple-Use Primer Set for Multiplex PCR by Using Compact GAsYu-Cheng Huang, Han-Yu Chuang, Huai-Kuang Tsai, Chun-Fan Chang and Cheng-Yan Kao1 Jan 2004Meta learning evolutionary artificial neural networksAjith Abraham1 Jan 2004 | Neurocomputing, Vol. 56Cost-Benefit Investigation of a Genetic-Programming HyperheuristicRobert E. Keller and Riccardo PoliA self-adaptation genetic algorithm based on knowledge and its application Zhurong Wang, Duwu Cui, Dapeng Huang and Hongfang Zhou Recommended Vol. 02, No. 02 Metrics History KeywordsInitialization HeuristicsRemoveSharpLocalOptHybrid Genetic AlgorithmPDF download
Publication Year: 2001
Publication Date: 2001-06-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 61
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot