[1]张军 刘羽 卢奉良.蚁群算法解决TSP问题的并行化研究与实现[J].计算机技术与发展,2011,(05):72-74.
　ZHANG Jun,LIU Yu,LU Feng-liang.Parallel Research and Implementation of Ant Colony Algorithm to Solve Problem of TSP[J].,2011,(05):72-74.
点击复制

蚁群算法解决TSP问题的并行化研究与实现()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2011年05期
页码:
72-74
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
Parallel Research and Implementation of Ant Colony Algorithm to Solve Problem of TSP
文章编号:
1673-629X（2011）05-0072-03
作者:
张军 刘羽 卢奉良
桂林理工大学信息科学与工程学院
Author(s):
ZHANG Jun;  LIU Yu;  LU Feng-liang
School of Information Science and Engineering ,Guilin University of Technology
关键词:
蚁群算法; TSP问题; 多核; OpenMp; 并行优化
Keywords:
ant colony algorithm;  the problem of TSP;  multi-core;  OpenMp ;  parallel optimization
分类号:
TP39
文献标志码:
A
摘要:
蚁群算法在处理大规模TSP（Traveling Salesman Problem）问题时耗时较长，为了解决这一不足，给出一种基于多核环境下的并行优化算法。采用OpenMp并行优化技术对蚁群算法中最为耗时的循环迭代和循环赋值部分进行改进，减少其运算时间，同时利用粗粒度并行策略和PC机多核的优势将具有一定规模的小蚁群分配到对应的处理器上，使其并行执行，并且在适当时机让各处理器上的蚁群进行相互问的通信。通过实验证明，改进后的并行蚁群算法程序执行时间明显缩短，执行效率显著提高。由此可见，改进后的并行蚁群算法是可行有效的
Abstract:
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

相似文献/References:

[1]段军,张清磊.蚁群算法在LEACH路由协议中的应用[J].计算机技术与发展,2014,24(01):65.
　DUAN Jun,ZHANG Qing-lei.Application of Ant Colony Algorithm Based on LEACH Routing Protocol[J].,2014,24(05):65.
[2]何小娜 逄焕利.基于二维直方图和改进蚁群聚类的图像分割[J].计算机技术与发展,2010,(03):128.
　HE Xiao-na,PANG Huan-li.Image Segmentation Based on Improved Ant Colony Clustering and Two- Dimensional Histogram[J].,2010,(05):128.
[3]熊伟平 曾碧卿.几种仿生优化算法的比较研究[J].计算机技术与发展,2010,(03):9.
　XIONG Wei-ping,ZENG Bi-qing.Studies on Some Bionic Optimization Algorithms[J].,2010,(05):9.
[4]林本强 唐依珠.基于蚁群算法的移动自适应网QoS路由算法[J].计算机技术与发展,2009,(06):9.
　LIN Ben-qiang,TANG Yi-zhu.Ant Colony Algorithm Based Ad Hoc Network QoS Routing Algorithm[J].,2009,(05):9.
[5]古明家 宣士斌 廉侃超 李永胜.基于蚁群和人工鱼群算法融合的QoS路由算法[J].计算机技术与发展,2009,(07):145.
　GU Ming-jia,XUAN Shi-bin,LIAN Kan-chao,et al.QoS Routing Algorithm Based on Combination of Modified Ant Colony Algorithm and Artificial Fish Swarm Algorithm[J].,2009,(05):145.
[6]姜学鹏 洪贝 曹耀钦.基于证据理论决策的蚁群优化算法[J].计算机技术与发展,2009,(08):120.
　JIANG Xue-peng,HONG Bei,CAO Yao-qin.Ant Colony Optimal Algorithms Based on Evidence Theory[J].,2009,(05):120.
[7]贾瑞玉 张新建 冯伦阔 李永顺.信息素增量动态更新的改进蚁群算法[J].计算机技术与发展,2009,(09):32.
　JIA Rui-yu,ZHANG Xin-jian,FENG Lun-kuo,et al.Ant Colony Algorithm with Dynamic Pheromones Increment Updating[J].,2009,(05):32.
[8]鲍娜 张德贤 孙傲冰 王飞.基于改进蚁群算法的网格组合拍卖资源分配[J].计算机技术与发展,2009,(10):149.
　BAO Na,ZHANG De-xian,SUN Ao-bing,et al.Research on Resource Allocation of Combinatorial Auction in Grid Based on Improved Ant Colony Algorithm[J].,2009,(05):149.
[9]邓义乔 张代远.蚁群算法在搜索引擎系统中的应用研究[J].计算机技术与发展,2009,(12):21.
　DENG Yi-qiao,ZHANG Dai-yuan.Research and Application of Ant Colony Algorithm in Searching Engine System[J].,2009,(05):21.
[10]段凤玲 李龙澍 曹文婷.具有多态特征和聚类处理的蚁群算法[J].计算机技术与发展,2009,(12):77.
　DUAN Feng-ling,LI Long-shu,CAO Wen-ting.Ant Colony Algorithm with Polymorphism and Clustering Processing[J].,2009,(05):77.
[11]宋世杰 刘高峰 周忠友 卢小亮.基于改进蚁群算法求解最短路径和TSP问题[J].计算机技术与发展,2010,(04):144.
　SONG Shi-jie,LIU Gao-feng,ZHOU Zhong-you,et al.An Improved Ant Colony Algorithm Solving the Shortest Path and TSP Problem[J].,2010,(05):144.

备注/Memo

备注/Memo:
广西自然科学基金（桂科自0832249）张军（1984-），男，湖北监利人，硕士研究生，研究方向为并行计算；刘羽，教授，博士，研究方向为并行计算、计算机网络
更新日期/Last Update: 1900-01-01