基于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.

相关文章!
  • 融合正向建模与反求计算的车用

    崔庆佳 周兵 吴晓建 李宁 曾凡沂<br />
    摘 要:针对减振器调试过程中工程师凭借经验调试耗时耗力等局限性,引入反求的思想,开展了

  • 浅谈高校多媒体教育技术的应用

    聂森摘要:在科学技术蓬勃发展的今天,我国教育领域改革之中也逐渐引用了先进技术,如多媒体技术、网络技术等,对于提高教育教学水平有很

  • 卫星天线过顶盲区时机分析

    晁宁+罗晓英+杨新龙<br />
    摘 要: 分析直角坐标框架结构平台和极坐标框架平台结构星载天线在各自盲区状态区域附近的发散问题。通过建