粒子群算法在交通领域的应用

1、粒子群算法在交通规划的研究综述0 引言优化问题是一个古老的问题，它所研究的内容是讨论在众多的方案中什么样的方案最优以及如何找出最优方案。交通规划作为新兴的交叉学科，其理论应用中存在着较多的寻优问题。随着优化理论的发展，一些新的智能算法得到了迅速发展和广泛应用，成为解决传统优化问题的新方法，这类算法主要有遗传算法启发于生物种群通过遗传和自然选择不断进化的功能，人工免疫系统，模拟于生物免疫系统的学习与认知功能，蚁群算法，模仿蚂蚁群体在路径选择和信息传递方面的行为，还有模拟退火算法、禁忌算法等等12。而粒子群优化算法(简称PSO)也是此类算法3。1粒子群算法1.1产生背景自然界中，鸟群运动的主体是离

2、散的，其排列看起来是随机的，但在整体的运动中它们却保持着惊人的同步性，其整体运动形态非常流畅且极富美感。1986年Craig Reynols 提出了Bird模型，用以模拟鸟类聚集飞行的行为，通过对现实世界中这些群体运动的观察，在计算机中复制和重建这些运动轨迹，并对这些运动进行抽象建模，以发现新的运动模式。之后，生物学家Frank Heppner在此基础上增加了栖息地对鸟吸引的仿真条件，提出了新的鸟群模型。受上述鸟群运动模型的影响，社会心理学博士James Kennedy和电子工程博士Russell Eberhart提出了粒子群算法，1995年的IEEE神经网络会议和第六届微机与人类科学会议上分

3、别发表了题为 “Partiele swam optimization” 和 “A new optimizer Using particle swam theory” 的两篇论文45，标志着粒子群优化算法的诞生。1.2基本原理粒子群算法(PSO)是一种基于迭代模式的优化算法，最初被用于连续空间的优化"在连续空间坐标系中，粒子群算法的数学描述如下:一个由m个粒子(particle)组成的群体在D维搜索空间中以一定速度飞行，每个粒子在搜索时，考虑到了自己搜索到的历史最好点和群体内(或邻域内)其他粒子的历史最好点，在此基础上变化位置(位置也就是解)。设搜索空间为D 维，总粒子数为n ，第i

4、个粒子位置向量为：Xi =(xi1 ，xi2 ， ，xid ，x iD)第i 个粒子“飞行”历史中的最优位置(即该位置对应解最优)为：Pi =(pi1 ，pi2 ，pid ， ，piD )其中第g 个粒子的历史最优位置Pg 为所有P i 中的最优；第i 个粒子的位置变化率向量为：Vi =(vi1 ，vi2 ，v id ， ，viD )每个粒子的位置按如下公式进行变化Vid =wv id +c1cR1(pid -xid )+c2cR2(pgd -xid ) (1)Xid =xid +vid (2)式中：c1、c2 为正常数，称为加速因子；cR1、cR2为 0 ，1之间的随机数；w 为惯性因子，w

5、 较大，适于对解空间进行大范围探查，w 较小，则适于小范围。第d(1 d D)维的位置X 变化范围为 Xdmin ，Xdmax ，速度V 变化范围 Vdmin ，Vdmax 。2粒子群算法在交通规划领域的应用现如今，交通问题成为了城市发展的一个焦点问题，交通拥堵，交通路网使用效率不均衡等问题在发达城市日益显现，而作为交通设施建设的前期规划阶段，交通规划的理论发展则进展较慢，特别是在交通流预测，交通分配阶段的计算理论过于复杂，实际应用均采用比较简单的计算过程，最后又造成结果与现实情况偏离较大，达不到规划的实际作用。因为交通需求预测的诸多优化主要是线性求解问题，利用的都是传统经典算法的求解过程，因

6、此在问题设计之初就对问题做了较多简化或是模型仿真适应性不强。随着智能算法的逐渐发展与应用，其在交通领域的应用逐渐成为交通规划求解优化问题的新工具，主要集中在交通诱导，交通规划，信号控制等方面，为交通发展的优化设计提供了较好的理论思路。这些算法大大丰富了现代优化技术，也为具有非线性、多极值等特点的复杂函数及组合优化问题提供了切实可行的解决方案。下面就分别概述粒子群算法在交通规划领域中的应用。2.1交通流预测的粒子群应用实时准确的交通流预测是交通控制和交通诱导的前提和关键，其研究一直是智能交通系统的研究热点。多年来，专家和学者们建立了很多预测模型和方法，如历史平均法、时间序列法、Kalman滤波法

7、、回归分析法等等。这些方法理论基础较成熟，应用也较多。但这些传统的预测方法大都是基于数理统计的方法，共同特点是先建立数据序列的主观模型，然后根据主观模型进行计算和预测，预测精度不能满足实际的要求，加之不具备自适应和自学习的能力，预测系统的鲁棒性没有保障近年来许多学者对城市交通流系统的非线性特性进行了深入研究，建立了多种考虑交通流非线性的交通流预测模型，如BP 神经网络模型、RBF 神经网络模型、Volterra 滤波器自适应预测模型等。其中，BP 神经网络模型是比较成功的预测模型。但该模型有两个明显的缺点：一是容易于陷入局部极小值；二是收敛速度慢。为提高BP神经网络预测模型的预测准确性，李松等

8、学者提出了一种基于改进粒子群算法优化BP神经网络的预测方法引入自适应变异算子对陷入局部最优的粒子进行变异，改进了粒子群算法的寻优性能，利用改进粒子群算法优化BP神经网络的权值和阈值。然后训练BP神经网络预测模型求得最优解。将该预测方法应用到实测交通流的时间序列进行有效性验证，结果表明了该方法对短时交通流具有更好的非线性拟合能力和更高的预测准确性。王惟、李志鹏为了准确预测交通流量，为实施交通疏导提供参考依据，提出了一种基于小生境粒子群优化高斯小波核函数支持向量机的交通流量预测方法67。首先将小波思想引入核函数，使用高斯小波核函数取代了经典支持向量机的高斯核函数。同时在支持向量机的学习算法上引入了

9、小生境粒子群优化算法，基于小生境粒子群的多样性的优势，使得支持向量机的参数得到最优解。最后进行了预测仿真，结果表明本文方法的预测精度高于传统方法。为交通流量的预测方法提供了一种参考。2.2交通分配的粒子群应用交通分配是在给定旅行时间函数和起讫点交通量分布的情况下，用适当的数理方法获得交通量在路网上的分配，为各路段上的交通量预测与路网规划提供理论依据。国际上通常把交通分配方法分为平衡模型与非平衡模型两大类，并以Wardrop 第1 、2 原理为划分依据，提出了交通分配的时间比原则、等时间原则和总行驶时间最小3 种分配原则的平衡模型。从理论上讲，平衡模型较非平衡模型具有结构严谨，思路明确，结果合理

10、，适用于宏观研究等特点。但由于变量较多、维数太大以及约束条件太多，使得对这类模型的求解显得较为困难，从而影响实际应用。王素欣等为了方便合理地分配交通量，提出了交通量多路径分配的粒子群优化算法89。算法的求解方法是在粒子群算法中构造了路径条数维的粒子空间，每一维对应一条可行性路线，其值为对应路径所分配的交通量；对粒子进行归一化处理，使交通量守恒，并进行交通量的多路径分配；根据目标函数评价与筛选粒子，直到满足终止条件。实例计算结果表明：利用粒子群算法得到的目标函数值最小，各路段分配的交通量没有超容量现象，模型求解过程具有方向性，对交通分配的网络规模无限制。将PSOA 应用于交通分配问题，为交通网络

11、分配提供一种新的算法思路。PSOA 在交通分配中的局限是优化前需要确定各OD 间的路径集。为减小PSOA 的局部优化问题，可采用各种改进的粒子群算法，如自适应粒子群算法与混合粒子群算法等。2.3交通网络的粒子群应用快速公交(BRT: Bus Rapid Transit)作为一种新型的大容量快速交通方式，一种可持续的城市交通模式，在各个国家缓解交通问题的过程中扮演着越来越重要的角色。公交网络优化设计问题(TNODP: Transit Network Optimal Design problem)是规划方案制定与优化调整的重要内容，是BRT系统规划设计中的重要部分，因而受到学者们的重视。由启发式算

12、法中提炼和实践而来的混合粒子群算法在求解过程中通过对问题在解空间的多点并行搜索，以较大的概率收敛于全局最优解，可以达到优化解集的目的，在优化问题的结果过程中得到良好的实践。通过对快速公交系统网络规划的描述，总结BRT网络的设线原则和规划的主要目标，进行BRT网络优化模型的构建，建立以乘客出行时间最小为目标和以直达客流最大为目标的优化模型，并进行约束条件的选择，确定可行性解集。 通过对粒子群基本模型和算法基本步骤的分析，引入遗传算法，形成PSO与GA结合的HPSO算法对模型的讨论，按照HPSO算法的基本步骤，对BRT线路走向和停靠站点优化问题模型的解进行编程迭代，得到最优解集。并通过实例验证了该

13、算法在优化解集的过程中的可行性。2.4公交线网的粒子群应用随着经济和社会的发展，在我国，城市公共交通的发展相对缓慢，交通堵塞越来越严重，给居民出行带来不便，尤其是常规公交存在着线路布设的不合理，线路分布的不均衡、比较零散等问题，不但降低了常规公交线网的运营效率，而且严重影响了公交线网的服务水平。目前大多数城市采用不分层法实现常规公交线网的优化布设，由于布设的线路分工不明确，衔接性差，缺乏整体性，甚至存在较多的交通盲区，因此，无法改善常规公交线网布设不合理的现状。梁利基于以上公交线网优化所面临的问题，采用分层法对公交线网进行优化。首先，对连续和离散 PSO 算法进行改进11。即针对 PSO 算法

14、极易陷入局部最优的缺点，基于动态指数改进策略和遗传变异的思想，从改变算法的惯性权重和加入变异算子两个方面结合将算法改进为变异 PSO 算法，并通过具体的测试函数，分析变异 PSO 算法与传统改进的 PSO 算法的收敛性能。其次，对公交线网采用分层法优化的优越性进行分析，并以兰州市的公交线网为研究对象，将变异 PSO 算法与灰色预测法相结合建立一种灰色变异粒子群组合预测模型，运用此模型在 MATLAB 软件中实现 OD 出行分布量的预测。最后，采用随机用户平衡方法实现 OD 客流量分配，在此基础上实现主干线、次干线优化模型的建立及各层优化约束条件的确定；采用变异 PSO 算法对各层进行求解，完成

15、主干线、次干线的优化布设；通过对优化后线网的重要指标计算分析，再次验证变异 PSO 算法具有良好的收敛性和分层法优化公交线网的优越性。公交 OD 客流量分配的准确性会影响线网优化的结果，因此，需进一步建立较高精度的分配模型。2.5交通控制的粒子群应用目前，智能交通系统(Intelligent Transportation System，ITS)是一个非常活跃的研究领域，国内外许多的专家学者对交通模型和控制策略进行了大量的研究工作，提出了许多交通模型和控制方法。而交通系统是一个具有随机性、非线性、离散性和不确定性的复杂系统，很难对其建立精确的数学模型。付绍昌等学者提出了自适应粒子群算法结合实数遗

16、传算法中变异算子的混合算法，它能提高算法的收敛性和稳定性121314。同时，通过对交通路口的通行情况的研究提出了一种新颖的离散交通信号控制模型。此模型以交叉路口各方向车流支路为基本单元，以各支路车流信息为输入，得出交通信号控制的各项性能指标。在此模型的基础上，应用自适应变异粒子群算法实现交通信号优化控制。自适应变异粒子群优化算法简单实用，同时也保持了粒子群优化算法的完整性，它的优化速度比遗传算法要快，比自适应粒子群优化算法更加稳定。结合自适应变异粒子群优化算法来优化交通信号配时方案。仿真结果表明自适应变异粒子群优化算法可以提高交叉路口通行能力，减少车辆延误，达到交通信号优化控制的目的，比传统方

17、法更好的适应交通流的变化。为交通信号控制提供了新的方法和思路。但此模型的控制周期时间必须为所取时间间隔的整数倍。为了达到更好的实时控制效果，下一步有待完善离散交通信号控制模型和进行多目标优化算法的研究。3总结与展望粒子群算法虽然对网络优化过程中的线路走向和停靠站点问题进行了解集的优化，但没有进一步对网络优化的其他环节进行理论上的验证，如果能够将规划过程中更多的优化问题运用到算法中来，会更有力地证明算法的可行性和效优性。采用HPSO算法迭代的OD出行时间与距离的关系的过程中，没有考虑复杂的等车延误、换乘延误、交叉口延误等因素，采取了较为理想化的状态进行分析，而考虑延误时，时间节省的构成更为丰富，体现出行距离对策略选择行为的影响。如果将约束条件细化运用于模型，将规划的经济效益考虑到运算过程中，则所建立的模型的求解，将更符合实中的经济和社会发展需要。从粒子群的研究方法分类可以看出，交通规划领域的各个方面，都可以通过粒子群算法进行优化求解，而且研究的求解算法并不是单一的，总是结合其他算法或者利用其