基于GPU的共享信息素矩阵多蚁群算法

吉林大学学报(工学版) ›› 2011, Vol. 41 ›› Issue (6): 1678-1683.

基于GPU的共享信息素矩阵多蚁群算法

白洪涛^1,2,欧阳丹彤^3,4,李熙铭^3,4,何丽莉^3,4

1.吉林大学公共计算机教学与研究中心|长春 130012；2.吉林大学地球探测科学与技术学院|长春 130026；3.吉林大学计算机科学与技术学院|长春 130012；4.吉林大学符号计算与知识工程教育部重点实验室|长春 130012

收稿日期:2009-06-19 出版日期:2011-11-01 发布日期:2011-11-01
通讯作者: 欧阳丹彤(1968-),女,教授,博士生导师.研究方向：基于模型的诊断和定理机器证明,并行计算. E-mail:ouyangdantong@163.com
作者简介:白洪涛(1975-),男,讲师,博士．研究方向：高性能计算,模型检测.E-mail:baihongtao@263.net
基金资助:
国家自然科学基金项目(60973089)；教育部博士学科点专项科研基金项目（20100061110031）；吉林省科技发展计划项目基金(20101501)；吉林省科技发展计划青年基金项目（201101039）；吉林大学符号计算与知识工程教育部重点实验室开放项目(93K-17-2009-K05)；吉林大学科学前沿与交叉学科创新项目（201103134）.

Multiple ant colonies sharing common pheromone matrix based on CPU

BAI Hong-tao^1,2, OU YANG Dan-tong^3,4, LI Xi-ming^3,4, HE Li-li^3,4

1.Center for Computer Fundamental Education, Jilin University,Changchun |130012,China;2.College of Earth Survey Science and Technology, Jilin University, Changchun 130026, China;3.College of Computer Science and Technology,Jilin University,Changchun 130012,China;4.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education,Jilin University,Changchun 130012,China

Received:2009-06-19 Online:2011-11-01 Published:2011-11-01

摘要/Abstract

摘要：

在研究并行蚁群信息素交流方法的基础上,提出了一种适于GPU统一计算架构模型的多蚁群算法。采用多个同构和异构蚁群共享同一信息素矩阵的交流策略,解决信息素多样性和算法性能之间的矛盾。在路径探索阶段,多只获得迭代最优解且差异较大的蚂蚁共同释放信息素,以利群体多样性；在路径开发阶段,获得唯一全局最优解的蚂蚁释放信息素,以利迅速收敛。多蚁群映射到GPU的线程块而群内蚂蚁对应块内多线程。以MMAS和ACS混合为例给出了该策略下信息素初始化和动态界限的新方法,证明了算法是值收敛和解收敛的。在标准TSP问题实例上的实验评测表明,该算法不仅提升了性能,在充分收敛条件下获得了更高质量的解。

关键词: 计算机软件, 蚁群优化, 共享信息素矩阵, 图形处理器, 统一计算架构

Abstract:

A parallel algorithm of multiple ant colonies on Compute Unified Device Architecture (CUDA) computation model of CPU is presented. Several integrated different kind of ant colonies share common pheromone matrix during the process of solution construction and pheromone trail update steps. Multiple ants, corresponding to those iteration-so-far-tours, update pheromone matrix to obtain the diversity throughout explorative search phase; and the one, corresponding to the best-so-far-tours, deposits pheromone to accelerate constringency from exploitation phase. Ant colonies are mapped to the thread blocks and ants within colony correspond to massively threads of CUDA. The mix of MMAS and ACS is implemented that a new initializing method and the max and min pheromone trail limits are used. Convergences both in value and solution are proved and experiments on TSPLIB demonstrate that this algorithm can get good average solution quality, and outperform the sequential MMAS, ACS and parallel algorithm with a dual-core CPU.

Key words: computer software, ant colony optimization, sharing common pheromone matrix, graphics processing unit, compute unified device architecture

中图分类号:

TP311.1

白洪涛^1,2,欧阳丹彤^3,4,李熙铭^3,4,何丽莉^3,4. 基于GPU的共享信息素矩阵多蚁群算法[J]. 吉林大学学报(工学版), 2011, 41(6): 1678-1683.

BAI Hong-tao, OU YANG Dan-tong, LI Xi-ming, HE Li-li. Multiple ant colonies sharing common pheromone matrix based on CPU[J]. 吉林大学学报(工学版), 2011, 41(6): 1678-1683.

参考文献

相关文章 15

[1]	马健, 樊建平, 刘峰, 李红辉. 面向对象软件系统演化模型[J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[2]	林金花, 王延杰, 孙宏海. 改进的自适应特征细分方法及其对Catmull-Clark曲面的实时绘制[J]. 吉林大学学报(工学版), 2018, 48(2): 625-632.
[3]	罗养霞, 郭晔. 基于数据依赖特征的软件识别[J]. 吉林大学学报(工学版), 2017, 47(6): 1894-1902.
[4]	应欢, 王东辉, 武成岗, 王喆, 唐博文, 李建军. 适用于商用系统环境的低开销确定性重放技术[J]. 吉林大学学报(工学版), 2017, 47(1): 208-217.
[5]	李勇, 黄志球, 王勇, 房丙午. 基于多源数据的跨项目软件缺陷预测[J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[6]	王念滨, 祝官文, 周连科, 王红卫. 支持高效路径查询的数据空间索引方法[J]. 吉林大学学报(工学版), 2016, 46(3): 911-916.
[7]	特日跟, 江晟, 李雄飞, 李军. 基于整数数据的文档压缩编码方案[J]. 吉林大学学报(工学版), 2016, 46(1): 228-234.
[8]	康辉, 王家琦, 梅芳. 基于Pi演算的并行编程语言[J]. 吉林大学学报(工学版), 2016, 46(1): 235-241.
[9]	陈鹏飞, 田地, 杨光. 基于MVC架构的LIBS软件设计与实现[J]. 吉林大学学报(工学版), 2016, 46(1): 242-245.
[10]	刘磊, 王燕燕, 申春, 李玉祥, 刘雷. Bellman-Ford算法性能可移植的GPU并行优化[J]. 吉林大学学报(工学版), 2015, 45(5): 1559-1564.
[11]	冯晓宁, 王卓, 张旭. 基于L-π演算的WSN路由协议形式化方法[J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[12]	李明哲, 王劲林, 陈晓, 陈君. 基于网络处理器的流媒体应用架构模型(VPL)[J]. 吉林大学学报(工学版), 2015, 45(5): 1572-1580.
[13]	武勇, 王俊, 曹运合, 张培川. 基于二次预测的粒子滤波算法[J]. 吉林大学学报(工学版), 2015, 45(5): 1696-1701.
[14]	王克朝, 王甜甜, 苏小红, 马培军. 基于频繁闭合序列模式挖掘的学生程序雷同检测[J]. 吉林大学学报(工学版), 2015, 45(4): 1260-1265.
[15]	黄宏涛，王静，叶海智，黄少滨. 基于惰性切片的线性时态逻辑性质验证[J]. 吉林大学学报(工学版), 2015, 45(1): 245-251.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed