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

上传人:李医生 文档编号:11750626 上传时间:2021-09-03 格式:DOCX 页数:4 大小:68.96KB
返回 下载 相关 举报
基于GPU加速的并行蚁群算法求解旅行商问题研究.docx_第1页
第1页 / 共4页
基于GPU加速的并行蚁群算法求解旅行商问题研究.docx_第2页
第2页 / 共4页
基于GPU加速的并行蚁群算法求解旅行商问题研究.docx_第3页
第3页 / 共4页
基于GPU加速的并行蚁群算法求解旅行商问题研究.docx_第4页
第4页 / 共4页
亲,该文档总共4页,全部预览完了,如果喜欢就下载吧!
资源描述

《基于GPU加速的并行蚁群算法求解旅行商问题研究.docx》由会员分享,可在线阅读,更多相关《基于GPU加速的并行蚁群算法求解旅行商问题研究.docx(4页珍藏版)》请在三一文库上搜索。

1、基于 GPU 加速的并行蚁群算法求解旅行商问题研究摘要:蚁群算法是求解旅行商问题的有效方法之一,但是随着蚁群规模和城市规模的增大,算法的运行速度将大大降低,本文利用GPU在CUDA7.0环境下,对蚁群算法进行化加速设计, 实验结果表明, 该方法取得了良好的加速效果,当蚁群规模增大时,加速倍大幅度提高。数据显示,蚁群个体和城市规模越大,加速效果越好。关键词:蚁群算法; GPU; CUDA中图分类号: TP18 文献标识码: A 文章编号: 1009-3044(2016) 12-0206-02旅行商问题(Traveling Salesman Problem,简称 TSPP 是一个典型的组合优化问题

2、。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等现实生活中的优化问题都可以归结为TSP求解问题。它解决从一个城市由发,经过若干个城市后又返回原城市的最优路径的求解问题。蚂蚁在觅食路径上会释放一种特殊的分泌物一“信息素” ,随着时间流逝,信息素会挥发,后面的蚂蚁根据路径上的信息素浓度,选择信息素多的路径去觅食,这样便形成了一个正反馈机制。在整个寻径过程中,虽然单只蚂蚁的选择能力有限,但它们的行为具有非常高的自组织性,相互之间交换路径,最终寻找到最优路径。受到蚁群系统信息共享机制的启发,意大利学者DorigoM 于 1992 年首次系统提出了蚁群算法,并成功地将该方法应用到求解TSP

3、问题中1该算法是启发式搜算算法的一种,采用了分布式并行计算机制,易于与其他方法结合,具有强的鲁棒性。同时,相对于其他搜算法,对初始路线要求不高,在搜索过程中不需要人工调整。研究表明,蚁群算法是解决TSP问题有效的算法之一,因此也成为近年来的研究热点。近年来,基于 GPU (图像处理器)的大规模通用并行计算,大大提高了计算机图形处理的效率 2。 GPU 的高速浮点运算能力、并行计算和可编程功能也为通用计算提供了良好的并行计算平台,同时也为蚁群算法的高速并行实现提供了可能。 NVIDIA 公司的统一计算设备架构(CUDA) ,为研究人员利用CPU进行数据并行处理提供了便捷的手段3。通过GPU加速并

4、行算法,是蚁群算法并行化、提高算法执行速度 的有效途径之一。1 蚁群算法基本原理蚁群算法受蚁群行为和反应特征的启发而得来的。觅食的蚂蚁在走过的路上释放信息素,其他觅食蚂蚁将沿着留有信息素的路径在相同位置找到食物。因此,信息素可用来实现间接通信的目的 4 。 基于信息素的城市探知转移概率公式:2基于GPU并行的蚁群算法通过对CUDA和GPU并行程序设计的研究,将基于蚁群算法的TSP求解优化路径问题转化为GPU中的多线程的并行处理过程, 充分利用 GPU 的高速浮点运算和并行计算的特性,以提高算法的速度。在蚂蚁遍历城市的过程中,每只蚂蚁独立地建立自己的遍历路径,对蚂蚁来说,自然地存在并行性。根据C

5、UDA 的编程模型 5 ,我们很自然地会将每只蚂蚁个体映射到 CUDA的一个线程上,用线程来模拟你蚂蚁个体,每个线程完成一只蚂蚁的城市周游回路。设蚂蚁个数为 M,城市个数为N, CUDA中Block个数为4,蚁群算法的GPU 并行化模型中,总线程个数为 M ,每个Block 中线程个数为 M/4 , 如图 3 所示。 在模型中, 将路径状态初始化、路径转移概率计算、路径长度计算、更新信息素定义为CUDA 函数。首先, M 个线程被分配在4 个 Block 中,同时启动, 计算各自的城市转移概率, 寻找转移城市; 其次,由 N 个线程分成N 个 Block, 计算路径上信息素增量; 再次,用一个

6、线程计算路径长度和最优路径;最后 N 个线程分成N个 Block ,更信路径信息素。3 实验与分析实验结果表明, 采用 GPU 并行化蚁群算法取得了良好的加速效果,当蚁群规模由 256 增大到 1024 、城市规模由 21增大到 76 时,加速倍数由 3.0 增大到10.75。数据显示,问 题规模越大,蚁群个体和城市规模越大,加速效果越好,对 于更大规模的复杂问题, 基于 GPU 的并行化蚁群算法将取得 更高的加速比。4 结束语本文研究了基本蚁群算法的原理,并基于GPU和CUDA高速并行计算模型,利用GPU在CUDA7.0环境下,对蚁群算 法进行化加速设计,实验结果表明,该方法取得了良好的加速

7、效果, 当蚁群规模增大时, 加速倍大幅度提高。 数据显示, 蚁群个体和城市规模越大,加速效果越好。参考文献: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 implementionJ. IEEE International Symposium on Intelligent Signal Processing and Communication Systems , 2012.5 David B.KirK, Wen-mei W. Hwu. 大规模并行处理器编程实战 M. 北京: 清华大学出版社, 2013.

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 科普知识


经营许可证编号:宁ICP备18001539号-1