基于GPU加速的细粒度并行蚁群算法

摘要

蚁群优化算法(Ant colony optimization algorithin，ACO)源于对蚂蚁觅食行为的研究，是一种基于群体智能方法的演化计算技术，在实际工程中表现出巨大的潜力。但在数值建模和优化计算等许多领域中，处理大量数据和求解大规模复杂问题时，ACO算法依然需要大量的计算时间，而并行ACO算法由于能较大幅度缩减问题求解的时间，因此成为一个研究热点。当前并行ACO算法主要在并行机上运行或用多线程技术模拟，主要存在下述不足：进程间通信损耗限制了粒子规模；大多数研究人员没有硬件环境，无法使用并行机解决问题；多线程技术是在CPU上用串行模拟并行，不能真正提高性能。 近年来，计算机图形处理器(Graphics processing unit，GPU)绘制流水线的高速度和并行性以及近年来发展起来的可编程功能，使其在通用计算领域的应用有着巨大的潜力。CUDA是Nvidia公司推出的GPU编程的统一计算设备架构。在统一计算设备架构下，GPU执行的模式是并发的线程。多个线程可以组成一个线程块。一个线程块中的线程能存取同一块公用的存储空间，而且可以快速进行同步的动作。 本文针对传统并行蚁群算法在实际应用中的不足，结合GPU的高速并行性，提出了一种基于GPU加速的细粒度并行蚁群算法(GPUACO)，将并行ACO求解过程转化为CUDA内核，使用CUDA线程块模拟蚂蚁个体，使ACO算法在GPU中加速执行。本文主要以最大最小蚂蚁系统和蚁群系统的并行实现为例，详细描述了算法设计思想和程序实现过程，提供了各自应用于对称TSP问题的实验结果，与相应串行算法在相同计算环境下的实验结果做出比较，并针对实验结果分析了GPUACO算法的特点。实验结果表明本文算法在取得了较好的优化效果的同时，解决了细粒度并行的蚁群规模限制问题，提高了算法的运算速度。

目录

文摘

英文文摘

声明

引 言

1蚁群算法及其并行的发展

1.1 TSP问题

1.2基本蚁群系统

1.3 AS扩展

1.4并行ACO的研究现状

2基于GPU的通用计算

2.1 基本概念

2.2 GPU通用计算的应用

2.3 GPU通用计算的限制

2.4.GPU通用计算的发展方向

3基于GPU加速的细粒度并行ACO

3.1 技术要点

3.2基于GPU的细粒度并行MMAS

3.3基于GPU的细粒度并行ACS

3.4本章小结

4实验与分析

4.1 GPUMMAS的实验结果

4.2 GPUACS的实验结果

4.3实验结果分析

4.4本章小结

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢