详情

原文传递蚁群算法及其在智能交通中的应用

论文题名：	蚁群算法及其在智能交通中的应用
关键词：	蚁群算法;智能交通;车辆路径
摘要：	随着经济的快速发展和汽车数量的不断增加，日益严重的交通问题已经成为束缚各国城市发展的瓶颈，我国的情况尤为严重。智能交通系统(Intelligent Transportation System，ITS)是解决现代社会交通需求与供给之间矛盾的重要途径之一，是解决交通基础设施建设增长缓慢与机动车数量迅速增长之间矛盾的最佳手段。近几年来，智能交通系统越来越受到人们的重视，它是以当代飞速发展的科学技术为支撑，将先进的计算机技术、通信技术、数据库技术、人工智能技术等运用于交通运输中，以达到缓解交通拥挤、保证交通安全、提高交通网络使用效率等目的。智能交通系统涉及到交通领域的许多方面,最优路径的选择就是其重要应用之一，是一类典型的组合优化问题，适合采用蚁群算法(ACA)求解。组合优化技术是一种以数学理论为基础，用于求解各种工程问题优化解的应用技术。随着计算机技术的发展，以蚁群算法为代表的智能启发算法得到了迅速发展和广泛应用。蚁群算法是模仿自然界的蚂蚁行为而发展起来的一种随机搜索算法。由于以信息素作为间接通信方式，使蚁群算法具有其他常规优化算法无法获得的优点。算法采用了正反馈并行自适应机制，良好的分布式计算机制，具有较强的鲁棒性，易于与其他启发式算法相结合。蚁群算法通过其内在的搜索机制和TF反馈特性，在一系列困难的组合优化阿题中取得了成效，这已经是被大量研究成果证明了的。但是蚁群算法也存在着一些缺陷。在蚂蚁的移动过程中，路径选择虽然受到信息素和启发信息的指导，但仍具有随机性，特别是当问题规模较大时，路径的选择通常需要较长的搜索时间。此外，由于个别路径上的信息素可能被过于强化，容易使算法陷入局部最优解。目前我国对智能交通系统的研究水平还比较低，而蚁群算法也是一种比较新的仿生算法。因此，需要对蚁群算法进行改进和完善，使其更广泛地应用于智能交通系统。论文的主要研究内容及创新点如下： (1)回顾了国内外智能交通系统的研究与发展状况，详细介绍了我国智能交通系统的构成和重要作用。 (2)系统阐述了蚁群算法的理论基础、算法模型和实现步骤。通过对算法的分析，得出算法的时间复杂度为O(Nc·n2·m)，空间复杂度为O(n2)+O(n·m)。此外还分析了影响算法性能的各种因素，特别是参数a、β、p，并通过仿真实验加以说明。最后总结了蚁群算法的特点和研究应用现状。 (3)本文从以下四个方面对基本蚁群算法进行了改进：信息素更新策略、参数β、参数p和引入探索因子gn。仿真实验表明，算法的性能得到了提高。 (4)将遗传算法融入蚁群算法，提出了基于奖惩机制的遗传蚁群算法(RP-GA-ACA)。详细介绍了该算法的主要思想、算法模型、实现步骤和时间复杂度。仿真实验表明，RP-GA-ACA算法在时间效率上优于蚁群算法，在求精效率上优于遗传算法。 (5)对交通道路网进行了较深入的研究，提出了交通道路网的表示方法和权重的确定方法. (6)将改进的蚁群算法应用到车辆路径问题(VRP)，提出了求解VRP问题的改进蚁群算法(VRP-ACA)。详细阐述了该算法的主要思想、算法模型和实现步骤，并通过仿真实验实现了路径的优化。 (7)介绍了交通领域中的混沌现象，将混沌理论引入蚁群算法，提出了混沌蚁群算法(CACO)。最后通过仿真实验检验了混沌蚁群算法的性能，表明了混沌蚁群算法更加适合应用于智能交通系统。
作者：	杨海
专业：	计算机软件与理论
导师：	王洪国
授予学位：	硕士
授予学位单位：	山东师范大学
学位年度：	2008
正文语种：	中文