论文部分内容阅读
蚁群优化算法(Ant Colony Optimization Algorithm,ACO)源于对蚁群觅食过程的研究,通过每只蚂蚁的简单搜索,整个蚁群能够发现食物源与蚁巢之间距离最短的路线,是以群体智能为基础的一种元启发式搜索算法。因为ACO实现起来不算很复杂,并且具有较强鲁棒性、正反馈性等优点,从而得到广泛的应用。但是传统ACO在解决大规模优化问题上,容易出现早熟的现象且计算时间太长,而改进的并行ACO算法能够明显减少求解问题的时间。计算机图形处理器(Graphic Processing Unit,GPU)近年来发展迅速,其处理器核心采用多流水线结构、支持数据向量处理以及达到了 32位浮点精度,是一个性能非常强大的并行通用计算平台。此外,NVIDIA公司还推出了专门的统一计算设备架构(Compute Unified Device Architecture,CUDA)。CUDA 架构中除了具有非常多的高性能并行计算指令,还提供了大量接口用于直接访问硬件,新的优化架构使得GPU提供的硬件计算资源的访问变得更加高效。因此针对大规模的实际应用,基于CUDA并行的的数据运算能够取得很好的性能。为了减少ACO在处理大规模问题时的计算时间,提升算法的性能,本文根据GPU的架构特性,改进了一种基于分组轮盘赌的GPU并行蚁群算法。使用CUDA内核并行求解ACO算法,并运用了新的轮盘赌策略来加强算法的并行性。本文根据改进的并行模型与策略,实现了并行的最大最小蚂蚁系统用于求解旅行商问题,详细阐述了算法的设计思想,并给出了具体的程序设计流程与实验结果。在相同的实验环境下对比了相应的串行算法和其他并行蚁群算法,针对实验结果,分析了本文算法特点。从实验的结果可以看出本文改进的ACO取得了非常好的优化效果,算法求解的时间明显得到了缩减。