学位论文 > 优秀研究生学位论文题录展示
基于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
|
相似论文
- 基于并行算法的模糊综合评价模型的设计与应用,TP18
- 基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
- 基于GPU的有限元方法研究,O241.82
- 基于图形处理器的SIFT算法研究,TP391.41
- GPU加速的仿射算术在几何设计中的应用研究,TP391.41
- GPU加速的粒子滤波PET图像重建算法,TP391.41
- 基于GPU的时间序列并行检索算法研究,TP391.41
- 基于CPU的源强反算算法研究,TP18
- 基于GPU的X射线重建算法加速研究,TP391.41
- 基于GPU的EDA加速技术,TP391.41
- AST3实时数据处理系统关键技术的研究,TP274
- GPU通用计算与基于SIFT特征的图像匹配并行算法研究,TP391.41
- 水平旋转式贴片机贴装过程优化研究,TN405
- 基于改进蚁群算法的油田注水管网规划设计研究,TE357.6
- 蚁群算法在风光互补系统优化配置中的应用,TM61;TM71
- 基于GPU的并行支持向量机的设计与实现,TP391.41
- 三维锥束CT图像重建加速技术研究,TP391.41
- 图像匹配的并行算法研究,TP301.6
- 基于GPU的二维流场可视化线性积分卷积方法的研究与实现,TP391.41
- GPU高性能计算技术在晶格玻尔兹曼方法模拟中的应用,TP391.41
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com
|