基于混沌高效遗传算法优化SV M的交通量预测＊

康海贵 李明伟 周鹏飞 赵泽辉

（大连理工大学工程建设学部 大连 116024）

支持向量机（SV M）在经验风险最小化的基础上同时采用了结构风险最小化准则［1］，很好地解决了小样本、非线性、高维数、局部极小等实际问题［2］，避免了神经网络的参数难以选择、易陷入局部极值和过拟合等缺陷.但是，支持向量机本身并没有给出选择合适参数的方法，目前主要依靠经验法和试算法，很大程度上影响了模型的推广使用.考虑到基于混沌理论改进的混沌高效遗传算法（CHEGA）在参数优选中表现出的快速、高效的特点，本文建立了基于CHEGA进行参数优选的CHEGA－SVM交通量预测模型，并进行了仿真验证.对比结果表明该模型在交通量预测过程中具有一定的实用性.

1 支持向量回归的基本原理

在解决函数回归问题时，SV M方法的基本思想是：通过事先定义的非线性映射φ：Rn→Rm（m≥n），把输入空间的数据x映射到一个高维特征空间，然后在该空间中做线性回归φ：Rn→Rm（m≥n）.给定数据点集为｛（xi，yi），i＝1，2，…，N｝，式中：xi∈Rn为输入变量；yi∈Rn为与xi相对应的输出向量；N为数据点总数.SV M通过下式进行函数回归估计

式中：ω，φ为m 向量；“·”表示特征空间中的点积；b∈R为阈值.SV M采用最小化结构Rstr来确定参数w和b，即

同时引入松弛变量ξi和ξ＊i（i＝1，2，…，l），式（2）可改写为

上式便是SVM的原始问题，可以看出原始问题是一个有线性约束的二次规划问题.根据强对偶定理，引入 Lagrange乘子αi和αi（i＝1，2，…，l），建立Lagrange函数，并对w，b，ξi和ξ＊i求偏导并令其为0，于是得到上述SV M原始问题的对偶问题为

式中：K（xi，yi）＝［φ（xi）·φ（xj）］为核函数，其作用是不必知道从低维输入空间到高维特征空间非线性映射φ（x）的具体形式，通过引入核函数就可得到决策回归方程.常用的核函数主要有

多项式函数 K［x，xi］＝［x·xi＋1］q

本文选用的核函数是RBF函数［3］，其中δ为RBF函数的宽度函数.设对偶问题的解为¯α＝根据SV M的稀疏性一对αi和最多只有一个不为零，即2，…，l）且只有少数可不为零，这些不为零的参数所对应的输入向量xi称为支持向量，则决策方程只由支持向量决定，与非支持向量无关.决策回归方程式（1）可改写为

式中：xi为训练年份影响因子向量；x为预测年份的影响因子向量；f（x）为指标集合向量.式（7）即为SVM的交通量预测模型.

由上述可知，SV M的参数主要为惩罚系数C、损失函数参数ε和RBF核函数参数δ2，它们的选择在很大程度上影响着SV M的预测精度和泛化性能，只有正确选择参数，才可以使SV M回归估计得到较好的拟合效果［4］，因此为了提高SV M预测模型的预测精度和泛化性能，本文利用CHEGA进行参数С，ε和δ2的优选.

2 混沌映射

式中：x（i）为变量x在第i次的迭代值，其中u是控制参量.

理论上已经证明当u≥4时系统完全处于混沌状态，所以x（0）可任意设为［0，1］区间内的初值，但不能为0.25，0.5和0.75，然后根据式（9）得到混沌变量［6］.

图1给出了n＝500，u＝4，x（0）＝0.45时混沌变量的分布情况.图2给出了n＝500一般随机均匀分布系统产生的均匀随机变量分布情况.

图1 Logistic映射混沌变量图

图2 均匀分布随机变量图

从图1和图2可以看出，Logistic混沌映射轨道点能够布满整个区域的内部和边界，并且区域的内部和边界的轨道点的数量分布比较均匀，而均匀分布点虽然能够布满整个区域，但多分布在区域的内部，在区域的边界上的数量分布很少.在大量的非线性优化问题中，最优点的分布可能在区域的内部，也可能在边界上，因此采用Logistic混沌映射来生成初始群体，并利用混沌变异改进的混沌高效遗传算法，能够更好地搜索整个区域，保持种群的多样性，进行精细搜索.

3 CHEGA－SV M交通量预测模型算法

式中：n为输入样本个数；Y1（t）为SV M 拟合序列；Y（t）为实际序列值.基于CHEGA优化CHEGA－SV M交通量预测模型的计算步骤如下.

步骤1 样本数据和参数初始区间归一化.对输入的样本数据和参数的初始化区间进行归一化处理，归一化方法如下.

式中：b（j）和a（j）分别为第j类数据取值范围的最大值和最小值.

步骤2 混沌随机父代群体初始化.由Logistic混沌映射在参数初始区间内生成初始父代群体，m 个初始父代群体记为y（j，i），（j＝1，2，3；i＝1，2，…，m），其中y（j，i）为第i个父代个体上的第j个基因，本文取m＝50，u＝4.0，y（j，0）＝0.7.

步骤3 父代个体的适应度评价.将第i个父代个体的基因作为SV M参数，以训练集样本为输入输出，对SV M模型进行训练，将SV M训练结束后返回的输出序列方差Q的倒数作为第i个父代个体的适应度值F（i）＝1／Q.

步骤4 选择操作.产生第1个子代群体｛y1（j，i），j＝1，2，3；i＝1，2，…，m｝，取比例选择方式，则父代个体y（j，i）的选择概率为ps（i）＝

CHEGA优化SV M参数问题可以转化为如下最小化问题则 序 列｛p（i），i＝1，2，…，m｝把［0，1］区间分成m 个子区间，生成m－5个随机数｛u（k），k＝1，2，…，n－5｝，若u（k）在［p（i－1），p（i）］中，则第i个个体y（j，i）被 选 中，即 y1（j，k）＝ y（j，i），为 增 强CHEGA进行全局优化搜索能力，这里把最优秀的5个父代个体直接加入子代群体中，即进行移民操作

步骤5 杂交操作.产生第2个子代群体｛y2（j，i），j＝1，2，3；i＝1，2，…，m｝，根据选择概率随机选择一对父代个体y（j，i1）＝y（j，i2）作为双亲，并进行如下随机线性组合，产生一个子代个体y2（j，i）

式中：u1，u2，u3都为随机数，通过杂交操作，共产生m个子代个体.

步骤6 混沌变异操作.产生第3个子代群体｛y3（j，i），j＝1，2，3；i＝1，2，…，m｝，CHEGA的混沌变异操作采用自适应变异概率pm（i）＝1－p（i）来代替个体y（j，i），从而得到子代个体y3（j，i），即

式中：u（j）为混沌变量；um为［0，1］区间上的均匀随机数.

步骤7 演化迭代.由步骤4到6得到的3m个子代个体，按照其适应度值F＊（i）从大到小进行排序，判断当前种群中最优个体是否满足终止准则，若满足转入步骤9，否则取排在最前面的m个子代个体作为新的父代群体.然后转入步骤3进入下一轮演化过程.停止准则采用最大进化代数Gmax与相邻进化代数最优个体适应值相对误差E相结合.

步骤8 引进加速遗传算子.每演化迭代两次，取进化得到的6m个子代个体中的m个优秀个体的变化区间作为新的初始变化区间，转入步骤2，重新开始迭代过程.

步骤9 训练模型输出预测结果.以当前种群中具有最大适应值的个体的染色体基因С，ε和δ2作为SV M参数训练模型，输入待测样本，输出预测值.

计算流程见图3.

4 模型仿真验证

4.1 CHEGA－SVM交通量预测模型的训练与预测

结合某市客运量统计数据进行仿真验证，指标集为1978～2008年全市客运量，经相关性分析得出影响因子集为1978～2008年全市消费品总额、人均收入、能源总量、生产总值、汽车拥有量和总人口.在总体样本中抽取1982、1986、1990、1995、2001、2007年的影响因子和指标作为测试集，其余为训练集，应用CHEGA－SV M交通量预测模型分别进行训练和预测.

利用Matlab 7.1编制模型程序，运行环境为：Core（T M）2CPU，1.81 MHz，2 GB内存的微机.操作系统：Windows XP.仿真中，С的取值范围为［0.01，200］；ε的取值范围为［0.01，0.8］；δ2取值范围为［0.01，50］，最大进化代数Gmax＝100，邻代最优个体适应值相对误差E＝0.000 01.为了验证模型的使用性能，同时选用基于GA优化的GA－SV M模型和基于梯度下降法的传统BP神经网络模型进行对比仿真预测，并采用以下三个评价指标进行预测性能对比分析.

图3 算法流程图

式中：Y1（t）为 SV M 拟合序列；Y（t）为实际序列值；n为检验数据个数.

结合实测数据，进行模型训练和客运量仿真预测，图4为CHEGA－SV M交通量预测模型训练曲线，由图4可以看出训练输出和实际值拟和的较好，拟合平均绝对相对误差为2.42%，拟合均方根误差为3.21%，说明CHEGA－SV M交通量预测模型对客运量的历史序列拟合较稳定.

图4 CHEGA－SV M模型训练图

利用得到的CHEGA－SV M交通量预测模型对1982、1986、1991、1996、2002、2007年的客运量进行预测.图5为CHEGA－SV M交通量预测值与实际值对比图，仿真预测平均绝对相对误差为2.92%，仿真预测均方根误差为3.89%.

图5 CHEGA－SV M模型预测图

4.2 CHEGA－SVM交通量预测模型性能对比分析

将预测得到的客运总量与传统BP神经网络模型和GA－SV M模型仿真预测结果进行比较分析，其中BP神经网络模型选择的是单隐层BP神经网络，BP神经网络参数：最大迭代次数为100次，隐层节点数为7，学习率为0.25，允许的平方根误差为0.000 1；GA参数：种群大小为50，进化最大代数为100，交叉概率Pc为0.55，变异概率Pm为0.005.仿真预测值如表1所列.

表1 CAGA－υ－SVR与其他3个模型的预测比较

将表1中数据按式（15）、（16）和（17）分别进行误差指标处理，处理结果如表2所列.

表2 仿真预测误差指标比较 %

从表2中可以看出，在对基于不同结构预测模型的仿真预测结果对比方面，SV M模型的仿真预测结果要优于传统的BP神经网络模型；对采用不同的算法进行参数优选的SV M模型对比方面，基于混沌高效遗传算法优化的SV M模型的预测精度优于采用传统遗传算法优化的SV M模型.

5 结束语

本文提出了基于CHEGA进行参数优选的CHEGA－SV M交通量预测模型，并结合实际数据进行了仿真验证，对比结果表明：（1）改进的混沌高效遗传算法可以遍历到整个区域的内部和边界，较好的保持了种群的多样性，提高了参数的优选精度，同时利用优秀个体群逐步缩小搜索空间，加快了寻优速度.利用混沌高效遗传算法优选SV M模型的参数，克服了SV M模型参数确定难度大、精度低的问题，增强了SV M模型的泛化能力；（2）应用CHEGA－SV M交通量预测模型进行交通量仿真预测，模型的仿真预测精度优于GASV M模型和传统BP神经网络模型，平均绝对相对误差控制在3.0%以内，提高了城市交通量的预测精度，说明采用该模型对城市交通量的预测是可行的；（3）本文提出的CHEGA－SV M交通量预测模型，应用于城市交通量的预测，可以为公路建设项目的设计、施工和管理及相关政策、法规的出台提供科学的参考依据.

［1］Ki m Kyoung－jae.Financial time series forecasting using support vector machines［J］.Neuron co mputing（S0925－2312），2003，55：307－319.

［2］Vapnik V N.An overview of statistical learning Theory［J］.IEEE Transactions on Neural Networ ks（S1045－9227），1999，10（5）：988－999.

［3］Keerthi K，Lin C J.Asy mptotic Behaviors of Support Vector Machines with Gaussian Kernel ［J］.Neural Computation，2003，153 （3）：1 667－1 689.

［4］Cher kessk V，Yunqian M A.Practical selection of SV M parameters and noise estimation for SV M regression［J］.Neural Networ ks，2004，17（1）：113－126.

［5］Rettemeir K，Falkenhagen B，Kongeter J.Risk assessment new trends in Ger many［C］／／ICOLD.The Proceedings of 21t h Int Congress on Lar ge Dams.Beijing：the Inter national Co mmission on Lar ge Dams，2000：625－641.

［6］Liu B，Wang L，Jin Y H，et al.Impr oved particle swar m optimization combined with chaos［J］.Chaos Solutions and Fractals，2005，25（5）：1 261.