史振華

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

0 引言

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

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

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

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

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

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

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

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

式中，R為 ［－1，1］之間的隨機數。

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

2 人工蜂群算法的改進

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

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

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

步驟2:隨機初始化階段。

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

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

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

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

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

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

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

對個體進行差分進化算法步驟如下。

步驟1:初始化種群，對種群進行評價。

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

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

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

2.2 跟隨蜂的蜜源選擇

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

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

圖1 搜索示意圖

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

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

2.3 反饋機制和森林法則

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

(1)反饋機制:

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

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

(2)樹林法則。

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

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

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

3 云計算流量預測模型構建

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

ω為權向量，b為偏置向量。根據風險最小化原則，公式 (14)轉換為如下優(yōu)化問題表達:

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

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

因此，SVM回歸函數為:

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

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

4 構建IABC－SVM預測模型

步驟1:輸入云計算資源負載序列，產生SVM的訓練集和驗證集。

步驟2:設定SVM的核函數參數σ的范圍，并設置改進的ABC算法參數。

步驟3:設置ABC算法的中蜜源對應每一個支持向量參數σ。

步驟4:SVM通過初始的參數σ對訓練集進行學習。

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

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

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

5 實驗與分析

5.1 數據來源

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

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

5.2 仿真結果分析

5.2.1 本文算法的預測效果

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

表1 連續(xù)9天的云計算中網絡流量仿真實際結果

表2 第8－9天的云計算中的網絡流量仿真結果

5.2.2 Clarknet平臺下的幾種預測方法的研究

在Clarknet平臺中將本文算法、SVM方法，IABC－LSSVM［19］在CPU負載和網絡負載的條件下進行對比，對比結果如3～4所示。

圖2 Clarknet平臺的網絡負載預測結果

圖3 4種算法下的CPU負載的MAE值比較

圖4 4種算法下的云中網絡負載的MAE值比較

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

6 結束語

針對云計算中的資源負載的預測效果，本文提出了云計算中的基于ABC優(yōu)化的SVM預測模型。仿真實驗說明本文算法能夠在CPU負載和網絡負載中具有比較好的預測精度，能夠為云計算下的資源預測提供了一種參考。