用于求解TSP问题的改进遗传算法

Improved Genetic Algorithm for Traveling Salesman Problem

TSP问题是一个典型的组合优化问题,也是一个NP难题,一般很难精确地求出其最优解,因而找出有效的近似解算法具有重要意义。针对基本遗传算法在解决TSP问题时所存在的收敛速度慢、容易"早熟"的问题,在选择算子中引入选择因子,同时提出一种改进的交叉算子和基于种群相似度的更新策略。改进的交叉算子是先比较两个城市间距离再进行交换城市序号,因此加快了收敛的速度,而基于种群的相似度更新策略则在算法的后期可以有效地防止早熟。通过对实例144进行测试,证明该算法在解决该类问题上取得了较好的效果。

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.