学位论文 > 优秀研究生学位论文题录展示

基于GPU的并行蚁群优化算法的研究与实现

作 者: 付杰
导 师: 周国华
学 校: 中国舰船研究院
专 业: 计算机应用技术
关键词: 蚁群优化算法 GPU 并行算法
分类号: TP301.6
类 型: 硕士论文
年 份: 2011年
下 载: 97次
引 用: 0次
阅 读: 论文下载
 

内容摘要


蚁群优化算法(Ant Colony Optimization,ACO)源于对蚂蚁觅食行为的研究,是一种基于群体智能方法的优化计算技术,在实际工程中表现出巨大的潜力。但在数值建模和优化计算等许多领域中,处理大量数据和求解大规模复杂问题时,ACO算法依然需要大量的计算时间。ACO的设计架构本质上具有并行性,所以将算法并行处理可以获得很高的性能提升,因此成为一个研究热点。当前并行ACO算法主要在并行机上运行或用多线程技术模拟,主要存在下述不足:大多数研究人员没有硬件环境,无法使用并行机解决问题;多线程技术是在CPU上用串行模拟并行,不能真正提高性能。近年来,计算机图形处理器(Graphics Processing Unit, GPU)的高性能并行计算能力以及近年来所发展起来的可编程性能,使其在并行计算领域的应用有着巨大的潜力。统一计算设备架构(Compute Unified Device Architecture, CUDA)是NVIDIA公司推出的GPU编程统一计算设备架构。在统一计算设备架构之下,GPU执行的模式是并发的线程。多个线程可以组成一个线程块,一个线程块中的线程能够存取同一块公用的存储空间,而且可以快速地进行同步操作。本文针对传统并行蚁群算法的不足,结合GPU的高性能并行计算能力,提出了一种基于GPU加速的并行蚁群优化算法,使ACO算法在GPU中加速执行。核心思想是让全部蚂蚁共享一个伪随机数矩阵,一个信息素矩阵,一个禁忌矩阵和一个概率矩阵。我们还使用了一个全新的基于这些矩阵的随机选择算法——AIR (All-In-Roulette)。本文主要以最大-最小蚂蚁系统的并行实现为例,详细描述了算法设计思想和程序实现过程,提供了应用于TSP问题的实验结果,与相应串行算法在相同计算环境下的实验结果做出比较,并针对实验结果分析了并行ACO算法的特点。实验结果表明本文算法在取得了较好优化效果的同时,提高了算法的运算速度。

全文目录


摘要  4-5
ABSTRACT  5-8
插图和附表清单  8-10
第一章 绪论  10-17
  1.1 研究背景与意义  10-11
  1.2 发展历史及研究现状  11-15
  1.3 本课题的研究思路和主要内容  15
  1.4 本文的组织框架  15-17
第二章 蚁群优化算法分析  17-24
  2.1 元启发式算法  17
  2.2 蚁群模型分析  17-22
    2.2.1 觅食原理  18-20
    2.2.2 问题描述  20
    2.2.3 人工蚂蚁的行为  20-22
    2.2.4 ACO 算法框架  22
  2.3 蚁群算法的其他模型  22-24
第三章 基于 GPU 的并行蚁群优化算法  24-57
  3.1 GPU 并行计算模型分析  24-35
    3.1.1 GPU 的硬件架构  27-29
    3.1.2 CUDA 程序设计模型  29-30
    3.1.3 CUDA 的线程模型  30-33
    3.1.4 CUDA 的存储器模型  33-35
  3.2 建立数学模型  35-40
    3.2.1 旅行商问题  35-37
    3.2.2 蚁群系统  37-38
    3.2.3 最大-最小蚂蚁系统  38-40
  3.3 并行MMAS 算法设计  40-57
    3.3.1 MMAS 算法模型  42-47
    3.3.2 蚁群优化算法并行化的理论分析  47-49
    3.3.3 GPU 存储器的优化设计  49-52
    3.3.4 具体算法实现  52-57
第四章 实验与分析  57-64
  4.1 并行MMAS 实验结果  57-58
  4.2 并行MMAS 运行时间分析  58-64
第五章 总结与展望  64-65
致谢  65-66
参考文献  66-69
攻读硕士学位期间发表的论文和取得的科研成果  69-70
详细摘要  70-73

相似论文

  1. 基于并行算法的模糊综合评价模型的设计与应用,TP18
  2. 基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
  3. 基于GPU的有限元方法研究,O241.82
  4. 基于图形处理器的SIFT算法研究,TP391.41
  5. GPU加速的仿射算术在几何设计中的应用研究,TP391.41
  6. GPU加速的粒子滤波PET图像重建算法,TP391.41
  7. 基于GPU的时间序列并行检索算法研究,TP391.41
  8. 基于CPU的源强反算算法研究,TP18
  9. 基于GPU的X射线重建算法加速研究,TP391.41
  10. 基于GPU的EDA加速技术,TP391.41
  11. AST3实时数据处理系统关键技术的研究,TP274
  12. GPU通用计算与基于SIFT特征的图像匹配并行算法研究,TP391.41
  13. 水平旋转式贴片机贴装过程优化研究,TN405
  14. 基于改进蚁群算法的油田注水管网规划设计研究,TE357.6
  15. 蚁群算法在风光互补系统优化配置中的应用,TM61;TM71
  16. 基于GPU的并行支持向量机的设计与实现,TP391.41
  17. 三维锥束CT图像重建加速技术研究,TP391.41
  18. 图像匹配的并行算法研究,TP301.6
  19. 基于GPU的二维流场可视化线性积分卷积方法的研究与实现,TP391.41
  20. GPU高性能计算技术在晶格玻尔兹曼方法模拟中的应用,TP391.41

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com