Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (6): 65-67.

• 学术探讨 • Previous Articles     Next Articles

New algorithm for solving TSP

SHEN Hong-lian,ZHANG Guo-li,LI Zhen-tao   

  1. College of Mathematics and Physics,North China Electric Power University,Baoding,Hebei 071003,China
  • Received:2007-06-18 Revised:2007-08-13 Online:2008-02-21 Published:2008-02-21
  • Contact: SHEN Hong-lian

一种求解TSP问题的新算法

申红莲,张国立,李振涛   

  1. 华北电力大学 数理学院,河北 保定 071003
  • 通讯作者: 申红莲

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问题的有效方法。