| 基于改进蚁群算法求解最短路径和TSP问题 |
| |
| 引用本文： | 宋世杰,刘高峰,周忠友,卢小亮.基于改进蚁群算法求解最短路径和TSP问题[J].微机发展,2010(4):144-147. |
| |
| 作者姓名： | 宋世杰 刘高峰 周忠友 卢小亮 |
| |
| 作者单位： | 内江师范学院数学与信息科学学院; |
| |
| 基金项目： | 四川省教育科研计划项目(07ZB043) |
| |
| 摘 要： | 为了能高效地求饵最短路径和TSP问题，利用速度恒定的蚂蚁群，行走最短路径的蚂蚁首先达到终点这个基本原理，提出了一种改进的蚁群算法。因为只要有一个蚂蚁达到终点，算法停止，所以该算法避免了蚂蚁往返爬行所消耗的时间。针对一定规模的最短路径和TSP问题，设置足够量的蚂蚁群，通过该算法能较快地求出全局最优解或者能很好逼近最优解的近似解，算法的时间复径杂度是线性级的，迭代次数较少，而且该算法是并行处理的。通过实验仿真，结果表明算法是可行有效的。
|
| 关 键 词： | 蚁群算法 最短路径 TSP问题 并行性 |
An Improved Ant Colony Algorithm Solving the Shortest Path and TSP Problem |
| |
| SONG Shi-jie,LIU Gao-feng,ZHOU Zhong-you,LU Xiao-liang.An Improved Ant Colony Algorithm Solving the Shortest Path and TSP Problem[J].Microcomputer Development,2010(4):144-147. |
| |
| Authors: | SONG Shi-jie LIU Gao-feng ZHOU Zhong-you LU Xiao-liang |
| |
| Affiliation: | SONG Shi-jie,LIU Gao-feng,ZHOU Zhong-you,LU Xiao-liang(School of Mathematics , Information,Neijiang Normal College,Neijiang 641112,China) |
| |
| Abstract: | In order to efficiently solve the shortest path and TSP problem,according to the constant speed of ant colony,the path on which the ant first reaches the destination is the shortest.An improved ant colony algorithm is proposed.If an ant has achieved the destination,the algorithm stopped,so the algorithm has avoided the time that ants out and home crawl.For the certain scale shortest path and TSP problem,the algorithm can obtain the global optimal solution or an approximate solution which is greatly close to... |
| |
| Keywords: | ant colony algorithm shortest path problem TSP parallelism |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
