Impact of grafting a 2-opt algorithm based local searcher into the genetic algorithm
Milan Djordjević, Milan Tuba, Bojan D. Djordjević · 2009
This paper examines the impact of grafting a 2-opt based local searcher into the standard genetic algorithm for solving the Travelling Salesman Problem with Euclidean distance. Pure genetic algorithms are known to be rather slow, while 2-opt search applied to the Travelling Salesman Problem quickly gives results that are far from optimal. We propose a strategy to graft a 2-opt local searcher into genetic algorithm, after recombination and mutation, to optimize each offspring's genomes. Genetic algorithm provides new search areas, while 2-opt improves convergence. We tested our algorithm on examples from TSPLIB and proved that this method combines good qualities from both applied methods, significantly over performing each of them.