期刊文献+

一种快速求解旅行商问题的蚁群算法 被引量:30

A Fast Ant Colony Optimization Algorithm for Traveling Salesman Problems
下载PDF
导出
摘要 蚁群优化是一种元启发式的随机搜索技术,是目前解决组合优化问题最有效的工具之一.将信息素更新和随机搜索机制的改进相结合,提出一种快速求解旅行商问题的蚁群算法.首先给出了一种新的信息素增量模型,以体现蚂蚁在不同路径上行走时所产生的信息素差异;然后以蚂蚁经过的路径(直线段)作为信息素扩散浓度场的信源,改进了信息素扩散模型,强化了蚂蚁间的协作和交流;最后采用较低复杂度的变异策略对迭代的结果进行优化.在大量通用数据集上的实验表明,该算法不仅能获得更好的最优解,而且收敛速度有显著的提高. Ant colony optimization (ACO) is a population-based metaheuristic technique to solve combination optimization problems effectively, such as traveling salesman problem (TSP), multidimensional knapsack problem (MKP), and so on. However, how to improve the performance of ACO algorithms is still an active research topic. Though there are many algorithms solving TSPs effectively, there is an application bottleneck that the ACO algorithm costs too much time in order to get an optimal solution. Combining the pheromone updating with an improvement of the stochastic search strategy, a fast ACO algorithm for solving TSPs is presented in this paper. Firstly, a new pheromone increment model called ant constant, which keeps energy conversation of ants, is introduced to embody the pheromone difference of different candidate paths. Meanwhile, a pheromone diffusion model, which is based on info fountain of a path, is established to reflect the strength field of the pheromone diffusion faithfully, and it strengthens the collaboration among ants. Finally, a simple mutation strategy with lower computational complexity is adopted to optimize the evolution result. Experimental results on different benchmark data sets show that the proposed algorithm can not only get better optimal solutions but also enhance greatly the convergence speed.
出处 《计算机研究与发展》 EI CSCD 北大核心 2009年第6期968-978,共11页 Journal of Computer Research and Development
基金 国家自然科学基金重大项目(60496322) 北京市自然科学基金项目(4083034) 北京市教育委员会科技发展基金项目(KM200610005020)~~
关键词 旅行商问题 蚁群优化 增量模型 扩散模型 变异策略 traveling salesman problem ant colony optimization increment model diffusion model mutation strategy
  • 相关文献

参考文献12

  • 1Dorigo M, Colorni A, Maniezzo V. Distributed optimization by ant colonies [C] //Proc of the 1st European Conf of Artificial Life. Paris: Elsevier, 1991.. 134-142.
  • 2Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperating agents [J]. IEEE Trans on Systems, Man, and Cybernetics, Part B, 1996, 26 (1): 29-41.
  • 3Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Trans on Evolutionary Computation, 1997, 1(1): 53-66.
  • 4Gambardetla L M, Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies [C]//Proc of the Int Conf on Evolutionary Computation. Piscataway, NJ: IEEE, 1996:622-627.
  • 5Stutzle T, Hoos HH. MAX-MIN ant system and local search for the traveling salesman problem[C]//Proc of the IEEE Int Conf on Evolutionary Computation. Piscataway, NJ: IEEE, 1997:309-314.
  • 6黄国锐,曹先彬,王煦法.基于信息素扩散的蚁群算法[J].电子学报,2004,32(5):865-868. 被引量:76
  • 7吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245. 被引量:306
  • 8吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1328-1333. 被引量:247
  • 9丁建立,陈增强,袁著祉.遗传算法与蚂蚁算法的融合[J].计算机研究与发展,2003,40(9):1351-1356. 被引量:287
  • 10肖鹏,李茂军,张军平,叶涛.单亲遗传算法及其在物流配送系统中的应用[J].系统工程,2000,18(1):64-66. 被引量:99

二级参考文献21

  • 1康立山 谢云 等.非数值并行算法(第1册)[M].北京:科学出版社,1997..
  • 2Marco Dorigo, Gambardella, Luca Maria. Ant colonies for the traveling salesman problem. Biosystems, 1997, 43(2): 73~81.
  • 3Marco Dorigo, Gambardelh, Luca Maria. Ant colony system: A cooperative learning approach to the traveling salesaum problem. IEEE Trans on Evolutionary Computation, 1997, 1(1) : 53~66.
  • 4Marco Dorigo, Eric Bonabeau, Theranlaz Guy. Ant algorithms and stigmergy. Future Generation Computer System, 2000, 16(8) : 851~871.
  • 5Thomas Stutzle, Holger H Hoos et al. MAX-MIN ant system. Future Generation Computer System, 2000, 16(8) : 889~914.
  • 6Marcus Randall, Andrew Lewis. A parallel implementation of ant colony optimization. Journal of Parallel and Distributed Computing, 2002, 62(9): 1421~1432.
  • 7Jiang Rui,Proc Conference on Intelligent Information Processing(WCC 2000 IIP 2000),2000年,478页
  • 8Wu Qinghong,计算机研究与发展,1999年,36卷,10期,1240页
  • 9康立山,非数值并行算法.1 模拟退火算法,1997年
  • 10Dorigo M,et al.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B,1996,26(1):29-41.

共引文献879

同被引文献308

引证文献30

二级引证文献369

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部