布谷鸟搜索算法优化支持向量机的停车位预测

梁 迪, 郭启航, 姜廷霖

(沈阳大学 机械工程学院, 辽宁 沈阳 110044)

随着我国汽车保有量的增加,停车位的预测及查询成为研究热点的问题.调查数据显示,造成交通拥堵的原因中有30%是因为驾驶者无法找到停车位所导致[1].可用停车位的预测,可以帮助驾驶者在出发或者距目标地点一段路程时,知道到达该停车场时可用停车位的数量,使其能够快速停放车辆.精确和快速地提供可用停车位的预测信息,不但可以使得驾驶者节省停车时间,同时也缓解了城市交通的停车难和拥堵等问题[2].

对一些停车管理系统的研究表明,引导式停车管理系统和基于云平台的停车诱导系统可以引导驾驶者将车停在就近停车位,帮助驾驶者找到空闲停车位[3-4].通过平均行驶距离、平均步行距离、停车占有率等指标对引导式停车管理系统的有效性进行评估,但这两种系统都缺少对停车位空余趋势变化的预判,容易导致驾驶者到达停车场时没有停车位可用,增加驾驶者不必要的行驶距离.Ajay等[5]通过分析收集的数据,采用Delphi技术筛选出重要参数,并建立停车位需求预测模型对校园停车位进行预测,有助于校园规划人员提供适当的停车设施,但这种非线性时间序列的数据拟合存在较大预测误差缺陷.为降低预测误差,孙涌等[6]采用多层前馈神经网络模型来预测空闲停车位,Doucoure等[7]将神经网络、支持向量机和回归树相结合进行停车位连续变化情况下的预测,这些预测方法在精度上得到了提高,但稳定性和容错性较差.

支持向量机(support vector machine,SVM)在1964年被提出,并在20世纪90年代由Vapnik等通过学习理论衍生出一系列改进和扩展算法.SVM处理高维度的非线性问题时具有很好的效果,而且SVM 模型有着优良的推广性[8].但SVM模型中参数的选择会直接影响模型的预测精度,惩罚系数C选择过高,模型容易过拟合.惩罚系数C选择过低,模型容易欠拟合.核函数宽度参数σ如果太小,容易出现训练集拟合精度高而测试集拟合精度低的情况.而布谷鸟搜索(cuckoo search,CS)算法具有很强的寻优能力以及参数少的特点,CS可以在SVM设置的参数解空间中进行寻优,找到最优的参数解,从而提高模型的预测精度.CS与SVM相结合的模型在诸多领域中都有应用,并都取得了不错的效果.在热点话题预测的应用中,布谷鸟搜索算法优化支持向量机模型可以准确描述热点话题的变化趋势[9].洑佳红[10]提出一种基于改进支持向量机的预测方法对尾矿库风险安全进行预测,并通过与粒子群算法、遗传算法进行对比得出其改进算法拟合准确率更好.刘超湖[11]提出一种基于改进布谷鸟搜索算法的支持向量机组合预测模型(ICS -SVM)应用于实际边坡变形预测,并选取7个基准函数测试ICS算法的寻优性能,验证了改进后的算法具有更高的预测精度以及良好地稳定性,可以较好地反映边坡实际变形情况.为了提高风电场输出功率的预测精度,刘家敏[12]等将小波分析(WD)与布谷鸟优化支持向量机(CS -SVM)相结合对风功率进行超短期预测,通过对预测结果的对比,WD -CS -SVM模型预测结果更加精准,具有较强的优越性和实用性.

针对停车预测中存在的问题,本文拟采用布谷鸟搜索算法与支持向量机(cuckoo search-support vector machine,CS -SVM)组合预测方法对空闲停车位进行预测.通过布谷鸟搜索算法优化SVM中的2个参数,惩罚系数C和核函数宽度σ,并在布谷鸟搜索算法中加入自适应动态调整公式,使步长因子根据每个阶段不同情况进行自适应动态调整,从而提高SVM模型的预测精度以及稳定性.通过构建CS -SVM模型对停车位做出准确预测,将所收集的空闲停车位数据分为训练集和测试集,训练集用于CS -SVM模型的训练,测试集用于对CS -SVM模型预测效果的验证.选择平均相对误差MMSE、均方根误差RMSE、确定性系数R2这3种评价指标对CS -SVM模型进行评价,并基于实际算例比较了CS -SVM、小波神经网络(WNN)以及支持向量机这3种方法的预测精度.

1 CS -SVM模型构建

1.1 布谷鸟搜索算法

布谷鸟搜索算法是2009年Yang和S.Deb提出的一种新兴启发算法[13],它不仅结合了鸟类及果蝇特殊的莱维飞行模式进行搜索,增加了种群之间的信息交流,加速收敛速度,而且参数少、操作简单、寻优能力强.布谷鸟寻窝的路径和位置更新公式如下:

(1)

在CS算法中,利用莱维飞行产生的步长不能确保快速收敛,具有一定的随机性且缺乏自适应性,所以步长因子要根据每个阶段不同情况来进行自适应的动态调整.离最佳鸟窝位置步长自适应动态调整公式如下:

Si=stepmin+(Smax-Smin)di.

(2)

式中,Smax和Smin分别表示最大步长和最小步长.

di定义如下:

(3)

式中:ni为第i个鸟窝的位置;nbest表示此时鸟窝的位置为最优位置;dmax为其他鸟窝位置与最佳鸟窝位置间的最大距离.

按照式(2),步长可以根据第i个鸟窝位置离最佳鸟窝位置的距离进行自适应调整.距离越近,步长越小;距离越远,步长越大.

1.2 支持向量机算法

SVM建模是利用非线性函数φ(x)将输入的数据样本映射到更高维的希尔伯特空间F中,转换为线性回归函数f(x)[14].SVM在高维的希尔伯特特征空间F中的线性回归函数为

f(x)=ω·φ(x)+b.

(4)

式中:ω表示权重向量;b表示偏向量.

为将结构风险降低到最小,可将式(4)优化转换为如下问题:

(5)

将式(5)优化问题转变为凸二次优化问题,引入拉格朗日乘数法,

将式(5)转换为对偶形式来提高收敛速度,转换如下:

(7)

对于线性回归问题,SVM回归函数为

(8)

为防止维数灾难发生,用核函数k(xi,x)代替高维空间中的向量内积(φ(xi),φ(x)),则SVM的回归函数为:

(9)

由于径向基核函数相较于其他核函数在没有先验知识的情况下具有参数少、性能稳定的特点,所以本文将径向基核函数作为SVM的核函数,其定义如下:

(10)

式中,σ为径向基核函数的宽度参数.

通过对SVM建模可以看出,惩罚因子C,核函数宽度参数σ的选择对SVM的性能有较大影响,因此本文采用布谷鸟搜索算法来优化SVM参数.

1.3 CS -SVM模型

建立CS -SVM停车位预测模型,首先将样本数据分为训练样本和测试样本,并设置算法所需的参数.在SVM中有C和σ2个参数需要寻优,采用CS算法对C和σ进行优化,构建CS -SVM停车位预测模型.建立CS -SVM模型的步骤如下.

Step 1 确定CS算法相应参数,即鸟巢的个数N,鸟巢被发现的概率Pa,最大迭代次数imax,抛弃鸟巢个数s,淘汰因数θ,C和σ的上限以及下限.

Step 2 将所选停车场实测数据分为训练样本和测试样本,然后把训练集归一化到[0,1]之间进行归一化处理.

Step 3 设定评价指标.选用平均相对误差MMSE、均方根误差RMSE作为评价CS -SVM模型精度的指标,选取确定性系数R2来评价模型的稳定性.各评价指标计算公式为

Step 4 初始化鸟巢位置(C,σ),设置初始概率参数Pa=0.8,将初始化的鸟巢位置(C,σ)代入SVM模型中,通过式(11)求出MMSE值,并保留最佳的鸟巢位置.

Step 5 更新布谷鸟鸟巢的位置,并将更新之后鸟巢位置的解代入到SVM模型中,得到更新后的MMSE值.将更新后所求MMSE值与上一代鸟巢位置所求解的MMSE值进行比较,若更新后解的MMSE值更小,则原来鸟巢位置将被更好的鸟巢位置所取代;反之,鸟巢位置不变.

Step 6 全局更新结束之后,进行局部搜索.每个鸟巢随机产生一个[0,1]之间的数r,若r>Pa,表示这个鸟巢会暴露,需要淘汰这个鸟巢,然后随机产生一个新的鸟巢;反之,鸟巢位置不变.

Step 7 局部搜索结束后,将所有鸟巢位置解的MMSE值按照大小排序,淘汰3个位置较差的鸟巢,并重新生成3个相应的鸟巢,计算其MMSE值.

Step 8 判断迭代是否终止,也就是迭代次数有没有超过最大迭代次数imax或者超过所设置的最小误差ε,若2个条件都没达到,则从第5个步骤继续迭代;若达到其中任一条件,则迭代终止,求得此时C和σ的最优解.并将此时鸟巢的最优解(C,σ)代入SVM进行训练,输出最终的预测值.

CS -SVM停车位预测模型构建过程图如图1所示.

图1 CS -SVM 预测模型构建图Fig.1 CS -SVM prediction model construction diagram

2 仿真实验

2.1 数据来源

本文选择辽宁省沈阳市新玛特中街店地下停车场的停车数据作为实验数据,统计时间为2019年12月10日—2019年12月12日16∶00—20∶00停车场4 h剩余停车位数据,以每5 min作为数据时间间隔,数据如表1～表3所示.

表1 12月10日16∶00—20∶00空闲停车位个数(间隔5 min)Table 1 Number of free parking spaces on December 10th from 16∶00—20∶00(every 5 minutes)

表2 12月11日16∶00—20∶00空闲停车位个数(间隔5 min)Table 2 Number of free parking spaces on December 11st from 16∶00—20∶00(every 5 minutes)

表3 12月12日16∶00—20∶00空闲停车位个数(间隔5 min)Table 3 Number of free parking spaces on December 12an from 16∶00—20∶00(every 5 minutes)

2.2 停车位数据预处理

为加快模型的SVM学习速度,对停车位数据进行预处理,归一化[0,1]之间,即:

(14)

2.3 实验结果分析及对比

将数据分成2部分,前50个数据作为训练样本用于预测模型的训练,其余数据作为验证集来检测预测模型的效果.将训练样本代入SVM进行训练,然后采用CS对SVM参数进行优化,得到最优参数为:C=80、σ=1.296.采用C=80,σ=1.296对训练集进行重新学习,建立CS -SVM停车位预测模型,将训练样本代入CS -SVM模型中,得到的拟合结果如图2所示.

图2 预测拟合曲线对比Fig.2 Comparison of prediction fitting curve

从图2可以看出,CS -SVM模型所预测的停车位变化趋势与实际值拟合程度非常高,拟合精度达到97.25%,比一般的拟合精度88%要高很多.与WNN(小波神经网络)、SVM(向量机)拟合结果相比,CS -SVM预测更加精确.从拟合结果来看, CS -SVM可以对停车位变化趋势进行预测,是一种拟合效果很好的停车位预测模型.

表4为CS -SVM实测值、WNN、SVM实测值对比,CS -SVM模型MMSE、RMSE值均最小,与其他模型相比,CS -SVM模型与实际测量值更为接近,预测精度更高.并且CS -SVM模型确定性系数R2也最小,因此稳定性相比WNN、SVM更佳

表4 CS -SVM、WNN、SVM实测值对比Table 4 Comparison of measured values of CS -SVM, WNN and SVM

3 结 论

为对空闲停车位进行准确预测,减少驾驶者寻找停车位所用时间,提出了一种布谷鸟搜索算法优化支持向量机的组合预测方法.通过CS算法对SVM的参数C和σ进行寻优,并在布谷鸟搜索算法中加入自适应动态调整公式,提高了模型的预测精度,增强了模型的稳定性.在预测时间步长相同的情况下,该方法与传统预测方法相比具有更高的预测精度,在停车位的预测中具有良好的效果,对于缓解城市交通拥堵也具有很强的现实意义.SVM模型实际上是通过不断优化的方法来解决二次线性规划问题的算法,改进后的CS -SVM仍然不适用于处理长时间序列问题,只适合处理小于30 min条件下短时间跨度的高精度预测.