[1]徐强,宋海洲,田朝薇.解TSP问题的蚁群算法及其收敛性分析[J].华侨大学学报(自然科学版),2011,32(5):588-591.[doi:10.11830/ISSN.1000-5013.2011.05.0588]
　XU Qiang,SONG Hai-zhou,TIAN Zhao-wei.Convergence Analysis of the Ant Colony Algorithm for Solving TSP[J].Journal of Huaqiao University(Natural Science),2011,32(5):588-591.[doi:10.11830/ISSN.1000-5013.2011.05.0588]
点击复制

解TSP问题的蚁群算法及其收敛性分析()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第32卷
期数:
2011年第5期
页码:
588-591
栏目:
出版日期:
2011-09-20

文章信息/Info

Title:
Convergence Analysis of the Ant Colony Algorithm for Solving TSP
文章编号:
1000-5013(2011)05-0588-04
作者:
徐强; 宋海洲; 田朝薇
华侨大学数学科学学院
Author(s):
XU Qiang;  SONG Hai-zhou;  TIAN Zhao-wei
School of Mathematical Sciences, Huaqiao University, Quanzhou 362021, China
关键词:
旅行商问题;  蚁群算法;  收敛性;  信息素
Keywords:
traveling salesman problem;  ant colony algorithm;  convergence;  pheromone
分类号:
TP301.6
DOI:
10.11830/ISSN.1000-5013.2011.05.0588
文献标志码:
A
摘要:
研究和证明求解旅行商问题(TSP)的蚁群算法收敛性.针对蚁群算法搜索时间长、收敛速度慢、易陷入局部最优等缺陷,改进Dorigo提出的基本蚁群算法.最后,用典型的旅行商问题CHN144进行仿真实验,结果表明,改进蚁群算法在收敛速度及求解能力上都有较大改善.
Abstract:
A detailed theoretical research on ant colony algorithm(ACA) is performed,and the convergence of the ACA for solving the traveling salesman problem(TSP) is proved.ACA has the limitations of stagnation and poor convergence,and is easy to fall in local optima,a series of improvement schemes such as roulette strategy and excellent ants release pheromone strategy are proposed.Finally,a typical example of Traveling salesman problem CHN144 is calculated.It is shown that the improved ACA has a satisfied convergence and search ability.

参考文献/References:

[1] 王会颖, 贾瑞玉. 一种求解0-1背包问题的快速蚁群算法 [J]. 计算机技术与发展, 2007(1):104-107.doi:10.3969/j.issn.1673-629X.2007.01.035.
[2] 高尚, 杨靖宇. 最短路的蚁群算法收敛性分析 [J]. 科学技术与工程, 2006(3):273-277.doi:10.3969/j.issn.1671-1815.2006.03.008.
[3] GUTJAHR W J. A graph-based ant system and its convergence [J]. Future Generation Computer Systems, 2000(8):873-888.doi:10.1016/S0167-739X(00)00044-3.
[4] GUTJAHR W J. ACO algorithms with guaranteed convergence to the optimal solution [J]. Information Processing Letters, 2002(3):145-153.doi:10.1016/S0020-0190(01)00258-7.
[5] STUTZLE T, DORIGO M. A short convergence proof for a class of ant colony optimization Algorithms [J]. IEEE Transactions on Evolutionary Computation, 2002(4):358-365.doi:10.1109/TEVC.2002.802444.
[6] 段海滨, 王道波. 蚁群算法的全局收敛性研究及改进 [J]. 系统工程与电子技术, 2004, (10):1506-1509.doi:10.3321/j.issn:1001-506X.2004.10.049.
[7] 宋海洲. TSP问题的一种快速近似算法及应用 [J]. 华侨大学学报(自然科学版), 2005(3):231-234.doi:10.3969/j.issn.1000-5013.2005.03.002.

相似文献/References:

[1]张银明.元素判别值分配法在求解TSP问题中的应用[J].华侨大学学报(自然科学版),2002,23(2):191.[doi:10.3969/j.issn.1000-5013.2002.02.018]
　Zhang Yinming.Application of the Allocation of Element Discrimination Value to the Solution of Traveling Salesman Problem[J].Journal of Huaqiao University(Natural Science),2002,23(5):191.[doi:10.3969/j.issn.1000-5013.2002.02.018]
[2]王占锋,杜海莲,安素芳,等.求解车辆路径问题的改进蚁群算法[J].华侨大学学报(自然科学版),2013,34(1):36.[doi:10.11830/ISSN.1000-5013.2013.01.0036]
　WANG Zhan-feng,DU Hai-lian,AN Su-fang,et al.An Improved Ant Colony Algorithm Based on Vehicle Routing Problem[J].Journal of Huaqiao University(Natural Science),2013,34(5):36.[doi:10.11830/ISSN.1000-5013.2013.01.0036]
[3]彭臻,王田,李晨阳,等.采用蚁群算法的移动摄像头探访规划[J].华侨大学学报(自然科学版),2014,35(5):533.[doi:10.11830/ISSN.1000-5013.2014.05.0533]
　PENG Zhen,WANG Tian,LI Chen-yang,et al.Visit Schedule of Mobile Cameras Base on Ant Colony Optimization[J].Journal of Huaqiao University(Natural Science),2014,35(5):533.[doi:10.11830/ISSN.1000-5013.2014.05.0533]

备注/Memo

备注/Memo:
福建省自然科学基金资助项目(Z0511028)
更新日期/Last Update: 2014-03-23