史振華

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

0 引言

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

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

1 人工蜂群算法簡述及不足

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

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

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

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

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

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

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

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

2.1 種群初始化及其個體選擇

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

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

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

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

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

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

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

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

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

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

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

步驟1:初始化種群，對種群進(jìn)行評價。

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

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

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

2.2 跟隨蜂的蜜源選擇

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

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

圖1 搜索示意圖

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

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

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

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

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

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

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

(2)樹林法則。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1 數(shù)據(jù)來源

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

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

5.2 仿真結(jié)果分析

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

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

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

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

5.2.2 Clarknet平臺下的幾種預(yù)測方法的研究

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

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

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

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

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

6 結(jié)束語

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