基于启发式算法的短时交通流量预测研究

周小敏

摘要：针对初始参数的有效性直接影响BP神经网络对短时交通流量预测的准确性这一问题，该文提出了基于CS（Cuckoo Search）算法与BP（Back Propagation）神经网络相结合的启发式算法来进行短时交通流量预测。该算法首先用相空间重构理论对训练序列进行重构，接着把重构后的序列作为BP神经网络的输入序列，同时采用CS算法来进行BP神经网络的最优阀值与初始连接权值的寻找，最后就得到了所需要的预测模型。仿真表明，本文所提算法在短时间内能够准确地预测交通流量的变化趋势，从而大大增加了所预测流量的可信度。

关键词：BP神经网络；短时交通流量；CS算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）23-5513-03

1 概述

随着城市人口不断增加，我国城市道路的建设进度难以跟上车辆数目的增长速度，从而使得交通拥堵问题日益严重，因此在现有道路条件下，如何对交通的进行高效的管理与调度以提升道路的通行能力，从而最大限度地缓解交通拥堵问题成为了一个十分重要的研究课题。而ITS（Intelligent Transport System，智能交通系统）[1]是目前最有效的解决办法之一。ITS把网络技术、信息技术、控制技术等先进的现代化技术运用到交通管理中，从而构建了一个覆盖全城的、全方位的、准确、实时、高效的智能系统。其中的交通流量预测是ITS的一项重要功能。这是因为ITS是根据未来的交通流量来制定相应的交通管理策略。因此，预测的准确性直接关系到交通管理测率的有效性。而短时交通流量预测为流量预测的重要组成部分。

经过多年的研究，人们在短时交通流量预测方面取得了丰硕的成果，提出许多的预测算法[2]。根据算法的理论依据，这些预测算法可以分成基于确定理论的预测算法与基于混沌理论的预测算法。常用的基于确定理论的预测算法有：Kalman滤波法、时间序列法、线性回归法等。这些算法都假设交通流量的变化是一个线性过程，但是在实际生活中，交通流量的变化是一个非线性时变的过程，因此这些基于确定理论的预测算法的预测准确度并不理想，其所得到的预测结果与实际情况相差会比较大，从而影响了交通管理策略的制定与调整。而常用的基于混沌理论的预测算法有：基于神经网络的预测法、基于遗传算法的预测法、基于向量机的预测法等。这些算法能够对非线性环境进行预测，从而能取得较高的预测精度。而该类算法的工作流程通常分为三个步骤：相空间的重构、预测算法的选择和参数优化、预测模型的生成。对训练序列进行相空间重构的目的是为了发掘训练序列背后所隐藏的内在规律。而预测算法是用来对从训练数据中提取预测模型，从而用于对未来进行预测。由于基于BP神经网络的短时交通流量预测算法能够实现自我学习并且具备预测可行度高等优点，因此本文选择该算法作为预测算法。但是，BP神经网络的阀值与初始连接权值直接影响该算法的预测可信度，如果参数设置不合理，该算法的收敛速度不仅会变慢而且所得到的预测模型也可能只是局部最优。针对这个问题，蚁群算法、遗传算法、退火算法等分别被用于BP神经网路的参数优化。但是，参数经过优化后的BP神经网络预测可行度还有有待提升。

而智能启发算法CS算法通过利用鸟类的飞行搜索原理，使得群体内的信息交流增多，从而实现了较快的收敛速度，这为参数优化问题提供了新的研究思路。在本文中，为了提高预测的可行度与精度，提出了基于CS（Cuckoo Search）算法与BP（Back Propagation）神经网络相结合的启发式算法（简称CS-BP算法）来进行短时交通流量的预测。

2 相关理论介绍

2.1 相空间重构

其中，[γ]与[vj]分别为该层的阀值和从隐层到输出层的连接权值。

在基于BP神经网络[4]的预测算法中，连接权值与阀值是随机产生的，从而会造成收敛速度以及预测结果都不是很理想，因此，采用CS算法对连接权值与阀值进行优化，从而提升BP神经网络的收敛速度与预测可行度。

2.3 CS算法

Yang等人在2009年的时候根据布谷鸟在后代繁衍中所使用的寄生策略，提出CS算法[5]。该算法遵守三个原则：

a）布谷鸟每次随机地在一个其它鸟的鸟巢中产一枚蛋；

b）放有优质蛋的鸟巢将会被保留；

c）一旦寄主鸟发现其巢中有布谷鸟的蛋，其要么放弃鸟巢，要么就把该蛋清出鸟巢。

令第t代中的第i个鸟巢的位置为[x（t）i]，搜索路径为[L（λ）]，那么在第t+1代中的第i个鸟巢的位置为：

[x（t+1）i=x（t）i+α⊕L（λ），（i=1，2，…，n）] （5）

其中，[α]为步长因子。

为了解决CS算法收敛速度慢等缺点，利用高斯扰动来加快收敛速度，实现方法为：第t代中的第i个鸟巢的位置[x（t）i]进行绕到扰动，从而实现对[x（t）i]的更进一步的搜索。

令[pt=x（t）1，x（t）2，…，x（t）nT]，则引入高斯扰动后的[p`t]：

[p`t=pt+β⊕ε] （6）

其中，[β]与[ε]分别为常量，扰动矩阵（矩阵大小与[pt]相同）。

从公式（6）可以看出，通过[β]与[ε]的使用，使得鸟巢的位置变化更灵活，从而实现了算法的快速收敛。

3 基于启发式算法的短时交通流量预测的实现

上一节分别对本文所提算法用到的相关理论进行了介绍，本节将综合利用上述理论来实现本文所提算法。算法的实现步骤为：

1）首先通过对交通流量进行测量得到短时流量训练序列，然后分别用关联维算法与互信息法来确定维数[m]与时延[τ]，最后利用[m]与[τ]对训练序列进行相空间重构，那么重构后的序列被用作神经网络的训练序列；

2）首先随机地生成[n]个鸟巢的位置[p（0）i=x（0）1，x（0）2，…，x（0）nT]，而鸟巢的位置是与神经网络的阀值与连接权重相对应的。然后神经网络根据每一个鸟巢位置所对应的参数开始训练，从而得到相应的预测精度，最后找出当前训练周期内的最优鸟巢[x（0）b]；

3）首先[x（0）b]保持不变，而其它鸟巢的位置利用公式（5）进行变化，接着计算变化了的位置所对应的预测精度，然后把本次所得到的预测精度与相应的上代预测精度相比较，最后把精度高的鸟巢位置保留下来，从而生成了一组新的鸟巢位置[kt=x（t）1，x（t）2，…，x（t）nT]；

4）首先随机生成一组[r]，接着把[r]与[Pa]进行比较，[kt]中的鸟巢位置被发现概率小的将被保留，其它的经随机地改变，从而得到一组新的位置，然后计算新位置所对应的预测精度，最后把精度高的位置保留下来，从而成了一组新的鸟巢位置[pt=x（t）1，x（t）2，…，x（t）nT]；

5）首先利用公式（6）对[pt]实施扰动，而扰动后的位置为[p't=x（t）'1，x（t）'2，…，x（t）'nT]，接着计算[p't]每个位置所对应的预测精度，最后把精度高的位置保留下来，从而成了一组新的鸟巢位置[p''t=x（t）''1，x（t）''2，…，x（t）''nT]，并令把[pt]=[p''t]；

6）首先跳出[pt]中预测精度最高的鸟巢[x（t）b]，接着判断该预测精度是否能够达到要求，如果达到，把[x（t）b]作为神经网络的参数设置，调到（7），否则的话，跳到（3）；

7）首先[x（t）b]所对应阀值与初始权值送入神经网络，然后神经网络开始用训练序列进行训练，从而得到预测模型，最后用预测模型进行预测。

4 仿真分析

为了验证本文所提算法（简称CS-BP）的性能，将对基于PSO的BP神经网络的预测算法（简称PSO-BP）和基于GA的BP神经网络的预测算法（简称GA-BP）与CS-BP三者的预测误差进行分析。

GA-BP的参数为：变异与交叉概率分别为0.12，0.73，种群规则与最大进化次数分别为30和300。PSO-BP的参数为：[c1=c2=3]，其它参数与GA-BP相同。而CS-BP的参数为：鸟巢数为30，[Pa=0.25]，最大进化次数不超过300。

三种预测算法根据[X]的前380个数据来生成预测模型，并使用预测模型来预测后100个数据，图2给出了三种算法预测的结果。

5 小结

本文针对交通流量预测中的短时交通流量预测问题，提出了基于CS Search）算法与BP神经网络相结合的启发式算法。并且仿真表明，本文所提算法在短时间内能够准确地预测交通流量的变化趋势，从而大大增加了所预测流量的可信度，为智能交通管理提供了重要的依据。

参考文献：

[1] Liu X， Fang Z. An agent-based intelligent transport system[M]//Computer Supported Cooperative Work in Design IV. Springer Berlin Heidelberg， 2008： 304-315.

[2] 沈国江， 王啸虎， 孔祥杰. 短时交通流量智能组合预测模型及应用[J]. 系统工程理论与实践， 2011， 31（3）： 561-568.