A New Method Based on Genetic Algorithms for Solving Traveling Salesman Problem
Farshad Frahadnia · 2009
This study examines combinations of different binary and unary operators to construct genetic algorithms for solving the traveling salesperson problem. Uniform order-based crossover, heuristic crossover, and edge recombination, are evaluated with inversion and reciprocal exchange mutations. Edge recombination was valuable in converging in the shortest number of generations, and order-based crossover the best performer in frequency of optimum solutions found. The inversion mutation method produced best averages for all populations, but reciprocal exchange performed well in frequency of optimum solutions. For TSP, inversion is actually the less invasive mutation, disrupting at maximum two edges, while reciprocal change can disrupt four edges. This paper explores application of genetic algorithms to TSP by examining combinations of different algorithms for the binary and unary operators used to generate better solutions and minimize the search space. Three binary and two unary operations were tested.