求解TSP问题的快速蚁群算法  

Fast ant colony algorithm for solving traveling salesman problem

作　　者：申铉京[1,2] 刘阳阳[1,2] 黄永平[1,2] 徐铁[3] 何习文[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012 [3]吉林石油集团有限责任公司洮河农场,吉林松原138000

出　　处：《吉林大学学报（工学版）》2013年第1期147-151,共5页Journal of Jilin University:Engineering and Technology Edition

基　　金：吉林省自然科学基金项目(201115025);符号计算与知识工程教育部重点实验室开放基金项目(450060445325);吉林大学研究生创新基金项目(20111063);吉林大学'大学生创新性实验计划'项目(2011A53100)

摘　　要：针对蚁群算法求解旅行商问题时存在收敛速度慢并容易陷入局部最优的问题,提出了一种改进的蚁群算法。改进算法采用信息素挥发因子自适应调整机制,调节算法收敛速度,保证算法的全局搜索能力。同时根据公共路径降低蚁群算法运算时间,诱导蚁群寻找更优解。实验结果表明,改进算法在迭代次数相对较少的情况下求得的平均解与已知最优解偏差为0.46%,最优解与已知最优解偏差为0.23%,在收敛速度及求解精度上均取到了较好的效果。Using ant colony algorithm to solve Traveling Salesman Problem （TSP） has certain disadvantages, such plunging into local minimum, slower convergence speed and so on. In order to find the optimal path accurately and rapidly, an improved ant colony algorithm is proposed. The improved algorithm uses adaptive adjusting mechanism of pheromone decay parameter to adjust the convergence speed and ensure the global search ability. With the help of common path, the computation time is reduced and the better solution can be obtained. Experiments show that, in a relatively few iterations, the percentage deviation of the average solution to the best known solution is 0.46%, and the percentage deviation of the best solution to the best known solution is 0.23%. The improved algorithm has high accuracy and convergence speed.

关 键 词：人工智能 蚁群算法 公共路径 自适应 旅行商问题 

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