CN109637121A

CN109637121A - 一种基于cs-svr算法的短时道路交通拥堵预测方法

Info

Publication number: CN109637121A
Application number: CN201810567338.3A
Authority: CN
Inventors: 胡启洲; 谈敏佳; 诸云; 岳民; 曾爱然; 周浩; 李晓菡; 陈杰; 丛子荃; 杨莹; 周畅
Original assignee: Nanjing University of Science and Technology
Current assignee: Nanjing University of Science and Technology
Priority date: 2018-06-05
Filing date: 2018-06-05
Publication date: 2019-04-16

Abstract

本发明公开了一种基于CS‑SVR算法的短时道路交通拥堵预测方法，算法属于道路拥堵预测技术领域，包括以下几个步骤：(1)收集原始数据并处理；(2)布谷鸟搜索算法(CS,Cuckoo Search)各参数初始化；(3)目标函数建立，初始适应度计算；(4)进行随机走动，计算新鸟巢位置；(5)更新最优目标函数值；(6)判断宿主鸟发现外来鸟蛋，改变或保留鸟巢位置。选取全局最优位置并判断是否达到迭代次数，若没达到最大迭代参数，则返回步骤S03，并且迭代代数加1；(7)若达到最大迭代代数或者满足精度要求，则利用SVR对测试样本进行交通拥堵预测。

Description

一种基于CS-SVR算法的短时道路交通拥堵预测方法

技术领域

本发明涉及一种道路交通拥堵流量预测方法，涉及一种基于CS-SVR算法的针对短时道路交通流量的预测，尤其是针对交通流量、速度的预测，属于道路拥堵预测技术领域。

背景技术

随着我国国民经济发展，城市化进程加快，越来越多的资源及劳动力涌向城市，促进城市发展同时，交通拥堵问题越来越突出，尤其是一些大城市的交通状况更为严重，交通拥堵现象不仅造成了城市投资成本增加，浪费了大量能源，还会增加环境污染，损害人们身体健康及带来了精神困扰，并会耽误人们很多事情，减少了社会活动效率，造成较大经济损失。因此对交通拥堵进行预测，尤其是预测交通流量有着重大的现实意义。

Vapnik等人于1995年首次提出向量机回归模型(SVR)，是一种基于“小样本”的学习机，主要用于函数逼近。目前，大量的研究表明SVR能够处理小样本、高维非线性预测问题，并且在模式识别、参数估计、故障预判领域得到广泛应用，因此将其引入到交通拥堵预测中。

2009年剑桥大学的Yang和Deb提出了一种新型元启发式搜索算法-布谷鸟搜索(Cuckoo Search，CS)算法。其机理是依据布谷鸟种群巢寄生繁衍的策略，通过鸟类特殊的Lévy飞行的方式寻找最优孵化的蛋，达到高效寻优目的。因此这种方法非常适用于优化SVR参数。

结合上述SVR的描述以及在预测方面的工作机理，本发明利用CS算法对SVR模型中径向基核函数(RBF)中出现的参数σ以及表达式中存在的惩罚因子C进行参数寻优，为此设计了一种交通拥堵预测流程。

发明内容

本发明提出一种基于CS-SVR算法，目的是针对短时道路交通拥堵的预测。包括以下步骤：

步骤S01：收集将要预测的某路段的某时段内的全部交通流量数据。为减少各数据之间特征相关性，提高预测精度，将其归一化，或者使用KPCA法进行降维，生成SVR训练样本。

步骤S02：初始化改进CS算法相关参数以及SVR各参数。包括鸟巢的数量n，预测精度acc，最大迭代iter、搜索的步长α₀、鸟蛋识别概率p_a，设定p_a为0.25。随机选取n个鸟巢初始位置假设每个鸟巢位置可用参数集合(C,g)表示，找出当前最优鸟巢的位置与最优适应度并记t＝0。

步骤S03：保留上代最优鸟巢位置利用公式(8)计算Lévy飞行步长并更新其他鸟巢位置。通过公式(7)得到新的鸟巢位置，计算它们适应度f。一般来说，适应度的设置遵循某方面指标最小或者最大的特性，本文选择预测精度误差最小作为适应度函数。

步骤S04：将这组新的鸟巢位置与上一组位置进行比较以及替换，得到一组较优的鸟巢位置

步骤S05：通过判断鸟巢主人是否识别出鸟蛋保留或改变鸟巢位置。产生一个服从均匀分布的随机数r作为鸟巢宿主发现外来蛋的概率并与设置好的识别概率定值P_a对比，加入随机的r大于P_a，则表明布谷鸟蛋已被识别，需要弃巢更新位置，反之保留鸟巢。因此。保留不被发现外来鸟蛋的鸟巢的位置，并且同时根据公式(12)改变发现外来鸟蛋的鸟巢位置p_t+1。

步骤S06：将步骤S05中的p_t+1与步骤S04中的p_t互相比较，用p_t+1中较优的解代替p_t中较差的解。并判断其最优适应度是否满足设置的预测精度acc。如满足，则停止迭代进入步骤S07；否则需返回步骤S03重新迭代更新。

步骤S07：保留最优鸟巢位置以及对应的(C,g)值作为SVR的最优参数，进行交通拥堵流量预测。

步骤S08：判断得出的值是否符合设定精度，如符合输出结果；否则，返回步骤S03。

有益效果：使用本发明方法的预测误差明显小于常用的SVM算法，预测精度提高至少 2.5倍。

附图说明

图1是本发明的流程图；

图2是对于路段2流量的预测结果；

图3是对于路段14流量的预测结果；

图4是对于路段22流量的预测结果；

图5是对于路段27流量的预测结果。

具体实施方式

下面结合附图和具体实施例对本发明作进一步说明。以下所描述的具体实施仅仅用以解释本发明，并不用于限定本发明。

本发明是利用布谷鸟搜索算法进行参数寻优，由SVR分类器给出交通拥堵识别结果。

SVR模型是支持向量机(Support Vector Machine,SVM)在回归估计问题中的进一步延伸。其回归本质是通过非线性映射φ(x)具体将低维数据x映射到高维特征空间，并完成线性回归拟合。其模型如下：

利用线性公式：

f(x_i)＝ωx_i+b (1)

对样本S＝{(x_i,y_i)|x_i∈Rⁿ,y_i∈R,i＝1,2,…,m}中的(x_i,y_i)进行线性拟合。其中，x_i∈Rⁿ是具有n个特征的输入指向量；y_i∈R是输出指标；f(x_i)是回归函数返回的预测值；变量系数ω是该函数的复杂度；b为偏置量，反映了预测函数之间误差度。

当样本不满足拟合函数时，定义ε线性不敏感损失函数为：

并引入两个非负的松弛变量ξ_i、来对应数据点x_i允许偏离的函数间距。之后通过最大化支持向量所组成的两条支持直线或者平面之间的几何间隔，在继续引入惩罚因子C之后，将线性回归拟合问题转化为约束优化问题，即：

式中的惩罚因子C为正则化参数；ε反映了误差量的精度要求。在求解上式中，引入Lagrange算子α_i、β_i与将式(3)构造为一个Lagrange方程：

根据KKT最优化条件，分别令并将(4)转化为：

可以解得最优解及b^*，其对应的样本即为支持向量，其中K(x_i,x_j)为核函数。因此所求的回归模型又可以表示为：

本发明选择泛化性更好的径向基核函数(RBF)构造SVR分类器。

径向基核函数(RBF)：令

利用布谷鸟搜索算法寻优目的是找出RBF核函数的σ以及公式(4)中的C。但由于套用了RBF公式，因此在程序编译时可直接设计寻优C和g。

布谷鸟搜索算法(CS)的本质就是使用搜索出来的新的解和更好的解来代替原本较差的解。为模拟布谷鸟搜索的过程，CS算法设定了三个理想状态：

(1)布谷鸟每次只能产一枚蛋，并随机选择鸟巢位置孵化，这代表一种解；

(2)在寻巢过程中，具有最优蛋的鸟巢会被保留并带到下一次迭代；

(3)设定的鸟巢数量是固定的，且布谷鸟蛋会被概率性得发现。如果发现，鸟巢主人会重新筑巢。

通过以上三种假设，CS算法的迭代更新通常可根据莱维(Lévy)飞行的方式更新。

Lévy飞行是许多动物和昆虫在飞行时所表现出来的一种具含幂律规律的特征。若用表示第i个鸟巢在第k代的鸟巢位置，在引入Lévy飞行模式后，此时寻巢路径和位置更新表达式为：

其中的λ为幂次系数；α为步长控制量，步长信息为：

上式α₀为常数，一般取值为0.01；x_best代表的是当前的最优解。

L(λ)为服从Lévy概率分布的随机搜索路径，这里采用Mantegna提出的模拟Lévy飞行搜索路径公式：

L(λ)＝μ/|v|^1/β,0＜β≤2 (9)

参数β＝λ-1，本文取值β＝1.5；μ和v需要服从正态分布，则

由于Lévy飞行的随机游走特性，局部极值附近会出现新解，因此该飞行的短步长搜索将会更有利于提高搜索解的质量。在某些状况之下，鸟巢宿主会概率性地发现鸟巢中布谷鸟的蛋。若宿主发现布谷鸟蛋的概率为P_a，则：

式中x_i，x_j，x_t为随机选择且互不相同的解；H(·)为阶跃函数；r为一个满足(0,1)均匀分布的随机数。在位置更新结束后，如果r＞P_a，鸟巢位置发生随机改变，否则就不变。

结合上述SVR的描述以及在预测方面的工作机理，本文利用CS算法对SVR核函数中出现的σ以及表达式中存在的惩罚因子C进行参数寻优。

为提高预测精度，需要对训练样本数据进行预处理，通常先选择KPCA法进行降维，再用一化预处理的方式将数据归类到[0,1]区间。

结合图1所示，本文利用CS算法对SVR核函数中出现的σ以及表达式中存在的惩罚因子C进行参数寻优，为此设计了一种交通拥堵预测流程，可将其步骤分解为：

步骤S01：收集要预测的某路段的某时段内的全部交通流量数据，包括速度等等。为减少各数据之间特征相关性，提高预测精度，将其归一化。生成SVR训练样本。

步骤S02：初始化改进CS算法相关参数以及SVR各参数。包括鸟巢的数量n，搜索精度acc，最大迭代iter、搜索的步长α₀、鸟蛋识别概率p_a，设定p_a为0.25。随机选取n个鸟巢初始位置假设每个鸟巢位置可用参数集合(C,g)表示，找出当前最优鸟巢的位置与最优适应度并记t＝0。

步骤S06：将步骤S05中的p_t+1与步骤S04中的p_t互相比较，用p_t+1中较优的解代替p_t中较差的解。并判断其最优适应度是否满足设置的搜索精度acc。如满足，则停止迭代进入步骤7；否则需返回步骤3重新迭代更新。

步骤7：保留最优鸟巢位置以及对应的(C,σ)值作为SVR的最优参数，建立交通拥堵预测模型。

为检验所提出的基于CS-SVR算法在道路交通流预测领域的可行性和有效性，本发明选择某市某新区路网中的第2号快速路段、第14号主干道路段、第22号次干道路段、第27号支路路段作为研究对象。

数据经过KPCA法降维之后，部分短时交通流量数据如表1所示：

可知每个路段有18组数据，按其时间顺序定义为1：5:00-5:05；2：5:05-5:10；3：5:10-5:15； 4：5:15-5:20；5：5:20-5:25；6：5:25-5:30；7：5:30-5:35；8：5:35-5:40；9：5:40-5:45；10： 5:45-5:50；11：5:50-5:55；12：5:55-6:00；13：6:00-6:05；14：6:05-6:10；15：6:10-6:15；16： 6:15-6:20；17：6:20-6:25；18：6:25-6:30。

下面在MATLAB环境下，检验本发明的预测精度，并与其他预测算法进行对比，仿真参数设定如下：

迭代代数M＝200；

鸟巢数量N＝20；

SVR交叉的算子为5；

最鸟蛋识别率为0.25；

预测精度为0.0001。

对于路段2流量的预测结果如图2所示。

对于路段14流量的预测结果如图3所示。

对于路段22流量的预测结果如图4所示。

对于路段27流量的预测结果如图5所示。

目前来说，对短时交通拥堵预测用的比较广的模型是SVM。为进一步验证本发明方法优越性，在使用表1同样数据的前提下，选择SVM对于交通流量预测的相对误差与本发明CS-SVR方法对于交通流量预测的相对误差，对比如表2所示。

通过表2可知，使用本发明方法的预测误差明显小于常用的SVM算法，预测精度提高至少2.5倍。因此可以证明本发明的有效性及可行性。

注意，在进行预测时，必须对数据进行归一化处理，否则可能出现预测误差较大的情况。此外，以上所述仅为算法在较佳实施情况下的结果，并不用以限制本发明，在不脱离本发明技术原理的前提下，还可以做出若干改进和变形，这些改进、变形以及将本发明的方法应用在其他预测对象也应视为本发明的保护范围。

Claims

1.一种基于CS-SVR算法的短时道路交通拥堵预测方法，包括以下步骤：

步骤S01，收集原始数据并处理；

步骤S02，采用布谷鸟搜索算法(CS,Cuckoo Search)对各参数初始化；

步骤S03，建立目标函数，计算初始适应度；

步骤S04，进行随机走动，计算新鸟巢位置；

步骤S05，更新最优目标函数值；

步骤S06，判断宿主鸟是否发现外来鸟蛋，改变或保留鸟巢位置；判断最优适应度值是否达到预测精度acc；如满足，则停止迭代进入步骤S07；否则需返回步骤S03重新迭代更新；

步骤S07，输出最优(C,g)值，并进行SVR交通拥堵预测；

步骤S08，判断得出的值是否符合设定精度，如符合输出结果；否则，返回步骤S03。

2.根据权利要求1所述的一种基于CS-SVR算法的短时道路交通拥堵预测方法，其特征在于，所述步骤S01中，数据处理的方法包括归一化法。

3.根据权利要求1所述的一种基于CS-SVR算法的短时道路交通拥堵预测方法，其特征在于，所述步骤S02中，布谷鸟搜索算法各参数初始化，所述参数包括：鸟巢数量n、最大迭代iter、预测精度acc、最大鸟蛋识别率p_a、搜索的步长α₀；鸟巢位置信息即是需要寻优的参数(C,g)，其中设定p_a为0.25。

4.根据权利要求1所述的一种基于CS-SVR算法的短时道路交通拥堵预测方法，其特征在于，所述步骤S03中，目标函数建立，初始适应度计算，包括：

利用SVR工具箱对训练样本进行训练，产生初步的预测精度值，此时的预测精度值为初始适应度值f⁽⁰⁾(i),i＝1,…,N；其中适应度值设定为利用SVR工具箱预测出的误差最小值。

5.根据权利要求1所述的一种基于CS-SVR算法的短时道路交通拥堵预测方法，其特征在于，所述步骤S04中，进行随机走动，计算新鸟巢位置，包括：

步骤1：保留上代最优鸟巢位置p^(j-1)(i),其中i表示第i个鸟巢，j表示当前迭代代数；

步骤2：使用模仿鸟类飞行的莱维(Lévy)飞行模式作为寻巢路径方式，进行鸟巢位置更新；位置更新公式如下：

p^(j+1)(i)＝p^(j)(i)+α·L(λ),i＝1,2,…,N

其中L(λ)为满足Lévy概率分布的随机搜索路径，s为随机步长，有：

L(s,λ)～s^-λ,(1＜λ≤3)

采用Mantegna提出的Lévy飞行搜索路径公式：

L(λ)＝μ/|v|^1/β,0＜β≤2

其中β＝λ-1，这里取β＝1.5；μ和v满足：

6.根据权利要求1所述的一种基于CS-SVR算法的短时道路交通拥堵预测方法，其特征在于，所述步骤S05中，更新最优目标函数值，包括：

利用SVR工具箱计算目前迭代代数的鸟巢适应值，并与上代鸟巢的适应值对比；设新适应值为fnew，第j代的适应值为f^(j)(i)，i＝1,2,…,N；假设存在fnew＜f^(j)(i)，则更新鸟巢位置，鸟巢位置变为假设存在fnew≥f^(j)(i)，则保留鸟巢位置，鸟巢位置不变还是f^(j)(i)，其中f^(j)(i)表示第j代第i个鸟巢的位置。

7.根据权利要求1所述的一种基于CS-SVR算法的短时道路交通拥堵预测方法，其特征在于，所述步骤S07，利用SVR对交通拥堵流量测试样本进行预测，包括：

输出结果：圆圈表示原始数据，即训练样本；星形表示预测结果，即用SVR预测后的回归预测数据；

判断标准：如果星形在圆圈正中间，表明数据完全一样，预测完全一致；如果星形在圆圈周围，表示预测结果有一定误差；如果完全在圈外，说明误差率太大，预测失败。