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.