期刊文献+

蚁群算法解决TSP问题的并行化研究与实现 被引量:7

Parallel Research and Implementation of Ant Colony Algorithm to Solve Problem of TSP
下载PDF
导出
摘要 蚁群算法在处理大规模TSP(Traveling Salesman Problem)问题时耗时较长,为了解决这一不足,给出一种基于多核环境下的并行优化算法。采用OpenMp并行优化技术对蚁群算法中最为耗时的循环迭代和循环赋值部分进行改进,减少其运算时间,同时利用粗粒度并行策略和PC机多核的优势将具有一定规模的小蚁群分配到对应的处理器上,使其并行执行,并且在适当时机让各处理器上的蚁群进行相互间的通信。通过实验证明,改进后的并行蚁群算法程序执行时间明显缩短,执行效率显著提高。由此可见,改进后的并行蚁群算法是可行有效的。 In order to resolve the disadvantage that ant colony algorithm solves large scale TSP( Traveling Salesman Problem) consuming a large amount of time, give a parallel optimization algorithm at multi-core environment. Applying the technology of parallel optimization about OpenMp improves the part of iteration and cyclic assignment in ant colony algorithm,because this part consumes the most of time. At the same time using Coarse-grained parallel strategy and multi-core's advantage assign a certain amount of small-colony to the cor- responding processor, then makes it executed parallelly and communicated with each other at the appropriate time. The experiment proves that the improved method makes the time of program execution shorter significantly and the efficiency higher observably when solve large scale TSP. This shows that the improved ant colony algorithm in parallel is feasible and effective.
出处 《计算机技术与发展》 2011年第5期72-74,78,共4页 Computer Technology and Development
基金 广西自然科学基金(桂科自0832249)
关键词 蚁群算法 TSP问题 多核 OPENMP 并行优化 ant colony algorithm the problem of TSP multi-core OpenMp parallel optimization
  • 相关文献

参考文献9

  • 1OpenMp C and C++ Application Program Interface (Version 2.0) [ EB/OL]. 2002. http ://www. open,np, org.
  • 2Stutzle T, Hhoos H. The MAX-MIN ant system and local search for the traveling salesman problem [ C ]// Proceedings of the IEEE International Conference on Evolutionary Computation ( ICEC' 97). USA : Indianapolis, 1997:309-314.
  • 3王娟,王建.一种求解TSP问题的改进蚁群算法[J].计算机技术与发展,2008,18(12):50-52. 被引量:5
  • 4崔明义,张新祥,苏白云,张瑞.用蚁群算法实现地理信息系统空间曲线的描述[J].计算机工程与应用,2008,44(30):160-162. 被引量:3
  • 5Stiitzle T. Parallelization strategies for ant colony optimization [J]. Lecture Notes in Computer Science, 1998,1498: 722- 741.
  • 6Marcus, Randall, Andrew, et al. A parallel implementation of ant colony optimization[ J]. Journal of Parallel and Distributed Computing ,2002,62 : 1421 - 1432.
  • 7Ellabib I, Calamai P, Basir O. Exchange Strategies for Multiple Ant Colony System[ J]. Information Sciences: An International Journal ,2007,177 ( 5 ) : 1248-1264.
  • 8Middendorf M, Reischle F,Schmech H. Multi Colony Ant Algorithms[ J ]. Journal of Heuristics: Special Issue on Parallel Metaheuristics, 2002,8 ( 3 ) : 305 - 320.
  • 9何丽莉,王克淼,白洪涛,胡成全.基于CMP的多种并行蚁群算法及比较[J].吉林大学学报(理学版),2010,48(5):787-792. 被引量:3

二级参考文献23

共引文献8

同被引文献65

引证文献7

二级引证文献27

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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