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

粒子群算法在交通规划的研究综述0 引言优化问题是一个古老的问题，它所研究的内容是讨论在众多的方案中什么样的方案最优以及如何找出最优方案。

交通规划作为新兴的交叉学科，其理论应用中存在着较多的寻优问题。

随着优化理论的发展，一些新的智能算法得到了迅速发展和广泛应用，成为解决传统优化问题的新方法，这类算法主要有遗传算法启发于生物种群通过遗传和自然选择不断进化的功能，人工免疫系统，模拟于生物免疫系统的学习与认知功能，蚁群算法，模仿蚂蚁群体在路径选择和信息传递方面的行为，还有模拟退火算法、禁忌算法等等[1][2]。

而粒子群优化算法(简称PSO)也是此类算法[3]。

1粒子群算法1.1产生背景自然界中，鸟群运动的主体是离散的，其排列看起来是随机的，但在整体的运动中它们却保持着惊人的同步性，其整体运动形态非常流畅且极富美感。

1986年Craig Reynols 提出了Bird模型，用以模拟鸟类聚集飞行的行为，通过对现实世界中这些群体运动的观察，在计算机中复制和重建这些运动轨迹，并对这些运动进行抽象建模，以发现新的运动模式。

之后，生物学家Frank Heppner在此基础上增加了栖息地对鸟吸引的仿真条件，提出了新的鸟群模型。

受上述鸟群运动模型的影响，社会心理学博士James Kennedy和电子工程博士Russell Eberhart提出了粒子群算法，1995年的IEEE神经网络会议和第六届微机与人类科学会议上分别发表了题为“Partiele swam optimization” 和“A new optimizer Using particle swam theory” 的两篇论文[4][5]，标志着粒子群优化算法的诞生。

1.2基本原理粒子群算法(PSO)是一种基于迭代模式的优化算法，最初被用于连续空间的优化"在连续空间坐标系中，粒子群算法的数学描述如下:一个由m个粒子(particle)组成的群体在D维搜索空间中以一定速度飞行，每个粒子在搜索时，考虑到了自己搜索到的历史最好点和群体内(或邻域内)其他粒子的历史最好点，在此基础上变化位置(位置也就是解)。

设搜索空间为D 维，总粒子数为n ，第i 个粒子位置向量为：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 较大，适于对解空间进行大范围探查，w 较小，则适于小范围。

第d(1 ≤d ≤D)维的位置X 变化范围为[ Xdmin ，Xdmax ]，速度V 变化范围[ Vdmin ，Vdmax] 。

2粒子群算法在交通规划领域的应用现如今，交通问题成为了城市发展的一个焦点问题，交通拥堵，交通路网使用效率不均衡等问题在发达城市日益显现，而作为交通设施建设的前期规划阶段，交通规划的理论发展则进展较慢，特别是在交通流预测，交通分配阶段的计算理论过于复杂，实际应用均采用比较简单的计算过程，最后又造成结果与现实情况偏离较大，达不到规划的实际作用。

因为交通需求预测的诸多优化主要是线性求解问题，利用的都是传统经典算法的求解过程，因此在问题设计之初就对问题做了较多简化或是模型仿真适应性不强。

随着智能算法的逐渐发展与应用，其在交通领域的应用逐渐成为交通规划求解优化问题的新工具，主要集中在交通诱导，交通规划，信号控制等方面，为交通发展的优化设计提供了较好的理论思路。

这些算法大大丰富了现代优化技术，也为具有非线性、多极值等特点的复杂函数及组合优化问题提供了切实可行的解决方案。

下面就分别概述粒子群算法在交通规划领域中的应用。

2.1交通流预测的粒子群应用实时准确的交通流预测是交通控制和交通诱导的前提和关键，其研究一直是智能交通系统的研究热点。

多年来，专家和学者们建立了很多预测模型和方法，如历史平均法、时间序列法、Kalman滤波法、回归分析法等等。

这些方法理论基础较成熟，应用也较多。

但这些传统的预测方法大都是基于数理统计的方法，共同特点是先建立数据序列的主观模型，然后根据主观模型进行计算和预测，预测精度不能满足实际的要求，加之不具备自适应和自学习的能力，预测系统的鲁棒性没有保障近年来许多学者对城市交通流系统的非线性特性进行了深入研究，建立了多种考虑交通流非线性的交通流预测模型，如BP神经网络模型、RBF神经网络模型、V olterra 滤波器自适应预测模型等。

其中，BP神经网络模型是比较成功的预测模型。

但该模型有两个明显的缺点：一是容易于陷入局部极小值；二是收敛速度慢。

为提高BP神经网络预测模型的预测准确性，李松等学者提出了一种基于改进粒子群算法优化BP神经网络的预测方法引入自适应变异算子对陷入局部最优的粒子进行变异，改进了粒子群算法的寻优性能，利用改进粒子群算法优化BP神经网络的权值和阈值。

然后训练BP神经网络预测模型求得最优解。

将该预测方法应用到实测交通流的时间序列进行有效性验证，结果表明了该方法对短时交通流具有更好的非线性拟合能力和更高的预测准确性。

王惟、李志鹏为了准确预测交通流量，为实施交通疏导提供参考依据，提出了一种基于小生境粒子群优化高斯小波核函数支持向量机的交通流量预测方法[6][7]。

首先将小波思想引入核函数，使用高斯小波核函数取代了经典支持向量机的高斯核函数。

同时在支持向量机的学习算法上引入了小生境粒子群优化算法，基于小生境粒子群的多样性的优势，使得支持向量机的参数得到最优解。

最后进行了预测仿真，结果表明本文方法的预测精度高于传统方法。

为交通流量的预测方法提供了一种参考。

2.2交通分配的粒子群应用交通分配是在给定旅行时间函数和起讫点交通量分布的情况下，用适当的数理方法获得交通量在路网上的分配，为各路段上的交通量预测与路网规划提供理论依据。

国际上通常把交通分配方法分为平衡模型与非平衡模型两大类，并以Wardrop 第1 、2 原理为划分依据，提出了交通分配的时间比原则、等时间原则和总行驶时间最小3种分配原则的平衡模型。

从理论上讲，平衡模型较非平衡模型具有结构严谨，思路明确，结果合理，适用于宏观研究等特点。

但由于变量较多、维数太大以及约束条件太多，使得对这类模型的求解显得较为困难，从而影响实际应用。

王素欣等为了方便合理地分配交通量，提出了交通量多路径分配的粒子群优化算法[8][9]。

算法的求解方法是在粒子群算法中构造了路径条数维的粒子空间，每一维对应一条可行性路线，其值为对应路径所分配的交通量；对粒子进行归一化处理，使交通量守恒，并进行交通量的多路径分配；根据目标函数评价与筛选粒子，直到满足终止条件。

实例计算结果表明：利用粒子群算法得到的目标函数值最小，各路段分配的交通量没有超容量现象，模型求解过程具有方向性，对交通分配的网络规模无限制。

将PSOA 应用于交通分配问题，为交通网络分配提供一种新的算法思路。

PSOA 在交通分配中的局限是优化前需要确定各OD 间的路径集。

为减小PSOA 的局部优化问题，可采用各种改进的粒子群算法，如自适应粒子群算法与混合粒子群算法等。

2.3交通网络的粒子群应用快速公交(BRT: Bus Rapid Transit)作为一种新型的大容量快速交通方式，一种可持续的城市交通模式，在各个国家缓解交通问题的过程中扮演着越来越重要的角色。

公交网络优化设计问题(TNODP: Transit Network Optimal Design problem)是规划方案制定与优化调整的重要内容，是BRT系统规划设计中的重要部分，因而受到学者们的重视。

由启发式算法中提炼和实践而来的混合粒子群算法在求解过程中通过对问题在解空间的多点并行搜索，以较大的概率收敛于全局最优解，可以达到优化解集的目的，在优化问题的结果过程中得到良好的实践。

通过对快速公交系统网络规划的描述，总结BRT网络的设线原则和规划的主要目标，进行BRT网络优化模型的构建，建立以乘客出行时间最小为目标和以直达客流最大为目标的优化模型，并进行约束条件的选择，确定可行性解集。

通过对粒子群基本模型和算法基本步骤的分析，引入遗传算法，形成PSO与GA 结合的HPSO算法对模型的讨论，按照HPSO算法的基本步骤，对BRT线路走向和停靠站点优化问题模型的解进行编程迭代，得到最优解集。

并通过实例验证了该算法在优化解集的过程中的可行性。

2.4公交线网的粒子群应用随着经济和社会的发展，在我国，城市公共交通的发展相对缓慢，交通堵塞越来越严重，给居民出行带来不便，尤其是常规公交存在着线路布设的不合理，线路分布的不均衡、比较零散等问题，不但降低了常规公交线网的运营效率，而且严重影响了公交线网的服务水平。

目前大多数城市采用不分层法实现常规公交线网的优化布设，由于布设的线路分工不明确，衔接性差，缺乏整体性，甚至存在较多的交通盲区，因此，无法改善常规公交线网布设不合理的现状。

梁利基于以上公交线网优化所面临的问题，采用分层法对公交线网进行优化。

首先，对连续和离散PSO 算法进行改进[11]。

即针对PSO 算法极易陷入局部最优的缺点，基于动态指数改进策略和遗传变异的思想，从改变算法的惯性权重和加入变异算子两个方面结合将算法改进为变异PSO 算法，并通过具体的测试函数，分析变异PSO算法与传统改进的PSO 算法的收敛性能。

其次，对公交线网采用分层法优化的优越性进行分析，并以兰州市的公交线网为研究对象，将变异PSO 算法与灰色预测法相结合建立一种灰色变异粒子群组合预测模型，运用此模型在MATLAB 软件中实现OD 出行分布量的预测。

最后，采用随机用户平衡方法实现OD 客流量分配，在此基础上实现主干线、次干线优化模型的建立及各层优化约束条件的确定；采用变异PSO 算法对各层进行求解，完成主干线、次干线的优化布设；通过对优化后线网的重要指标计算分析，再次验证变异PSO 算法具有良好的收敛性和分层法优化公交线网的优越性。

公交OD 客流量分配的准确性会影响线网优化的结果，因此，需进一步建立较高精度的分配模型。

2.5交通控制的粒子群应用目前，智能交通系统(Intelligent Transportation System，ITS)是一个非常活跃的研究领域，国内外许多的专家学者对交通模型和控制策略进行了大量的研究工作，提出了许多交通模型和控制方法。