蚁群算法解决TSP问题的并行化研究与实现  

Parallel Research and Implementation of Ant Colony Algorithm to Solve Problem of TSP

作　　者：张军[1] 刘羽[1] 卢奉良[1] 

机构地区：[1]桂林理工大学信息科学与工程学院,广西桂林541004

出　　处：《计算机技术与发展》2011年第5期72-74,78,共4页Computer Technology and Development

基　　金：广西自然科学基金(桂科自0832249)

摘　　要：蚁群算法在处理大规模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.

关 键 词：蚁群算法 TSP问题 多核 OPENMP 并行优化 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]