ABSTRACT

This paper, proposes a solution for Travelling Salesman Problem (TSP) [1], using Genetic Algorithm (GA). The proposed algorithm works on data sets of latitude and longitude coordinates of cities and provides optimal tours in shorter time; giving convergence that is fast and better. To improve the solution few heuristic improvements are applied to prevent converging to local optima. The principle of natural selection here is based on both survival and reproduction capacities; that accelerate the convergence speed. Various factors affect the performance of GA(s), such as genetic operators, population etc. As the performance of GA is greatly affected by the initial population, the initial population for the algorithm is sorted first, using Quick Sort, this preserves the better fit population. Also, GA parameters such as selection and mutation probabilities are varied, to obtain enhanced and better performance. The computational results are compared with symmetric problems for some benchmark TSP LIB instances.