一种改进灰狼算法优化LSSVM的交通流量预测

戴丽珍，付 涛，杨 刚，杨 辉，徐芳萍

(华东交通大学 电气与自动化工程学院，南昌 330013) (江西省先进控制与优化重点实验室，南昌 330013)

1 引 言

智能交通系统[1]的一个关键部分—交通流预测，在信号灯控制、交通拥堵疏导、驾驶路线引导等方面均发挥着重要作用.高效、准确的交通流预测可以保障ITS的准确运行，也为交通管控部门提供决策依据.随着全球ITS技术的飞速发展，交通流预测技术的研究成为一个热点问题.

研究表明，城市路面交通网中某一时间点的交通流量与前几个时间点的交通流量有映射关系，并且交通流量具有周期性[2].为了提高交通流量预测的准确性，常采用时间序列技术和回归模型等[3-9]方法.由于交通流有不确定性、复杂性和非线性等特点，导致其精确预测存在一定的难度.随着优化算法的发展，基于神经网络和群体智能优化的方法也被广泛应用于交通流量的预测.Chan[10]等人提出了一种基于粒子群优化算法的短时交通流预测方法，提高了预测的稳定性和可靠性.王凡[11]等人提出了一种基于AOSVR的交通流预测及参数选择的方法.Li[12]等人提出基于了粒子群优化混沌BP神经网络的短时交通流预测.Xu[13]等人提出了利用分类和回归树进行短期交通量预测.杨凡[14]等人研究了一种混合神经网络挖掘模型方法用于交通流预测.以上方法均在某种程度上提升了交通流的预测精度，但由于构建模型的差异，性能优劣无法判定.可以明确的是：基于群体优化的预测技术已被应用于交通流量预测，以提高预测模型的准确性.

在解决样本数量少、非线性系统以及模式识别等方面拥有诸多优势的SVM被Cortes和Vapnik提出，并能将其推广到线性拟合等其他机器学习问题中[15].Suyken为了解决SVM求解二次规划问题带来的训练时间过长等问题，提出用求解线性方程组问题代替求解二次规划问题的最小二乘支持向量机(Least Square SVM，LSSVM)[16].因此，LSSVM也被用于交通流量的预测[17，18].最小二乘支持向量机的性能在很大程度上依赖于它的两个核心参数(惩罚因子γ和核函数参数σ).其中，γ是平衡了对样本的拟合性能(经验风险)和测试样本的预测性能(结构风险)，即结构风险随着γ的增大而上升，经验风险却相反；且γ越大，模型将过拟合，而γ越小，模型将欠拟合.而σ的情况与γ相反.为了确定这两个关键参数，粒子群优化算法PSO、遗传算法GA、差分进化算法DE、人工蜂群算法BA和模拟退火算法SA等多种启发式算法已被尝试[19-23].灰狼优化算法(Grey Wolf Optimization，GWO)是模拟狼群的种群地位和捕猎行为的一种新群体智能优化算法，常用于模型的参数优化.当优化目标只有一个峰值时，GWO算法收敛速度较快；但当优化目标有多个峰值时，尽管GWO算法全局搜索性能比PSO和GA等算法高，而易造成局部最优(即早熟现象)[24]，从而导致模型陷入欠拟合或过拟合.由于在GWO算法中，控制距离参数a与迭代次数是线性关系且成反比，忽略了工程应用中优化问题的多样性，尤其是优化目标有多个峰值时，易陷入早熟.因此，为了实现交通流的精确预测，本文拟研究基于LSSVM的交通流预测建模方法，并通过增加GWO算法的种群多样性和改进GWO算法的控制距离参数a来优化LSSVM的参数，提高模型的预测精度.

2 最小二乘支持向量机模型

最小二乘支持向量机是对支持向量机改进得到的(不等式约束问题简化为等式约束问题).考虑数据样本(xt,yt)(t=1,2,…,l)，其中xt∈Rn，yt∈Rn分别为样本输入和样本输出，l为样本的数量.通过非线性变换，可将样本输入x映射到高维空间：

f(x)=wTφ(x)+c

(1)

其中：w为超平面的权值，c为常数，φ(·)为空间转换函数.

最小二乘支持向量机的目标函数定义如下：

(2)

其中：ei为误差，γ为惩罚因子.

构造拉格朗日函数如下：

(3)

其中：ai为拉格朗日乘子.根据KKT条件可得：

(4)

求解式(4)，可得LSSVM数学模型如下：

(5)

其中：K(·)为模型核函数，通常采用RBF核函数，即：

(6)

其中：σ为核函数参数.

因此LSSVM模型的性能主要取决于γ和σ.

3 基于改进GWO的LSSVM模型

(7)

(8)

(9)

A=a(2r1-1)

(10)

C=2r2

(11)

其中：t为当前迭代数；Dp(t)(p=α、β、η)为灰狼与猎物之间的距离；A和C为系数向量；Xp为当前猎物位置；Xl(l=1,2,3)为普通灰狼根据Xp更新的位置；a为控制距离参数，为由2-0的线性递减量；r1和r2为[0 1]随机数.

综上，灰狼优化算法的主要步骤如下：

Step 1.参数初始化.

Step 2.初始化种群个体并计算函数目标值，选择最优个体α、β和η.

Step 3.计算a、A和C的值，按照式(7)计算种群个体与最优个体的距离并根据式(8)-式(9)更新个体位置.

Step 4.更新最优个体位置.

Step 5.判断是否达到要求.如果达到设定值，则运行结束，否则转至Step 3继续迭代.

GWO算法在寻优过程中能自动调整控制距离参数a，且自身的参数具有良好的鲁棒性能，能够较好地平衡算法中种群的全局搜索能力和局部搜索能力[25].因此，控制距离参数a的设计，在一定程度上会影响到算法的全局搜索能力与局部搜索能力之间的平衡性.通常情况下，控制距离参数a随着迭代次数的增大，从2-0线性递减.当算法处于寻优初期时，搜索步长较大，全局搜索能力较强，不易陷入局部最优，且随机参数r1在一定范围时，|A|≥1，表明算法进行全局搜索；而当算法处于寻优后期时，搜索步长较小，局部搜索能力较强，易于收敛，且随机参数r1在一定范围时，|A|<1，表明算法进行局部搜索[26].

4 改进灰狼算法优化LSSVM交通流预测模型

对于GWO算法而言，探索能力对于其优化性能至关重要[27].GWO算法容易出现早熟现象，要想避免该现象，通常可采用丰富种群多样性、自适应变异、处理重复个体等方法[28].针对灰狼优化算法因种群多样性低以及控制距离参数a与迭代次数是线性关系且成反比的问题，忽略了工程应用中优化问题的多样性，尤其是优化目标有多个峰值时，存在早熟的缺点，结合差分进化算法和控制距离参数非线性化提出了改进的灰狼优化算法.为增加算法种群多样性进行如下改进：

1)变异操作：

Di(t)=xα+B(xβ-xη)

(12)

其中：Di(t)为变异个体位置，xp为当前种群中随机的3个个体位置，B为收缩因子.

2)交叉操作：

(13)

其中：R为交叉概率；yi为新个体.

3)选择操作：

(14)

其中：f(·)为评价函数.

对于控制距离参数a我们作如下改进：

a=cos(tπ/(2T))+(1-t/T)1.1

(15)

其中：T为最大迭代次数.

应用改进灰狼算法优化LSSVM模型参数进行交通流预测的流程如图1所示.

综上，改进的灰狼优化算法主要步骤如下：

1)构建数据集(即训练集与测试集)，并对数据预处理，得到路段的历史交通流量数据的时间序列.

2)利用改进灰狼优化算法对LSSVM参数优化(即惩罚因子γ和核函数参数σ)，主要步骤如下：

Step 1.参数初始化.

Step 2.初始化种群并计算函数目标值，选择最优个体α、β和η.

Step 3.计算a、A和C的值，根据式(7)计算种群个体与最优个体的距离并根据式(8)、式(9)更新个体位置.

Step 4.由式(12)-式(14)对当前种群执行变异、交叉和选择操作，计算个体的目标函数值.

Step 5.更新最优个体位置.

Step 6.判断是否达到要求.如果达到设定值，则运行结束，否则转至Step 3继续迭代.

3)根据最优参数得到最优模型后进行交通流量预测.

由于初始化的种群可能不能满足要求，这时候就需要扩充种群，而算法采用交叉、变异、选择操作，为算法种群增加了变异种群，因此，可以极大的改善算法的早熟现象.且通过对式(15)所示的控制距离参数a的非线性化的调整，与传统的GWO算法相比，非线性的控制距离参数a随着迭代次数的增加，斜率先递减后递增，且比传统a的斜率小，当t在0.8T到0.9T之间，a的斜率开始上升，如图1所示.因此，控制距离参数的非线性化能够保证在部分情况下，算法依然处于全局搜索，例如：当t=2/T，且随机数r1在一定范围内时，非线性化a=1.17，而传统a=1，这时改进GWO参数|A|≥1，而传统的GWO参数|A|<1；而当t接近最大迭代次数时，a以非线性递增的衰减速度趋于0且比传统的a衰减慢，这样也能保证局部搜索的充分性.

图1 改进灰狼算法优化LSSVM流程Fig.1 Improved grey wolf algorithm to optimize LSSVM process

5 仿真实验

5.1 实验数据来源与处理

本文采集了4天山东省某路段交通流量数据样本，每隔15分钟采集一次，共采集384组数据样本.

由于是数据驱动建模，首先需要确定模型输入与输出.依据相空间重构确定时间序列的迟滞时间及镶嵌维度，并建立数学模型：

y(n+k)=[x(n),x(n-t),…,x(n-(d-1)t)]T

(16)

其中：y(·)=x(·)为模型的输出，x(n)为时间序列，k为预测步长.

因为是对交通流时间序列进行预测，则令k=1，且每15min预测一次交通流量.由差分熵可以确定该时间序列的迟滞时间t=7，镶嵌维度d=4.训练和测试数据样本分别为276组和92组.

5.2 参数选择

使用改进GWO算法优化LSSVM模型参数前，定义改进GWO算法的优化目标函数为平均相对误差emape，如式(20)所示.改进GWO算法可调参数设置如下，种群数量npop=20，种群参数上、下界分别为ub=[1000,1000]、lb=[0.01,0.01]，缩放因子B∈(0.3,0.7)，交叉概率为R=0.1，最大迭代次数T=50等，其他模型同类型参数均一致.

5.3 实验结果分析

对预测结果采用如下指标进行评价：

最大绝对误差：

(17)

归一化均方根误差：

(18)

均方差：

(19)

平均相对误差：

(20)

为评价本文提出方法的优势，采用GWO-LSSVM、PSO-LSSVM、小波神经网络和ELM与本文方法对比，各自独立运行100次取评价指标平均值，对比结果如表1所示.

表1 模型评价指标结果对比Table 1 Comparison of model evaluation index results

仿真结果如图2-图6所示(其中图3-图6图例一致).对比分析如下：

图2 模型平均预测值对比Fig.2 Comparison of model average predictions

1)改进GWO-LSSVM模型对交通流量预测与其他算法相比，评价指标明显高于其他4种算法.

2)图3-图6中GWO-LSSVM的结果是由于GWO算法在寻优过程中，γ很大，σ很小导致模型出现过拟合现象，陷入局部最优.

图3 最大绝对误差Fig.3 Maximum absolute error

图4 归一化均方差Fig.4 Normalized mean square error

图5 均方误差Fig.5 Mean square error

图6 平均相对误差Fig.6 Mean relative error

3)值得注意的是，与PSO-LSSVM、小波神经网络相比，虽然本文提出方法性能指标发生5次较大幅度跳跃(可接受范围)如图3-图6，但是泛化性能明显提升.

6 结束语

为提高基于LSSVM的交通流量预测精度，本文提出了改进灰狼优化算法对LSSVM参数(惩罚因子γ和核函数参数σ)进行优化.为了提高算法全局搜索能力，避免过早陷入局部最优，设计了灰狼优化算法内部的交叉、变异和选择操作，并且使得控制参数a的非线性化，丰富了灰狼优化算法中种群的多样性，提升了算法的搜索性能.仿真结果显示，改进GWO优化LSSVM与GWO-LSSVM相比增强了泛化能力，能够获得较高的预测精度；与PSO-LSSVM相比，鲁棒性和泛化能力均有提升；与小波神经网络和ELM相比，虽然模型有所差别，但是泛化能力和鲁棒性有所提升.此外由于改进GWO算法加入了交叉、变异、选择操作，导致寻优时间较长，不符合实时性要求，因此本文方法通过历史数据建立模型，获得模型参数后预测当前交通流量.