A HYBRID GENETIC ALGORITHM — A NEW APPROACH TO SOLVE TRAVELING SALESMAN PROBLEM
G. Andal Jayalakshmi, Sarmitha Sathiamoorthy, Ramasamy Rajaram · International Journal of Computational Engineering Science · 2001
This paper introduces three new heuristics for the Euclidean Traveling Salesman Problem (TSP). One of the heuristics called Initialization Heuristics (IH) is applicable 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 struck 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.