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