基于布谷鳥搜索算法的SVR參數(shù)選擇

何思露, 韓堅(jiān)華

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州 510006)

互聯(lián)網(wǎng)出現(xiàn)至今，發(fā)展十分迅速，給人們帶來了極大的便利，但問題接踵而至，隨著網(wǎng)絡(luò)規(guī)模與應(yīng)用領(lǐng)域的不斷擴(kuò)大，出現(xiàn)網(wǎng)絡(luò)擁塞、網(wǎng)絡(luò)故障、網(wǎng)絡(luò)安全等問題，如何對(duì)與Web服務(wù)系統(tǒng)運(yùn)行環(huán)境關(guān)聯(lián)的網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行測(cè)量、收集和預(yù)測(cè)已成為改善Web服務(wù)系統(tǒng)運(yùn)行環(huán)境的主要難題之一[1]．若能預(yù)測(cè)網(wǎng)絡(luò)流量的走向趨勢(shì)，根據(jù)網(wǎng)絡(luò)流量的預(yù)測(cè)結(jié)果為服務(wù)器制定合理的任務(wù)調(diào)度策略(如：Web服務(wù)端點(diǎn)可以根據(jù)當(dāng)前的資源、網(wǎng)絡(luò)環(huán)境狀況，按照最優(yōu)資源分配方案完成服務(wù)請(qǐng)求，同時(shí)，Web服務(wù)調(diào)用方可以使用Axis2提供的阻塞和非阻塞客戶端API[2]，設(shè)計(jì)因不能及時(shí)獲得服務(wù)響應(yīng)而阻塞客戶端的應(yīng)對(duì)措施)，或?yàn)樽赃m應(yīng)控制能夠依據(jù)不斷變化的環(huán)境狀態(tài)信息(如：網(wǎng)絡(luò)流量的異常情況)而自主調(diào)整系統(tǒng)參數(shù)，以保持在期望范圍內(nèi)的Web服務(wù)系統(tǒng)性能[3]，都將會(huì)提高互聯(lián)網(wǎng)應(yīng)用的服務(wù)質(zhì)量和安全性．但網(wǎng)絡(luò)是復(fù)雜的、多方因素影響的，網(wǎng)絡(luò)流量也必然呈現(xiàn)出高度自相似、時(shí)變性和非線性等特征，這注定傳統(tǒng)的預(yù)測(cè)方法無法做到高的準(zhǔn)確率．

支持向量回歸機(jī)(SVR)在解決非線性回歸問題時(shí)有極大的優(yōu)勢(shì)，本文選擇它進(jìn)行網(wǎng)絡(luò)流量的回歸預(yù)測(cè)．但SVR算法自身又有一定的缺陷，即參數(shù)尋優(yōu)結(jié)果的好壞對(duì)SVR回歸的準(zhǔn)確率影響巨大．本文將布谷鳥搜索算法應(yīng)用于SVR的參數(shù)尋優(yōu)過程，它相較于傳統(tǒng)尋優(yōu)算法(如遺傳算法等)，不僅加快了尋優(yōu)速度，還提高了預(yù)測(cè)結(jié)果的準(zhǔn)確率．

1 SVR的理論基礎(chǔ)

支持向量機(jī)(SVM)是Cortes和Vapnik于1995年首先提出的[4]．它創(chuàng)造性地將線性不可分的問題通過核函數(shù)映射到高維空間，使之線性可分．對(duì)SVM的分類理論進(jìn)行推廣，并將其應(yīng)用到回歸預(yù)測(cè)中，便成了SVR．下面簡(jiǎn)單介紹SVR的理論.

假設(shè)給定樣本集合：

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

(1)

其中n為樣本個(gè)數(shù)，xi表示輸入樣本，yi表示輸出樣本．

定義一個(gè)超平面：

(2)

考慮到現(xiàn)實(shí)情況下的誤差，引入不敏感損失參數(shù)ε，并假定落于ε-帶中的樣本點(diǎn)都是無損失的．即：

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

解Lagrange乘子式

將式(6)代入式(5)，得到原問題的對(duì)偶問題：

便是求得的線性回歸函數(shù)．

上述為線性情況，在非線性情況下，要將點(diǎn)通過核函數(shù)K(xi,xj)的形式映射到高維空間．這時(shí)只需將式(8)轉(zhuǎn)換為：

其中核函數(shù)主要有以下幾種形式：

多項(xiàng)式核函數(shù)

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

(10)

Sigmoid核函數(shù)

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

(11)

RBF核函數(shù)

由于RBF核函數(shù)相對(duì)其他核函數(shù)而言，有參數(shù)較少的優(yōu)點(diǎn)，故本文用RBF核函數(shù)作為實(shí)驗(yàn)核函數(shù)[5]．

2 基于布谷鳥算法的參數(shù)選擇

在用SVR進(jìn)行回歸預(yù)測(cè)時(shí)，算法的流程如圖1所示.

圖1 SVR回歸流程

2.1 SVR的主要參數(shù)

大量實(shí)驗(yàn)表明，核函數(shù)的選擇對(duì)回歸的準(zhǔn)確率影響較小，而影響最大的是參數(shù)的選擇．在式(12)中，一般設(shè)γ=-1/(2δ2)，為控制半徑，該參數(shù)對(duì)預(yù)測(cè)的精度有較大影響，另外一個(gè)影響比較大的參數(shù)是懲罰因子C．其中控制半徑γ反映了支持向量的點(diǎn)之間的相關(guān)程度，γ越大支持向量間的相關(guān)性越強(qiáng)，模型的精度會(huì)相對(duì)降低；γ越小持向量的相關(guān)性越弱，機(jī)器學(xué)習(xí)能力會(huì)減弱，推廣能力變差[6]．懲罰因子C反映了對(duì)錯(cuò)誤樣本的懲罰力度，加大C，錯(cuò)誤樣本數(shù)變少，但機(jī)器可能會(huì)產(chǎn)生過學(xué)習(xí)的情況，模型泛化能力變差；減小C，模型泛化能力變好，但樣本被錯(cuò)分的情況會(huì)增多．

在參數(shù)(C,γ)的選擇方面，現(xiàn)在主流的方法是遺傳算法[7]、粒子群算法[6]等．但這些算法都有其局限性，在SVR尋參過程中，容易出現(xiàn)早熟的現(xiàn)象，且算法本身參數(shù)對(duì)尋參結(jié)果影響較大．

判斷參數(shù)尋優(yōu)好壞，主要需要考慮兩方面的因素：其一是所需時(shí)間問題，所需時(shí)間短則表示算法收斂速度快；其二是預(yù)測(cè)的精度，預(yù)測(cè)精度高則擬合效果好．總體，在SVR的尋參過程中，我們追求的目標(biāo)是所需時(shí)間短，同時(shí)用尋參結(jié)果訓(xùn)練的模型預(yù)測(cè)精度高、誤差?。?/p>

2.2 布谷鳥搜索算法

布谷鳥搜索算法(Cuckoo Search,CS)，是由Yang 和Deb[8]在結(jié)合了布谷鳥的繁殖行為和Lévy飛行的特性后提出的一種新興的啟發(fā)式算法．實(shí)驗(yàn)結(jié)果[9]顯示，布谷鳥搜索算法具有參數(shù)少、全局搜索能力強(qiáng)、搜索路徑優(yōu)和多目標(biāo)求解問題強(qiáng)等優(yōu)點(diǎn)．

布谷鳥是寄生育雛的形式[10]，在產(chǎn)卵期間，會(huì)選擇將其鳥蛋產(chǎn)于相似的鳥類的窩中，讓宿主代為孵化，且每個(gè)寄生巢中只產(chǎn)一枚卵．布谷鳥搜索算法模仿布谷鳥的這種行為，結(jié)合了Lévy飛行搜索機(jī)制，使得算法能有效跳出局部最優(yōu)解[11]．

在模擬布谷鳥的尋窩方式時(shí)，需要假定3個(gè)理想化的狀態(tài)[12]：

(1)一只布谷鳥一次只產(chǎn)一個(gè)卵，并隨機(jī)選取一個(gè)寄生巢來孵化；

(2)在隨機(jī)選取的寄生巢中，最好的寄生巢會(huì)被保留到下一代；

在該算法中，假定每個(gè)寄生巢中有若干個(gè)卵，它們分別代表一種解決方案，而布谷鳥的卵代表一種新的、潛在比較好的解決方案，來代替這個(gè)原有的、可能沒那么好的解決方案．這種情況下，用下面的公式來改進(jìn)寄生巢的質(zhì)量：

(13)

gbest表示當(dāng)前最好的寄生巢[13]．

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

2)計(jì)算每個(gè)寄生巢的目標(biāo)函數(shù)值g(NESTi)，并記錄當(dāng)前最優(yōu)解，即值最小的g(NESTi)；

3)按照式(13)對(duì)其他寄生巢的位置進(jìn)行更新，若這一代中比上代的目標(biāo)函數(shù)值更好，則取代之前的最優(yōu)解，成為新的最優(yōu)解，即根據(jù)Lévy飛行的算法更新NESTi的值，若發(fā)現(xiàn)比當(dāng)前更小的g(NESTi)時(shí)，取代之；

4)過程中設(shè)置一個(gè)隨機(jī)數(shù)random與pa進(jìn)行比較，若random>pa則隨機(jī)改變當(dāng)前寄生巢的位置，得到一組新的位置，即得到一組新的NESTi；

5)若g(NESTi)≤g(Tol)則輸出最優(yōu)解，否則跳回3)繼續(xù)迭代，直至迭代次數(shù)t=T，輸出當(dāng)前g(NESTi).

3 結(jié)果與分析

為了驗(yàn)證上述布谷鳥搜索算法的一般性和有效性，本文做了2個(gè)實(shí)驗(yàn)，其中實(shí)驗(yàn)1是對(duì)網(wǎng)絡(luò)流量進(jìn)行回歸預(yù)測(cè)[14]，實(shí)驗(yàn)2是對(duì)白葡萄酒的質(zhì)量進(jìn)行預(yù)測(cè)．在實(shí)驗(yàn)過程中，采用臺(tái)灣大學(xué)林智仁開發(fā)的Libsvm在matlab的軟件平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)，同時(shí)3種算法的最大迭代次數(shù)均設(shè)置為100次，種群數(shù)量為25，C和γ的取值范圍是(0, 100]，布谷鳥搜索算法中，我們?cè)O(shè)置隨機(jī)變換概率pa為0.25，遺傳算法中交叉率設(shè)為0.4，變異率為0.1，粒子群算法中，局部搜索能力參數(shù)c1初始設(shè)置為1.5，全局搜索能力參數(shù)c2初始設(shè)置為1.7．

3.1 網(wǎng)絡(luò)流量實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)采集于Brandeis大學(xué)校園網(wǎng)的中心路由器于1994年1月20日監(jiān)測(cè)的14:10～16:10內(nèi)的TCP數(shù)據(jù)流量，按1 s為時(shí)間尺度，對(duì)該流量序列進(jìn)行聚類操作，截取其中350 s的流量序列作為實(shí)驗(yàn)數(shù)據(jù)．

我們分別拿遺傳算法、粒子群算法、布谷鳥搜索算法尋優(yōu)的結(jié)果對(duì)SVR模型進(jìn)行訓(xùn)練，并拿回歸預(yù)測(cè)的數(shù)據(jù)與原始數(shù)據(jù)對(duì)比．為了定量地比較不同參數(shù)尋優(yōu)的結(jié)果，定義均方根誤差

和相關(guān)系數(shù)：

大量的混凝土外加劑的試驗(yàn)表明，后摻法比先摻法的混凝土工作性能要好，而且要達(dá)到相同的效果，后摻法的摻量在通常情況下會(huì)更小，這與混凝土外加劑與水泥顆粒的吸附和分散有關(guān)。

表1實(shí)驗(yàn)1中布谷鳥搜索算法與其他算法的均方根誤差和相關(guān)系數(shù)對(duì)比

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相關(guān)系數(shù)0.816 5010.211 0520.998 08 時(shí)間/s10534318

由表1可以看出，布谷鳥搜索算法算法所需時(shí)間大大少于遺傳算法和粒子群算法，在收斂速度方面顯示出了極大的優(yōu)勢(shì)，且通過布谷鳥搜索算法尋找出的參數(shù)訓(xùn)練出的SVR模型，相關(guān)系數(shù)最高，均方誤差最小(即尋參結(jié)果的預(yù)測(cè)精度最高)．同時(shí)不難發(fā)現(xiàn)雖然3種算法選出的參數(shù)差別不是很大，但其均方根誤差和相關(guān)系數(shù)卻有較大的差異，這也證明了尋優(yōu)參數(shù)的好壞對(duì)模型的預(yù)測(cè)精度有很大的影響．

幾種算法的預(yù)測(cè)數(shù)據(jù)和原始數(shù)據(jù)的對(duì)比見圖2.

3.2 白葡萄酒質(zhì)量預(yù)測(cè)

為了進(jìn)一步驗(yàn)證布谷鳥搜索算法的有效性，選取了UCI數(shù)據(jù)集中的Wine Quality數(shù)據(jù)集(其規(guī)模為4 898*12)進(jìn)行測(cè)試，與網(wǎng)絡(luò)流量不同的是，這是一個(gè)多變量的預(yù)測(cè)問題．我們截取數(shù)據(jù)集的前350項(xiàng)作為實(shí)驗(yàn)數(shù)據(jù)．實(shí)驗(yàn)中，將葡萄酒的得分作為因變量，其他的11項(xiàng)測(cè)量指標(biāo)(如酒的pH值、固定酸度等)作為自變量．實(shí)驗(yàn)步驟和參數(shù)設(shè)置與實(shí)驗(yàn)1相同．

各算法的對(duì)比見表2，幾種算法的預(yù)測(cè)數(shù)據(jù)和原始數(shù)據(jù)的對(duì)比見圖3.

對(duì)比實(shí)驗(yàn)1和實(shí)驗(yàn)2，不難發(fā)現(xiàn)，隨著自變量維數(shù)的增加，計(jì)算量也隨之增大，運(yùn)行各算法所需的時(shí)間幾乎成倍增加，這說明數(shù)據(jù)量越大，布谷鳥搜索算法的優(yōu)勢(shì)越明顯．在單變量和多變量的預(yù)測(cè)問題中，布谷鳥搜索算法都有較好的性能，遺傳算法次之，而粒子群算法收斂速度慢，預(yù)測(cè)精度不高．

造成這一現(xiàn)象的主要原因是，SVR的參數(shù)尋優(yōu)過程是一個(gè)多峰問題，遺傳算法有交叉和變異的操作，這使其有可能跳出局部最優(yōu)解，逐漸向全局最優(yōu)解靠近，粒子群算法在收斂時(shí)粒子位置和速度的調(diào)整都過多依賴于當(dāng)前最優(yōu)粒子，這導(dǎo)致算法的早熟，而布谷鳥搜索算法由于引入了Lévy飛行搜索機(jī)制，相對(duì)前2種算法更容易跳出局部最優(yōu)解而獲得全局最優(yōu)解．同時(shí)，它在局部搜索策略和全局搜索空間的探索之間有更好的平衡性，提高了算法的效率．另外，值得一提的是布谷鳥搜索算法自身的控制參數(shù)少，相對(duì)更加穩(wěn)定，通用性更強(qiáng)[12]．

表2實(shí)驗(yàn)2中布谷鳥搜索算法與其他算法的均方根誤差和相關(guān)系數(shù)對(duì)比

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相關(guān)系數(shù)0.570 1250.433 339 0.936 959時(shí)間/s20265340

圖2 實(shí)驗(yàn)1中原始數(shù)據(jù)和回歸數(shù)據(jù)的對(duì)比

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

針對(duì)實(shí)驗(yàn)1的網(wǎng)絡(luò)流量預(yù)測(cè)，另外取0.5 s、5 s、10 s作為新的時(shí)間尺度進(jìn)行了預(yù)測(cè)，發(fā)現(xiàn)隨著時(shí)間尺度的增大，均方根誤差的平均值呈減少趨勢(shì)，這說明時(shí)間尺度越大，預(yù)測(cè)的精度越高．這一現(xiàn)象是由布谷鳥搜索算法的不足引起的，它不能很好地適應(yīng)數(shù)據(jù)激變的情況，對(duì)于變化率過大的數(shù)據(jù)，難以達(dá)到很好的擬合效果．故隨著時(shí)間尺度的加大，網(wǎng)絡(luò)數(shù)據(jù)會(huì)相對(duì)平滑，預(yù)測(cè)精度也會(huì)隨之升高．在進(jìn)行網(wǎng)絡(luò)流量預(yù)測(cè)時(shí)，如何平衡預(yù)測(cè)的實(shí)時(shí)性和結(jié)果的準(zhǔn)確性，仍需要進(jìn)一步研究．

圖3 實(shí)驗(yàn)2中原始數(shù)據(jù)和回歸數(shù)據(jù)的對(duì)比

4 結(jié)論

對(duì)網(wǎng)絡(luò)流量的預(yù)測(cè)能為建立自主計(jì)算機(jī)系統(tǒng)的負(fù)載預(yù)測(cè)和評(píng)估模型奠定基礎(chǔ)[3]，同時(shí)在網(wǎng)絡(luò)安全和管理上也有重要的意義．本文充分利用SVR在解決非線性問題時(shí)的優(yōu)勢(shì)，將其用于網(wǎng)絡(luò)流量的預(yù)測(cè)，并針對(duì)遺傳算法、粒子群算法在SVR參數(shù)尋優(yōu)過程中的不足，提出了基于布谷鳥搜索算法的改進(jìn)方法，使得該預(yù)測(cè)模型可以自動(dòng)根據(jù)輸入的自變量、因變量對(duì)參數(shù)進(jìn)行選擇，與傳統(tǒng)方法相比，在性能上有較大提升，為SVR的參數(shù)選擇提供了一條新的途徑．

參考文獻(xiàn)：

[1] 張冉, 趙成龍. ARIMA 模型在網(wǎng)絡(luò)流量預(yù)測(cè)中的應(yīng)用研究[J]. 計(jì)算機(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] 羅淵. 基于自學(xué)習(xí)調(diào)整 Web 服務(wù)端點(diǎn)行為策略的問題研究[D]. 廣州:廣東工業(yè)大學(xué), 2013.

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

[3] 廖備水, 李石堅(jiān), 姚遠(yuǎn), 等. 自主計(jì)算概念模型與實(shí)現(xiàn)方法[J]. 軟件學(xué)報(bào),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, 克里斯蒂亞尼尼, 肖-泰勒, 等. 支持向量機(jī)導(dǎo)論[M]. 北京:電子工業(yè)出版社, 2004.

[5] 白茹, 滕奇志, 楊曉敏, 等. 基于 SVM 和 GA 的藥物與人血清白蛋白結(jié)合的預(yù)測(cè)[J]. 計(jì)算機(jī)工程與應(yīng)用, 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參數(shù)選擇及其應(yīng)用[J]. 自動(dòng)化與儀表,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] 劉勝,李妍妍. 自適應(yīng)GA-SVM參數(shù)選擇算法研究[J]. 哈爾濱工程大學(xué)學(xué)報(bào), 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] 李煜,馬良. 新型元啟發(fā)式布谷鳥搜索算法[J]. 系統(tǒng)工程, 2012,30(8):64-69.

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

[13] 柳新妮,馬苗. 布谷鳥搜索算法在多閾值圖像分割中的應(yīng)用[J]. 計(jì)算機(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] 姜明,吳春明,張旻,等. 網(wǎng)絡(luò)流量預(yù)測(cè)中的時(shí)間序列模型比較研究[J]. 電子學(xué)報(bào),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.