基于改进蚁群算法求解最短路径和TSP问题  

An Improved Ant Colony Algorithm Solving the Shortest Path and TSP Problem

作　　者：宋世杰[1] 刘高峰[1] 周忠友[1] 卢小亮[1] 

机构地区：[1]内江师范学院数学与信息科学学院,四川内江641112

出　　处：《计算机技术与发展》2010年第4期144-147,共4页Computer Technology and Development

基　　金：四川省教育科研计划项目(07ZB043)

摘　　要：为了能高效地求解最短路径和TSP问题,利用速度恒定的蚂蚁群,行走最短路径的蚂蚁首先达到终点这个基本原理,提出了一种改进的蚁群算法。因为只要有一个蚂蚁达到终点,算法停止,所以该算法避免了蚂蚁往返爬行所消耗的时间。针对一定规模的最短路径和TSP问题,设置足够量的蚂蚁群,通过该算法能较快地求出全局最优解或者能很好逼近最优解的近似解,算法的时间复径杂度是线性级的,迭代次数较少,而且该算法是并行处理的。通过实验仿真,结果表明算法是可行有效的。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 the optimal solution, and its time complexity is linear. It has less iterations and this algorithm is parallel processing. Simulation result shows that this algorithm is feasible and effective.

关 键 词：蚁群算法 最短路径 TSP问题 并行性 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]