学位论文 > 优秀研究生学位论文题录展示

基于视觉反馈与行为记忆的GPU并行蚁群算法

作 者: 程童
导 师: 郭禾
学 校: 大连理工大学
专 业: 计算机应用技术
关键词: 蚁群算法 视知觉 累积学习理论 行为记忆 GPU 并行算法
分类号: TP301.6
类 型: 硕士论文
年 份: 2011年
下 载: 18次
引 用: 0次
阅 读: 论文下载
 

内容摘要


蚁群优化算法(Ant Colony Optimization algorithm, ACO)是解决组合优化问题最有效的方法之一,在诸如数据挖掘,路由寻址等领域取得了较好的应用。然而,传统蚁群算法存在的收敛速度慢、寻优能力不足的问题始终制约着蚁群算法的发展,在应对大规模及超大规模优化问题时力不能及。因此,蚁群算法的优化成为该领域长期以来的研究热点,其主要手段有两种:一是对蚁群算法模型的改进;二是对算法进行并行化改造。本文首先在分析现有改进算法的基础上,结合人类视知觉的相关理论及罗伯特·M·加涅(Robert M. Gagne)所提出的累积学习理论,建立了一种具备视觉反馈和行为记忆的蚁群算法新模型VM-MMACO(Visual-Memory based Max-Min Ant Colony Optimization Algorithm),使得蚂蚁能够通过人工视觉过滤寻路过程中的信息素噪声。增强搜索质量,同时,通过反复的探路行为学习经验,在后续的迭代过程中,通过经验压缩寻路范围,加快收敛速度;其次,使用CUDA(Compute Unified Device Architecture)在GPU环境下对新模型进行并行化改造。CUDA是由NVIDIA公司给出的针对GPU通用计算的解决方案,可以充分利用GPU硬件的并行计算能力,大幅缩短计算所需的时间。在这一部分,本文给出了新模型所对应的CUDA并行模型及相关实验。经过大量与传统改进策略的对比实验发现,新算法在求解质量与求解时间上均有较大程度改进,同时给出证明,新算法没有提高原有算法的复杂度。通过在GPU上的实验表明,相对于原有改进策略,新模型的可并行化程度更高,可以获得更大的加速比。

全文目录


摘要  4-5Abstract  5-8引言  8-101 蚁群算法介绍及其研究现状  10-18  1.1 TSP问题  10-11  1.2 经典蚁群优化算法  11-14    1.2.1 基本蚂蚁系统  11-12    1.2.2 最大最小蚂蚁系统  12-13    1.2.3 蚁群系统  13    1.2.4 基于排列的蚂蚁系统  13-14    1.2.5 精英蚂蚁系统  14  1.3 串行ACO研究现状  14-17    1.3.1 基于信息素扩散的蚁群算法  14    1.3.2 改进扩散蚁群算法  14-15    1.3.3 近似骨架导向蚁群算法  15-16    1.3.4 基于全局与局部蚂蚁的蚁群算法  16    1.3.5 具备感觉和知觉特征的蚁群算法  16-17  1.4 GPU并行ACO研究现状  17-18    1.4.1 基于GPU的最大最小蚁群算法  17    1.4.2 基于GPU加速的细粒度并行蚁群算法  17    1.4.3 基于All-In-Roulette选择算法的GPU并行蚁群优化算法  17-182 基于视觉反馈与行为记忆的蚁群算法  18-29  2.1 VM-MMACO算法基本原理  18-20  2.2 VM-MMACO算法相关理论  20-26    2.2.1 视觉形成机制及抽象模型  20-23    2.2.2 累积学习理论及抽象模型  23-26  2.3 VM-MMACO算法模型  26-293 GPU环境下并行VM-MMACO算法  29-42  3.1 GPU物理结构及与其它并行平台对比  29-31    3.1.1 GPU物理结构  29-30    3.1.2 与多核CPU的对比  30    3.1.3 与分布式集群的区别  30-31    3.1.4 GPU的优势  31  3.2 CUDA编程模型及技术要点  31-35    3.2.1 CUDA编程模型  31-33    3.2.2 编程要点  33-35  3.3 基于GPU的VM-MMACO并行算法  35-424 实验与结果分析  42-52  4.1 VM-MMACO仿真实验结果  42-48    4.1.1 VM-MMACO仿真  42-45    4.1.2 与其它蚁群算法的对比  45-46    4.1.3 参数取值对VM-MMACO算法的影响  46-48  4.2 GPU下VM-MMACO实验结果  48-52    4.2.1 与GPU环境下MMACO的对比  48-50    4.2.2 与串行环境下VM-MMACO的对比  50-52结论  52-53参考文献  53-55附录A 程序代码  55-74攻读硕士学位期间发表学术论文情况  74-75致谢  75-76

相似论文

  1. 多导弹协同作战突防效能评估及组合优化算法研究,TJ760.1
  2. 基于蚁群算法的电梯群优化控制研究,TU857
  3. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  4. 动态环境下移动对象导航系统相关技术的研究,TP301.6
  5. 基于改进蚁群算法的机器人路径规划研究,TP242
  6. 基于并行算法的模糊综合评价模型的设计与应用,TP18
  7. 改进的蚁群算法及其在TSP上的应用研究,TP301.6
  8. 基于免疫机制蚁群算法的电力系统无功优化研究,TP18
  9. 基于物理拓扑感知的Chord算法研究,TP393.02
  10. 电渣炉过程控制系统的设计及优化控制,TP273
  11. Ad Hoc网络中分簇路由算法的研究,TN929.5
  12. 图像信息处理机的图像处理方法研究,TP391.41
  13. 基于GPU的有限元方法研究,O241.82
  14. 小型无人机在警用领域的应用与造型设计研究,V279
  15. 智能光网络中路由选择算法的研究,TN929.1
  16. 面向无线传感器网络的多路径路由协议研究,TN915.04
  17. 改进蚁群算法在盲均衡中的应用,TN911.5
  18. 智能光网络动态路由和波长分配算法的研究,TN929.1
  19. 基于蚁群算法的移动商务个性化推荐体系研究,TP391.3
  20. 基于蚁群算法的车辆调度问题研究,TP301.6

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com