关键词: TSP,遗传算法,改进交叉算子,相似度

Abstract: Traveling salesman problem(TSP) is a typical combination optimization problem,which is also a NP hard problem.It’s hard to find a precision result,and it is very important to search for the near result.Based on basic genetic algorithm in solving TSP problems of slow convergence speed and easy to premature,an improved crossover ope-rator and the updating strategy based on similarity of a population was put forward in this paper.The improved crossover operator exchanges the two cities’ number by comparing the distance between the two cities,thus accelerates the convergence speed.And the updating strategy based on population can effectively prevent the population from premature in the later stages of the algorithm.Espcially,for the CHN144,the best path it finds is better than the basic one.

Key words: TSP,Genetic algorithm,Improved crossover operator,Similarity