微分进化策略在忙时话务预测中的应用

支持向量机结合微分进化策略在忙时话务预测中的应用韩锐①*贾振红①覃锡忠①常春②王浩②①（新疆大学信息科学与工程学院乌鲁木齐830046）②（中国移动新疆分公司乌鲁木齐830063）摘要：本文用支持向量回归机与微分进化策略相结合的方法，对新疆两个地区的月平均忙时话务量进行预测。凭借微分进化策略良好的全局搜索性质，以预测平均相对误差为目标函数，对支持向量机的超参数进行寻优，利用优化好的支持向量机月平均忙时话务量进行预测，并与传统的网格寻优算法和RBF神经网络进行比较。结果表明支持向量机的泛化能力与微分进化策略的搜索能力相结合，可以得到更好的预测效果。在微分进化策略的两种扰动策略当中，对当前最优值的扰动策略要好于对当前随机值扰动的策略。关键字：微分进化策略；支持向量机；月忙时话务预测中图分类号：TP181文献标识码：AApplicationofSVMwithDE-strategytoTelephoneTrafficLoadofMonthlyBusyHourPredictionHanRui①JiaZhen-hong①QinXi-zhong①ChangChun②WangHao②①(CollegeofInformationScienceandEngineering,XinjiangUniversity,Urumqi830046,China)②(XinjiangMobileCommunicationCompany,Urumqi,830063,China)Abstract:TelephonetrafficloadofmonthlybusyhourintwostatesofXinjiangarepredictedbythemethodofsupportvectormachinecombineswithdifferentialevolutionstrategy.Thehyper-parameterofSVMisoptimizedviatheDE-strategyandtheMAPEcriteriaisdefinedastheobjectivefunction.TelephonetrafficloadofmonthlybusyhourisforecastedbytheoptimizedSVM,thepredictedresultiscomparedwiththemethodofgridsearchandRBFneuralnetwork.AbetterpredictionresultisobtainedbythegeneralizationpropertyofSVMcombineswithsearchingpropertyofDE-strategy.ThestrategyofperturbingthecurrentbestvalueisbetterthanperturbingthecurrentrandomvalueintheDE-strategy.Keywords:Differentialevolutionstrategy(DE-strategy);Supportvectormachine(SVM);Trafficloadofmonthlybusyhourprediction.1引言支持向量机理论自从提出以来[1]，就因其良好的泛化能力和严密的数学结构受到学者们的广泛关注[2]。近几年，支持向量机作为一种预测工具，已经应用在了医疗诊断[3]、电能需求预测[4]，以及链路负荷[5]等方面。然而，支持向量机的学习性能与其核函数的超参数有着很重要的联系[6]。因此，合适的超参数对支持向量机的预测能力有很大的帮助。微分进化策略[7]作为一种实值的群体智能优化算法，具有实现简单、可控参数少、鲁棒性强等特点，适用于求解全局优化问题，并对目标函数的可微性与约束条件没有要求，已在实际应用中取得良好的效果[8]。利用微分进化策略优秀的全局搜索能力，可以对支持向量机的超参数进行搜索，从而达到预期的优化目标。本文首先通过忙时话务量的定义，计算新疆地区的每月话务总量，从而得到每月忙时平均话务量的时间序列，其次通过微分进化策略对支持向量回归机的超参数进行寻优，最后利用训练好的支持向量回归机对每月忙时平均话务量进行时间序列预测。2相关原理及算法2.1对月忙时平均话务量的定义对每天产生的话务量进行每隔一小时的统计，一天就会统计24个话务量的值，对应每天的0点到24点，记录当天24个话务量值里的最大值作为对此日忙时话务量的统计。___________________________中国移动新疆分公司研究发展基金项目。*通信联系人。对当月每天的忙时话务量进行排序，去除最小的8个值及最大的2个值，再对剩余的数据取平均，由此构成当月的月忙时平均话务量。2.2支持向量回归机理论对于一组给定的数据集RRyxyxTdii)},(),...,,{(11，其中ix为训练数据集的大小，dR为输入特征空间，iy为与之相对应的输出数据的大小。回归问题就是要估计出ix与iy的关系：RbyRxbxxfyd,,)(,)((1)其中,对应在dR空间的内积。)(为核函数，把训练数据映射到高维空间F上FRd：，因此在原空间上解决非线性问题就等同于在新的高维空间上解决线性回归问题。机器学习理论对这一问题可以表述为在一组函数)},({xf中寻求一个最优的函数),(xf使得预期的期望风险)(R达到最小。nhnhRRemp)4/ln()1)/2(ln()()((2)其中n为样本容量，h为VC维。支持向量机理论把(2)式转化为寻求如下问题的最优解：)()(),()()(21max1111iiniiniiijijjninjiiyxxkW(3)niCtsiiniii,...2,1,,00)(..1(4)其中由不敏感损失函数),,(fyxL来定义，决定了回归曲线的平坦程度。C为惩罚因子，表示对错分样本的惩罚。由此，支持向量机所求得的回归函数可以使(1)式改写为：SVijiiibxxkxf1),()()((5)其中最常用的核函数为径向基核函数：)exp(),(2ijixxxxk(6)由KKT条件可以知道，系数)(ii中只有一部分是非零值，并且训练样本的误差大于或等于，这些训练样本就是支持向量。(4)式中的C以及(6)式中的被合称为支持向量机的超参数，对支持向量机的学习性能有着重要的影响。2.3微分进化策略理论微分进化策略的基本思想为：对种群中的每个个体i，从当前的种群中随机的选择三个点，以其中一个点为基础、另两个点为参照做一个扰动，所得点与个体i交叉以后进行“自然选择”，保留其中的较优者，实现种群的进化。不失一般性，设待求解的优化问题为)(minxfnRx，则微分进化策略[9]描述为：1)初始化进化参数：种群规模N，交叉概率CR，交叉因子F，进化代数t，自变量下界Ljx和上界Ujx，随机生成初始种群)0(,),0(1NXX，其中)0(,),0()0()()(1iniixxX；2)个体评价：计算每个个体)(tXi的目标值))((tXfi；3)种群繁殖：对种群中的每个个体)(tXi，随机生成三个互不相同的整数1r，2r，3rN,,2,1以及随机整数njrand,,2,1，otherwisetxjjorPrandiftxtxFtxtxijrandCrjrjrjij),(]1,0[)),()(()()()()()()()(321(7)4)选择：otherwisetxtxftxfiftxtXijijijiji),())(())((),()1()()()()((8)5)终止检验：如果种群)1(tXi满足终止准则，则输出)1(tXi中具有最小目标值的个体作为最优解，否则重新转至步骤2）。在本文的问题中，应当取2n，即需要优化的参数为两个，支持向量机的超参数C以及，则微分进化策略的扰动策略如图1所示：图1：超参数的变异策略3实验及仿真结果本文的实验数据来自新疆两个地区的月平均忙时话务量统计，从2005年8月到2008年10月共39个值，采用前36个值作为支持向量机的训练数据，后三个值作为测试数据。所有的数据首先都归整到0至0.5的范围内，测试的误差评价准则为平均相对误差准则piiiiyyypMAPE11(9)其中p为预测步数，iy为数据的真实值，iy为支持向量机的预测值。的取值设为0.01，输入向量的维数选取14，则支持向量回归机的输入值与目标值可以表述为：352322153214212221xxxxxxxxxxxxX，361615xxxY(10)对于微分进化策略的初始值设定[10]，我们可以取得10,3,nNP，6.0F，6.0CR。本文选取12NP，8.0F，8.0CR,迭代次数为150次。所要优化的目标函数为平均相对误差函数(13)，选择常用的两种扰动策略作为微分进化策略的繁殖方式，并与传统的网格寻优法以及RBF神经网络进行比较。表1：参数的搜索方式与取值范围方法扰动策略或搜索方式参数搜索范围策略1)(32xxFxbest2600~100C，95.0~005.0策略2)(32xxFxrand2600~100C，95.0~005.0网格寻优iC5.1，j5.119~1i，0~9jRBF神经网径向基宽度参数=5对新疆两个地区的月平均忙时话务量的后三个月的预测效果如下图所示：图2：A地区预测图图3：B地区预测图由上图可以看出，以微分进化策略为基础的两种搜索方法的效果要明显好于网格寻优算法以及RBF神经网络。每种方法的平均相对误差由下表给出，因为微分进化策略初始化种群的随机性，所以每次的实验结果会略有不同，因此策略1和策略2的平均相对误差由程序单独运行10次后的平均值得出。表2：预测月平均忙时话务量的平均相对误差方法A地区平均相对误差B地区平均相对误差策略14.372.74策略24.613.07网格寻优5.443.28RBF神经网11.227.474总结通过对新疆两个不同地区月平均忙时话务量的预测，可以看出支持向量机相对于RBF神经网络而言，有更好的泛化能力。而超参数的选择对支持向量机的泛化能力有着很重要的影响，本文利用微分进化策略良好的全局搜索能力，对超参数进行寻优，取得了比网格寻优法更好的预测效果。实验结果表明，微分进化策略的当前最优值的扰动策略要好于对当前随机值扰动的策略。参考文献[1]VladimirN.Vapnik.TheNatureofStatisticalLearningTheory(SecondEdition)[M].Springer,NewYork,2000.[2]L.P.Wang(Ed.).SupportVectorMachines:TheoryandApplication[M].Springer,Berlin,2005.[3]A.H.Khandoker,M.Palaniswami,andC.K.Karmakar.SupportVectorMachinesforAutomatedRecognitionofObstructiveSleepApneaSyndromeFromECGRecordings[J].IEEETrans.InformationTechnologyinBiomedicine,2009,Vol.13,pp.37-48.[4]Ruas,G.I.S.;Bragatto,T.A.C.;Lamar,M.V.;Aoki,A.R.;deRocco,S.M.Electricalenergydemandpredicti