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

粒子群优化算法在路径规划中的应用

作　者: 方昕
导　师: 曹菡
学　校: 陕西师范大学
专　业: 计算机应用技术
关键词: 路径规划 PSO算法 旅行商问题 并行模型
分类号: TP391.41
类　型: 硕士论文
年　份: 2010年
下　载: 178次
引　用: 1次
阅　读: 论文下载
 

内容摘要


城市交通影响着全国各大城市的经济和旅游业的发展。人们总希望所在的城市交通便利、路况规划合理,这将有利于人们的出行,因此城市的路径规划问题就显得尤为重要。根据出行者的出行目的和要求,路径规划问题在一定程度上可具体化为旅行商问题(Traveling Salesman Problem-TSP),例如：城市景点环游路径。旅行商问题是通过路径搜索算法来求解。路径搜索算法经历了由传统搜索算法到智能搜索算法发展过程,因为近些年智能搜索算法表现出了良好的性能,如遗传算法、蚁群算法、粒子群优化算法等。其中粒子群优化算法PSO (Particle Swarm Optimization)以概念简单、易于实现、鲁棒性较好等特点。目前用于求解TSP问题的PSO算法的求解过程较为复杂、求解速度较慢,实验结果无法说明算法总体性能的优势,并且实验多以测试数据为研究对象。因此,本文以实际地理数据作为TSP问题的研究对象,详述了基于地理坐标的离散PSO算法求解TSP问题的模型,用于解决实际问题。为了进一步改善算法的全局搜索能力,又提出了自平衡机制,使得算法过程简便并且算法性能得到提高。同时,采用多线程并行来提高算法的求解速度,弥补了算法并行化研究的不足。本文主要做了四大方面研究：(1)在实际的景点数据中利用PSO算法解决TSP问题,提出一种基于地理坐标的离散PSO算法。实验对同一迭代次数的不同粒子个数的最优解和平均解进行了计算并记录,将不同迭代次数的最优解和平均解进行了统计和对比,结果表明了算法在求解实际问题时具有重要的现实意义,可算法存在易陷入局部最优的缺陷。(2)为了使得算法不易陷入局部最优且算法求解过程较为简便,提出了自平衡离散PSO算法。此算法相对已有改进算法而言不采用将其它算法思想相结合的思路,而是通过自身达到平衡搜索能力的目的。实验统计方法和基于地理坐标的离散PSO算法的实验一样,结果表明此算法求解出来的解比前者优,且求解过程较为简便,能有效平衡算法的搜索能力不易陷入局部最优解。(3)为了进一步提高自平衡离散PSO算法的求解速率,设计了适用于此算法的并行模型,采用了基于多核平台的OpenMP多线程并行方式来改善算法性能。关于此算法基于多核的并行程序设计现还很缺乏,此算法并行方式的研究不但促进了算法并行化的发展,而且通过实验和结果证实了其能有效提高算法性能。(4)实现了对上述这些PSO算法在路径规划中的应用系统的设计与开发,系统由地图数据模块、参数设置模块、算法求解模块和结果显示模块组成。通过系统实验结果表明了算法性能逐步得到改善,也能有效解决实际TSP问题,同时可向正在建设中的西安市地铁部门提供路径参考,以便促进城市景点环游轨道发展,促进城市交通及经济发展。

全文目录


摘要  3-5
Abstract  5-10
第1章 绪论  10-18
  1.1 研究背景  10-11
  1.2 粒子群算法的研究现状  11-14
    1.2.1 群智能算法  11-12
    1.2.2 粒子群算法研究现状  12-14
  1.3 粒子群算法的研究意义  14-15
  1.4 路径规划问题  15-16
  1.5 本文的主要工作  16-18
第2章 粒子群优化算法概述  18-28
  2.1 粒子群算法思想起源  18
  2.2 粒子群算法基本原理与基本过程  18-20
  2.3 粒子群算法的特征  20-22
    2.3.1 PSO算法相关概念  20
    2.3.2 PSO算法参数设置  20-21
    2.3.3 PSO算法优点与不足  21-22
  2.4 粒子群算法收敛性分析  22-25
  2.5 常见的粒子群算法改进  25-26
  2.6 本章小结  26-28
第3章 基于路径规划问题的改进粒子群算法  28-38
  3.1 旅行商(TSP)问题  28-30
  3.2 基于地理坐标的离散PSO算法  30-34
    3.2.1 算法模型  30-32
    3.2.2 算法思想  32-33
    3.2.3 实验数据与分析  33-34
  3.3 自平衡离散PSO算法  34-37
    3.3.1 算法思想  34-36
    3.3.2 实验数据与分析  36-37
  3.4 本章小结  37-38
第4章 并行的自平衡粒子群算法  38-48
  4.1 并行概述  38-39
  4.2 并行模型  39-42
    4.2.1 OpenMP  39-40
    4.2.2 MPI  40-41
    4.2.3 多线程并行  41-42
  4.3 多线程的自平衡离散PSO算法  42-45
    4.3.1 算法思想  42-43
    4.3.2 实验数据与分析  43-45
  4.4 本章小结  45-48
第5章 应用系统的设计与实现  48-58
  5.1 应用系统的模型  48-51
    5.1.1 系统模型的提出  48-49
    5.1.2 系统模型的设计思想  49-51
  5.2 应用系统设计  51-54
    5.2.1 相关工具介绍  51-52
    5.2.2 系统功能模块  52
    5.2.3 系统工作流程  52-53
    5.2.4 系统界面设计  53-54
  5.3 应用系统实现  54-56
    5.3.1 地图数据准备  54
    5.3.2 实验结果  54-56
  5.4 本章小结  56-58
第6章 总结与展望  58-60
  6.1 本文总结  58
  6.2 未来展望  58-60
参考文献  60-64
附录  64-67
致谢  67-69
攻读硕士学位期间研究成果及奖励  69

相似论文

  1. 动态环境下移动对象导航系统相关技术的研究,TP301.6
  2. 基于改进蚁群算法的机器人路径规划研究,TP242
  3. 移动WSN基于虚拟簇头数据收集策略的研究,TP212.9
  4. 移动机器人全覆盖路径规划算法的研究,TP242
  5. 复杂动态环境下的小型足球机器人路径规划研究,TP242
  6. 面向GPS导航拖拉机的最优全局覆盖路径规划研究,TN967.1
  7. RoboCup中型组足球机器人的设计和开发,TP242
  8. 移动机器人路径规划研究及仿真实现,TP242
  9. 双层车库车辆调度辅助决策支持系统,TP242
  10. 无线传感器网络节点三维定位算法研究,TN929.5
  11. 基于数字高程模型栅格地图的移动机器人路径规划研究,TP242
  12. 车库管理系统线路生成与重复利用方法研究,TP315
  13. 城市交通智能控制策略与仿真系统研究,U495
  14. 车辆导航系统路径规划技术的研究,TP301.6
  15. 轮式仿人机器人导航与路径规划研究,TP242
  16. 船体分段的机器人焊接路径规划与离线编程,TP242
  17. 城市公交最优化换乘系统研究与实现,U12
  18. 机器人系统路径规划的研究,TP242
  19. 超市多任务机器人实用化路径规划方法研究,TP242
  20. 面向智能清扫机器人的路径规划技术研究,TP242
  21. 空间站零燃料大角度姿态机动方法,V448.2

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理（信息加工） > 模式识别与装置 > 图像识别及其装置
© 2012 www.xueweilunwen.com