基于GPU加速的并行蚁群算法求解旅行商问题研究

    杨雅宁+蔺勇

    

    

    摘要：蚁群算法是求解旅行商问题的有效方法之一，但是随着蚁群规模和城市规模的增大，算法的运行速度将大大降低，本文利用GPU在CUDA7.0环境下，对蚁群算法进行化加速设计，实验结果表明，该方法取得了良好的加速效果，当蚁群规模增大时，加速倍大幅度提高。数据显示，蚁群个体和城市规模越大，加速效果越好。

    关键词：蚁群算法；GPU；CUDA

    中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）12-0206-02

    旅行商问题（Traveling Salesman Problem，简称TSP）是一个典型的组合优化问题。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等现实生活中的优化问题都可以归结为TSP求解问题。它解决从一个城市出发，经过若干个城市后又返回原城市的最优路径的求解问题。

    蚂蚁在觅食路径上会释放一种特殊的分泌物—“信息素”，随着时间流逝，信息素会挥发，后面的蚂蚁根据路径上的信息素浓度，选择信息素多的路径去觅食，这样便形成了一个正反馈机制。在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但它们的行为具有非常高的自组织性，相互之间交换路径，最终寻找到最优路径。受到蚁群系统信息共享机制的启发，意大利学者DorigoM于1992年首次系统提出了蚁群算法，并成功地将该方法应用到求解TSP问题中[1]。该算法是启发式搜算算法的一种，采用了分布式并行计算机制，易于与其他方法结合，具有强的鲁棒性。同时，相对于其他搜算法，对初始路线要求不高，在搜索过程中不需要人工调整。研究表明，蚁群算法是解决TSP问题有效的算法之一，因此也成为近年来的研究热点。

    近年来，基于GPU（图像处理器）的大规模通用并行计算，大大提高了计算机图形处理的效率[2]。GPU的高速浮点运算能力、并行计算和可编程功能也为通用计算提供了良好的并行计算平台，同时也为蚁群算法的高速并行实现提供了可能。NVIDIA公司的统一计算设备架构（CUDA），为研究人员利用CPU进行数据并行处理提供了便捷的手段[3]。通过GPU加速并行算法，是蚁群算法并行化、提高算法执行速度的有效途径之一。

    1 蚁群算法基本原理

    蚁群算法受蚁群行为和反应特征的启发而得来的。觅食的蚂蚁在走过的路上释放信息素，其他觅食蚂蚁将沿着留有信息素的路径在相同位置找到食物。因此，信息素可用来实现间接通信的目的[4]。基于信息素的城市探知转移概率公式：

    2 基于GPU并行的蚁群算法

    通过对CUDA和GPU并行程序设计的研究，将基于蚁群算法的TSP求解优化路径问题转化为GPU中的多线程的并行处理过程，充分利用GPU的高速浮点运算和并行计算的特性， 以提高算法的速度。

    在蚂蚁遍历城市的过程中，每只蚂蚁独立地建立自己的遍历路径，对蚂蚁来说，自然地存在并行性。根据CUDA的编程模型[5]，我们很自然地会将每只蚂蚁个体映射到CUDA的一个线程上，用线程来模拟你蚂蚁个体，每个线程完成一只蚂蚁的城市周游回路。

    设蚂蚁个数为M，城市个数为N，CUDA中Block个数为4，蚁群算法的GPU并行化模型中，总线程个数为M，每个Block中线程个数为M/4，如图3所示。在模型中，将路径状态初始化、路径转移概率计算、路径长度计算、更新信息素定义为CUDA函数。首先，M个线程被分配在4个Block中，同时启动，计算各自的城市转移概率，寻找转移城市；其次，由N个线程分成N个Block，计算路径上信息素增量；再次，用一个线程计算路径长度和最优路径；最后N个线程分成N个Block，更信路径信息素。

    3 实验与分析

    实验结果表明，采用GPU并行化蚁群算法取得了良好的加速效果，当蚁群规模由256增大到1024、城市规模由21增大到76时，加速倍数由3.0增大到10.75。数据显示，问题规模越大，蚁群个体和城市规模越大，加速效果越好，对于更大规模的复杂问题，基于GPU的并行化蚁群算法将取得更高的加速比。

    4 结束语

    本文研究了基本蚁群算法的原理，并基于GPU和CUDA高速并行计算模型，利用GPU在CUDA7.0环境下，对蚁群算法进行化加速设计，实验结果表明，该方法取得了良好的加速效果，当蚁群规模增大时，加速倍大幅度提高。数据显示，蚁群个体和城市规模越大，加速效果越好。

    参考文献：

    [1] 宗德才， 王康康， 丁勇. 蚁群算法求解旅行商问题综述[J]. 计算机与数字工程， 2014（11）.

    [2] 占正锋， 李戈， 张学贺， 伊旭悦. 基于CUDA的图像预处理并行化研究[J]. 智能工程， 2014.

    [3] 李建明， 胡祥培， 庞占龙， 钱昆明. 一种基于GPU 加速的细粒度并行蚁群算法[J]. 控制与决策， 2009（8）.

    [4] Shi-An Li，Min-Hao Yang，Chung-Wei Weng，Yi-Hong Chen，Chia-Hung Lo，Ching-Chang Wong. Ant Colony Optimization algorithm design and its FPGA implemention[J]. IEEE International Symposium on Intelligent Signal Processing and Communication Systems， 2012.

    [5] David B.KirK， Wen-mei W. Hwu. 大规模并行处理器编程实战[M]. 北京： 清华大学出版社， 2013.