doi: 10.7763/IJCTE.2010.V2.258
A Novel Genetic Algorithm for GTSP
Zaheed Ahmed1
,
Irfan Younas2 ,
Muhammad Zahoor3
- 1University Institute of Information Technoloty, University of Arid Agriculture Rawalpindi, Pakistan.
- 2HITEC University Taxila Cantt., Taxila, Pakistan.
- 3University, Rawalpindi, Pakistan.
Abstract
The Generalized Travelling Salesman Problem (GTSP) is a special instance of the well-known travelling salesman problem which belongs to NP-hard class of problems. In the GTSP problem which is being addressed in this research we split the set of nodes (e.g. cities) into non-overlapping subsets; where the optimal solution is a minimum cost tour visiting exactly one node from each subset. In this paper a genetic algorithm with new and innovative way of generating initial population is presented. Concepts like cluster segmentation, partially greedy crossover, greedy insert mutation and enhanced swap mechanisms are also introduced. An initial analysis of the proposed algorithm shows enhanced results in terms of optimality and computational time as compared to existing approaches.
Keywords
- Generalized travelling salesman problem
- genetic algorithms
- greedy insert mutation
- partially greedy crossover
How to Cite
Zaheed Ahmed, Irfan Younas, and Muhammad Zahoor, "A Novel Genetic Algorithm for GTSP," International Journal of Computer Theory and Engineering, vol. 2, no. 6, pp. 892-896, 2010. https://doi.org/10.7763/IJCTE.2010.V2.258
Copyright & License
Copyright © 2010 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).