蚁群算法求解TSP问题若干改进策略的研究  

Stuty on Some Improvement Strategies of Ant Colony Algorithm for Solving TSP

作　　者：劳眷[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《科学技术与工程》2009年第9期2459-2462,共4页Science Technology and Engineering

摘　　要：蚁群算法是求解TSP问题的一个性能较好的仿生型的智能优化算法,但存在着运行时间长、容易陷入局部最优的缺点,导致停滞现象的出现,找不到全局最优解。实验表明,使用候选集合策略和局部搜索策略能提高算法所求得的解的质量,同时也会明显加快求解的速度。使用信息素变异和重新初始化策略,能增加路径探索的多样性,使算法对搜索空间的探索始终保持在一个合理的水平上,有效地避免算法陷入停滞状态,从而找到全局最优解。Ant colony algorithm is a bionic intelligence algorithm which has good performance for solving TSP, but it has the shortcoming of long running time and easily getting into local best solution, so the algorithm would fall into stagnation state and cannot find the global best solution. The expriments show that the use of candidate set and local searching strategies can improve the solution quality,and the solving speed is evidently faster. Through the use of pheromone mutation and restart strategie,the algorithm can enhance the variedness of tour exploration,keep tour exploration at a reasonable level,efficiently avoid falling into stagnation state,and find the global best solution at last.

关 键 词：蚁群算法 旅行商问题(TSP) 信息素 

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