云計(jì)算環(huán)境中基于分布估計(jì)蛙跳算法的資源調(diào)度

寧菲菲，王建璽

云計(jì)算環(huán)境中基于分布估計(jì)蛙跳算法的資源調(diào)度

寧菲菲，王建璽

針對(duì)云計(jì)算環(huán)境下的資源調(diào)度問題，提出了一種基于分布估計(jì)蛙跳算法的云資源調(diào)度策略。在運(yùn)用混合蛙跳算法（SFLA）搜索全局最優(yōu)解的同時(shí)，在SFLA的局部搜索環(huán)節(jié)引入基于群體的增量學(xué)習(xí)算法（PBILA），通過建立反映優(yōu)質(zhì)解分布的概率模型，增加子群間的協(xié)作、增強(qiáng)群體的全面學(xué)習(xí)能力。仿真實(shí)驗(yàn)結(jié)果表明：該資源調(diào)度策略不僅能夠有效地避免陷入局部最優(yōu)，而且較好地提升了全局收斂性能。

云計(jì)算；資源調(diào)度；蛙跳算法；分布估計(jì)算法；基于群體的增量學(xué)習(xí)算法

0 引言

近年來，隨著互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大和電子商務(wù)、在線視頻等新型互聯(lián)網(wǎng)應(yīng)用的迅猛發(fā)展，海量的數(shù)據(jù)存儲(chǔ)、業(yè)務(wù)的快速增長(zhǎng)以及企業(yè)運(yùn)維成本的不斷提高對(duì)互聯(lián)網(wǎng)的發(fā)展提出了新的挑戰(zhàn)。為了給用戶提供更為方便、快捷的高質(zhì)量網(wǎng)絡(luò)服務(wù)，云計(jì)算作為一種新型的服務(wù)計(jì)算模型在2006年一經(jīng)提出便得到了廣泛關(guān)注。根據(jù)美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）的定義：云計(jì)算是一種通過互聯(lián)網(wǎng)以按需的方式隨時(shí)隨地對(duì)一個(gè)可配置的共享資源池（包括計(jì)算設(shè)施、存儲(chǔ)設(shè)備、應(yīng)用和服務(wù)等）進(jìn)行訪問的服務(wù)模式[1]。資源調(diào)度作為云計(jì)算中的一個(gè)重要問題，其性能優(yōu)劣直接影響到云計(jì)算資源的利用率、用戶滿意度以及企業(yè)的運(yùn)營(yíng)成本。

由于云計(jì)算環(huán)境下的資源調(diào)度是一個(gè)NP完全問題，因此，許多學(xué)者提出了大量的基于啟發(fā)式智能算法的云資源調(diào)度策略。例如，劉衛(wèi)寧等[2]提出了基于改進(jìn)二進(jìn)制編碼的量子遺傳算法的云資源調(diào)度策略，使其適用于實(shí)數(shù)編碼并有效避免了在量子編碼的空間內(nèi)陷入局部最優(yōu)。左利云[3]等提出了基于多目標(biāo)集成蟻群優(yōu)化算法，用于解決資源調(diào)度問題。劉萬軍[4]等提出了一種基于粒子群優(yōu)化算法的云資源調(diào)度策略，盡量避免資源調(diào)度過程中負(fù)載失衡問題的產(chǎn)生。金偉健[5]等提出了基于蝙蝠算法的云資源分配策略，以有效兼顧任務(wù)完成時(shí)間和成本。

本文提出一種基于分布估計(jì)蛙跳算法的資源調(diào)度策略，將混合蛙跳算法和分布估計(jì)算法有效結(jié)合。通過在CloudSim平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)測(cè)試算法性能，仿真結(jié)果表明：分布估計(jì)蛙跳算法不僅能夠有效避免在資源調(diào)度過程中陷入局部最優(yōu)，而且較好地提升了算法的全局收斂性能。

1 云資源調(diào)度模型

[6]對(duì)云計(jì)算環(huán)境中的資源調(diào)度問題建模表示為由s個(gè)虛擬機(jī)資源和t個(gè)用戶任務(wù)所組成的云資源調(diào)度模型，可將該模型表示為四元組SM＝(R, M, F, θ)。其中，R為由s個(gè)虛擬機(jī)資源所組成的資源集合；M為由t個(gè)用戶任務(wù)所組成任務(wù)集合；F表示云資源調(diào)度模型的優(yōu)化目標(biāo)函數(shù)；θ則表示解決云資源調(diào)度問題所采用的優(yōu)化算法。云資源調(diào)度模型的主要特征詳細(xì)描述如下：

（1）資源集合R＝{rc1, rc2, …, rcs}，虛擬機(jī)資源rcj(1≤j≤s)負(fù)責(zé)處理分配到該資源上的子任務(wù)。

（2）任務(wù)集合M＝{m1, m2, ..., mt}，第mx(1≤x≤t)個(gè)用戶任務(wù)可以劃分為Nx個(gè)子任務(wù)，且子任務(wù)間相互獨(dú)立。

（3）任務(wù)mx的執(zhí)行時(shí)間可以表示為公式（1）：

其中，W(k, n, rcj)表示任務(wù)mx的第n個(gè)子任務(wù)所在的虛擬機(jī)資源rcj在處理分配到該資源上的第k個(gè)子任務(wù)時(shí)所使用的時(shí)間；pos表示任務(wù)mx的第n個(gè)子任務(wù)在虛擬機(jī)資源rcj的計(jì)算隊(duì)列中所處的位置則表示虛擬機(jī)資源rcj按照其計(jì)算隊(duì)列中子任務(wù)的排序依次執(zhí)行各子任務(wù)直至完成任務(wù)mx的第n個(gè)子任務(wù)為止所用的時(shí)間。

（4）用ETC(i, rcj)表示第i 個(gè)子任務(wù)在虛擬機(jī)資源rcj上的執(zhí)行時(shí)間，則執(zhí)行完成任務(wù)集合M內(nèi)所有任務(wù)需要的總時(shí)間T可以表示為公式（2）：

其中：cnt(rcj)表示分配到rcj資源上的子任務(wù)總量。

（5）用戶任務(wù)的平均完成時(shí)間AVG可以表示為公式（3）：

2 分布估計(jì)蛙跳算法

2.1 混合蛙跳算法

混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）是由Eusuff和Lansey等人[7]提出的一種基于群體智能的進(jìn)化算法，通過模擬青蛙群體覓食過程用于解決多目標(biāo)優(yōu)化問題。由于SFLA概念簡(jiǎn)單、參數(shù)少，而且具有計(jì)算速度快、全局搜索尋優(yōu)能力強(qiáng)以及易于實(shí)現(xiàn)等特點(diǎn)，因此，該算法在水資源分配、車間作業(yè)流程安排等眾多領(lǐng)域都有著廣泛應(yīng)用[8]。SFLA的主要思想是：將整個(gè)青蛙群體劃分為若干個(gè)子群體，每個(gè)子群體具有自己的文化，子群體中的每只青蛙也具有自己的文化，在與其他青蛙個(gè)體相互作用的同時(shí)，還伴隨著子群體的進(jìn)化而進(jìn)化。首先在各子群體內(nèi)部分別執(zhí)行局部搜索，當(dāng)局部搜索迭代結(jié)束后，將所有的子群體進(jìn)行混合并進(jìn)行文化交流，即執(zhí)行全局信息交換。子群體的局部搜索和全局信息交換交替進(jìn)行，直到終止條件滿足為止。接下來簡(jiǎn)要介紹SFLA的主要步驟。

步驟1：初始化。隨機(jī)生成N只青蛙組成初始蛙群，每只青蛙都代表著優(yōu)化問題的一個(gè)可行解Y=(y1, y2, ... , yE)，E表示解的維數(shù)。

步驟2：排序。計(jì)算每只青蛙的適應(yīng)度F(i)，并按照適應(yīng)度對(duì)所有青蛙進(jìn)行降序排序。每只青蛙都對(duì)應(yīng)一個(gè)序號(hào)Si（1≤ i≤N），Si表示排序后該青蛙在序列中的位置。

步驟3：子群劃分。將N只青蛙組成的初始蛙群劃分為L(zhǎng)(L

其中，Gi表示對(duì)序號(hào)為Si的青蛙所分配子群的群號(hào)。根據(jù)公式（4）進(jìn)行子群劃分，排序后序號(hào)為1的青蛙被分入1號(hào)子群，序號(hào)為2的青蛙被分入2號(hào)子群，… ，序號(hào)為L(zhǎng)的青蛙被分入L號(hào)子群，序號(hào)為L(zhǎng)+1的青蛙被分入1號(hào)子群，序號(hào)為L(zhǎng)+2的青蛙被分入2號(hào)子群，依此類推，直到所有青蛙被分配完畢為止。

步驟4：局部搜索。設(shè)Yb為子群中具有最優(yōu)適應(yīng)度的可行解，Yw為子群中適應(yīng)度最差的可行解，Yg為整個(gè)蛙群中具有最優(yōu)適應(yīng)度的可行解。在各子群內(nèi)部進(jìn)行局部搜索，并根據(jù)公式（4）用子群內(nèi)具有最優(yōu)適應(yīng)度的可行解Yb來更新適應(yīng)度最差的可行解Yw。得公式（5）：

其中，rand()函數(shù)產(chǎn)生值為0～1之間的隨機(jī)數(shù)。若根據(jù)公式(5)更新后得到的解newYw的適應(yīng)度優(yōu)于Yw，則Yw=newYw；否則用整個(gè)蛙群中具有最優(yōu)適應(yīng)度的可行解Yg代替Yb重復(fù)執(zhí)行公式（5）得到newYw，若其適應(yīng)度仍不優(yōu)于Yw，則隨機(jī)產(chǎn)生一個(gè)可行解代替Yw。在各子群體內(nèi)部根據(jù)公式（5）重復(fù)執(zhí)行更新Yw的操作，直到迭代次數(shù)達(dá)到設(shè)定的最大局部搜索次數(shù)為止。

步驟5：全局信息交換。當(dāng)所有子群結(jié)束一輪的局部搜索之后，將所有子群的青蛙進(jìn)行混合，執(zhí)行全局信息交換并記錄當(dāng)前整個(gè)蛙群中具有最優(yōu)適應(yīng)度的可行解Yg，即全局最優(yōu)解。

步驟6：計(jì)算并判斷終止條件。如果終止條件得到滿足，則算法結(jié)束，否則轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。

2.2 分布估計(jì)算法

分布估計(jì)算法（Estimation of Distribution Algorithms，EDAs）是進(jìn)化計(jì)算領(lǐng)域所提出的一種全新進(jìn)化模式。分布估計(jì)算法的主要思想是運(yùn)用統(tǒng)計(jì)學(xué)習(xí)的手段建立一個(gè)描述群體（即解空間）內(nèi)個(gè)體（即解）分布的概率模型，通過對(duì)概率模型隨機(jī)采樣產(chǎn)生新的群體以實(shí)現(xiàn)群體的不斷進(jìn)化，重復(fù)執(zhí)行直到滿足終止條件為止[9]。

分布估計(jì)算法的關(guān)鍵在于建立一個(gè)能夠精確反映優(yōu)化問題的概率模型。本文選擇運(yùn)用最早被提出的分布估計(jì)算法——基于群體的增量學(xué)習(xí)算法PBILA[9]的學(xué)習(xí)規(guī)則來建立描述優(yōu)質(zhì)解分布的概率模型。具體實(shí)現(xiàn)可以歸納為以下3個(gè)主要步驟：

步驟1：初始化群體，建立描述解空間的概率模型。

將第z個(gè)子群在執(zhí)行SFLA局部搜索的第q次迭代時(shí)，子群內(nèi)具有最優(yōu)適應(yīng)度的可行解表示為每個(gè)元素的取值范圍為［1, s］上的整數(shù)。根據(jù)所有子群內(nèi)最優(yōu)適應(yīng)度可行解的信息，得到如公式（6）所示的初始化群體每一列的取值情況，計(jì)算得到如公式（7）所示的描述解空間的概率模型上取值為j(1≤j≤m)的概率如公式（6）、（7）：

步驟2：評(píng)估種群中的個(gè)體，并從中選取適應(yīng)度較高的個(gè)體集合，運(yùn)用統(tǒng)計(jì)學(xué)習(xí)等方法對(duì)概率模型進(jìn)行更新。

計(jì)算群體Yqb中L個(gè)個(gè)體的適應(yīng)度，從中選擇最優(yōu)的W(W

2.3 分布估計(jì)蛙跳算法

混合蛙跳算法中，通過向子群內(nèi)具有最優(yōu)適應(yīng)度的可行解Yb學(xué)習(xí)，該子群內(nèi)適應(yīng)度最差的可行解Yw得到更新，而只有當(dāng)更新后得到的可行解newYw的適應(yīng)度優(yōu)于Yb時(shí)，子群內(nèi)具有最優(yōu)適應(yīng)度的可行解Yb才能得到更新。這不僅造成混合蛙跳算法的全局收斂速度較慢，而且導(dǎo)致其容易陷入局部最優(yōu)[8]。

本文通過將混合蛙跳算法和分布估計(jì)算法相結(jié)合，根據(jù)所有子群內(nèi)最優(yōu)適應(yīng)度可行解的信息，建立一個(gè)描述解空間內(nèi)優(yōu)質(zhì)解分布的概率模型，使適應(yīng)度最差的可行解的每一次更新信息都來自該概率模型，而不像混合蛙跳算法中適應(yīng)度最差的可行解只向該子群內(nèi)的最優(yōu)適應(yīng)度可行解學(xué)習(xí)，從而增進(jìn)子群間的學(xué)習(xí)與協(xié)作，使算法具有更為全面的學(xué)習(xí)能力，避免陷入局部最優(yōu)。此外，在執(zhí)行局部搜索的每一次迭代時(shí)，概率模型和各子群內(nèi)的最優(yōu)適應(yīng)度可行解都將依據(jù)種群中的優(yōu)質(zhì)個(gè)體進(jìn)行更新，加速子群進(jìn)化，算法的收斂速度得到提高。

分布估計(jì)蛙跳算法(EDSFLA) 的具體步驟如下：

步驟1：初始化。隨機(jī)生成N只青蛙組成初始蛙群。步驟2：排序。計(jì)算每只青蛙的適應(yīng)度F(i)，對(duì)青蛙個(gè)體按照適應(yīng)度進(jìn)行降序排序。

步驟3：子群劃分。將蛙群劃分為L(zhǎng)個(gè)子群。步驟4：在各子群內(nèi)執(zhí)行局部搜索：

步驟4-1 設(shè)numdd為子群內(nèi)部進(jìn)行局部搜索的迭代次數(shù)，ddz為設(shè)定的局部搜索總次數(shù)，初始化numdd=1；

步驟4-2 根據(jù)個(gè)體的適應(yīng)度，確定各子群內(nèi)的最優(yōu)適應(yīng)度可行解Yb和最差適應(yīng)度可行解Yw；

步驟4-5 將W個(gè)最優(yōu)適應(yīng)度可行解隨機(jī)放入各個(gè)子群內(nèi)，若新放入的可行解的適應(yīng)度優(yōu)于子群內(nèi)的最優(yōu)適應(yīng)度可行解Yb，則Yb被替換，否則保持不變;

步驟4-6 根據(jù)公式(5)更新各子群中的最差適應(yīng)度可行解Yw；若newYw的適應(yīng)度優(yōu)于Yw，則用newYw代替Yw，否則就用中適應(yīng)度最好的可行解代替Yb，根據(jù)公式(5)重新更新Yw，如果更新后可行解的適應(yīng)度仍然沒有改進(jìn)，則隨機(jī)選擇一個(gè)可行解來替代Yw；

步驟4-7 若numdd

步驟5：全局信息交換。當(dāng)所有子群結(jié)束一輪的局部搜索之后，將所有子群進(jìn)行混合，完成全局信息交換并記錄全局最優(yōu)解Yg；

步驟6：計(jì)算并檢驗(yàn)終止條件。若滿足終止條件，則算法結(jié)束；否則轉(zhuǎn)到步驟二重新執(zhí)行排序和子群劃分。通常，如果算法在經(jīng)過連續(xù)幾次的全局信息交換之后，全局最優(yōu)解未能得到顯著改進(jìn)則算法強(qiáng)制退出。

3 仿真實(shí)驗(yàn)與性能分析

為了測(cè)試本文提出的資源調(diào)度算法的性能，在云計(jì)算仿真平臺(tái)CloudSim上進(jìn)行仿真實(shí)驗(yàn)，選擇混合蛙跳算法和遺傳算法與本文算法EDSFLA作對(duì)比實(shí)驗(yàn)。參數(shù)設(shè)置如下：種群規(guī)模N=300，子群個(gè)數(shù)L=30，子群內(nèi)青蛙個(gè)數(shù)M=10，子群內(nèi)的局部搜索次數(shù)ddz=15。

3.1 不同任務(wù)數(shù)量下的算法性能對(duì)比

在云計(jì)算的資源數(shù)量固定不變，任務(wù)數(shù)量不斷變化的情況下，SFLA、GA與EDSFLA，3種算法在進(jìn)行資源調(diào)度時(shí)的性能變化曲線如圖1所示：

圖1 不同任務(wù)數(shù)量下平均完成時(shí)間對(duì)比

從圖1可以看出，3種算法在處理較少數(shù)量的任務(wù)時(shí)，資源調(diào)度所表現(xiàn)出的性能非常相近，這主要是因?yàn)椋合鄬?duì)于數(shù)量較少的待處理任務(wù)，云資源的數(shù)量比較充足，因此，在處理任務(wù)時(shí)基本上不會(huì)出現(xiàn)資源競(jìng)爭(zhēng)現(xiàn)象。隨著云計(jì)算任務(wù)量的增加，3種算法所需的任務(wù)處理時(shí)間都在不斷增多，其中，任務(wù)的平均完成時(shí)間增長(zhǎng)速度最快是遺傳算法GA，混合蛙跳算法SFLA次之，變化最為緩慢的是EDSFLA。因此，相較于SFLA和GA兩種算法，在運(yùn)用同等數(shù)量的資源處理較大的任務(wù)量時(shí)，EDSFLA具有較優(yōu)的資源調(diào)度性能。

3.2 不同資源數(shù)量下的算法性能對(duì)比

在云計(jì)算的任務(wù)數(shù)量固定不變，資源數(shù)量不斷變化的情況下，SFLA、GA和EDSFLA，3種算法在進(jìn)行資源調(diào)度時(shí)的性能變化曲線如圖2所示：

圖2 不同資源數(shù)量下平均完成時(shí)間對(duì)比

仿真實(shí)驗(yàn)參數(shù)設(shè)置為：任務(wù)數(shù)量t=30，每個(gè)任務(wù)被劃分的子任務(wù)數(shù)Nx=20，重復(fù)執(zhí)行該實(shí)驗(yàn)5次取平均結(jié)果。

從圖2可以看出，隨著資源數(shù)量的不斷增加，任務(wù)的平均完成時(shí)間逐漸減少，且相較于 SFLA 和 GA兩種算法，本文提出的資源調(diào)度算法EDSFLA完成任務(wù)所需時(shí)間最短，資源調(diào)度性能最優(yōu)。由于結(jié)合了混合蛙跳算法和分布估計(jì)算法，在有效避免陷入局部最優(yōu)的同時(shí)，還加快了算法的收斂速度。

4 總結(jié)

基于分布估計(jì)蛙跳算法的資源調(diào)度策略通過將分布估計(jì)算法引入混合蛙跳算法的局部搜索環(huán)節(jié)，根據(jù)所有子群最優(yōu)適應(yīng)度可行解的信息建立一個(gè)描述優(yōu)質(zhì)解分布的概率模型，使適應(yīng)度最差的可行解的每一次更新信息都來自該概率模型，此外，在執(zhí)行局部搜索的每一次迭代時(shí)，依據(jù)種群中優(yōu)質(zhì)個(gè)體的信息，概率模型和各子群的最優(yōu)適應(yīng)度可行解都會(huì)得到更新。該算法在通過增強(qiáng)算法的全面學(xué)習(xí)能力有效避免陷入局部最優(yōu)的同時(shí)，還使得算法的全局收斂性能得到提升。

參考文獻(xiàn)

[1] MELL P, GRANCE T. The NIST Definition of Cloud Computing[R]. National Institute of Standards and Technology, 2011.

[2] 劉衛(wèi)寧,靳洪兵,劉波.基于改進(jìn)量子遺傳算法的云計(jì)算資源調(diào)度[J].計(jì)算機(jī)應(yīng)用,2013,33(8):2151-2153.

[3] 左利云,左利鋒.云資源中多目標(biāo)集成蟻群優(yōu)化調(diào)度算法[J].計(jì)算機(jī)應(yīng)用,2012,32(7):1916-1919.

[4] 劉萬軍,張孟華,郭文越.基于MPSO 算法的云計(jì)算資源調(diào)度策略[J].計(jì)算機(jī)工程,2011,37(11):43-48.

[5] 金偉健,王春枝.基于蝙蝠算法的云計(jì)算資源分配研究[J].計(jì)算機(jī)應(yīng)用研究,2014,32(9):121～124.

[6] 孫大為,常桂然,李鳳云等. 一種基于免疫克隆的偏好多維QoS云資源調(diào)度優(yōu)化算法[J].電子學(xué)報(bào),2011,39(8):18 24-1831.

[7] EUSUFF M M, LANSEY K E. Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[C]//Proc of Word Water Congress.2004:111.

[8] 張恒巍,衛(wèi)波,王晉東等.基于分布估計(jì)蛙跳算法的云資源調(diào)度方法[J].計(jì)算機(jī)應(yīng)用研究,2014,31(11):3225-3228. [9] 周樹德,孫增圻.分布估計(jì)算法綜述[J].自動(dòng)化學(xué)報(bào),2007,33(2):113-124.

TP181

A

2015.01.13）

1007-757X(2015)07-0059-03

寧菲菲（1985-），女，漢族，河南省平頂山人，平頂山學(xué)院，軟件學(xué)院，助教，碩士，研究方向：無線傳感器網(wǎng)絡(luò)與云計(jì)算，平頂山，467000

王建璽（1981-），女，漢族，河南社旗人，碩士，平頂山學(xué)院，軟件學(xué)院，講師，碩士，研究方向：計(jì)算機(jī)圖像處理與模式識(shí)別，平頂山，467000