基于蚁群算法的交通地理最佳路径的研究

摘要

交通地理信息系统（GIS-T,GeographicInformationSystemforTransportation），是一个以地理信息系统（GIS，GeographicInformationSystem）为技术支撑，以城市交通为依托，以城市交通查询、规划和决策为目的的信息处理系统。它涉及到交通领域的许多方面，最优路径的选择就是其重要应用之一，是一类典型的组合优化问题，在车辆导航系统以及各种城市应急系统中有着广泛的应用。传统的最优路径算法以Dijkstra算法为代表。这些算法均属于贪心算法，存在典型的局部最小问题，是一种静态的局部最优算法。当前的实际交通网络数据规模庞大，算法需要提前将整个交通数据导入才能进行路径的选择。这样显然不能反映出交通中不断变化的道路实际情况对交通路径选择的影响。蚁群算法是一种新兴的模拟仿生算法，算法具有模拟生物界群体觅食的能力，并且能够在实际的路径搜索过程中对外界的影响做出动态的响应，因而在交通最优路径选择中具有极大的可行性与适应性。 论文首先介绍了交通地理信息系统的国内外研究现状、关键技术、主要功能和具体应用，然后讨论研究了传统的最短路径选择算法，其中有Dijkstra算法、Floyd算法以及其他几种基于智能计算的最短路径算法。在以上几种经典的最短路径算法的基础上，结合蚂蚁觅食行为引入蚁群算法，并研究了基本蚁群算法的原理、模型、实现步骤和流程，分析了重要参数的设置，总结了蚁群算法的优缺点，介绍了几种经典的改进蚁群算法，由于传统的改进蚁群算法模型只提高了算法全局寻优的能力或者算法的收敛速度，为求在收敛速度和全局寻优能力之间取得一种平衡，本文提出了基于自适应信息素更新的双种群蚁群算法，根据信息量的分布情况进行信息量的更新，以动态地调整各路径上的信息量分布，使之不至于过分集中或者分散，以在加速收敛的同时避免早熟。使用自适应的信息素更新策略，增强了算法的全局寻优能力，同时，通过使用双种群策略进一步提高了算法的收敛速度。通过实验结果分析，验证了改进后的蚁群算法在稳定性和寻优能力两方面都取得了良好的效果。最后应用改进后的蚁群算法，建立一个在不同交通条件下搜索GIS-T的最短路径问题的模型。

目录

文摘

英文文摘

声明

第1章绪论

1.1课题研究背景和意义

1.2国内外研究现状和进展

1.2.1国外研究现状

1.2.2国内研究现状

1.3本文研究内容及章节安排

1.3.1本文的研究内容

1.3.2本文的章节安排

第2章交通地理信息系统的关键技术与应用

2.1交通地理信息系统的概念

2.1.1内涵

2.1.2特点

2.2交通地理信息系统的主要功能和关键技术

2.2.1主要功能

2.2.2关键技术

2.3交通地理信息系统的基本框架

2.3.1系统管理子系统

2.3.2电子地图子系统

2.3.3信息查询子系统

2.3.4公交查询子系统

2.3.5交通导航子系统

2.4交通地理信息系统的具体应用

2.5本章小结

第3章基于改进蚁群算法模型的研究

3.1经典最短路径算法

3.1.1传统Diikstra算法

3.1.2 Floyd算法

3.1.3其他最短路径算法

3.2基本蚁群算法

3.2.1基本蚁群算法的原理

3.2.2基本蚁群算法的模型

3.2.3基本蚁群算法的实现步骤和流程

3.2.4基本蚁群算法的参数设置

3.2.5基本蚁群算法的优缺点

3.2.6几种经典的蚁群算法

3.3基于自适应的信息素更新的双种群蚁群算法

3.3.1自适应的信息素更新策略

3.3.2双种群策略

3.3.3算法的描述

3.3.4算法的流程

3.3.5算法时间复杂度分析

3.3.6实验结果与分析

3.4本章小结

第4章基于蚁群算法的GIS-T最佳路径的研究

4.1出行者路径选择的分析

4.2最佳路径搜索

4.3本章小结

第5章总结与展望

5.1全文工作总结

5.2未来工作展望

参考文献

致谢

附录 硕士期间参与的科研项目和发表的论文