Abstract: In order to solve TSP problem，a new algorithm is proposed in this paper.It defines adaptive crossing and mutation probability based on distance density and fitness，adopts improved exchange heuristic crossover operator，which the new individual is no worse than the old one.In addition，according to the difference between the best individual and the better individual，it adopts the method that use double exchange produce new individuals or do simulated annealing operation，the local search accelerates the pace that algorithm approach the best individual.The artificial experiment shows that the new algorithm is a valid method for solving TSP problem.

摘要： 为了求解TSP问题，提出了一种新的遗传算法。它利用距离密集度和适应度定义了自适应的交叉和变异概率，采用改进的交换启发交叉算子，产生不差于父代的个体。根据最优和次优个体的差异，采用2变换法产生新个体或者进行模拟退火操作，局部搜索加快了算法向最优个体靠近的速度。仿真实验表明新算法是一种求解TSP问题的有效方法。