首页 | 本学科首页   官方微博 | 高级检索  
     

求解TSP问题的改进蚁群算法
引用本文:张军英 敖磊 贾江涛 高琳. 求解TSP问题的改进蚁群算法[J]. 西安电子科技大学学报(自然科学版), 2005, 32(5): 681-685
作者姓名:张军英 敖磊 贾江涛 高琳
作者单位:[1]西安电子科技大学计算机学院,陕西西安710071 [2]西安电子科技大学雷达信号处理重点实验室,陕西西安710071
基金项目:国家自然科学基金资助项目(60371044,30470414);国家留学回国人员科研基金资助项目
摘    要:分析了标准蚁群算法易于出现早熟停滞现象的主要原因,在原有算法基础上引入局部信息激素、最优最差路径信息激素更新策略及变参数策略,扩大了解的搜索空间,有效抑制了收敛过程中的早熟停滞现象,大大提高了算法收敛速度;同时引入局部最优搜索策略,增大了解突变的机率,求解质量得到了极大的改善.对于典型旅行商问题库中旅行商问题的实验及与标准蚁群算法的比较实验验证了该方法的有效性.

关 键 词:蚁群算法 组合优化 旅行商问题
文章编号:1001-2400(2005)05-0681-05
收稿时间:2004-10-25
修稿时间:2004-10-25

An improvement of the ant colony algorithm for solving TSP problems
Zhang JunYing;Ao Lei;Gu JiangTao;Gao Lin. An improvement of the ant colony algorithm for solving TSP problems[J]. Journal of Xidian University, 2005, 32(5): 681-685
Authors:Zhang JunYing  Ao Lei  Gu JiangTao  Gao Lin
Affiliation:(1. School of Computer Science and Technology, Xidian Univ., Xi′an 710071, China;2. Key Lab. of Radar Signal Processing, Xidian Univ., Xi′an 710071, China) ;
Abstract:As a novel bionic evolutionary algorithm, the ant colony algorithm has been widely applicable to many complicated combinatorial optimization problems. However, the standard any colony algorithm often gets stock into premature stagnation after the iteration process. In this paper, through an analysis of the main reason of the premature stagnation phenomenon in the standard ant colony algorithm, we present a modified version of the algorithm by introducing the local pheromone, modifying the pheromones of the best route and the worst route, as well as making the parameter of the algorithm to be variant during its iteration and searching with a local optimization strategy. Experimental results for solving TSP problems with both the standard ant colony algorithm and the proposed one show that averagely speaking, the proposed method is much better in both the quality of the solution and the speed of convergence compared with the Standard any colony algorithm.
Keywords:ant colony algorithm    combinatorial optimization   TSP
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《西安电子科技大学学报(自然科学版)》浏览原始摘要信息
点击此处可从《西安电子科技大学学报(自然科学版)》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号