A Novel Genetic Algorithm for Traveling Salesman Problem Based on Neighborhood Code

摘要

Classic genetic algorithm is not suitable to solve traveling salesman problem, because the encoding of the traveling salesman problem is either the permutations of the cities or the combinations of edges, which can not be directly operated by ordinary crossover or mutation operators. This paper introduces a novel encoding for traveling salesman problem, which can be operated by the ordinary crossover and mutation operators; and in order to accelerate the rate of the convergence, a novel local improvement approach is also presented.