基于GPU的并行蚁群优化算法的研究与实现
Stuty and Realization of Parallel Ant Colony Optimization Based on GPU
蚁群优化算法(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算法的特点。实验结果表明本文算法在取得了较好优化效果的同时,提高了算法的运算速度。
- 作者：
- 付杰
- 学位授予单位：
- 中国舰船研究院
- 专业名称：
- 计算机应用技术
- 授予学位：
- 硕士
- 学位年度：
- 2011年
- 导师姓名：
- 周国华
- 中图分类号：
- TP301.6
- 关键词：
- 蚁群优化算法；GPU；并行算法
- Ant Colony Optimization；GPU；Parallel Algorithm