基于蟻群優(yōu)化 蛙跳算法的云計算資源調(diào)度算法

陳 暄，徐見煒，龍 丹

(1.浙江工業(yè)職業(yè)技術(shù)學院，浙江 紹興312000; 2.浙江大學 理學部，杭州310058)

(*通信作者電子郵箱chenxuan1979@sina.com)

0 引言

云計算下的資源調(diào)度一直以來都是研究的重點，能否有效、合理地分配資源關(guān)系到云計算下是其效率能否提高的關(guān)鍵［1］。將啟發(fā)式智能算法運用在資源調(diào)度中已經(jīng)成為了當前研究的熱點，國內(nèi)外學者從不同的方向進行了研究。將基本的蟻群優(yōu)化(Ant Colony Optimization，ACO)算法［4－5］、粒子群優(yōu)化(Particle Swarm Optimization，PSO) 算法［2－3］、遺傳算法(Genetic Algorithm，GA)［6－7］運用在云計算資源調(diào)度中取得了一定的效果。文獻［8］提出了基于改進量子遺傳算法(Improved Quantum Genetic Algorithm，IQGA)的云計算資源調(diào)度，該算法通過改進量子遺傳算法的二進制編碼使其適用于實數(shù)編碼，仿真實驗結(jié)果表明與遺傳算法(GA)和粒子群優(yōu)化(PSO)算法相比能夠提高云資源調(diào)度效率;但存在的問題是調(diào)度模型的假設(shè)條件設(shè)置得過于簡單，求解效率和準確性還需要進一步提高。文獻［9］提出了一種在云計算環(huán)境中結(jié)合遺傳算法和蟻群算法的資源調(diào)度算法，該算法利用遺傳算子的快速全局收斂性生成一個初始信息素分布，然后利用雙向收斂蟻群算法反復(fù)迭代求解，從而提高算法的效率;但存在的問題是算法的迭代步驟過于頻繁復(fù)雜，增大了空間計算量。文獻［10］設(shè)計了一種基于改進蟻群優(yōu)化算法的云計算資源調(diào)度優(yōu)化模型，利用蟻群優(yōu)化算法得到的路徑作為云計算資源調(diào)度目標函數(shù)的最優(yōu)解，仿真實驗說明該算法具有很好的效果;但存在的問題是實驗中僅僅與傳統(tǒng)的蟻群算法、粒子群算法相比，并沒有針對一些新的改進的算法進行對比，同時實驗中云計算相關(guān)指標太少，不能完全說明所提算法在其他指標方面的優(yōu)越性。文獻［11］提出了一種基于貪心算法的云計算資源調(diào)度策略，建立了云計算環(huán)境下資源調(diào)度算法的貪心模型，以最小執(zhí)行時間和滿意度為目標，構(gòu)建資源調(diào)度方案;但存在的問題是貪心算法自身存在著一定的缺陷，因此在云計算的資源調(diào)度中的效果并不是非常滿意。文獻［12］提出一種基于時間成本負載加強型的蟻群優(yōu)化(Time，Cost and Load Balance-Enhanced ACO，TCLB-EACO)優(yōu)化算法，通過創(chuàng)新地改進信息素和啟發(fā)信息提高了算法效率;但存在的問題是沒有與其他的智能算法進行比較，實驗效果相對單一。文獻［13］從綠色云計算角度出發(fā)，提出了機器啟動時間的虛擬機策略，并通過資源延遲感知的實時任務(wù)調(diào)度(Startup Time Aware Real Scheduling，STARS)算法來進行調(diào)度資源，實驗說明該算法在時效性、節(jié)能和資源利用率方面都具有比較好的效果。文獻［14］提出將螢火蟲算法用來尋找云計算中的目標資源中的最佳調(diào)度策略，仿真實驗說明提高了云計算資源分配效率;但存在的問題是螢火蟲算法自身存在收斂快等缺點并沒有得到解決，實驗僅僅與基本算法進行對比。文獻［15］提出將改進的蟻群算法用于負載均衡的云計算資源調(diào)度中，仿真實驗說明該算法能夠有效地降低執(zhí)行成本，滿足資源負載均衡;但存在的問題是沒有考慮用戶的服務(wù)質(zhì)量(Quality of Service，QoS)要求。文獻［16］提出一種基于生產(chǎn)函數(shù)的云服務(wù)提供商收益最大化同時兼顧用戶滿意度的資源調(diào)度算法，通過與基于博弈的效用優(yōu)化算法進行比較，仿真結(jié)果表明該調(diào)度算法具有更好的性能;但存在問題是生產(chǎn)函數(shù)具有一定的局限性，無法很好地適應(yīng)云計算下的動態(tài)變換特點。文獻［17］提出基于禁忌搜索的云計算平臺下服務(wù)資源均衡調(diào)度方法，依據(jù)云計算調(diào)度系統(tǒng)的結(jié)構(gòu)特點對云計算環(huán)境下的資源均衡資源調(diào)度問題進行形式化描述，將混沌理論和粒子群理論相結(jié)合得到資源調(diào)度和資源均衡度的目標函數(shù)，完成對云計算資源調(diào)度，獲得了比較好的效果;但存在的問題是禁忌算法自身算法效率低，對云計算資源調(diào)度的效果會具有一定的影響，影響調(diào)度效率。文獻［18］提出了一種考慮時間 成本約束條件的蟻群優(yōu)化算法，不僅能使任務(wù)處理時間較短，執(zhí)行費用較低，且能使系統(tǒng)負載相對均衡，資源利用率高;但存在的問題是僅僅是與其他改進的蟻群算法相比，沒有與更多的智能算法進行比較，存在一定的不足。

針對以上云計算資源調(diào)度存在的問題，本文首先描述建立QoS的云計算中的資源分配模型，其次，提出基于蟻群優(yōu)化 蛙跳算法(ACO-Shuffled Frog Leading Algorithm，ACOSFLA)的融合算法運用到云計算資源調(diào)度中，最后仿真實驗表明融合后的算法能夠有效地提高云計算的資源調(diào)度效率。

1 基于QoS的云計算資源分配模型

傳統(tǒng)的調(diào)度算法以資源使用效率為第一目標，算法自身的適應(yīng)性不好，局限性大。面向商業(yè)服務(wù)的云計算必須提供具有高效、可靠和公平的資源為這些云端用戶服務(wù)，并以滿足云用戶的最大化需求為宗旨。在云計算資源調(diào)度中，針對大量資源被調(diào)用的請求，首先需要檢測資源各個性能指標，計算各個資源當前的占用率和負載情況，尋找更加適合的資源來執(zhí)行相應(yīng)的任務(wù)，有效地提高資源的利用率。本文提出了基于QoS的云計算模型，構(gòu)造具有完成時間、費用、可用性和安全性四個指標的效用函數(shù)來衡量云計算下的資源效果。

為了進一步研究具有針對性，本文采用文獻［19］的資源調(diào)度中的任務(wù)和資源進行抽象化處理，建立由m個用戶和n個資源組成的調(diào)度模型，設(shè)R表示所有資源集合，即R={r1，r2，…，rn}，其中:ri表示第 i個資源 ri={ri(1)，ri(2)，…，ri(t)}，t為不同的屬性。本文選取t的值為4，表示時間、費用、可用性和安全性四個屬性。用戶的集合為U={u1，u2，…，um}，其中m表示的用戶個數(shù)，假設(shè)一個用戶ux在某一個時刻提交的任務(wù)為tsj，因此第k個任務(wù)可以表示為tsjk={tsjk(1)，tsjk(2)，…，tsjk(t)}。在云計算環(huán)境中，用戶ux針對某一個資源的不同維度特征屬性的QoS為:qij={qij(1)，qij(2)，…，qij(t)}，其中qij(k)表示用戶j對ri的第k個屬性對應(yīng)的QoS。用戶uj對應(yīng)資源ri的第k個特征屬性用戶的效用表示為θij(qij(k))，因此本文設(shè)定的基于QoS的目標優(yōu)化效用函數(shù)為:

任務(wù)tsj完成時間反映了該資源rj具備完成對應(yīng)任務(wù)tsj的能力，在規(guī)定時間內(nèi)完成，其值為1，否則就為0，其效用函數(shù)如下:

云計算服務(wù)具有比較高的性價比，設(shè)b為用戶uj對于任務(wù)tsj的預(yù)算費用，設(shè)c為用戶uj對于任務(wù)tsj的實際費用。如果超過預(yù)算費用，效用的值為0，效用函數(shù)如下:

云計算中的可用性反映了用戶提交服務(wù)請求后，能夠成功返回處理的概率，可用性越高，說明用戶滿意度越大，設(shè)定可用性為a，e為常數(shù)，隨著a逐漸增大，用戶的QoS提高幅度越大，效用呈指數(shù)式增長，表達式如下:

系統(tǒng)安全性是關(guān)系到用戶對于QoS性能指標反饋的關(guān)鍵，在Qos中使用監(jiān)測異常數(shù)值大小來表示系統(tǒng)安全性，設(shè)定s1、s2表示不同的安全層次安全界限，效用表達式如下:

2 基于改進的蟻群和蛙跳融合算法

2.1 改進的蟻群算法

蟻群優(yōu)化(ACO)算法是一種模擬真實螞蟻群體覓食行為的仿生學優(yōu)化算法，它具有正反饋、分布式和啟發(fā)式的搜索特點，在解決復(fù)雜的優(yōu)化問題方面取得了比較好的效果，其本質(zhì)是使用信息素來作為種群中的個體的交流的介質(zhì)，其計算式如下:

2.1.1 信息素更新

傳統(tǒng)的蟻群算法存在的主要缺陷是信息素的值依賴于問題的規(guī)模，因此，本文針對信息素進行改進，把蟻群算法的信息素更新過程分為兩個階段，并將信息素的值限定在特定的區(qū)間中。第一個階段是順序更新階段，使用前n個迭代上的最優(yōu)方案來更新路徑上的信息素;第二個階段是當前迭代達到最優(yōu)解，全局最優(yōu)路徑上的信息素才能夠被更新。更新公式如下:

當cf＜t(t為［0，1］內(nèi)的數(shù))時，使用前m個解序列來更新路徑上的信息素;否則，就執(zhí)行當前迭代的最優(yōu)解來更新信息素。

2.1.2 設(shè)置經(jīng)驗反饋因子

針對信息素的改進主要考慮啟發(fā)信息對于路徑的影響，這使得螞蟻在算法的迭代初期容易選擇最短的路徑，而沒有考慮被選取為解的路徑的組合對最終路徑長度的影響，從而導(dǎo)致了搜索具有盲目性的問題，通過研究發(fā)現(xiàn)一些短的解元素所在的路徑的整體長度往往很大，導(dǎo)致算法最終收斂到局部最優(yōu)而不是全局最優(yōu)。為了能夠有效地避免在算法的初始階段就失去原本具有最優(yōu)解的可能性，需要在概率選擇中增加另一個權(quán)重——經(jīng)驗反饋因子w來考慮選取的路徑對于搜索過程的長期影響。在初始階段中，當解元素傾向引導(dǎo)螞蟻尋找短路徑時，就會被賦予較高的權(quán)重;反之，當解元素可能會引導(dǎo)螞蟻走向較長的路徑時，就應(yīng)該減少元素的權(quán)重，這樣就能夠讓螞蟻的搜索初期選擇不同的路徑，增加了多條路徑選擇的多樣性，避免算法陷入局部最優(yōu)解。反饋因子如下:

式中:cmin和cmax分別表示兩個點之間的路徑長度的最小值和最大值;cmid代表兩者的平均值;c(a)表示路徑的長度;A(i，j)表示路徑(i，j)的螞蟻的集合。

2.2 蛙跳算法

蛙跳算法(SFLA)是一種啟發(fā)式優(yōu)化算法，它通過執(zhí)行啟發(fā)式函數(shù)而執(zhí)行啟發(fā)式搜索，從而獲得全局最優(yōu)解，其思想是首先將蛙群分解為不同數(shù)目的子群，其次在子群中按照一定的策略進行搜索，最后再進行全局交換。

1)子群劃分。

設(shè)置全部的青蛙有M個，子群數(shù)目為k，子群內(nèi)的候選解的個數(shù)為 n。xi=(xi1，xi2，…，xiD) 表示第 i個候選解，其中 D表示候選解的維數(shù)。

2)子群內(nèi)部搜索。

在子群搜索的過程中獲得的候選解如果是最差的，需要對其進行更新，反之，則需要使用此時的候選解替換繼續(xù)執(zhí)行搜索。

3)全局信息交換。

當所有子群完成內(nèi)部搜索之后，將所有的子群再次進行重新劃分并在群內(nèi)進行搜索，直到滿足找到最優(yōu)最優(yōu)解的時候，結(jié)束條件結(jié)束。

2.2.1 局部優(yōu)化

使用差分進化算法進行局部更新主要是隨機選取一個目標的個體進行更新，而且這個子群的更新對象還是子群中的最差個體，并且在整個優(yōu)化過程中更新策略并不是一成不變的。為了能夠達到算法在進化前期提高種群的多樣性和后期加快算法的收斂的優(yōu)化效果，采用變異方式對其進行優(yōu)化。

1)變異操作。

在算法的前期中，為了保持種群的多樣性，提高全局搜索能力，對子群中的最差個體按照式(13)進行更新，隨機選擇三個個體，其中一個個體作為目標個體，其他兩個個體用來更新移動的步長，采用rand差分算子。

其中:Xr1為目標個體;Xr2和Xr3為隨機選取的其他兩個個體;X'w為產(chǎn)生的新個體;F1∈(0，1)。

為了有助于收斂到最優(yōu)點，用子群中最好的個體作為目標個體，引入差分算子best變異，更新策略如下:

式中:Xr2和Xr3為隨機選取的其他兩個個體;X'w為產(chǎn)生的新個體;Xb為子群最優(yōu)個體;F2∈(0，1)，且F1+F2=1。

2)選擇操作。

將進行一次迭代后將產(chǎn)生的新個體X'w與子群最差個體Xw進行適應(yīng)度評價，根據(jù)自然法則，選擇適應(yīng)值更好的個體進入到下一代種群，如式(15)所示:

3)交叉操作。

為了能夠進一步提供算法的局部搜索能力，保持種群的多樣性，引入交叉操作進行了改進，更新策略如下:

2.2.2 全局優(yōu)化

設(shè)所有青蛙子群的個數(shù)為m，每個子群內(nèi)的最優(yōu)青蛙個體分別為:Pb(1)，Pb(2)，…Pb(m)，全局最優(yōu)解為 Pg，在Pb(1)和Pb(m)中隨機選擇兩個個體作為父代，再結(jié)合Pg進行交叉，按照下式生成后代:

式中:r1+r2+r3=1 且r1，r2，r3∈(0，1)。r1，r2，r3的大小決定了父代個體之間交叉域的大小，在青蛙種群中采用精英保留策略，淘汰較差的個體，但是由于Pb表示各個子群中的內(nèi)部最優(yōu)個體，因此會導(dǎo)致陷入局部最優(yōu)。所以在不同的子群最優(yōu)個體之間進行交叉操作，能夠避免陷入局部最優(yōu)，從而達到全局最優(yōu)。

2.3 算法步驟

首先，將蟻群算法的個體與云計算資源調(diào)度方案進行對應(yīng)，其次，采用改進的蟻群算法得到的解作為蛙跳算法初始種群個體進行進一步優(yōu)化，最后得到最優(yōu)的個體即最佳的調(diào)度方案。其算法步驟如下:

步驟1 將蟻群算法中的個體與云計算中的資源調(diào)度方案進行一一對應(yīng)。

步驟2 初始化，設(shè)置最大迭代次數(shù)、蟻群算法相關(guān)參數(shù)初始值、蛙跳算法參數(shù)初始值。

步驟3 構(gòu)建螞蟻路徑，將選中的路徑對應(yīng)到螞蟻的禁忌表中，直到所有螞蟻都完成一次遍歷，按照式(12)改進概率轉(zhuǎn)移規(guī)則選取下一個元素。

步驟4 將螞蟻通過路徑得到的解作為蛙跳算法的初始蛙群個數(shù)，并按照式(13)～(17)的相關(guān)操作對蛙跳算法進行改進。

步驟5 按照式(9)、(10)對信息素進行更新。

步驟6 算法終止，找到最優(yōu)個螞蟻個體即最佳的云計算資源調(diào)度方案。

3 仿真實驗與分析

為了進一步說明本文算法在云計算中的效果，將本文算法與其他算法通過Cloudsim仿真平臺對比資源調(diào)度的效果。本文算法所需要的主要參數(shù)如表1所示，設(shè)定任務(wù)數(shù)量一定，資源數(shù)目為［5，100］，對比的指標為在時間、成本、可用性和安全性。

實驗內(nèi)容將本文算法ACO-SFLA與基本蟻群(ACO)算法、基本蛙跳算法(SFLA)、改進的粒子群(Improved Particle Swarm Optimizaiton，IPSO) 算法［20］、改進的人工蜂群算法(Improved Artifical Bee Colony algorithm，IABC)［21］進行對比，5種算法在資源數(shù)目逐漸增大的情況下的不同性能對比如圖1所示。

圖1 不同算法在不同資源下的性能對比Fig.1 Performance comparison of different algorithms under different resources

由圖1(a)可以看出，本文算法曲線在下降過程中比較平緩，且完成時間優(yōu)于其他4種算法，表明本文算法與其他算法相比能夠有效地節(jié)約完成時間;從圖1(b)中可以看出，5種算法的成本伴隨著資源數(shù)目的增大而逐漸降低，本文算法消耗的成本優(yōu)于其他4種算法;圖1(c)中描述了5種算法的用戶滿意度調(diào)查都比較滿意，本文算法滿意度稍微低于其他4種算法，這說明本文算法在執(zhí)行時間和成本方面給云客戶帶來了較好的用戶體驗;圖1(d)的結(jié)果表明了5種算法在資源調(diào)度的過程中都具有比較好的安全性，算法之間相差不大，且算法的異常數(shù)值的峰值都比較小，而本文算法的峰值相對小一些。綜合以上分析得出本文算法能夠較好地解決對云計算資源調(diào)度的問題，產(chǎn)生更好的優(yōu)化策略。

表1 算法參數(shù)列表Tab.1 Algorithm parameter list

4 結(jié)語

在云計算資源調(diào)度算法問題中，本文引入了蟻群算法和蛙跳算法，將改進后的兩種算法進行融合用于云計算資源調(diào)度，取得了較好的調(diào)度效果;但由于僅僅是從考慮的QoS指標角度出發(fā)，忽略了云計算中的一些諸如能量消耗、任務(wù)數(shù)量等因素，這將在下一步的研究中繼續(xù)展開。