基于人工蜂群優(yōu)化的支持向量機(jī)模型在Web服務(wù)QoS預(yù)測(cè)中的應(yīng)用

安吉宇　楊　瑜　劉志中

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　河南 焦作 454000)

?

基于人工蜂群優(yōu)化的支持向量機(jī)模型在Web服務(wù)QoS預(yù)測(cè)中的應(yīng)用

安吉宇楊瑜劉志中

(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院河南 焦作 454000)

摘要在開(kāi)放的網(wǎng)絡(luò)環(huán)境下，Web服務(wù)的服務(wù)質(zhì)量QoS具有很強(qiáng)的動(dòng)態(tài)性。為了提高服務(wù)QoS的準(zhǔn)確性，為服務(wù)選擇、服務(wù)組合提供可靠的QoS信息，在考慮Web服務(wù)所處的網(wǎng)絡(luò)環(huán)境和所要處理任務(wù)的特征對(duì)服務(wù)QoS影響的前提下，提出一種基于人工蜂群優(yōu)化的支持向量機(jī)QoS動(dòng)態(tài)預(yù)測(cè)方法。該方法首先對(duì)人工蜂群算法進(jìn)行改進(jìn)，提出了面向觀察蜂的免疫選擇機(jī)制和面向偵查蜂的改進(jìn)逃逸機(jī)制；然后，采用改進(jìn)的人工蜂群算法對(duì)支持向量機(jī)的參數(shù)進(jìn)行優(yōu)化；最后采用優(yōu)化的支持向量機(jī)預(yù)測(cè)Web服務(wù)處理具體任務(wù)時(shí)的QoS。實(shí)驗(yàn)結(jié)果表明，該提出的QoS預(yù)測(cè)方法具有較好的預(yù)測(cè)速度和精度。

關(guān)鍵詞改進(jìn)人工蜂群算法支持向量機(jī)Web服務(wù)服務(wù)質(zhì)量動(dòng)態(tài)預(yù)測(cè)

0引言

隨著云計(jì)算、物聯(lián)網(wǎng)、虛擬化、面向服務(wù)、高性能計(jì)算等高新信息技術(shù)的快速發(fā)展，網(wǎng)絡(luò)中涌現(xiàn)了很多功能相似或相同但QoS具有很大差異的Web服務(wù)，QoS已經(jīng)成為評(píng)價(jià)和選擇最佳候選服務(wù)的重要依據(jù)。由于Web服務(wù)運(yùn)行環(huán)境的開(kāi)放性、用戶任務(wù)的不確定性、服務(wù)負(fù)載的波動(dòng)性等不確定因素，使得Web服務(wù)的QoS具有很強(qiáng)的動(dòng)態(tài)性[1]。如何準(zhǔn)確地預(yù)測(cè)Web服務(wù)的QoS，為服務(wù)選擇、服務(wù)組合提供可靠的QoS數(shù)據(jù)，成為服務(wù)計(jì)算領(lǐng)域亟需解決的關(guān)鍵問(wèn)題。

目前，國(guó)內(nèi)外學(xué)者針對(duì)Web服務(wù)的QoS預(yù)測(cè)問(wèn)題展開(kāi)了初步的研究，并取得了一定的研究成果。Shao等人[2]在2007年最早提出使用協(xié)同過(guò)濾法對(duì)用戶未使用過(guò)的Web服務(wù)的QoS進(jìn)行預(yù)測(cè)。在此基礎(chǔ)上，紹凌霜等人[3]對(duì)協(xié)同過(guò)濾方法進(jìn)行了改進(jìn)，提出了基于歐幾里德距離的相似度計(jì)算公式，并給出了一種綜合考慮用戶相似度和服務(wù)相似度的QoS預(yù)測(cè)方法。為了提高目標(biāo)服務(wù)QoS的準(zhǔn)確度，Zheng等人[4]提出了一種基于混合協(xié)同過(guò)濾方法的QoS預(yù)測(cè)方法。該預(yù)測(cè)方法設(shè)計(jì)了兩種信心權(quán)重，其中一種信心權(quán)重表示對(duì)基于用戶之間相似度得到的QoS預(yù)測(cè)值的信任程度，另一種信心權(quán)重表示對(duì)基于服務(wù)之間相似度得到的QoS預(yù)測(cè)值的信任程度。通過(guò)引入這兩種信心權(quán)重，可以自動(dòng)地調(diào)整QoS預(yù)測(cè)過(guò)程中對(duì)兩種預(yù)測(cè)值的依賴程度，從而提高QoS預(yù)測(cè)的準(zhǔn)確度。

事實(shí)上，由于用戶任務(wù)自身屬性的差異性，以及服務(wù)的執(zhí)行環(huán)境的動(dòng)態(tài)性、公開(kāi)性和多樣化，導(dǎo)致Web服務(wù)的QoS具有很強(qiáng)的波動(dòng)性、非線性等特點(diǎn)，難以對(duì)其確立精準(zhǔn)的線性預(yù)測(cè)模型。文獻(xiàn)[5]提出了一種支持QoS動(dòng)態(tài)預(yù)測(cè)的多Agent QoS預(yù)測(cè)模型，采用SOM神經(jīng)網(wǎng)絡(luò)對(duì)Web服務(wù)QoS進(jìn)行非線性學(xué)習(xí)和動(dòng)態(tài)預(yù)測(cè)，在一定程度上提高了模型的靈活性。但神經(jīng)網(wǎng)絡(luò)存在著過(guò)學(xué)習(xí)和局部極小值的缺陷，導(dǎo)致預(yù)測(cè)精度不高。文獻(xiàn)[6]從服務(wù)自身和運(yùn)行環(huán)境出發(fā)，考慮任務(wù)類型、任務(wù)量、服務(wù)器負(fù)載和網(wǎng)絡(luò)傳輸速率對(duì)Web服務(wù)QoS的影響，使用事例推理CBR(Case-based reasoning)方法對(duì)Web服務(wù)QoS進(jìn)行動(dòng)態(tài)預(yù)測(cè)，該方法不需要復(fù)雜的計(jì)算過(guò)程，但對(duì)事例庫(kù)的規(guī)模具有一定的依賴性，且對(duì)事例庫(kù)更新規(guī)則的定義仍不夠完善。

為了更好地描述Web服務(wù)QoS與其影響因素之間復(fù)雜的非線性關(guān)系，進(jìn)一步提高Web服務(wù)QoS預(yù)測(cè)的精度，構(gòu)建了基于改進(jìn)人工蜂群算法I-ABC(Improved artificial bee colony)優(yōu)化支持向量機(jī)SVM的Web服務(wù)QoS動(dòng)態(tài)預(yù)測(cè)方法，該方法首先使用I-ABC對(duì)SVM參數(shù)進(jìn)行優(yōu)化，然后采用優(yōu)化的參數(shù)建立SVM預(yù)測(cè)模型并對(duì)Web服務(wù)QoS進(jìn)行預(yù)測(cè)。實(shí)驗(yàn)結(jié)果表明，本文的改進(jìn)方案在提高SVM參數(shù)尋優(yōu)速度和精度的基礎(chǔ)上，取得了較好的QoS預(yù)測(cè)效果。

1改進(jìn)的人工蜂群算法

人工蜂群算法[7]ABC(Artificial bee colony)是由Karaboga D提出的一種模擬蜜蜂群體覓食行為的智能優(yōu)化算法。算法不需要復(fù)雜的操作過(guò)程且具有很好的魯棒性，并在優(yōu)化復(fù)雜高維多峰函數(shù)方面比遺傳算法、粒子群算法具有更優(yōu)的性能[8]。目前，人工蜂群算法已廣泛用于解決各類優(yōu)化問(wèn)題，如信號(hào)處理[9]、多目標(biāo)優(yōu)化[10]及函數(shù)數(shù)值優(yōu)化[11]等。然而作為一種新興的智能算法，傳統(tǒng)ABC存在著進(jìn)化速度緩慢、過(guò)早收斂、易陷入局部最優(yōu)等問(wèn)題。

ABC算法中，蜜蜂種群中的個(gè)體分為雇傭蜂、觀察蜂和偵查蜂三種類型，并依靠三個(gè)蜂種間的相互協(xié)作使算法朝著最優(yōu)方向進(jìn)化。傳統(tǒng)蜂群算法中，有以下兩個(gè)原因?qū)е滤惴ㄈ菀紫萑刖植孔顑?yōu)[8,12]：

(a) 觀察蜂選擇食物源時(shí)采用輪盤(pán)賭機(jī)制。在這種機(jī)制中，適應(yīng)度越高的食物源被選中的概率越大，這有助于提高算法的收斂性，但適應(yīng)度較差的食物源幾乎得不到更新，破壞了種群的多樣性；同時(shí)隨著算法的進(jìn)化，食物源的適應(yīng)度趨于一致會(huì)導(dǎo)致各食物源吸引到觀察蜂的概率接近，造成算法的進(jìn)化停滯，導(dǎo)致算法陷入局部最優(yōu)；

(b) 偵查蜂在發(fā)現(xiàn)和更新可能導(dǎo)致算法過(guò)早收斂的個(gè)體時(shí)，存在以下缺陷：偵查蜂個(gè)體選擇主要依賴于參數(shù)limit，而在不同應(yīng)用環(huán)境中的limit值具有很大的差異性，導(dǎo)致算法的通用性低；僅根據(jù)個(gè)體的更新次數(shù)來(lái)確定導(dǎo)致算法早熟的個(gè)體，忽略了個(gè)體位置對(duì)種群多樣性的影響，存在片面性；逃逸算子式在一定的范圍內(nèi)隨機(jī)產(chǎn)生新個(gè)體，不確定的逃逸尺度造成了逃逸操作的盲目性，導(dǎo)致算法的尋優(yōu)精度降低，收斂速度緩慢。

鑒于以上觀察蜂選擇食物源機(jī)制和偵查蜂逃逸行為的不足，本文在平衡種群收斂性和多樣性的基礎(chǔ)上，通過(guò)借鑒文獻(xiàn)[8]與文獻(xiàn)[12]的研究思路，提出了面向觀察蜂的免疫選擇機(jī)制與面向偵查蜂的逃逸機(jī)制，形成了改進(jìn)的人工蜂群算法(I-ABC)。

設(shè)求解的優(yōu)化問(wèn)題為D維，I-ABC首先需要對(duì)群體進(jìn)行初始化，即采用隨機(jī)的方式生成SN個(gè)初始解(SN代表雇傭蜂或觀察蜂的數(shù)目)。每個(gè)解xi(i=1,2,…,SN)是一個(gè)D維向量，相應(yīng)于第i個(gè)食物源，其食物源質(zhì)量為Fiti(即適應(yīng)度)。初始化結(jié)束后，雇傭蜂、觀察蜂和偵查蜂分別進(jìn)行循環(huán)搜索，求解具有最優(yōu)適應(yīng)度的食物源。I-ABC搜索過(guò)程如下：

(1) 雇傭蜂搜索機(jī)制

I-ABC中，雇傭蜂仍采取原有的搜索機(jī)制。雇傭蜂在種群中每個(gè)食物源位置附近按照下式搜索新的食物源：

vij=xij+φij(xij-xkj)

(1)

式中，j∈{1,2,…,D}，k∈{1,2,…,SN}，k和j都是隨機(jī)選取，且k≠i，φij為[-1,1]間的隨機(jī)數(shù)。xij為食物源xi的第j維分量，xkj為隨機(jī)選擇食物源xk的第j維分量。

當(dāng)產(chǎn)生的新食物源質(zhì)量相對(duì)于原食物源沒(méi)有得到提升時(shí)，則保持舊食物源位置不變，并對(duì)食物源個(gè)體xi未更新的次數(shù)triali進(jìn)行記錄：

(2)

(2) 觀察蜂的免疫選擇機(jī)制

I-ABC中，觀察蜂選取食物源的概率由適應(yīng)度比例式(4)和每個(gè)食物源對(duì)應(yīng)的抗體濃度式(5)共同決定。每一處食物源對(duì)應(yīng)某一抗體，則雇傭蜂所提供食物源訊息xi被觀察蜂重用的幾率如下：

Pi=αPfi+(1-α)Pai

(3)

(4)

式中，α為常數(shù)且α∈(0,1]，Pai為抗體濃度決定的選擇概率，如式(5)所示，實(shí)現(xiàn)了高濃度的抗體選擇幾率小，低濃度的抗體選擇幾率大。

(5)

式中，k為常數(shù)且k∈(0,1]，Cxi為抗體xi的濃度，表示為：

(6)

式中，axij表示抗體xi和xj之間的親和度，TH表示確定的閾值。axij如下式表示：

(7)

式中，ED表示抗體xi和xj之間的Euclid距離。

觀察蜂的免疫選擇機(jī)制中，當(dāng)多個(gè)食物源具有相同的適應(yīng)度時(shí)，食物源對(duì)應(yīng)的抗體濃度越大，則被選擇的概率越小，反之，食物源被選擇的概率越大；當(dāng)食物源對(duì)應(yīng)的抗體濃度相同時(shí)，具有較高適應(yīng)度的食物源被選擇的概率則較大。這樣，在保留了具有高適應(yīng)度的食物源的同時(shí)，維持了種群的多樣性，增加了算法獲得全局最優(yōu)解的可能性，避免算法過(guò)早收斂。

(3) 偵查蜂逃逸行為的改進(jìn)

I-ABC中，為了消除偵查蜂個(gè)體選擇對(duì)參數(shù)limit的依賴性，采用輪賭法的方式選擇偵查蜂個(gè)體，個(gè)體xi被選擇的概率為：

(8)

式中，Espi表示蜂群個(gè)體xi的逃逸指標(biāo)，主要受以下兩個(gè)要素的綜合制約：個(gè)體未更新次數(shù)、個(gè)體位置對(duì)種群多樣性影響程度；其中，(Espi)max與(Espi)min分別表示屬性Espi的最大值及最小值。

Espi=triali-disi

(9)

式中，disi表示個(gè)體xi位置對(duì)種群多樣性的影響程度，表示如下：

(10)

式中，aveFit表示種群中個(gè)體適應(yīng)度的平均值。式(10)采用個(gè)體xi的適應(yīng)度與種群平均適應(yīng)度的偏離程度來(lái)判定xi位置對(duì)種群多樣性變化的影響。

在基于上述選擇機(jī)制確定目標(biāo)偵查蜂后，需要對(duì)相應(yīng)的食物源進(jìn)行更新操作。為了克服傳統(tǒng)ABC中偵查蜂逃逸操作的盲目性，在有效控制逃逸尺度的基礎(chǔ)上，設(shè)定了改進(jìn)的逃逸算子式：

(11)

(12)

從式(9)和式(10)可以發(fā)現(xiàn)，設(shè)定的逃逸指標(biāo)全面衡量了個(gè)體位置對(duì)算法過(guò)早收斂的影響程度；式(8)中采用自適應(yīng)選擇機(jī)制來(lái)確定偵查蜂個(gè)體，使偵查蜂不再受參數(shù)的控制；式(11)設(shè)計(jì)了變尺度的逃逸算子，使算法初期進(jìn)行大尺度的逃逸，后期的逃逸尺度逐漸減小，在兼顧種群多樣性的同時(shí)，加強(qiáng)了算法后期的深度尋優(yōu)性能。

2基于I-ABC優(yōu)化的SVM模型

2.1SVM的參數(shù)優(yōu)化

支持向量機(jī)是通過(guò)尋求結(jié)構(gòu)風(fēng)險(xiǎn)最小化來(lái)最小化實(shí)際風(fēng)險(xiǎn)的機(jī)器學(xué)習(xí)方法，主要目標(biāo)是在有限信息的條件下得到最優(yōu)結(jié)果，能夠較好地解決小樣本、非線性、高維數(shù)以及局部極小值問(wèn)題，并具有很好的泛化性能[13]。

支持向量機(jī)回歸主要是通過(guò)非線性映射的方式，將n維輸入空間映射到高維的特征空間(Hilbert空間)；然后在特征空間中構(gòu)造最優(yōu)線性回歸函數(shù)[14]：

y=f(x)=wTφ(x)+b

(13)

式中，w為偏置項(xiàng)，b為閾值，φ(x)表示非線性映射。

根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，支持向量機(jī)實(shí)質(zhì)上就是求解一個(gè)優(yōu)化問(wèn)題[14]：

(14)

(15)

對(duì)式(14)引入Lagrange函數(shù)，可將原問(wèn)題轉(zhuǎn)化為其對(duì)偶形式：

(16)

(17)

式中，k(xi,xj)=φ(xi)·φ(xj)為核函數(shù)。由此可以得到支持向量機(jī)回歸函數(shù)：

(18)

大量的實(shí)驗(yàn)結(jié)果顯示，支持向量機(jī)時(shí)間序列預(yù)測(cè)結(jié)果的精度與嵌入維數(shù)m，懲罰因子c、損失函數(shù)參數(shù)ε、選擇的核函數(shù)以及核函數(shù)參數(shù)σ之間存在一定的關(guān)系，且共同制約著SVM預(yù)測(cè)的準(zhǔn)確率[15]。其中，核函數(shù)是任何一個(gè)滿足Mercer條件的正定函數(shù)，合適的核函數(shù)可以很好地避免維數(shù)災(zāi)難，是提高預(yù)測(cè)準(zhǔn)確度的關(guān)鍵。c控制著經(jīng)驗(yàn)風(fēng)險(xiǎn)和VC維之間的平衡。ε用來(lái)確定誤差的邊界。σ主要體現(xiàn)SVM對(duì)輸入變量的敏感程度，σ值過(guò)大或過(guò)小都會(huì)對(duì)SVM性能產(chǎn)生負(fù)面影響，導(dǎo)致學(xué)習(xí)效率和預(yù)測(cè)質(zhì)量的下降[16]。

因此，為了保證SVM的學(xué)習(xí)能力和推廣能力，需要選用高效的優(yōu)化算法在一定的先驗(yàn)區(qū)間內(nèi)搜索出支持向量機(jī)各參數(shù)的最優(yōu)組合，進(jìn)而獲取具有高預(yù)測(cè)性能的支持向量機(jī)。

支持向量機(jī)核函數(shù)主要有四種，即多項(xiàng)式核函數(shù)、Sigmoid核函數(shù)、徑向基核函數(shù)和q次多項(xiàng)式核函數(shù)[17]，本文選取當(dāng)前應(yīng)用最廣泛的徑向基核函數(shù)。同時(shí)，由文獻(xiàn)[18]可知，對(duì)于選擇的參數(shù)ε總是可以找到最佳的(c,σ)組合，并且這種組合對(duì)參數(shù)ε具有魯棒性。本文在確定ε的情況下，使用I-ABC對(duì)參數(shù)組合(c,σ)進(jìn)行參數(shù)尋優(yōu)。

2.2基于I-ABC的支持向量機(jī)參數(shù)優(yōu)化算法

將I-ABC算法用于支持向量機(jī)參數(shù)優(yōu)化過(guò)程中，其中采用(c,σ)來(lái)表示食物源位置，位置(c,σ)相應(yīng)的適應(yīng)度Fiti表示在取該參數(shù)對(duì)時(shí)算法的整體性能。計(jì)算適應(yīng)度時(shí)，需要對(duì)相應(yīng)的食物源使用SVM模型利用訓(xùn)練集進(jìn)行訓(xùn)練，并由訓(xùn)練好的模型對(duì)測(cè)試集的數(shù)據(jù)進(jìn)行測(cè)試，測(cè)試所得到的性能評(píng)價(jià)即為食物源對(duì)應(yīng)的適應(yīng)度[19]。此處定義I-ABC算法的適應(yīng)度函數(shù)為模型在測(cè)試數(shù)據(jù)集上的回歸準(zhǔn)確率，表示為：

(19)

Algorithm1基于I-ABC的支持向量機(jī)參數(shù)優(yōu)化算法

輸入支持向量機(jī)訓(xùn)練集數(shù)據(jù)

輸出最優(yōu)參數(shù)對(duì)(c,σ)

Step1相關(guān)參數(shù)的設(shè)定

首先，需要對(duì)I-ABC中的控制參數(shù)進(jìn)行初始化，在多次試驗(yàn)后，I-ABC中參數(shù)設(shè)定規(guī)則如下：食物源數(shù)量SN=20，最大進(jìn)化代數(shù)G=75，D為優(yōu)化參數(shù)的個(gè)數(shù)，設(shè)為2。然后，初始化模型參數(shù)c和σ的搜索范圍，設(shè)定為[0.1,1000]。

Step2初始食物源生成

采用隨機(jī)的方式產(chǎn)生SN個(gè)食物源，并分配蜂群；然后依據(jù)適應(yīng)度函數(shù)Fiti對(duì)每個(gè)食物源進(jìn)行評(píng)價(jià)；

Step3雇傭蜂階段

雇傭蜂按照式(1)搜索新的食物源并對(duì)其適應(yīng)度進(jìn)行評(píng)價(jià)；若新食物源適應(yīng)度優(yōu)于當(dāng)前食物源則保存，反之則放棄，并記錄其未更新次數(shù)triali。

Step4觀察蜂階段

觀察蜂根據(jù)式(3)所得的概率，采用輪盤(pán)賭方法選取食物源；然后依據(jù)式(1)生成新的食物源，并根據(jù)新食物源的適應(yīng)度通過(guò)貪婪機(jī)制保留最優(yōu)食物源。

Step5偵查蜂階段

按照式(8)所定義的逃逸指標(biāo)，采用輪盤(pán)賭方式來(lái)選擇偵查蜂個(gè)體，并使用逃逸算子式(11)對(duì)偵查蜂對(duì)應(yīng)的食物源進(jìn)行更新；同時(shí)計(jì)算出新食物源的適應(yīng)度，且需判斷是否更新triali。

Step6更新全局最優(yōu)解

對(duì)具有全局最優(yōu)適應(yīng)度的食物源進(jìn)行記錄。

Step7結(jié)束條件判定

若算法達(dá)到最大進(jìn)化代數(shù)則停止迭代，此時(shí)得到的全局最優(yōu)解為最終SVM模型的參數(shù)。否則轉(zhuǎn)Step3。

3基于優(yōu)化SVM的QoS預(yù)測(cè)方法

采用I-ABC得到SVM的最優(yōu)參數(shù)后，需要采用優(yōu)化的參數(shù)建立SVM預(yù)測(cè)模型，并將預(yù)測(cè)模型應(yīng)用到Web服務(wù)QoS預(yù)測(cè)中。其中，定義Web服務(wù)QoS的影響因素為：QoS_influence_factors = 。基于優(yōu)化SVM的Web服務(wù)QoS預(yù)測(cè)算法描述如下：

Algorithm2基于優(yōu)化SVM的Web服務(wù)QoS預(yù)測(cè)算法

輸入{pf1,pf2,…,pfn}

// QoS_influence_factors

輸出Web服務(wù)QoS預(yù)測(cè)值qf

Step1訓(xùn)練樣本的構(gòu)建

Step2數(shù)據(jù)預(yù)處理

由于各影響因子量綱的差異性，為了提高SVM的泛化能力和減少訓(xùn)練時(shí)間，建模之前需要對(duì)樣本數(shù)據(jù)進(jìn)行歸一化處理，將其范圍控制在區(qū)間[0,1]。歸一化公式為：

(20)

Step3參數(shù)優(yōu)化

采用改進(jìn)的蜂群算法在先驗(yàn)區(qū)間內(nèi)選擇最優(yōu)的參數(shù)對(duì)(c,σ)。

Step4建立預(yù)測(cè)模型

使用優(yōu)選的參數(shù)對(duì)Step1中構(gòu)造的訓(xùn)練樣本進(jìn)行學(xué)習(xí)，獲得形如式(18)的決策函數(shù)，建立Web服務(wù)QoS預(yù)測(cè)模型。

Step5QoS預(yù)測(cè)

根據(jù)Step4建立的預(yù)測(cè)模型，利用預(yù)測(cè)樣本完成對(duì)tf時(shí)刻Web服務(wù)QoS的預(yù)測(cè)，并輸出預(yù)測(cè)結(jié)果。

4實(shí)驗(yàn)分析

4.1實(shí)驗(yàn)設(shè)計(jì)

為了對(duì)上文所提QoS動(dòng)態(tài)預(yù)測(cè)方法的有效性進(jìn)行測(cè)試，開(kāi)發(fā)了模仿實(shí)際環(huán)境中客戶端對(duì)Web服務(wù)調(diào)用的實(shí)驗(yàn)環(huán)境。其中，Web服務(wù)類型分為兩種：Task A為上傳文件操作，Task B為下載文件操作，相應(yīng)的執(zhí)行次數(shù)代表任務(wù)的量。實(shí)驗(yàn)過(guò)程中，客戶端采用隨機(jī)的方法生成任務(wù)，其中，任務(wù)類型在Task A和Task B中隨機(jī)生成，并在[500,2000]內(nèi)隨機(jī)生成任務(wù)量的大小，然后將任務(wù)隨機(jī)地提交給Web服務(wù)進(jìn)行處理。考慮到實(shí)際中Web服務(wù)運(yùn)行環(huán)境的波動(dòng)性，服務(wù)器通過(guò)定期隨機(jī)的產(chǎn)生背景任務(wù)量，來(lái)控制Web服務(wù)負(fù)載的變化。

實(shí)驗(yàn)過(guò)程中，每當(dāng)生成一個(gè)新的任務(wù)請(qǐng)求時(shí)，記錄任務(wù)的類型和任務(wù)量，并記錄任務(wù)提交時(shí)間Tsub和任務(wù)處理完成時(shí)間Tcomplete，則任務(wù)處理時(shí)間為T(mén)complete-Tsub，任務(wù)處理時(shí)間即為任務(wù)反應(yīng)時(shí)間。在任務(wù)執(zhí)行過(guò)程中，每5 s記錄一次Web服務(wù)所在服務(wù)器的CPU負(fù)載(CPU利用率)，每處理完一個(gè)任務(wù)，用該任務(wù)處理期間CPU負(fù)載的平均值作為服務(wù)處理該任務(wù)時(shí)的CPU負(fù)載。任務(wù)處理完成后，根據(jù)任務(wù)執(zhí)行時(shí)的Web服務(wù)負(fù)載、任務(wù)類型、任務(wù)量和反應(yīng)時(shí)間，構(gòu)成SVM格式的QoS數(shù)據(jù)樣本：，其中，QoS_influence_factors = 為輸入向量，反應(yīng)時(shí)間為輸出。實(shí)驗(yàn)共收集QoS數(shù)據(jù)896個(gè)，數(shù)據(jù)涵蓋了在不同的負(fù)載狀況下，Web服務(wù)處理不同類型任務(wù)的情況。實(shí)驗(yàn)中只對(duì)Web服務(wù)反應(yīng)時(shí)間這一QoS屬性進(jìn)行預(yù)測(cè)，其他QoS屬性值的預(yù)測(cè)方法相同。實(shí)驗(yàn)基于Libsvm工具箱。

4.2實(shí)驗(yàn)分析

4.2.1基于不同智能優(yōu)化算法的預(yù)測(cè)結(jié)果比較

為了評(píng)估改進(jìn)算法的收斂速度和精度，本文同時(shí)實(shí)現(xiàn)了I-ABC優(yōu)化的SVM (I-ABC_SVM)和現(xiàn)有的一些智能算法優(yōu)化的SVM對(duì)Web服務(wù)QoS進(jìn)行預(yù)測(cè)，如粒子群算法優(yōu)化的SVM[20](PSO_SVM)、遺傳算法優(yōu)化的SVM[15](GA_SVM)以及標(biāo)準(zhǔn)的蜂群算法優(yōu)化的SVM[21](ABC_SVM)，并對(duì)它們的預(yù)測(cè)性能進(jìn)行了比較。

實(shí)驗(yàn)中，從獲取的數(shù)據(jù)集中取前100個(gè)QoS數(shù)據(jù)用作訓(xùn)練集，同時(shí)從剩余的數(shù)據(jù)中隨機(jī)取4組數(shù)據(jù)用作測(cè)試集，并采用智能算法優(yōu)化的SVM對(duì)其QoS進(jìn)行預(yù)測(cè)。由于實(shí)驗(yàn)中使用的優(yōu)化算法都屬于啟發(fā)式算法，它們對(duì)數(shù)據(jù)進(jìn)行多次尋優(yōu)預(yù)測(cè)的結(jié)果會(huì)出現(xiàn)不同值，因此對(duì)每組數(shù)據(jù)作5次試驗(yàn)，并對(duì)預(yù)測(cè)準(zhǔn)確率和預(yù)測(cè)時(shí)間分別取平均值，實(shí)驗(yàn)結(jié)果如表1、表2所示。

表1　基于不同智能算法優(yōu)化的SVM預(yù)測(cè)準(zhǔn)確率比較

表2　基于不同智能算法優(yōu)化的SVM預(yù)測(cè)時(shí)間比較

從表1和表2可以看出，本文所提算法得到的預(yù)測(cè)模型，可以得到較高的預(yù)測(cè)準(zhǔn)確率。本方法在參數(shù)尋優(yōu)時(shí)不僅能夠搜索到全局最優(yōu)解，而且具有較高的尋優(yōu)效率，通過(guò)減少參數(shù)的尋優(yōu)時(shí)間，從而大大減少了整個(gè)模型的預(yù)測(cè)時(shí)間，能夠很好地滿足即時(shí)預(yù)測(cè)中對(duì)預(yù)測(cè)時(shí)間的高要求。

圖1為本實(shí)驗(yàn)運(yùn)用不同智能算法優(yōu)化的SVM預(yù)測(cè)進(jìn)化圖。從圖1可以看出，相較于傳統(tǒng)ABC方法，I-ABC由于引入了觀察蜂在選擇食物源時(shí)的免疫系統(tǒng)抗體濃度調(diào)節(jié)機(jī)制和改進(jìn)的偵查蜂逃逸方式，有效地逃離了早熟收斂，并加快了算法的收斂速度。與其他智能優(yōu)化算法相比，I-ABC僅需要更少的進(jìn)化代數(shù)就能達(dá)到比其他算法更好的預(yù)測(cè)精度，表現(xiàn)出更快的全局收斂速度(用進(jìn)化代數(shù)表示)和更好的全局搜索能力。而PSO算法和GA算法在進(jìn)化過(guò)程中收斂速度緩慢，且在實(shí)驗(yàn)中由于未尋得最優(yōu)數(shù)據(jù)而導(dǎo)致預(yù)測(cè)準(zhǔn)確率較低。

圖1　基于不同智能算法優(yōu)化SVM的Web服務(wù)QoS預(yù)測(cè)進(jìn)化圖

4.2.2本文預(yù)測(cè)方法與基于CBR預(yù)測(cè)方法的比較

即時(shí)預(yù)測(cè)中，對(duì)預(yù)測(cè)過(guò)程執(zhí)行時(shí)間和數(shù)據(jù)存取速度都具有較高的要求。為了驗(yàn)證本文即時(shí)預(yù)測(cè)方法的性能，在歷史數(shù)據(jù)數(shù)目不同的情況下，分別采用CBR和I-ABC_SVM方法對(duì)一組QoS數(shù)據(jù)進(jìn)行預(yù)測(cè)。實(shí)驗(yàn)結(jié)果如圖2所示。

圖2　不同歷史數(shù)據(jù)數(shù)目情況下CBR和I-ABC_SVM方法預(yù)測(cè)準(zhǔn)確率比較

從圖2中可以看出，隨著歷史事例數(shù)目的增加，CBR方法的預(yù)測(cè)準(zhǔn)確率呈上升趨勢(shì)，但上升速度緩慢且相較于I-ABC_SVM方法整體預(yù)測(cè)準(zhǔn)確率較低，主要原因是CBR方法對(duì)事例庫(kù)規(guī)模有一定依賴性，當(dāng)歷史數(shù)目比較少時(shí)，由于獲取的有用信息有限，導(dǎo)致預(yù)測(cè)準(zhǔn)確率低；隨著歷史數(shù)目的增多，獲取的數(shù)據(jù)能夠包含更多的有用信息，從而可以通過(guò)對(duì)預(yù)測(cè)數(shù)據(jù)進(jìn)行更好的指導(dǎo)來(lái)提高預(yù)測(cè)準(zhǔn)確率。實(shí)驗(yàn)中，由于事例庫(kù)沒(méi)有涵蓋預(yù)測(cè)所需的有效信息導(dǎo)致準(zhǔn)確率較低。

而對(duì)于I-ABC_SVM方法來(lái)說(shuō)，在不同歷史數(shù)據(jù)數(shù)目情況下均達(dá)到了較好的預(yù)測(cè)效果，體現(xiàn)出了在小樣本預(yù)測(cè)方面的優(yōu)良性能；但預(yù)測(cè)準(zhǔn)確率整體呈下降趨勢(shì)，主要是由于當(dāng)歷史數(shù)目過(guò)多時(shí)，I-ABC_SVM會(huì)出現(xiàn)過(guò)擬合現(xiàn)象，從而導(dǎo)致模型推廣能力降低。由此得出，基于小樣本預(yù)測(cè)的I-ABC_SVM可以減少對(duì)歷史數(shù)據(jù)的存儲(chǔ)代價(jià)，從而在即時(shí)預(yù)測(cè)中表現(xiàn)出了一定的優(yōu)勢(shì)。

5結(jié)語(yǔ)

Web服務(wù)QoS預(yù)測(cè)是Web服務(wù)選擇和服務(wù)組合過(guò)程中非常重要的步驟。為了保證Web服務(wù)QoS的精確度，本文設(shè)計(jì)了一種基于改進(jìn)蜂群算法優(yōu)化SVM的Web服務(wù)QoS動(dòng)態(tài)預(yù)測(cè)方法，該方法針對(duì)傳統(tǒng)蜂群算法存在搜索速度慢、過(guò)早收斂、易陷入局部最優(yōu)的缺陷，利用觀察蜂的免疫選擇機(jī)制和偵查蜂的改進(jìn)逃逸機(jī)制來(lái)維持種群多樣性，加快收斂速度和精度。實(shí)驗(yàn)結(jié)果證明，引入I-ABC的SVM不僅具有更好的魯棒性和收斂性，且取得了優(yōu)異的預(yù)測(cè)性能。下一步的工作重點(diǎn)是通過(guò)獲取更多的QoS數(shù)據(jù)集，從而對(duì)CBR和SVM方法在即時(shí)預(yù)測(cè)中的特性做更深入的分析。

參考文獻(xiàn)

[1] 張淼淼,李決龍,邢建春,等.基于灰色神經(jīng)網(wǎng)絡(luò)的多Agent服務(wù)集成系統(tǒng)服務(wù)質(zhì)量預(yù)測(cè)[J].南京大學(xué)學(xué)報(bào)(自然科學(xué)),2013,49(2):268-277.

[2] Shao Lingshuang,Zhang Jing,Wei Yong,et al.Personalized QoS prediction for Web services via collaborative Filtering[C]//Web Ser-vices,2007.ICWS 2007.IEEE International Conference on.IEEE,2007:439-446.

[3] 邵凌霜,周立,趙俊峰,等.一種Web Service的服務(wù)質(zhì)量預(yù)測(cè)方法[J].軟件學(xué)報(bào),2009,20(8):2062-2072.

[4] Zheng Zibin,Ma Hao,Michael R Lyu,et al.WSRec:A collaborative filtering based Web service recommender system[C]//IEEE International Conference on Web Services,2009:437-444.

[5] Malak J S,Mohsenzadeh M,Seyywdi M.A Web service QoS prediction based on multi agents[C]//International Conference on Computer Technology and Development,2009:265-269.

[6] 劉志中,王志堅(jiān),周曉峰,等.基于事例推理的Web服務(wù)QoS動(dòng)態(tài)預(yù)測(cè)研究[J].計(jì)算機(jī)科學(xué),2011,38(2):119-121,137.

[7] Karaboga D.An idea based on honey bee swarm for numerical optimization,Technical Report-TR06[R].Kayseri: Erciyes University,2005.

[8] 付麗,羅鈞.引入跟蹤搜索和免疫選擇的人工蜂群算法[J].模式識(shí)別與人工智能,2013,26(7):688-694.

[9] Yu Xiangyu,Zhu Zucong.A modified artificial bee colony algorithm with its applications in signal processing[J].International Journal of Computer Applications in Technology,2013,47(2-3):297-303.

[10] Adaryani M R,Karami A.Artificial bee colony algorithm for solving multi-objective optimal power flow problem[J].International Journal of Electrical Power & Energy Systems,2013,53(1):219-130.

[11] Xiang Wanli,An Meiqing.An efficient and robust artificial bee colony algorithm for numerical optimization[J].Computers & Operations Research,2013,40(5):1256-1265.

[12] 葛宇,梁靜,王學(xué)平,等.求解函數(shù)優(yōu)化問(wèn)題的改進(jìn)的人工蜂群算法[J].計(jì)算機(jī)科學(xué),2013,40(8):252-257.

[13] 鄧乃揚(yáng),田英杰.支持向量機(jī)理論、算法與拓展[M].北京:科學(xué)出版社,2009:87-102.

[14] 吳新杰,張丹,許超.基于支持向量機(jī)處理圓度誤差[J].遼寧大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,34(3):204-206.

[15] 張穎璐.基于遺傳算法優(yōu)化支持向量機(jī)的網(wǎng)絡(luò)流量預(yù)測(cè)[J].計(jì)算機(jī)科學(xué),2008,35(5):177-179.

[16] 單黎黎,張宏軍,王杰,等.一種改進(jìn)粒子群算法的混合核ε-SVM參數(shù)優(yōu)化及應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究,2013,30(6):1636-1639.

[17] 苗志剛,付強(qiáng).基于灰色支持向量機(jī)的城市用水量預(yù)測(cè)研究[J].計(jì)算機(jī)仿真,2012,29(8):196-199.

[18] 劉靖旭,蔡懷平,譚躍進(jìn).支持向量回歸參數(shù)調(diào)整的一種啟發(fā)式算法[J].系統(tǒng)仿真學(xué)報(bào),2007,19(7):1540-1543,1547.

[19] 馬元良,裴生雷.基于改進(jìn)遺傳算法的SVM參數(shù)優(yōu)化研究[J].計(jì)算機(jī)仿真,2013,26(7):150-152,193.

[20] 胡云艷,彭敏放,田成來(lái),等.基于粒子群算法優(yōu)化支持向量機(jī)的模擬電路診斷[J].計(jì)算機(jī)應(yīng)用研究,2012,29(11):4053-4055.

[21] 劉路,王太勇.基于人工蜂群算法的支持向量機(jī)優(yōu)化[J].天津大學(xué)學(xué)報(bào),2011,44(9):803-809.

APPLICATION OF SVM MODEL OPTIMISED BY ARTIFICIAL BEE COLONY ALGORITHM IN WEB SERVICE QOS PREDICTION

An JiyuYang YuLiu Zhizhong

(CollegeofComputerSciencesandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

AbstractThe QoS of Web service has a strong dynamism in the open network environment. In order to improve the accuracy of Web service QoS and provide reliable QoS information for service selection and service combination, this paper proposes a dynamic QoS prediction method which is based on the support vector machine (SVM) optimised by artificial bee colony under the premise of taking into consideration the networks environment of the Web service and the effect of the features of the task to be processed on Web service QoS. The method firstly makes the improvement on artificial bee colony algorithm (I-ABC), presents the immune selection mechanism for onlooker bees and the improved escape mechanism for scout bees. Then, it uses the I-ABC to optimise the parameters of SVM. Finally it uses the optimised SVM to predict the QoS of Web service which is processing some specific tasks. Experimental results show that this QoS prediction method can get higher prediction efficiency and accuracy.

KeywordsImproved artificial bee colonySupport vector machineWeb serviceDynamic quality of service prediction

中圖分類號(hào)TP393

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.01.066

收稿日期：2014-06-16。國(guó)家自然科學(xué)基金面上基金項(xiàng)目(6117 5066)；國(guó)家自然科學(xué)基金青年基金項(xiàng)目(61300124)；河南省高校科技創(chuàng)新人才計(jì)劃項(xiàng)目(2011GGJS-056)；河南省理工大學(xué)校博士基金項(xiàng)目；河南理工大學(xué)校創(chuàng)新團(tuán)隊(duì)；河南省教育廳科學(xué)技術(shù)重點(diǎn)研究項(xiàng)目(13B 630034)。安吉宇，副教授，主研領(lǐng)域：服務(wù)建模及流程優(yōu)化。楊瑜，碩士生。劉志中，博士。