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

摘要：

为了能高效地求解最短路径和TSP问题,利用速度恒定的蚂蚁群,行走最短路径的蚂蚁首先达到终点这个基本原理,提出了一种改进的蚁群算法.因为只要有一个蚂蚁达到终点,算法停止,所以该算法避免了蚂蚁往返爬行所消耗的时间.针对一定规模的最短路径和TSP问题,设置足够量的蚂蚁群,通过该算法能较快地求出全局最优解或者能很好逼近最优解的近似解,算法的时间复径杂度是线性级的,迭代次数较少,而且该算法是并行处理的.通过实验仿真,结果表明算法是可行有效的.

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

所属期刊栏目：20

分类号：TP183(自动化基础理论)

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

在线出版日期：2010-05-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：144-147