云計(jì)算中基于IABC算法的負(fù)載預(yù)測(cè)的研究

史振華

(紹興職業(yè)技術(shù)學(xué)院，浙江紹興 312000)

0 引言

云計(jì)算中資源負(fù)載關(guān)系到云服務(wù)質(zhì)量的高低，通過(guò)預(yù)測(cè)未來(lái)資源負(fù)載能夠有效的提高云計(jì)算的資源調(diào)度效率［1］。由于云計(jì)算資源具有實(shí)時(shí)性，動(dòng)態(tài)性等特點(diǎn)，導(dǎo)致了資源負(fù)載預(yù)測(cè)同樣具有不確定性和非線性［2］等特點(diǎn)，因此，國(guó)外學(xué)者使用很多的方法對(duì)其進(jìn)行研究，文獻(xiàn)［3-6］主要是以靜態(tài)的對(duì)象研究為主，但是無(wú)法達(dá)到很好的預(yù)測(cè)效果。國(guó)內(nèi)學(xué)者在此基礎(chǔ)上進(jìn)行了相應(yīng)的研究，對(duì)一些算法［712］從不同的角度提出了預(yù)測(cè)方法，文獻(xiàn) ［13-17］從不同的角度提出了云計(jì)算資源的預(yù)測(cè)方法，都取得了比較好的效果。

本文將人工蜂群算法與SVM相結(jié)合構(gòu)建預(yù)測(cè)模型，通過(guò)對(duì)人工蜂群算法的種群進(jìn)行初始化，采用差分進(jìn)化算法對(duì)個(gè)體選擇、吸引子策略構(gòu)建蜜源選擇、使用反饋機(jī)制和森林法則等措施提高人工蜂群算法的性能，并進(jìn)一步優(yōu)化SVM中參數(shù)，提高了預(yù)測(cè)精度。

1 人工蜂群算法簡(jiǎn)述及不足

人工蜂群算法 (Artificial Bee Colony Algorithm，簡(jiǎn)稱ABC)是一種根據(jù)蜜蜂采蜜行為而受到啟發(fā)提出的一種群智能優(yōu)化算法，其工作的過(guò)程是每一個(gè)蜂群個(gè)體之間進(jìn)行分工與信息分享、信息交流，從而相互合作完成采蜜工作，ABC算法具有操作簡(jiǎn)單、參數(shù)控制少、魯棒性強(qiáng)的優(yōu)點(diǎn)。特別是ABC算法用于處理某個(gè)最優(yōu)問(wèn)題的時(shí)候，其算法中對(duì)應(yīng)的蜜源的位置就是優(yōu)化問(wèn)題中的可行解，而蜜源中花粉的數(shù)量對(duì)應(yīng)優(yōu)化問(wèn)題可行解的質(zhì)量高低，蜜蜂尋找花蜜速度對(duì)應(yīng)可行解的優(yōu)化速度，獲得最大的花蜜量對(duì)應(yīng)著優(yōu)化問(wèn)題的最優(yōu)解。首先，算法隨機(jī)產(chǎn)生N個(gè)初始解，采蜜蜂的數(shù)量為N，將蜜源與采蜜蜂進(jìn)行一對(duì)一對(duì)應(yīng)，其次，當(dāng)采蜜蜂進(jìn)行搜索蜜源的時(shí)候會(huì)移動(dòng)到新位置，通過(guò)將新位置的花蜜與上一個(gè)位置的花蜜的數(shù)量進(jìn)行對(duì)比，選擇優(yōu)質(zhì)的蜜源，在采蜜蜂完成全部的搜索后，將搜索結(jié)果對(duì)比花蜜容量，從中選擇優(yōu)質(zhì)蜜源，當(dāng)所有的采蜜蜂完成搜索之后，觀察蜂會(huì)根據(jù)采蜜蜂提供的蜜源信息以一定的概率選擇蜜源，最后，判斷蜜源花蜜量經(jīng)過(guò)有限次的搜索之后得到最優(yōu)解即為最優(yōu)質(zhì)的蜜源。在ABC算法中，蜜蜂被分為三類，分別是雇傭蜂、跟隨蜂和偵察蜂。這3種蜜蜂的搜索行為如下:

(1)雇傭蜂搜索。算法中的雇傭蜂主要是為了能夠圍繞在特定的蜜源周圍隨時(shí)進(jìn)行搜索，當(dāng)需要在另一個(gè)蜜源附近進(jìn)行開(kāi)采花蜜的時(shí)候，雇傭蜂在該蜜源附近進(jìn)行新的搜索，其搜索公式如 (1)。當(dāng)尋找到新的蜜源之后，進(jìn)行適應(yīng)度 (公式2)方面的評(píng)價(jià)，并與上一個(gè)蜜源的適應(yīng)度對(duì)比，如果高于上一個(gè)蜜源，則進(jìn)行依靠。

式中，φij表示在 ［－1，1］中的隨機(jī)數(shù)，fit(v)是適應(yīng)度評(píng)價(jià)函數(shù)。

(2)跟隨蜂搜索。雇傭蜂主要將蜂蜜送到蜂巢之后，會(huì)邀請(qǐng)跟隨蜂一起飛向蜜源。跟隨蜂是否接受邀請(qǐng)主要與雇傭蜂依靠的蜜源質(zhì)量具有一定的關(guān)系，通常來(lái)說(shuō)當(dāng)蜜源的質(zhì)量越高，就能夠吸引到更多的跟隨蜂前往，反之，則會(huì)失去更多的跟隨蜂，導(dǎo)致該蜜源被放棄，跟隨蜂選擇的概率如公式 (3)所示。

(3)偵察蜂搜索。當(dāng)蜜源采摘完畢之后，在蜜源附近的雇傭蜂就變成了偵察蜂，從而進(jìn)行全局搜索。其搜索的公式如 (4)所示。

式中，R為 ［－1，1］之間的隨機(jī)數(shù)。

雖然該算法在很多實(shí)際問(wèn)題中被廣泛的應(yīng)用，但還是存在一定的不足，比如種群的初始化是隨機(jī)的，沒(méi)有考慮對(duì)整個(gè)種群的共享信息的有效利用，導(dǎo)致算法在進(jìn)行局部搜索的過(guò)程中能力差且陷入局部最優(yōu)，收斂速度還需要進(jìn)一步提高等問(wèn)題。

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

2.1 種群初始化及其個(gè)體選擇

基本的ABC算法的種群是沒(méi)有初始化的即位置是隨機(jī)的，這樣會(huì)導(dǎo)致種群在分布的時(shí)候不均勻，因此整個(gè)算法的性能也會(huì)受到一定的影響，為了能夠有效的避免這種情況的發(fā)生，有效的提高算法的搜索效率。本節(jié)采用反向?qū)W習(xí)的策略對(duì)種群進(jìn)行初始化，用來(lái)增加種群多樣性，以便更好的產(chǎn)生最優(yōu)解。其解決的策略是在反向?qū)W習(xí)策略中，將一個(gè)可行解計(jì)算出對(duì)應(yīng)的反向解，然后將這兩個(gè)解進(jìn)行合并排序，按照設(shè)定的條件選出一個(gè)個(gè)體作為下一代個(gè)體。其步驟如下:

步驟1:初始化種群規(guī)模N。

步驟2:隨機(jī)初始化階段。

步驟4:從 {X(N)∪OX(N)}中選擇適應(yīng)值最好的前N個(gè)值作為種群初始解。

在種群的初始解初始階段，首先通過(guò)對(duì)種群中個(gè)體進(jìn)行差、變異等操作重新得到一個(gè)新的種群，其次與父代個(gè)體進(jìn)行交叉操作，計(jì)算種群中的個(gè)體適應(yīng)度值進(jìn)行排列，從中選擇出優(yōu)秀的種群個(gè)體，得到新一代群體。最后進(jìn)行包括變異、交叉和選擇3個(gè)操作的進(jìn)化過(guò)程．

(1)變異。對(duì)于個(gè)體xi，按照如下生成變異個(gè)體:

式中，xr1，xr2和xr3從進(jìn)化種群中隨機(jī)選取3個(gè)個(gè)體，設(shè)定F為縮放比例因子用以控制向量產(chǎn)生的影響。

(2)交叉。為了進(jìn)一步增加種群多樣性，引入差分進(jìn)化算法:

式中，j=1，2，…D，D為空間維數(shù)，CR為0到1之間的概率。

(3)選擇。使用貪婪策略，將交叉后的個(gè)體vi和父代個(gè)體xi按照公式 (7)生成子代個(gè)體:

對(duì)個(gè)體進(jìn)行差分進(jìn)化算法步驟如下。

步驟1:初始化種群，對(duì)種群進(jìn)行評(píng)價(jià)。

步驟2:對(duì)其中的個(gè)體按公式執(zhí)行 (5)產(chǎn)生變異。

步驟3:對(duì)個(gè)體和變體執(zhí)行 (6)和 (7)生成新的個(gè)體。

步驟4:對(duì)新的個(gè)體組成的新的種群進(jìn)行總體評(píng)價(jià)，從而確定下一代種群。

2.2 跟隨蜂的蜜源選擇

在ABC算法中，跟隨蜂是通過(guò)輪盤(pán)賭策略來(lái)選擇蜜源的，雖然能夠保證優(yōu)秀的蜜源能被選中，但有的時(shí)候從整體上也會(huì)錯(cuò)失更加優(yōu)秀的蜜源，顯然這樣會(huì)延長(zhǎng)耗費(fèi)計(jì)算的資源，導(dǎo)致迭代時(shí)間延長(zhǎng)，本文算法在遵守這種理念初衷的前提下，提出一種“吸引點(diǎn)”策略，通過(guò)引入cr來(lái)改變跟隨蜂的搜索方式。所有的跟隨蜂全部以吸引點(diǎn)為中心的周圍等比例的縮放來(lái)共同開(kāi)發(fā)，從而從整體上有效的提高算法的開(kāi)發(fā)能力。而吸引點(diǎn)cr作為蜂群中的“蜂王”，按照一定的比例范圍吸引所有跟隨蜂靠近它，搜索示意如圖1所示。白色框表示吸引子，黑色球表示不同的種群的初始位置，三角形表示圍繞吸引點(diǎn)后的種群所在的新位置。

本文對(duì)于吸引點(diǎn)的獲得按照兩種方式來(lái)進(jìn)行。第一種情況是當(dāng)種群的個(gè)體獲得全局最優(yōu)解的時(shí)候，吸引點(diǎn)cr的值通過(guò)公式 (8)得到，第二種情況就是沒(méi)有獲得全局最優(yōu)解的時(shí)候，吸引點(diǎn)按 (9)得到:

圖1 搜索示意圖

式中，vi表示當(dāng)前可行解的蜜源，r1，r2，r3是一組隨機(jī)數(shù)目，且r1+r2+r3=1，吸引點(diǎn)cr作為整個(gè)蜂群的中心，而每一個(gè)偵察蜂都以它為中心，從遠(yuǎn)到近根據(jù)一定的比例進(jìn)行縮放，這樣能夠有效的降低個(gè)體飛越邊界的可能性，同時(shí)個(gè)體的整體算法的尋優(yōu)能力得到了加強(qiáng)，整體算法開(kāi)發(fā)能力也逐步增強(qiáng)。因此對(duì)種群個(gè)體進(jìn)行位置更新為:

式中，xmax和xmin是種群中的上限和下限，在算法的每一步進(jìn)化過(guò)程中，r的值恒定，保證種群個(gè)體不丟失原先的社會(huì)信息。

2.3 反饋機(jī)制和森林法則

為了進(jìn)一步解決ABC算法陷入局部最優(yōu)，容易產(chǎn)生收斂速度慢的問(wèn)題，本文將反饋機(jī)制和森林法則進(jìn)行整體融合，其主要思想是在ABC算法的全局搜索的過(guò)程中引入反饋機(jī)制，這樣可以擴(kuò)大算法的感知的范圍，因此整體上提高算法的開(kāi)發(fā)能力和探索能力，通過(guò)線性微分遞增來(lái)平衡算法中的開(kāi)發(fā)能力和探索能力，模擬森林法則中的優(yōu)勝劣汰的方式，隨機(jī)的選擇較差的個(gè)體進(jìn)行初始化。

(1)反饋機(jī)制:

從雇傭蜂搜索公式中可以發(fā)現(xiàn)，ABC算法主要用于搜索而不是進(jìn)行開(kāi)發(fā)，隨著算法的不斷深入，如何能夠更好的開(kāi)發(fā)是算法后期中薄弱環(huán)節(jié)，特別是從平衡算法的角度出發(fā)，其探索能力和開(kāi)發(fā)能力上如何解決算法的收斂能力是非常重要的，本文根據(jù)粒子群算法的中的全局最優(yōu)解的概念啟發(fā)，在搜索公式中引入線性微分遞增策略和全局最優(yōu)解的思路來(lái)解決以上問(wèn)題，采用公式如 (10)，(11):

式中，xgj表示全局最優(yōu)解，xij代表當(dāng)前解，xkj是當(dāng)前不同于xij的一個(gè)隨機(jī)解，rij是一個(gè)屬于 (－1，1)之間的隨機(jī)數(shù)，wmax和wmin分別表示自適應(yīng)因子中的最大值和最小值，設(shè)T為最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。在公式 (10)的描述中，rij是不確定的隨機(jī)數(shù)，通過(guò)相應(yīng)的反饋機(jī)制使得最優(yōu)解的蜜源的質(zhì)量能夠在上一代蜜源中得到更新，因此說(shuō)明目前的方向是正確的，因此可以繼續(xù)在該方向上搜索，反之，則向相反的方法搜索。當(dāng)上一代蜜源得到更新的時(shí)候，d=1，否則d=0，通過(guò)反饋機(jī)制，可以直接搜索可能存在最優(yōu)解的區(qū)域。

(2)樹(shù)林法則。

自然界中存在這樣一種優(yōu)勝劣汰的現(xiàn)象。速度慢的動(dòng)物往往會(huì)被兇猛的動(dòng)物吃掉，本文中的適應(yīng)度差的解就好比速度慢動(dòng)物，容易被重新初始化。在算法中，適應(yīng)度差的解個(gè)體周圍的其他解的適應(yīng)度也比較差，對(duì)這些個(gè)體按照隨機(jī)原則重新初始化，設(shè)定全局適應(yīng)度最差的個(gè)體gw的領(lǐng)域半徑范圍如公式 (12)。

式中，Range表示全局適應(yīng)度最差個(gè)體的領(lǐng)域半徑，本文將全局最優(yōu)解與最差解之間的歐式距離作為領(lǐng)域范圍的半徑。顯然，根據(jù)公式 (12)所確定的領(lǐng)域范圍，從適應(yīng)度差的個(gè)體中隨機(jī)抽取個(gè)體需要滿足如 (13)條件:

式中，a表示為一個(gè)范圍系數(shù)，只有滿足公式 (13)的種群個(gè)體被才能被重新初始化。

3 云計(jì)算流量預(yù)測(cè)模型構(gòu)建

云計(jì)算的資源負(fù)載預(yù)測(cè)可以通過(guò)SVM來(lái)建立預(yù)測(cè)模型，在模型中使用非線性映射函數(shù)φ(x)將云計(jì)算中的短時(shí)間中的負(fù)載數(shù)列x1，x2，…xn作為樣本從低維空間投影到高維的特征空間中，并進(jìn)行線性回歸，SVM在高維特征空間中的回歸函數(shù)為:

ω為權(quán)向量，b為偏置向量。根據(jù)風(fēng)險(xiǎn)最小化原則，公式 (14)轉(zhuǎn)換為如下優(yōu)化問(wèn)題表達(dá):

式中，‖ω‖是與函數(shù)f具有相關(guān)復(fù)雜度相關(guān)的項(xiàng)，ε表示不敏感損失稀疏，，ζi和C表示松弛因子和懲罰因子。為了將問(wèn)題 (15)轉(zhuǎn)換為凸二次優(yōu)化問(wèn)題，特引入朗格朗日乘子:

式中，αi和α*i表示拉格朗日乘子，γi表示損失因子，將公式 (16)轉(zhuǎn)換為對(duì)偶形式，如下:

因此，SVM回歸函數(shù)為:

為了簡(jiǎn)化 (18)，將使用核函數(shù) K(xi，x)代替 (φ(xi)，φ(x))，因此SVM函數(shù)如下:

從以上式中發(fā)現(xiàn)，建立基于SVM的云計(jì)算負(fù)載預(yù)測(cè)模型的目的就是為了找到最優(yōu)支持向量參數(shù)σ。即也就是云計(jì)算負(fù)載預(yù)測(cè)值。

4 構(gòu)建IABC－SVM預(yù)測(cè)模型

步驟1:輸入云計(jì)算資源負(fù)載序列，產(chǎn)生SVM的訓(xùn)練集和驗(yàn)證集。

步驟2:設(shè)定SVM的核函數(shù)參數(shù)σ的范圍，并設(shè)置改進(jìn)的ABC算法參數(shù)。

步驟3:設(shè)置ABC算法的中蜜源對(duì)應(yīng)每一個(gè)支持向量參數(shù)σ。

步驟4:SVM通過(guò)初始的參數(shù)σ對(duì)訓(xùn)練集進(jìn)行學(xué)習(xí)。

步驟5:使用改進(jìn)的方法對(duì)ABC算法中三類蜜蜂的初始解和相關(guān)搜索進(jìn)行操作。

步驟6:當(dāng)?shù)螖?shù)超過(guò)最大迭代次數(shù)的時(shí)候，訓(xùn)練結(jié)束，輸出種群最優(yōu)位置，即為SVM中的向量參數(shù)σ最優(yōu)值，否則轉(zhuǎn)向步驟5繼續(xù)執(zhí)行。

步驟7:采用向量參數(shù)σ來(lái)建立預(yù)測(cè)模型f(x)，對(duì)驗(yàn)證集合的預(yù)測(cè)結(jié)果進(jìn)行分析。

5 實(shí)驗(yàn)與分析

5.1 數(shù)據(jù)來(lái)源

為了能夠有效的說(shuō)明本文算法在云計(jì)算資源負(fù)載中發(fā)揮的作用，選擇Clarknet［18］的網(wǎng)絡(luò)負(fù)載作為本文實(shí)驗(yàn)的研究對(duì)象，在時(shí)間的設(shè)定上選擇連續(xù)7天的100個(gè)歷史數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，數(shù)據(jù)間隔為4個(gè)小時(shí)，預(yù)測(cè)未來(lái)2天的的云計(jì)算下的負(fù)荷數(shù)據(jù)。本文使用平均絕對(duì)誤差MAE來(lái)計(jì)算預(yù)測(cè)模型的有效性，公式如下，其中yt為實(shí)際負(fù)載數(shù)據(jù)為預(yù)測(cè)數(shù)據(jù)，T為預(yù)測(cè)時(shí)間序列，如公式 (20)所示，但由于SVM對(duì)于［0，1］之間的數(shù)據(jù)具有非常高的敏感度，因此需要對(duì)網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行歸一化處理，公式 (21)所示。

式 (21)中，x表示原始網(wǎng)絡(luò)流量，max(x)和min(x)表示最大值和最小值。

5.2 仿真結(jié)果分析

5.2.1 本文算法的預(yù)測(cè)效果

本文選取了連續(xù)9天的云計(jì)算的網(wǎng)絡(luò)流量簡(jiǎn)化結(jié)果，單位為Gb/S，對(duì)應(yīng)結(jié)果如表1所示。表2為采用本文算法來(lái)預(yù)測(cè)得到第8～9天的云計(jì)算下流量預(yù)測(cè)結(jié)果。從表2中發(fā)現(xiàn)，根據(jù)相同的時(shí)間序號(hào)下的云計(jì)算的云計(jì)算網(wǎng)絡(luò)流量預(yù)測(cè)與表1種的網(wǎng)絡(luò)流量的仿真結(jié)果的誤差基本上在5%之內(nèi)，圖2顯示了Clarknet平臺(tái)中的實(shí)際負(fù)載和預(yù)測(cè)負(fù)載的效果，圖中的兩條線大部分都重合或者十分相近，從以上的分析中可以說(shuō)明本文算法具有良好的預(yù)測(cè)效果。

表1 連續(xù)9天的云計(jì)算中網(wǎng)絡(luò)流量仿真實(shí)際結(jié)果

表2 第8－9天的云計(jì)算中的網(wǎng)絡(luò)流量仿真結(jié)果

5.2.2 Clarknet平臺(tái)下的幾種預(yù)測(cè)方法的研究

在Clarknet平臺(tái)中將本文算法、SVM方法，IABC－LSSVM［19］在CPU負(fù)載和網(wǎng)絡(luò)負(fù)載的條件下進(jìn)行對(duì)比，對(duì)比結(jié)果如3～4所示。

圖2 Clarknet平臺(tái)的網(wǎng)絡(luò)負(fù)載預(yù)測(cè)結(jié)果

圖3 4種算法下的CPU負(fù)載的MAE值比較

圖4 4種算法下的云中網(wǎng)絡(luò)負(fù)載的MAE值比較

從圖4得到本文提出的算法在不同的云計(jì)算CPU負(fù)載條件下相比于其他兩種預(yù)測(cè)方法明顯具有良好的效果，預(yù)測(cè)精度更高，預(yù)測(cè)誤差小，這說(shuō)明本文預(yù)測(cè)方法能夠適應(yīng)CPU在不同負(fù)載變換下的預(yù)測(cè)結(jié)果。圖5中發(fā)現(xiàn)本文算法的曲線相對(duì)于其他兩種算法曲線的波動(dòng)性小，相對(duì)平緩，這說(shuō)明本文算法能夠適應(yīng)不同條件下的網(wǎng)絡(luò)負(fù)載預(yù)測(cè)。從以上2個(gè)實(shí)驗(yàn)中發(fā)現(xiàn)本文算法能夠有效的提高蜂群種群在解空間中的搜索能力，提高全局搜索效率，從而使得基于IABC的預(yù)測(cè)具有更好的效果。

6 結(jié)束語(yǔ)

針對(duì)云計(jì)算中的資源負(fù)載的預(yù)測(cè)效果，本文提出了云計(jì)算中的基于ABC優(yōu)化的SVM預(yù)測(cè)模型。仿真實(shí)驗(yàn)說(shuō)明本文算法能夠在CPU負(fù)載和網(wǎng)絡(luò)負(fù)載中具有比較好的預(yù)測(cè)精度，能夠?yàn)樵朴?jì)算下的資源預(yù)測(cè)提供了一種參考。