基于布谷鸟搜索算法的SVR参数选择

何思露, 韩坚华

(广东工业大学计算机学院，广州 510006)

互联网出现至今，发展十分迅速，给人们带来了极大的便利，但问题接踵而至，随着网络规模与应用领域的不断扩大，出现网络拥塞、网络故障、网络安全等问题，如何对与Web服务系统运行环境关联的网络流量数据进行测量、收集和预测已成为改善Web服务系统运行环境的主要难题之一[1]．若能预测网络流量的走向趋势，根据网络流量的预测结果为服务器制定合理的任务调度策略(如：Web服务端点可以根据当前的资源、网络环境状况，按照最优资源分配方案完成服务请求，同时，Web服务调用方可以使用Axis2提供的阻塞和非阻塞客户端API[2]，设计因不能及时获得服务响应而阻塞客户端的应对措施)，或为自适应控制能够依据不断变化的环境状态信息(如：网络流量的异常情况)而自主调整系统参数，以保持在期望范围内的Web服务系统性能[3]，都将会提高互联网应用的服务质量和安全性．但网络是复杂的、多方因素影响的，网络流量也必然呈现出高度自相似、时变性和非线性等特征，这注定传统的预测方法无法做到高的准确率．

支持向量回归机(SVR)在解决非线性回归问题时有极大的优势，本文选择它进行网络流量的回归预测．但SVR算法自身又有一定的缺陷，即参数寻优结果的好坏对SVR回归的准确率影响巨大．本文将布谷鸟搜索算法应用于SVR的参数寻优过程，它相较于传统寻优算法(如遗传算法等)，不仅加快了寻优速度，还提高了预测结果的准确率．

1 SVR的理论基础

支持向量机(SVM)是Cortes和Vapnik于1995年首先提出的[4]．它创造性地将线性不可分的问题通过核函数映射到高维空间，使之线性可分．对SVM的分类理论进行推广，并将其应用到回归预测中，便成了SVR．下面简单介绍SVR的理论.

假设给定样本集合：

T={(x1,y1),…,(xn,yn)}，

(1)

其中n为样本个数，xi表示输入样本，yi表示输出样本．

定义一个超平面：

(2)

考虑到现实情况下的误差，引入不敏感损失参数ε，并假定落于ε-带中的样本点都是无损失的．即：

用Lagrange乘子法求解,其中α为拉格朗日乘子：

解Lagrange乘子式

将式(6)代入式(5)，得到原问题的对偶问题：

便是求得的线性回归函数．

上述为线性情况，在非线性情况下，要将点通过核函数K(xi,xj)的形式映射到高维空间．这时只需将式(8)转换为：

其中核函数主要有以下几种形式：

多项式核函数

K(xi,xj)=((xi·xj)+1)q;

(10)

Sigmoid核函数

K(xi,xj)=tanh(ν(xi·xj)+c);

(11)

RBF核函数

由于RBF核函数相对其他核函数而言，有参数较少的优点，故本文用RBF核函数作为实验核函数[5]．

2 基于布谷鸟算法的参数选择

在用SVR进行回归预测时，算法的流程如图1所示.

图1 SVR回归流程

2.1 SVR的主要参数

大量实验表明，核函数的选择对回归的准确率影响较小，而影响最大的是参数的选择．在式(12)中，一般设γ=-1/(2δ2)，为控制半径，该参数对预测的精度有较大影响，另外一个影响比较大的参数是惩罚因子C．其中控制半径γ反映了支持向量的点之间的相关程度，γ越大支持向量间的相关性越强，模型的精度会相对降低；γ越小持向量的相关性越弱，机器学习能力会减弱，推广能力变差[6]．惩罚因子C反映了对错误样本的惩罚力度，加大C，错误样本数变少，但机器可能会产生过学习的情况，模型泛化能力变差；减小C，模型泛化能力变好，但样本被错分的情况会增多．

在参数(C,γ)的选择方面，现在主流的方法是遗传算法[7]、粒子群算法[6]等．但这些算法都有其局限性，在SVR寻参过程中，容易出现早熟的现象，且算法本身参数对寻参结果影响较大．

判断参数寻优好坏，主要需要考虑两方面的因素：其一是所需时间问题，所需时间短则表示算法收敛速度快；其二是预测的精度，预测精度高则拟合效果好．总体，在SVR的寻参过程中，我们追求的目标是所需时间短，同时用寻参结果训练的模型预测精度高、误差小．

2.2 布谷鸟搜索算法

布谷鸟搜索算法(Cuckoo Search,CS)，是由Yang 和Deb[8]在结合了布谷鸟的繁殖行为和Lévy飞行的特性后提出的一种新兴的启发式算法．实验结果[9]显示，布谷鸟搜索算法具有参数少、全局搜索能力强、搜索路径优和多目标求解问题强等优点．

布谷鸟是寄生育雏的形式[10]，在产卵期间，会选择将其鸟蛋产于相似的鸟类的窝中，让宿主代为孵化，且每个寄生巢中只产一枚卵．布谷鸟搜索算法模仿布谷鸟的这种行为，结合了Lévy飞行搜索机制，使得算法能有效跳出局部最优解[11]．

在模拟布谷鸟的寻窝方式时，需要假定3个理想化的状态[12]：

(1)一只布谷鸟一次只产一个卵，并随机选取一个寄生巢来孵化；

(2)在随机选取的寄生巢中，最好的寄生巢会被保留到下一代；

在该算法中，假定每个寄生巢中有若干个卵，它们分别代表一种解决方案，而布谷鸟的卵代表一种新的、潜在比较好的解决方案，来代替这个原有的、可能没那么好的解决方案．这种情况下，用下面的公式来改进寄生巢的质量：

(13)

gbest表示当前最好的寄生巢[13]．

故布谷鸟搜索算法的主要步骤可描述如下：

2)计算每个寄生巢的目标函数值g(NESTi)，并记录当前最优解，即值最小的g(NESTi)；

3)按照式(13)对其他寄生巢的位置进行更新，若这一代中比上代的目标函数值更好，则取代之前的最优解，成为新的最优解，即根据Lévy飞行的算法更新NESTi的值，若发现比当前更小的g(NESTi)时，取代之；

4)过程中设置一个随机数random与pa进行比较，若random>pa则随机改变当前寄生巢的位置，得到一组新的位置，即得到一组新的NESTi；

5)若g(NESTi)≤g(Tol)则输出最优解，否则跳回3)继续迭代，直至迭代次数t=T，输出当前g(NESTi).

3 结果与分析

为了验证上述布谷鸟搜索算法的一般性和有效性，本文做了2个实验，其中实验1是对网络流量进行回归预测[14]，实验2是对白葡萄酒的质量进行预测．在实验过程中，采用台湾大学林智仁开发的Libsvm在matlab的软件平台上进行仿真实验，同时3种算法的最大迭代次数均设置为100次，种群数量为25，C和γ的取值范围是(0, 100]，布谷鸟搜索算法中，我们设置随机变换概率pa为0.25，遗传算法中交叉率设为0.4，变异率为0.1，粒子群算法中，局部搜索能力参数c1初始设置为1.5，全局搜索能力参数c2初始设置为1.7．

3.1 网络流量实验

实验数据采集于Brandeis大学校园网的中心路由器于1994年1月20日监测的14:10～16:10内的TCP数据流量，按1 s为时间尺度，对该流量序列进行聚类操作，截取其中350 s的流量序列作为实验数据．

我们分别拿遗传算法、粒子群算法、布谷鸟搜索算法寻优的结果对SVR模型进行训练，并拿回归预测的数据与原始数据对比．为了定量地比较不同参数寻优的结果，定义均方根误差

和相关系数：

大量的混凝土外加剂的试验表明，后掺法比先掺法的混凝土工作性能要好，而且要达到相同的效果，后掺法的掺量在通常情况下会更小，这与混凝土外加剂与水泥颗粒的吸附和分散有关。

表1实验1中布谷鸟搜索算法与其他算法的均方根误差和相关系数对比

Table 1 RMSE and the correlation coefficients of cuckoo search algorithm and other algorithms in experiment 1

算法遗传算法粒子群算法布谷鸟搜索算法C的值1.60.14.6γ的值2.00.011.8均方根误差6.8e-031.8e-029.9e-05相关系数0.816 5010.211 0520.998 08 时间/s10534318

由表1可以看出，布谷鸟搜索算法算法所需时间大大少于遗传算法和粒子群算法，在收敛速度方面显示出了极大的优势，且通过布谷鸟搜索算法寻找出的参数训练出的SVR模型，相关系数最高，均方误差最小(即寻参结果的预测精度最高)．同时不难发现虽然3种算法选出的参数差别不是很大，但其均方根误差和相关系数却有较大的差异，这也证明了寻优参数的好坏对模型的预测精度有很大的影响．

几种算法的预测数据和原始数据的对比见图2.

3.2 白葡萄酒质量预测

为了进一步验证布谷鸟搜索算法的有效性，选取了UCI数据集中的Wine Quality数据集(其规模为4 898*12)进行测试，与网络流量不同的是，这是一个多变量的预测问题．我们截取数据集的前350项作为实验数据．实验中，将葡萄酒的得分作为因变量，其他的11项测量指标(如酒的pH值、固定酸度等)作为自变量．实验步骤和参数设置与实验1相同．

各算法的对比见表2，几种算法的预测数据和原始数据的对比见图3.

对比实验1和实验2，不难发现，随着自变量维数的增加，计算量也随之增大，运行各算法所需的时间几乎成倍增加，这说明数据量越大，布谷鸟搜索算法的优势越明显．在单变量和多变量的预测问题中，布谷鸟搜索算法都有较好的性能，遗传算法次之，而粒子群算法收敛速度慢，预测精度不高．

造成这一现象的主要原因是，SVR的参数寻优过程是一个多峰问题，遗传算法有交叉和变异的操作，这使其有可能跳出局部最优解，逐渐向全局最优解靠近，粒子群算法在收敛时粒子位置和速度的调整都过多依赖于当前最优粒子，这导致算法的早熟，而布谷鸟搜索算法由于引入了Lévy飞行搜索机制，相对前2种算法更容易跳出局部最优解而获得全局最优解．同时，它在局部搜索策略和全局搜索空间的探索之间有更好的平衡性，提高了算法的效率．另外，值得一提的是布谷鸟搜索算法自身的控制参数少，相对更加稳定，通用性更强[12]．

表2实验2中布谷鸟搜索算法与其他算法的均方根误差和相关系数对比

Table 2 RMSE and the correlation coefficients of cuckoo search algorithm and other algorithms in experiment 2

算法遗传算法粒子群算法布谷鸟搜索算法C的值2.61004.5γ的值0.240.010.33均方根误差5.6e-027.4e-028.8e-03相关系数0.570 1250.433 339 0.936 959时间/s20265340

图2 实验1中原始数据和回归数据的对比

Figure 2 Comparison of the original data and the prediction data in experiment 1

针对实验1的网络流量预测，另外取0.5 s、5 s、10 s作为新的时间尺度进行了预测，发现随着时间尺度的增大，均方根误差的平均值呈减少趋势，这说明时间尺度越大，预测的精度越高．这一现象是由布谷鸟搜索算法的不足引起的，它不能很好地适应数据激变的情况，对于变化率过大的数据，难以达到很好的拟合效果．故随着时间尺度的加大，网络数据会相对平滑，预测精度也会随之升高．在进行网络流量预测时，如何平衡预测的实时性和结果的准确性，仍需要进一步研究．

图3 实验2中原始数据和回归数据的对比

4 结论

对网络流量的预测能为建立自主计算机系统的负载预测和评估模型奠定基础[3]，同时在网络安全和管理上也有重要的意义．本文充分利用SVR在解决非线性问题时的优势，将其用于网络流量的预测，并针对遗传算法、粒子群算法在SVR参数寻优过程中的不足，提出了基于布谷鸟搜索算法的改进方法，使得该预测模型可以自动根据输入的自变量、因变量对参数进行选择，与传统方法相比，在性能上有较大提升，为SVR的参数选择提供了一条新的途径．

参考文献：

[1] 张冉, 赵成龙. ARIMA 模型在网络流量预测中的应用研究[J]. 计算机仿真,2011,28(2):171-174.

Zhang R, Zhao C L. Application research on network traffic prediction base on ARIMA[J]. Computer Simulation, 2011,28(2):171-174.

[2] 罗渊. 基于自学习调整 Web 服务端点行为策略的问题研究[D]. 广州:广东工业大学, 2013.

Luo Y. The research of adjusting the behaviors of web service endpoint based self-learning[D]. Guangzhou: Guangdong University of Technology, 2013.

[3] 廖备水, 李石坚, 姚远, 等. 自主计算概念模型与实现方法[J]. 软件学报,2008, 19(4):779-802.

Liao B S, Li S J, Yao Y, et al. Conceptual model and realization methods of autonomic computing[J]. Journal of Software,2008, 19(4):779-802.

[4] Cristianini N, 克里斯蒂亚尼尼, 肖-泰勒, 等. 支持向量机导论[M]. 北京:电子工业出版社, 2004.

[5] 白茹, 滕奇志, 杨晓敏, 等. 基于 SVM 和 GA 的药物与人血清白蛋白结合的预测[J]. 计算机工程与应用, 2009, 45(12): 226-228.

Bai R, Teng Q Z, Yang X M. Prediction of combinative activity of drugs and human serum albumin by using SVM and GA[J].Computer Engineering and Applications,2009, 45(12):226-228

[6] 陈林,潘丰. 基于量子PSO的SVM参数选择及其应用[J]. 自动化与仪表,2009(1):5-8.

Chen L,Pan F. Parameters selection and application of support vector machines based on quantum delta particle swarm optimization algorithm[J]. Automation and Instrumentation, 2009(1):5-8.

[7] 刘胜,李妍妍. 自适应GA-SVM参数选择算法研究[J]. 哈尔滨工程大学学报, 2007, 28(4):298-402.

Liu S,Li Y Y. Parameter selection algorithm for support vector machines based on adaptive genetic algorithm[J].Journal of Harbin Engineering University, 2007, 28(4):298-402.

[8] Yang X S, Deb S. Cuckoo search via Lévy flights[C]∥Proceedings of world congress on nature&biologically inspired computing.India: IEEE Publications,2009:210-214．

[9] Yang X S, Deb S. Engineering optimisation by cuckoo search[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2010, 1(4): 330-343.

[10] Yoon K J, Kweon I S. Adaptive support-weight approach for correspondence search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(4): 650-656.

[11] Payne R B. The cuckoos[M]. Oxford:Oxford University Press, 2005.

[12] 李煜,马良. 新型元启发式布谷鸟搜索算法[J]. 系统工程, 2012,30(8):64-69.

Li Y, Ma L.A new metaheuristic cuckoo search algorithm[J]. Systems Engineering, 2012,30(8):64-69.

[13] 柳新妮,马苗. 布谷鸟搜索算法在多阈值图像分割中的应用[J]. 计算机工程. 2013,39(7):274-278.

Liu X N, Ma M. Application of cuckoo search algorithm in multi-threshold image segmentation[J]. Computer Engineering, 2013,39(7):274-278.

[14] 姜明,吴春明,张旻,等. 网络流量预测中的时间序列模型比较研究[J]. 电子学报,2009,37(11):2353-2358.

Jiang M, Wu C M, Zhang M, et al. Research on the comparison of time series models for network traffic prediction[J]. Acta Electronica Sinica. 2009,37(11):2353-2358.