基于图形处理器的快速蚁群算法（仅供参考）

1、精品毕业设计窗体顶端基于图形处理器的快速蚁群算法（仅供参考）摘要:蚁群优化算法在优化计算中已得到了很多应用,但在进行大规模优化时,执行时间过长仍是应用该算法的一个瓶颈.为此,研究了一种基于图形处理器(Graphics Process Unit, GPU)最新统一渲染架构CUDA(Compute Unified Device Architecture)的快速蚁群优化算法.该算法用CPU控制迭代,而蚂蚁的路径构建过程在GPU的多核处理器上并行完成,用以加速蚂蚁群体的周游进度.实验结果表明,该算法与串行蚁群优化算法相比,迭代速度提高了数十倍,同时也表明当前GPU通用计算也在一定程度上适合随机算法.关

2、键词:蚁群优化; 图形处理器; 并行计算; 统一渲染架构A Speed-up Ant Colony Algorithm Based on Graphics Process UnitsAbstract. Despite the numerous applications of ACO (Ant Colony Optimization) algorithm in optimization computation, it remains a computational bottleneck that the ACO algorithm costs too much time in order to

3、find an optimal solution for large-scaled optimization problems. Therefore, a quickly GPU-based (Graphics Process Unit) version under CUDA (Compute Unified Device Architecture, CUDA) of the ACO algorithm is presented. The iteration control is completed by CPU and solution construction step is offloa

4、ded to the GPU to speedup the whole tour process. Experiments demonstrate that the GPU-based algorithm makes the speed of convergence dozens of times faster than the CPU-version. At the same time, they illustrate that the general purpose GPU environment is suited to heuristic algorithms.Key words: A

5、CO; GPU; parallel computing; CUDA0 引言蚁群优化(Ant Colony Optimization, ACO)算法是模拟自然界中真实蚁群的觅食行为而形成的一种模拟进化算法,于20 世纪 90 年代意大利的M.Dorigo等学者提出1,2.ACO首先应用于旅行商问题(Traveling Salesman Problem, TSP)3,并取得了较好的结果.其后,ACO被广泛用于求解路由问题4、分配问题5、调度问题6等NP完全问题,显示出ACO在求解复杂组合优化问题方面的优越性.随着现实世界中问题的规模越来越大,ACO算法存在搜索时间过长的问题.为了提高ACO的收敛性

6、能,国内外学者提出了很多改进算法.如文献7提出基于变异和动态信息素更新的策略.文献8提出一种相遇算法等.除串行算法优化外,ACO的生态属性及设计思想决定了ACO的并行化是提升性能尤其是缩短迭代时间的自然方向.大部分并行策略都可以归结为精细并行策略和粗糙并行策略.对于精细并行策略,Bolondi等针对TSP提出了一种方法,采用了每一个处理器对应一只蚂蚁的策略,当所有蚂蚁完成一次搜索时进行同步.实验表明,庞大的通信开销成为这种方式的主要瓶颈.对于粗糙并行策略,多个蚁群并行地工作在不同的处理器中,蚁群每隔一定的时间间隔进行一次信息交换,各算法的区别在于信息交换的时机和内容不同9-11.另一种是基于共

7、享存储体系架构的并行化,这种并行化策略目前的研究还不多,在12中有所尝试,环境是OpenMP,应用于工业调度;文13基于PThread提出了一种共享信息素矩阵的ACO算法,以TSP问题进行测试,获得了性能的提升,但在更多处理器下的通信开销问题没有给出分析.尽管已经实现了一些ACO并行算法且对它们在受限的设置中进行了测试,但是应该如何设计ACO的高效率比功能性版本,以及相对于顺序版本算法的性能将得到何种程度的改进仍然是两个有待解决的问题14.现代个人计算机普遍装配了支持并行处理和高精度运算的高性能单指令流多数据流(Single Instruction Multiple Data, SIMD)处理

8、器图形处理器(Graphics Processing Units, GPU).传统上GPU只是针对图形本身的应用,如光照计算、深度检测、光栅化、反走样等等.而今随着其性能和计算精度的提高,尤其是可编程性的发展,基于GPU的通用计算在并行和高性能计算领域发挥越来越重要的作用,GPU正逐步成为最具性价比的共享内存多处理器计算平台15,16.本文针对GPU的通用计算特性,研究了一种适合于GPU的ACO并行加速方法,在最新统一渲染架构CUDA(Compute Unified Device Architecture)上进行了实现.路径构建过程中,多个蚂蚁在GPU的流处理器(Stream Processo

9、rs)上并行搜索,并由GPU以Warp的方式调度,充分并行化的同时避免了其他并行平台算法的通信开销,获得了较高的性能加速比,也为GPU上的随机优化算法开拓了思路.1 蚁群优化算法的数学模型根据仿生学家长期的研究发现,蚂蚁虽没有视觉,但运动时会在路径上释放出一种特殊的分泌物信息素(Pheromone)14.蚁群正是通过信息素的正反馈机制和集体自催化行为来找出最优路径的.为了能够清楚地表达蚁群算法的数学模型,借助对称TSP,给出经典的ACO算法蚂蚁系统(Ant System, AS).设表示时刻位于城市的蚂蚁的个数,为蚂蚁总数,则有.表示时刻在城市,上残留的信息量.初始时刻,各条路径上的信息量相等

10、,设(为常数).蚂蚁在运动过程中,根据各条路径上的信息量决定转移方向.表示在时刻蚂蚁由城市转移到城市的概率:(1)其中,为先验知识或称为能见度,在TSP问题中为城市转移到城市的启发信息,一般取;为在路径上残留信息的重要程度;为启发信息的重要程度;与实际蚁群不同,人工蚁群具有记忆功能,用以记录蚂蚁当前走过的城市,称为禁忌表.经过若干时刻,所有蚂蚁都完成了一次周游,它们本次周游的禁忌表已满.这时,计算每一只蚂蚁所走过的路径,并保存最短路径(),然后清空禁忌表.随着时间的推移,以前留下的信息逐渐消逝,用参数表示信息的消逝程度,蚂蚁完成一次循环以后,各路径上的信息量要根据式(2)进行调整:(2),其中

11、,表示第只蚂蚁在本次循环中留在路径上的信息量,表示本次循环中路径上信息量的增量,为常数,表示第只蚂蚁在本次循环中走过的路径长度.2 CUDA:GPU通用计算新架构统一计算设备架构CUDA是一种新型的软硬件架构,用于将GPU作为数据并行计算设备,CPU只需对GPU进行计算的发放和管理,而无需将其映射到图像API.与以往的通用程序接口如Cg相比,CUDA提供了更多的灵活性,高效地将计算问题映射到硬件体系结构上.CUDA应用由两部分组成,其一是执行在GPU上的程序,称为核心(Kernel).核心程序是CUDA架构的程序语言,是基于标准C的扩展.另一个部分是执行在CPU上的程序,提供过程控制、数据传输

12、和核心调用等功能.核心程序是由大量可在GPU上并行执行的线程组成的.如图1所示,线程以矩阵的形式被组织成线程块(Block),线程块再被组织成网格(Grid).特别地,一个线程块内的线程可以同步并共享GPU的共享存储器(Shared Memory, SM),而不同线程块的线程则只能通过全局存储器(Global Memory, GM)通信.Fig.1 Architecture of CUDAGPU特别适于加速解决计算密集而数据可并行的问题.自CUDA出现以来,其在数字仿真、物理模拟和分子动力学等方面都有了应用18-20.3 基于GPU的并行加速基于GPU流模型的体系结构,GPU的通用计算还存在诸

13、多限制,简单地移植串行算法到GPU上并不能很好地发挥其性能.首先,GPU不能自我启动和I/O,必须依靠CPU进行环境设置和数据、代码载入等初始化工作,只能作为CPU的协处理器.其次,GPU的绝大多数晶体管被计算单元(Arithmetic Logical Unit, ALU)所占据,其计算能力强大而流程控制能力薄弱.最后,GPU的通用计算可编程接口尚不完善,还存在诸多约束条件,做通用计算要做特殊处理.由此,我们一方面利用GPU强大的数据处理能力,另一方面用CPU的优势弥补GPU的劣势,设计了GPU-based ACO算法框架如下:Fig.2 Framework of GPU-base ACO实验

14、表明,ACO算法的性能瓶颈在路径搜索过程,尤其是问题规模较大时,蚂蚁数目也相应增加(通常蚂蚁数目等于问题规模).如图2所示,我们将该步骤移植到GPU上, 只蚂蚁在GPU的多核处理器上进行并行搜索,以提高搜索效率.绝大多数GPU-based ACO和其顺序执行版本的行为是等价的,但带有局部更新规则的ACO如蚁群系统(Ant Colony System, ACS)除外,目前尚无理论和实验表明哪一种方式更优.CPU内存和GPU显存间的数据传输是GPU通用计算带来的额外开销.GPU-based ACO的数据传输发生在:(1)数据初始化时,城市距离矩阵、初始信息素矩阵由CPU内存上传至GPU的GM中;(

15、2)一次迭代结束后,蚂蚁周游的路径下载至内存;(3)下一次迭代开始前,新信息素矩阵上传至GM.其中(1)整个求解中只发生一次,对算法整体效率不构成影响.而(2)、(3)将在实验部分进行分析. 4 实验分析本节,我们选择最高效的ACO算法之一最大最小蚂蚁系统(MAX-MIN Ant System, MMAS)作为测试的基准,讨论GPU-based MMAS与MMAS的性能差异.实验是一台配有Intel Pentium D 965 CPU 3.7 GHz和2GB主存的普通PC上进行的.GPU采用Geforce 8800GTX,拥有1.35 GHz时钟,768 MB显存和128个流处理器. 选用TS

16、P问题的标准测试库TSPLIB21中的多种不同规模的问题进行了实验.各个问题名称中的数字即为所包含的城市数,令,其他各参数设置为:,.对每一种问题用MMAS和GPU-based MMAS两个算法重复50次实验,每次运行迭代1000次.4.1 迭代性能首先,给出CPU-based MMAS在不同问题规模下对MMAS的加速比,如图3所示:Fig.3 Iteration performance test从图3中可以看出,针对小规模问题,GPU-based MMAS的仅有几倍的性能提升,而当规模达到1000以上时,加速比也达到了数十乃至数百.原因是问题规模小,蚂蚁数目也小,GPU-based MMAS

17、将时间耗在了数据存取上,且基于概率选择的随机访问更增加了访问延迟,只有蚂蚁数目达到一定数目,才能充分发挥GPU的大量处理器资源,获得更好的执行速度.4.2 解的质量其次,给出算法所获得解的质量的比较,如表1所示:Table 1 Final solutions qualityInstance Algorithm Best solution Worst solution Average solutionberlin52 MMAS 7544.366 7716.69 7613.2956GPU-based MMAS 7544.365 7716.69 7647.76ch130 MMAS 6232.921

18、6395.173 6299.6702GPU-based MMAS 6194.582 6351.531 6278.547tsp225 MMAS 4363.609 4465.28 4427.9596GPU-based MMAS 4228.536 4608.153 4430.952rat575 MMAS 8807.166 8944.012 8889.2736GPU-based MMAS 8408.56 9043.106 8774.6328从表1中可以看出,尽管本文所采用的GPU平台只能支持单精度浮点数,且CPU比GPU多了80位寄存器扩展,但是GPU获得了与CPU同等质量的解.说明对于ACO算法而言

19、,数据精度的微小差别不会影响算法的求解能力.4.3 数据传输代价数据传输是GPU-based MMAS的额外代价.图4比较了不同问题的数据传输时间占迭代时间的百分比.Fig .4 Data transfer cost如图4所示,迭代过程中的数据传输随着问题规模的扩大对整个性能的影响逐渐减弱,达到2000时几乎可以忽略不计(0.08%).可见GPU-based MMAS求解大规模问题更具优势.5 结论ACO类算法具有天然的并行性,而研究并行ACO必须依靠多处理器系统.本文研究了一种基于GPU的ACO算法框架,并以MMAS为例进行了实现.使用了最新的GPU通用计算体系结构CUDA,符合GPU通用计

20、算的发展方向,未来的GPU将进一步向通用化和高性能发展.本文的首要贡献是证明了基于GPU的随机算法是可行和有效的.尝试基于GPU的多蚁群并行化是进一步研究方向.参考文献1 COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies c Proceedings of the ECAL91 European Conf. of Artificial Life. Paris: Elsevier, 1991. 134-144. 2 DORTGO M, MANIEZZO V, COLORNI A. Ant system

21、: Optimization by a colony cooperating Agents J. IEEE Trans. on Systems, Man, and Cybernetics Part B: Cybernetics, 1996, 26(1):29-41. 3 DORTGO M, GAMBARDELLA L M. Ant colony system: A cooperative learning approach to the traveling salesman problem J. IEEE Trans. on Evolutionary Computation, 1997,1(l

22、):53-66. 4 ZHEN T, ZHANG Q W, ZHANG W S, et al. Hybrid ant colony Algorithm for the vehicle routing with time windows. C Proceedings - ISECS International Colloquium on Computing, Communication, Control, and Management, CCCM 2008, 8-12.5 LV Congying, YU Zhezhou, ZHOU Chunguang, et al. A Dynamic and

23、Adaptive Ant Algorithm Applied to Quadratic Assignment Problems J. Journal of Jilin University (Science Edition) , 2005, 43 (4): 873-875(in chinese). 吕聪颖,于哲舟,周春光等. 动态自适应蚁群算法在二次分配问题中的应用J. 吉林大学学报(理学版) , 2005, 43 (4) : 873-875. 6 XING Lining, CHEN Yingwu. Mission Planning of Satellite Ground Station Sy

24、stem Based on the Hybrid Ant Colony Optimization J. ACTA AUTOMATICA SINICA, 2008,34(4):414-419(in chinese). 邢立宁,陈英武.基于混合蚁群优化的卫星地面站系统任务调度方法.自动化学报,2008,34(4):414-419.7 ZHU Qingbao, YANG Zhijun. An Ant Colony Optimization Algorithm Based on Mutation and Dynamic Pheromone Updating J. Journal of Software

25、, 2004, 15(2):185-192(in chinese).朱庆保, 杨志军. 基于变异和动态信息素更新的蚁群优化算法J.软件学报, 2004, 15(2):185-192.8 WU Bin, SHI Zhongzhi, An ant colony algorithm based partition algorithm for TSP J. Chinese Journal of Computers, 2001,24(12):13281333(in chinese).吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法J.计算机学报,2001,24(12):1328-1333.9 BU

26、LLNHEIMER B, KOTSIS G, STRAUSS C. Parallelization strategies for the ant system J. Applied Optimization, 1998, 24:87-100.10MIDDENDORF M, REISCHLE F, SCHMECK H. Multi colony ant algorithms J. Journal of Heuristics, 2002, 8(3): 305-320.11CHEN Ling, ZHANG Chunfang. Adaptive Parallel Ant Colony Algorith

27、m J. MINI MICRO SYSTEMS, 2006,27(9):1695-1699(in chinese).陈崚,章春芳.自适应的并行蚁群算法J.小型微型计算机系统, 2006,27(9):1695-1699.12DELISLE P, KRAJECKI M, GRAVEL M, et al. Parallel implementation of an ant colony optimization metaheuristic with openmp. C Proceedings of the 3rd European Workshop on OpenMP. 2001, Barcelon

28、e, Espagne, IEEE, 2001. 79-84.13LU Qiang, GAO Yanming, QIAN Peide. Sharing One Pheromone Matrix: A New Approach to Parallel ACO J. ACTA AUTOMATICA SINICA,2007, 33(4):418-421(in chinese).吕强,高彦明,钱培德. 共享信息素矩阵:一种新的并行ACO方法J.自动化学报, 2007, 33(4):418-421.14DORIGO M, STUZLE T. Ant Colony Optimization M. MIT Press, 2007.15WU Enhua. State of the art and future challenge on general purpose computation by graphics processing unitJ. Journal of software,2004,15(10):1493-1503(in chinese).吴