Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (27): 62-64.DOI: 10.3778/j.issn.1002-8331.2008.27.020

• 理论研究 • Previous Articles     Next Articles

Travelling Salesman Problem based on a reformed parallel genetic algorithm

CHEN Yan-feng,TIAN You-xian   

  1. College of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China
  • Received:2007-11-14 Revised:2008-02-25 Online:2008-09-21 Published:2008-09-21
  • Contact: CHEN Yan-feng

一种改进并行遗传算法解决TSP

陈妍峰,田有先   

  1. 重庆邮电大学 计算机科学与技术学院,重庆 400065
  • 通讯作者: 陈妍峰

Abstract: The operation of the genetic algorithm of Travelling Salesman Problem(TSP) needs lots of time and it is easy to fall into the local optimal solution.In order to avoid the problem,the parallel compound genetic algorithm is proposed.The method,which avoids the local optimal problem and reduces the time of the operation,makes use of the parallel of the selection,the cross,the variation.The amount of species distributes the average to the CPU for operating in the environment of MPI.The experience proves the time of the operation less than the simple genetic algorithm and strengthens the ability of the global optimal solution.

摘要: 针对旅行商问题(Travelling Salesman Problem,TSP)的遗传算法的大规模操作,需要大量运算时间而且容易造成局部最优解,提出一种并行混合遗传算法。该方法基于MPI并行环境,利用种群中选择、交叉、变异操作的并行化,将种群中个体平均的分配到处理器中进行操作,有效地避免局部最优解的出现和减少算法的运行时间。实验证明该方法相对于简单遗传算法具有更强全局寻优能力以及耗费更少的操作时间。