基于遗传算法的分层路径寻优策略和路径查询系统的设计

论文摘要

随着交通及旅游业的不断发展,对出行路径的合理规划就显得日益重要。在路径规划问题中,最常涉及得就是最短路径。由于路径规划中考虑的因素可以不同,如时间、费用、道路的容量等,最短路径问题就可以引申为最快、最低费用路径问题。不管选取哪种标准,路径规划中都是为了实现其路径最优。所以,最优路径规划最终都可以归结为在特定的道路网络中搜索总代价最小的目标路径问题。最短路径问题一直是研究的热点,其中比较经典的算法是Dijkstra算法,此外还有Ford算法、A算法、A*算法、动态规划法等。为了提高搜索的效率,很多学者对Dijkstra算法进行了改进,它们在一定程度上能降低算法执行的时间复杂度或空间复杂度。此外,由于Dijkstra算法的时间复杂度为O(n~2),当道路节点的数目很大的时候,它的执行效率就显得相对较差。为了克服这个问题,有的学者引入了限制搜索区域的思想,缩小搜索空间,比如椭圆限制、矩形限制等。遗传算法是一种基于生物进化论中的优胜劣汰、自然选择和适者生存原理以及生物遗传规律的智能搜索方法,具有较强的全局搜索能力、稳健性、并行性和启发式随机搜索特性,它通过维持一组可行解,并通过对可行解的重新组合,改进可行解在多维空间内的移动轨迹或趋向,最终走向最优解,克服了传统优化方法容易陷入局部极值的缺点。这使得在解决路径寻优问题中,遗传算法只需要对部分路径进行编码,再通过不断的进化操作,最终便可在整个搜索空间中获得最优或较优的解。而实际上,当解空间达到一定的规模时,单纯的遗传算法往往很难获得令人满意的解,这是因为遗传算法的搜索本身具有一定的盲目性和随机性,搜索空间越大,对其性能的影响就越大。在本文中,采用分层的思想,将整个解空间分解成两个或多个子空间,实现分级搜索,以提高遗传算法的路径寻优的效率和解的质量。与单纯的遗传算法相比,分层算法更倾向选择有利于行驶的高层路径,尽可能少的选择较差的低层路径,这种选择也符合出行者的决策心理,使路径的选择更加合理。论文主要完成两部分的工作:第一是算法的研究,主要是遗传算法的研究。本文采用了改进的遗传算法用于路径的寻优,使用分层的思想提高求解的效率,最后并通过实验结果的比较,证明其可行性和有效性;第二是路径查询系统的设计,包括系统功能模块的设计、系统工作流程的设计和系统界面的设计,最后,基于Oracle数据库,通过Visual Studio 2005和MapXtreme 2005完成了路径查询系统的设计,使系统实现了路径查询功能和地理信息处理功能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.1.1 智能交通系统的概述
• 1.1.2 智能交通系统的研究现状
• 1.2 交通网络中路径寻优算法的研究现状
• 1.2.1 传统的路径搜索算法
• 1.2.2 智能搜索算法
• 1.3 本文的主要工作
• 1.4 本文的组织结构
• 第2章 道路网络的导入、存储与访问
• 2.1 GIS的数据模型
• 2.1.1 空间数据模型
• 2.1.2 属性数据模型
• 2.2 Oracle Spatial
• 2.3 空间数据的导入
• 2.4 空间数据的存储
• 2.4.1 道路数据的存储
• 2.4.2 道路的分层及其存储表示
• 2.5 Oracle中空间数据的访问
• 2.5.1 OO4O访问空间数据
• 2.5.2 ADO.NET访问空间数据
• 2.6 小结
• 第3章 遗传算法
• 3.1 遗传算法的概念
• 3.2 遗传算法的基本原理与方法
• 3.2.1 编码
• 3.2.2 适应度函数
• 3.2.3 遗传算子
• 3.2.4 算法的终止条件
• 3.3 遗传算法的描述
• 3.4 遗传算法的基本理论
• 3.4.1 模式定理
• 3.4.2 积木块假设
• 3.4.3 隐并行性定理
• 3.5 小结
• 第4章 基于遗传算法的分层路径寻优算法的设计
• 4.1 分层辅助算法-Dijkstra算法的描述
• 4.2 求解路径问题的遗传算法设计
• 4.2.1 遗传算法主要内容的描述
• 4.2.2 算法的实现
• 4.2.3 实验结果比较与分析
• 4.3 基于遗传算法的分层路径寻优算法的设计
• 4.3.1 算法的实现
• 4.3.2 实验结果比较与分析
• 4.4 小结
• 第5章 路径查询系统的设计
• 5.1 MapXtreme 2005简介
• 5.1.1 MapXtreme 2005主要功能
• 5.1.2 MapXtreme 2005体系结构
• 5.2 系统设计
• 5.2.1 系统的功能模块设计
• 5.2.2 系统的工作流程设计
• 5.2.3 系统的界面设计与实现
• 5.3 小结
• 第6章 全文总结
• 6.1 结论
• 6.2 展望
• 参考文献
• 附录
• 致谢
• 攻读硕士学位期间的研究成果