| 一种改进并行遗传算法解决TSP |
| |
| 引用本文： | 陈妍峰,田有先. 一种改进并行遗传算法解决TSP[J]. 计算机工程与应用, 2008, 44(27): 62-64. DOI: 10.3778/j.issn.1002-8331.2008.27.020 |
| |
| 作者姓名： | 陈妍峰 田有先 |
| |
| 作者单位： | 重庆邮电大学 计算机科学与技术学院，重庆 400065 |
| |
| 摘 要： | 针对旅行商问题（Travelling Salesman Problem，TSP）的遗传算法的大规模操作，需要大量运算时间而且容易造成局部最优解，提出一种并行混合遗传算法。该方法基于MPI并行环境，利用种群中选择、交叉、变异操作的并行化，将种群中个体平均的分配到处理器中进行操作，有效地避免局部最优解的出现和减少算法的运行时间。实验证明该方法相对于简单遗传算法具有更强全局寻优能力以及耗费更少的操作时间。
|
| 关 键 词： | 并行 遗传算法 消息传递接口 旅行商问题 |
| 收稿时间： | 2007-11-14 |
| 修稿时间： | 2008-2-25 |
Travelling Salesman Problem based on a reformed parallel genetic algorithm |
| |
| CHEN Yan-feng,TIAN You-xian. Travelling Salesman Problem based on a reformed parallel genetic algorithm[J]. Computer Engineering and Applications, 2008, 44(27): 62-64. DOI: 10.3778/j.issn.1002-8331.2008.27.020 |
| |
| Authors: | CHEN Yan-feng TIAN You-xian |
| |
| Affiliation: | College of Computer Science and Technology，Chongqing University of Posts and Telecommunications，Chongqing 400065，China |
| |
| 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. |
| |
| Keywords: | parallel genetic algorithm Message Passing Interface(MPI) Travelling Salesman Problem(TSP) |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
