基于改进的遗传算法优化的BP神经网络交通流量预测模型

Traffic Flow Prediction Model of BP Neural Network Based on Adaptive Genetic Algorithm Optimization

摘要: 短时交通流量是一种具有较强的随机性数据，不仅受到上下游历史数据的影响，而且还与天气等因素有关。为了提高短时交通流量预测的精度，采用遗传算法与BP神经网络组合的方法进行研究。同时针对BP神经网络存在网络初始权值随机的缺陷以及传统遗传算法易陷入局部最优和过早收敛等问题，给出了一种基于自适应遗传算法优化的BP神经网络短时交通流量预测模型，该模型通过自适应遗传算法对BP神经网络的初始权值进行优化，从而对短时交通流量进行预测分析。并结合实验数据验证了该模型的可靠性，该模型可以优化出行体验以及为交通管理部门制定缓解交通拥堵措施。

Abstract: Short-term traffic flow is a kind of strong random data, which is not only affected by historical data of upstream and downstream, but also related to weather factors. In order to improve the accuracy of short-term traffic flow prediction, a combination of genetic algorithm and BP neural network is used for research. At the same time, aiming at the shortcomings of the random initial weight of the BP neural network and the traditional genetic algorithm is easy to fall into local optimum and premature convergence, a short-term traffic flow prediction of the BP neural network based on the adaptive genetic algorithm optimization is given A model that optimizes the initial weight of a BP neural network through an adaptive genetic algorithm to predict and analyze short-term traffic flow. The reliability of the model is verified with experimental data. The model can optimize the travel experience and specify traffic congestion measures for the traffic management department.

1. 引言

在如今交通系统中，交通流是判断道路交通状况非常关键的因素，而短时交通流预测也是智能交通领域 [1] 中研究的热点。短时交通流预测依托数据采集设备采集的实时交通流数据，来预测未来15分钟内的交通路网状态，为出行者提供更佳的行驶路径，优化出行体验。

随着各国相继提出“交通强国”发展战略，国内外学者提出了多种交通流预测模型。交通流预测的方法大致可以分为2种：第一种是有参数的方法，第二种是无参数的方法。其中，有参数的方法主要包括：卡尔曼滤波方法 [2]，历史平均模型 [3] 等。Cook和Ahmaed率先建立了时间序列中的Box-Jenkins模型用来预测城际高速公路的机动车流量问题 [4]。但是这些有参数的方法不仅要要求较多的历史数据，而且对使用者的数学知识水平以及建模能力和技巧都要求很高。无参数的方法包括人工神经网络以及机器学习等方法。人工神经网络作为一种新的学习领域，已经被成功的应用在多分类任务，目标图像识别等众多领域中。因此越来越多的学者开始尝试并应用神经网络进的方法进行短时交通流预测。朱中 [5] (1998)建立单层的BP神经网络模型用以来预测某路段交通流量，其预测结果与传统的线性回归相比，精确度提高较为明显。

交通流是一种典型的时间和空间都相关的数据，BP神经网络具有强大的非线性映射能力而广泛的应用在交通流预测中。BP神经网络存在网络的权值和阈值随机的缺点，非常消耗训练资源，导致降低预测精度。为了克服以上缺陷，本文提出了一种基于改进的自适应遗传算法优化的BP神经网络的交通流量预测模型。由于改进的自适应的遗传算法具有很强的局部搜索能力 [6]，能过改进传统遗传算法在搜索过程中陷入局部最优解和过早收敛等问题。通过改进的自适应遗传算法优化的BP神经网络的权值和阈值，然后训练BP神经网络预测模型以求得最优解。

2. 交通流量时空特性分析

短时交通流量预测的核心，是提取海量历史交通流数据的特征。短时交通流量呈现很强的时间和空间特性，从空间维度来看，某个路段的交通流量不仅会受到其上游路段交通流量数据影响而且还与其下游路段的交通流量有关，从时间维度来看，交通流量是一个随着时间序列变化的数据，与其先前时刻和后一个时刻都有关。目前很多短时交通流量预测模型都是侧重时间维度，而忽略了空间维度特性。鉴于此，本论文重点研究交通流量数据的时空特性的提取以及选择合适的训练数据的大小，来提高预测模型的精度。

某路口的短时交通流量会受到相邻的上下游路口交通流量数据影响，为了确定上下游每个路口交通流量对待预测路口的影响程度，引入了皮尔逊相关系数相关系数 ${\rho }_{xy}$ 作为评价相关强度标准。一般 ${\rho }_{xy}>0.68$ 时，数据呈现出很强的关联性，可以根据相关系数的大小来衡量上下游不同路口数据进行排名，选择合适输入数据的大小。

${\rho }_{xy}=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(x_i-\bar{x}\right)\left(y_i-\bar{y}\right)}}{\sqrt{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\left(x_i-\bar{x}\right)}^2}}\sqrt{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{\left(y_i-\bar{y}\right)}^2}}}$ (1)

其中， $x_i$ 和 $y_i$ 代表两个交通流量序列，若 ${\rho }_{xy}$ 的值越大，表明这两个时间序列的交通流数据相关性越强。

为了在训练数据体现交通流的时间和空间特性，结合计算不同时间序列数据的相关系数，构建时间–空间相关系数矩阵，其具体的表示式如下：

$X_w=\left[\begin{array}{cccc}{W}_{1,t-\left(Q-1\right)}& W_{1,t-\left(Q-2\right)}& \cdots & W_{1,t}\\ W_{2,t-\left(Q-2\right)}& W_{2,t-\left(Q-2\right)}& \cdots & W_{2,t}\\ ⋮& ⋮& \ddots & ⋮\\ W_{p,t-\left(Q-1\right)}& W_{p,t-\left(Q-2\right)}& \cdots & W_{p,t}\end{array}\right]$ (2)

在时间–空间相关系数矩阵，Q代表的输入交通流量时间序列数据的长度，P代表预测观测点相邻点的位置。构成 $X_w$ 矩阵包含了时间和空间信息，最大程度上贴近实际应用场景，提高预测精度。

3. 遗传算法优化的BP神经神经网络

3.1. BP神经网络

BP神经网络是一种经典的前馈神经网络 [7]，该网络的核心是工作信号的反向传播机制。当训练数据从输入层输入到网络后，经过一层或者多层隐含层的逐层处理后，直至抵达网络的输出层。其中每一层中的神经元状态有两种：激活或者抑制。且每层中的神经元状态只会影响相邻的下一层神经元的状态。在训练过程中，若BP神经的实际输出和理想的期望偏差较大时，此时则转入反向传播机制，在工作信号反向传播过程中会动态调节每层网络的阈值和权值，从而不断的缩小BP神经网络实际输出与期望之间的误差。典型的三层神经网络的拓扑结构如下图1所示：

Figure 1. Basic structure of BP neural network

图1. BP神经网络基本结构

现有学习样本m个， $X_1,X_2,\cdots ,X_m$，BP神经网络的实际输出为 $y_1,y_2,\cdots ,y_m$，与其对应设定期望输出为 $t_1,t_2,\cdots ,t_m$，其中BP神经网络中间隐含层的神经元的个数为S个。BP神经网络算法核心是计算理想期望值与网络实际输出的均方差来动态修正每层神经网络连接的权值和阈值 [8]，使得网络实际的输出值不断的逼近期望值。

隐含层第i个节点的输入量为：

$ne{t}_i={\displaystyle \underset{j=1}{\overset{M}{\sum }}{w}_{ij}{x}_j+{\theta }_i}$ (3)

其中 $W_{ij}$ 为隐含层第i个节点与神经网络输入层第j个节点之间的连接权值， ${\theta }_i$ 为隐含层第i个节点的阈值。

则BP神经网络中间隐含层的第i个节点的输出量为：

$y_i=\varphi \left(ne{t}_i\right)=\varphi \left({\displaystyle \underset{j=1}{\overset{S}{\sum }}{w}_{ij}{x}_j+{\theta }_i}\right)$ (4)

其中 $\varphi \left(x\right)$ 表示为BP神经网络中间隐含层的激活函数。

输出层的第k个节点的输入量为：

$y_i=ne{t}_k={\displaystyle \underset{i=1}{\overset{q}{\sum }}{\omega }_{ki}{y}_i+{\alpha }_k={\displaystyle \underset{i=1}{\overset{q}{\sum }}{\omega }_{ki}\varphi \left({\displaystyle \underset{j=1}{\overset{M}{\sum }}{\omega }_{ij}{x}_j+{\theta }_i}\right)}}+{\alpha }_k$ (5)

输出层的第k个节点的输出量为：

$o_k=\phi \left(ne{t}_k\right)=\phi \left({\displaystyle \underset{i=1}{\overset{q}{\sum }}{\omega }_{ki}{y}_i+{\alpha }_k}\right)$ (6)

则可以计算神经网络的第k个节点的输出量 $o_k$ 与实际数据 $Z_k$ 之间的均方差E：

$E=\frac{1}{2}{\left(Z_K-o_K\right)}^2$ (7)

如果均方误差E小于训练设定的误差值，则神经网络会进入反向传播机制，不断的修正不同层的权值和阈值，直至均方误差小于设定的误差。

3.2. 遗传算法

遗传算法 [9] (Genetic Algorithm, GA)的核心思想来源于达尔文的生物进化论，通过模仿生物进化过程中的“物竞天择”机制而发展起来的随机全局搜索和优化方法。根据达尔文的生物进化理论，在大自然不断变化的环境中，对环境适应能力强的个体存活下来的几率大，而不能适应环境的个体逐渐被淘汰。适应性好的个体通过遗传机制将好的基因传给其后代，并且在适应环境的过程中发生一些不定的变异，变异的结果使之向有利于适应环境的方向发展，所以说生物进化过程是一个不断优化和选择的过程，遗传算法正是通过编程语言对遗传进化过程中环境不断选择过程的重构。借鉴生物进化机制，遗传算法模拟生物的进化的过程寻找对象的最优解。它将问题可行性通过编码机制编成基因串，即染色体，通过特定的适应函数的筛选以及类似自然界的选择，交叉，变异等操作产生新的种群，这样一代又一代周而复始的进化使群体中个体的适应度逐渐提高，直到满足一定条件，最终得到最优解。典型的遗传算法如下图2所示。

在遗传算法中，有三大核心操作：选择，交叉和变异。具体的算法流程如下 [10]：

1) 选择。选择操作是根据一定算法规则从目前种群去选择部分个体作为下一代种群的个体。常用的选择算子包括：赌轮盘选择方法，排序选择方法与最优保存策略等。

2) 交叉。交叉算子模拟遗传机制中的重组过程，以便将当前的最佳基因遗传给下一个群体中，并获得新的最佳个体。交叉算子的具体步骤如下：

步骤一：在当前种群中任意选择一对个体；

步骤二：计算个体的基因长度，随机选择一个整数或多个整数作为交叉位置。

步骤三：利用交叉概率 $P_c\left(0<P_c<1\right)$ 运行交叉算子，在交叉算子位置改变基因，这样获得了新的个体。在GA中，交叉算子包括：一点相交，两点相交，多点相交或均匀相交。

3) 变异。变异算子模拟了在自然进化中个体的某些个体朝着特定方向变异的现象。这样根据变异概率 $P_m$ 获得新的个体，个体的多样性是靠变异操做来实现的。

Figure 2. Genetic algorithm flow chart

图2. 遗传算法流程图

3.3. 遗传算法优化的BP神经网络

通过遗传算法来优化BP神经网络，其核心就是求解BP神经网络每层权值和阈值的最优解，可以最大程度的降低训练成本来提高模型的预测精度。本文采用的是实数编码，需要对神经网络的输入层，隐含层以及输出层每个节点的权值进行编码，该神经网络的输入节点个数为m，中间最大隐含层最大节点数为L，经过编码之后的长度为 [11]：

$编码长度=m\ast L+L+n\ast L+n+1$ (8)

在遗传算法优化BP神经网络初始权值时，遗传算法根据适应函数的大小来改变个体选择的速率，因此需要设置一个适应的适应函数来确定个体被选择的概率。由于遗传算法在最优值搜索过程中，其适应度值不断地增大，因此，可以将适应度函数设置为如下表达式 [12]：

$\text{fitness}=\frac{1}{{\displaystyle \underset{i=1}{\overset{N}{\sum }}\left|y_i-x_i\right|}+\varsigma }$ (9)

在公式(9)中， $y_i$ 表示遗传算法优化的BP神经网络的预测得到的车流量数据， $x_i$ 表示的真实的车流量数据，N为训练样本的数量。同时为了避免遗传算法适应函数的分母为0，引入一个不为零的变量 $\varsigma$。

但是，传统的遗传算法也存在一定的缺陷，当优化的目标函数过于复杂时，其优化之后的结果不是特别的理想，不仅算法优化非常耗时，而且得到的优化结果与实际值不太相符。为解决此问题，同时为了提高遗传算法的全局搜索最优解的能力和防止陷入局部最优解，给出了一种自适应遗传算法优化的BP神经网络模型来获得最优的BP神经网络初始权值。

4. 基于改进的自适应遗传算法优化的BP神经网络

遗传算法是拥有较强的全局最优值搜索方法 [13]，但是传统的遗传算法本身还存在着一定的缺陷。传统遗传算法中的交叉概率与变异概率通常是设定成常数，导致在训练过程中，群体的选择操作在局部终止，算法易陷入局部最优解。此时，群体的多样性呈现的比较差，可以通过增大交叉与变异概率来摆脱算法陷入局部最优。而在群体的多样性呈现比较强时，可以通过减小交叉与变异概率以加快收敛速度。因此，根据自适应函数调节交叉与变异概率的自适应算法应运而生。

4.1. 改进的自适应遗传算法

在传统的遗传算法中，交叉概率与变异概率的值通常是设定成一个定值 [14]，这种忽略了不同个体的特征的方法一定程度上阻碍了算法的收敛速度。在遗传算法中，算法的收敛度和搜索结果很大情况下会受到交叉概率 $P_c$ 和变异概率的影响。如果交叉概率 $P_c$ 的值设定的很大，则新个体的产生速率很快，但适应度较高的个体可能会被破坏，若 $P_c$ 值取的较小，则会导致群体的整体进化进度；如果变异概率 $P_m$ 的取值太大，则可能导致算法最终不收敛，若变异概率 $P_m$ 取的值太小，则新个体产生的速率过慢，导致整个种群的多样性差。因此，为了解决以上问题，自适应遗传算法(Adaptive Genetic Algorithm, AGA) [15] 应运而生，使得交叉与变异d1概率可以随适应度值的变化而动态的进行调节，使得算法收敛速度提升的同时确保最优解的输出。

$P_c=\{\begin{array}{ll}\frac{k_1\left(f_{\max }-f_1\right)}{f_{\max }-f_{\text{avg}}}\hfill & f_1\ge f_{\text{avg}}\hfill \\ k_2\hfill & f_1<f_{\text{avg}}\hfill \end{array}$ (10)

$P_m=\{\begin{array}{ll}\frac{k_3\left(f_{\max }-f_2\right)}{f_{\max }-f_{\text{avg}}}\hfill & f_2\ge f_{\text{avg}}\hfill \\ k_4\hfill & f_2<f_{\text{avg}}\hfill \end{array}$ (11)

式中： $0<k_1,k_2,k_3,k_4<1$, $f_{\text{avg}}$ 和 $f_{\max }$ 分别为种群中的平均适应度值和最大适应度值， $f_1$ 和 $f_2$ 分别为交叉个体中较大的适应度值和变异个体的适应度值。

从公式分析可以看出，当 $f_1$ 和 $f_2$ 与 $f_{\text{avg}}$ 相接近时，算法的交叉与变异概率会变得很小。这种调节方式不利于进化初值时种群中较优个体的变化，容易导致进化出现早熟收敛现象。所以按式(12)和式(13)进行修改，使种群中最小的适应度的个体的交叉变异概率不为0，分别提高到了 $P_{c2}$ 和 $P_{m2}$ [16]，提高了种群中较优个体的交叉概率和变异概率，加快了进化的进程。

$P_c=\{\begin{array}{ll}{P}_{c1}-\frac{\left(P_{c1}-P_{c2}\right)\left(f_{\text{avg}}-f^{\prime }\right)}{f_{\text{avg}}-f_{\min }}\hfill & f^{\prime }\le f_{\text{avg}}\hfill \\ P_{c1}\hfill & f^{\prime }>f_{\text{avg}}\hfill \end{array}$ (12)

$P_m=\{\begin{array}{ll}{P}_{m1}-\frac{\left(P_{m1}-P_{m2}\right)\left(f_{\text{avg}}-f\right)}{f_{\text{avg}}-f_{\min }}\hfill & f\le f_{\text{avg}}\hfill \\ P_{m1}\hfill & f>f_{\text{avg}}\hfill \end{array}$ (13)

式中： $f_{\min }$ 、 $f_{\text{avg}}$ 、 $f^{\prime }$ 、f分别为最小适应度值、平均适应度值、交叉操作中小的适应度值以及变异个体的适应度值，由于在种群选择中采用了模拟退火 [17] 法的选择操作和改进后的精英保留策略，所以这里的交叉、变异概率可以取较大的值。

4.2. 改进的自适应遗传算法优化BP神经网络

由于BP神经网络在训练时，其输入层与隐含层和输出层和隐含层之间的阈值和权值是随机生成的，导致训练的次数过多，而且遗传算法在全局搜索时容易陷入局部最优的局面。因此给出了基于改进的自适应遗传算法优化的BP神经网络模型，对BP神经网络的权值和阈值的最优解进行搜索，其算法流程如图3所示：

Figure 3. BP neural network optimized by improved genetic algorithm

图3. 改进的遗传算法优化的BP神经网络

5. 算法仿真及实验结果分析

本节通过历史交通流数据，对BP神经网络，基于遗传算法的BP神经网络以及基于改进的自适应遗传算法优化的BP神经网络进行交通流预测的精度仿真对比分析。

5.1. 数据源的来源

在模型训练过程中使用的数据来自美国加州交通运输部PeMS [18] 系统(performace meausuremnet system)，该系统中数据在交通流的预测中使用的最广泛，其数据包含多个路段的数据，数据的采集时间间隔为5分钟。本节选取同一段的数据进行训练和预测。其中路段的采取时间为2016年3月1日至2016年9月1日，将数据按照4:1的比例进行划分训练集与测试集，训练集用来训练模型，测试集用来预测的数据进行比对，来判定预测的精度。在测试之前，数据需要经过一定的预处理以及去噪，数据预处理方法本文就不详细介绍。其目标路段一天的交通流量如图4所示：

Figure 4. One day’s traffic volume on the target road section

图4. 目标路段一天的车流量

5.2. 算法的仿真测试设置

BP神经网络和基于改进的遗传算法的具体参数如表1所示。

其中，BP神经网络输入个数为288个，因为交通流的采样间隔为5分钟。神经网络的输出层表示预测未来的一天的交通流预测。

Table 1. Parameter settings

表1. 参数设置

5.3. 交通流预测仿真分析

本小节分别对比了BP神经网络，基于遗传算法改进的BP神经网络，以及基于改进的遗传算法优化的BP神经网络，预测交通流的精度。

图5展示了不同的模型预测输出，从图5可以得出：基于改进的遗传算法优化的BP神经网络的预测输出值最接近实际真实值。

Figure 5. Comparison of traffic flow prediction results of different algorithms

图5. 不同算法预测交通流结果对比

这里，我们对比了不同算法的平均误差，平方差，均方差，其对比结果如表2所示。

Table 2. Comparison of algorithm errors

表2. 算法误差对比

结合图4交通流预测数据和表2的误差对比数据来看，可以得出基于改进的遗传算法优化的BP神经网络模型预测的误差最小，优与单个BP神经网络预测模型以及基于传统的遗传算法优化的BP神经网络预测欧模型。

通过研究和实测数据可以得知，BP神经网络存在一定的缺陷，应用于交通流预测存在较大的误差。通过遗传算法优化的BP神经网络，可以在一定程度上提升预测精度，但是传统的遗传算法在搜寻最优解的过程中会出现局部最优解的情况。针对以上存在的问题，给出了一种基于改进的自适应的遗传算法优化的BP神经网络交通流预测模型，不仅设置的自适应函数收敛速度快，而且预测的误差较传统方法大大降低。