云計算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略

【摘要】 資源調(diào)度是云計算的核心問題，傳統(tǒng)的遺傳算法雖然可以用于云計算環(huán)境中的資源調(diào)度，但是由于傳統(tǒng)遺傳算法存在收斂慢、易早熟等特點，所以這種算法并不適應(yīng)于多聚類環(huán)境下的密集型任務(wù)調(diào)度?；诖?，我們提出了云計算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略以彌補傳統(tǒng)遺傳算法的不足。本文主要通過對云計算概念的介紹以及如何優(yōu)化遺傳算法的資源調(diào)度策略來展開討論。

【關(guān)鍵詞】 云計算環(huán)境概念 優(yōu)化遺傳算法 資源調(diào)度策略

近些年來，隨著計算機(jī)技術(shù)的飛速發(fā)展，云計算計算模式應(yīng)運而生。Web2.0技術(shù)以及系統(tǒng)虛擬化等技術(shù)的發(fā)展促進(jìn)了云計算的不斷完善。目前，云計算被廣泛地應(yīng)用于商業(yè)計算。它作為下一代并行與分布式計算，具有超大規(guī)模、抽象化、高可靠性、通用性等特點，受到國內(nèi)各領(lǐng)域的廣泛關(guān)注。接下來，我們就具體的介紹云計算環(huán)境中如何通過資源調(diào)度策略進(jìn)行優(yōu)化遺傳算法。

一、云計算技術(shù)概述

隨著計算機(jī)技術(shù)的發(fā)展以及計算模式的創(chuàng)新，云計算成為一種新的計算模式。云計算是一種將分布式計算、并行計算、網(wǎng)格計算、虛擬化計算以及Web服務(wù)等技術(shù)進(jìn)行融合和結(jié)合新的計算機(jī)技術(shù)而形成的新的計算方式。它的優(yōu)點更加突出，計算方式更加便捷，計算結(jié)果更加權(quán)威。隨著現(xiàn)代技術(shù)的不斷發(fā)展，云計算也逐漸應(yīng)用到各個領(lǐng)域之中。

通過對云計算的整體評估和了解，我們將云計算分為兩個方面。一方面是能夠提供用來構(gòu)造應(yīng)用程序的基礎(chǔ)設(shè)施，包括計算機(jī)方面的硬件設(shè)施和軟件設(shè)施。這一方面使得云計算能夠涵蓋一般計算方式的特點，并突破了傳統(tǒng)計算方式的束縛。另一方面是提供建立在基礎(chǔ)設(shè)施上的云應(yīng)用。通過建立在基礎(chǔ)設(shè)施上的云應(yīng)用，不僅可以增加基礎(chǔ)設(shè)施本身的應(yīng)用范圍，而且能夠擴(kuò)大云應(yīng)用的適用范圍，將云應(yīng)用應(yīng)用到更多的領(lǐng)域之中。

我們除了根據(jù)云應(yīng)用的功能將其非為兩個方面之外，還根據(jù)它的使用者將其分為私有云和公共云。顧名思義，私有云是私人專有的云，需要用戶自行購買硬件設(shè)備，然后自己通過所購買的設(shè)備進(jìn)行維護(hù)整個系統(tǒng)，系統(tǒng)中的所有數(shù)據(jù)均是用戶自己進(jìn)行管理的，信息內(nèi)容也是和用戶密切相關(guān)的，用戶對于系統(tǒng)的管理具有自主性。私有云的規(guī)模相對有限，在使用的過程中，由于只有簡單的硬件基礎(chǔ)設(shè)備，所以云計算的高性能性和高性價比的優(yōu)勢不能夠充分的顯示出來。而對于公共云來說，這些方面就是有云服務(wù)提供商所提供的，并不需要用戶進(jìn)行投資。公共云的使用中，用戶不需要自行購買設(shè)備，也不需要自己進(jìn)行系統(tǒng)的維護(hù)。他們只需要向云服務(wù)提供商支付一定的費用，就可以免費的使用云計算。整個公共云系統(tǒng)的設(shè)備維護(hù)和管理以及系統(tǒng)的升級的工作都是由云服務(wù)提供商負(fù)責(zé)，不需要用戶進(jìn)行管理。這就使得公共云在使用和維護(hù)中具有具有更大的靈活性和成本優(yōu)勢。

二、優(yōu)化遺傳算法的資源調(diào)度策略

接下來，我們根據(jù)Baidu的MaP/Reduce模型，對云計算環(huán)境下優(yōu)化遺傳算法的資源調(diào)度策略進(jìn)行具體的介紹。首先，在傳統(tǒng)的遺傳算法中，我們所采用的是一種基于染色體編碼方式和適應(yīng)度函數(shù)改進(jìn)的遺傳算法去實現(xiàn)分布式大規(guī)模任務(wù)的資源調(diào)度。在這個過程中，我們通常是將任務(wù)總數(shù)作為染色體基因串的長度，而具體到每一個任務(wù)時，我們會將每一個任務(wù)所映射的資源ID作為染色體的基因值。但是這種做法會造成系統(tǒng)的超載，編碼的基因串的長度遠(yuǎn)遠(yuǎn)地超過了基因池內(nèi)的資源總數(shù)，所以在具體的計算時會造成算法進(jìn)化速度慢，并且容易出現(xiàn)錯誤的情況，由于在基因池內(nèi)無法找到相應(yīng)的資源，所以有些基因串在具體的計算中可能會出現(xiàn)亂碼和無法計算的情況，最終導(dǎo)致收斂到最優(yōu)解的時間過長。

云計算模式的出現(xiàn)很好的解決了這一技術(shù)難題，它彌補了傳統(tǒng)的遺傳計算方式的缺陷，在技術(shù)上完善了傳統(tǒng)遺傳計算方式。在云計算環(huán)境中，我們改進(jìn)了染色體的編碼方式，通過將資源總數(shù)作為染色體的基因串長度、每個資源所映射的任務(wù)總數(shù)以及任務(wù)ID作為染色體的基因值來加快算法的收斂速度。這種編碼方式所形成的基因串的總數(shù)小于系統(tǒng)資源池內(nèi)的總數(shù)，所以在計算過程中可以達(dá)到最優(yōu)的資源調(diào)度，從而達(dá)到提高計算速度和計算準(zhǔn)確度的目的。這也是云計算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略的方式之一，同時也是被各個領(lǐng)域所接受并廣泛應(yīng)用的原因之一。這種改進(jìn)染色體編碼的形式，很好的彌補了傳統(tǒng)遺傳計算的缺陷，不僅能夠全面的提高收斂速度，而且還能夠提高正確率以增加通過遺傳計算來正確預(yù)測種群進(jìn)化方向的目標(biāo)。另外，由于云計算環(huán)境的動態(tài)異構(gòu)的特性，所以我們在對適應(yīng)度函數(shù)進(jìn)行設(shè)計的時候，不僅要充分的考慮到資源節(jié)點動態(tài)的任務(wù)處理能力，還要充分的考慮到異構(gòu)環(huán)境下任務(wù)的映射時間和結(jié)果的匯聚時間問題。只有充分的考慮到這兩個方面，我們才能夠在云計算環(huán)境中對遺傳計算實現(xiàn)最有計算。與此同時，在算法的初始階段和接近收斂的階段，還要對適應(yīng)度函數(shù)作出調(diào)整，確保通過最優(yōu)的遺傳計算來預(yù)測種群的正確進(jìn)化方向以及尋求更廣闊的尋優(yōu)空間。

1、染色體的編碼和種群的初始化。染色體本身的編碼方式有很多，這里我們采用資源-任務(wù)的間接實數(shù)編碼方式來進(jìn)行介紹。這種編碼方式的的主要步驟是：首先對染色體進(jìn)行預(yù)編碼，設(shè)有m個任務(wù)，設(shè)定任務(wù)的ID={1；2；3；4，…，m}，n個資源節(jié)點，設(shè)定資源的ID={1，2，3，…，n}，那么我們就可以得到染色體的基因串長度為任務(wù)總數(shù)m，染色體基因值為資源ID。假設(shè)某一參數(shù)的取值范圍是[umin，umax]，我們用長度為l的二進(jìn)制編碼符號串來表示該參數(shù)，則它總共能夠產(chǎn)生 2l種不同的編碼，參數(shù)編碼時的對應(yīng)關(guān)系如下：

00000000…00000000=0 umin

00000000…00000001=1 umin+δ

……

11111111…11111111=2l–1 umax

其中，δ為二進(jìn)制編碼的編碼精度。

當(dāng)我們確定了染色體的編碼方式之后，還需要進(jìn)行種群的初始化，由于初始的種群具有多樣性和不確定性，所以在這里我們采用隨機(jī)的方式來產(chǎn)生初始種群，種群的大小我們設(shè)定為Scale。下面是由初始化種群形成適應(yīng)度值最優(yōu)的染色體的圖解。

2、基于最優(yōu)跨度和負(fù)載均衡的雙適應(yīng)度函數(shù)。適應(yīng)度函數(shù)是通過最有跨度和負(fù)載均衡來衡量的。對于任何一種染色體來說，它的任務(wù)資源分配方案的最優(yōu)跨度應(yīng)該是該分配方案下最晚完成任務(wù)的資源節(jié)點所用的總?cè)蝿?wù)的執(zhí)行時間。

3、選擇復(fù)制。遺傳算法對個體適應(yīng)性的評價方式是選擇操作。選擇操作也是實現(xiàn)群體優(yōu)良基因傳播的基本方式。在科研角度上通過選擇復(fù)制可以將種群內(nèi)的基因進(jìn)行自由的組合，從而組合出最優(yōu)的基因組和。

4、交叉。產(chǎn)生新個體的主要方法是交叉算子。交叉算子能夠決定遺傳算法的全局搜索能力。在具體的操作中，我們從全局的角度出發(fā)去尋找交叉對。即基因重組。交叉對是按照較大的概率從群體中選擇2個個體進(jìn)行交換2個個體某位或某些位基因。通過對交叉對的研究，我們能夠?qū)⒎N群內(nèi)的基因進(jìn)行簡單的組合，從而發(fā)現(xiàn)最優(yōu)基因以及簡單的對種群的進(jìn)化方向進(jìn)行預(yù)測等。

5、變異。產(chǎn)生新個體的輔助方法則是變異算子。交叉算子雖然能夠?qū)崿F(xiàn)全局搜索，但是它卻做不到對搜索空間的細(xì)節(jié)進(jìn)行局部的搜索。在這個時候，如果我們采用變異算子來調(diào)整個體編碼串中的部分基因值，就可以從局部角度出發(fā)式個體更加逼近最優(yōu)解。交叉算子和變異算子的完美結(jié)合有利于我們在遺傳算法中進(jìn)行全面的搜索能力的提高。

三、算法性能的正確評估

上面我們采用的Baidu中的MaP/Reduce模型進(jìn)行介紹，接下來我們通過對云仿真器上的CloudSim進(jìn)行仿真計算的介紹。CloudSim是在離散時間模擬包SimJava上開發(fā)的一種函數(shù)庫，CloudSim繼承了GridSim的編程模型，不僅突破了原有模型的局限性而且形成了屬于自己的一套新型計算模式。CloudSim具有以下幾個特點：首先，CloudSim能夠做到支持大型云計算的基礎(chǔ)設(shè)施的建模和仿真，這對于傳統(tǒng)的仿真計算模式來說是不可能實現(xiàn)的。其次CloudSim是一個自足的支持?jǐn)?shù)據(jù)中心、服務(wù)代理人、調(diào)度和分配策略的平臺。該平臺包含了各種軟件結(jié)構(gòu)框架和體系結(jié)構(gòu)組件，從而擴(kuò)大了資源池的資源總數(shù)，并且所包含的大量軟件對提高收斂速度也有很大的幫助，對提高遺傳計算的正確率也就不言而喻了。CloudSim所包含的軟件結(jié)構(gòu)框架和體系結(jié)構(gòu)組件包括SimJava、GridSim、CloudSim、UserCode4各層次。其中的CIS和DataCenterBroker能夠很好的實現(xiàn)資源發(fā)現(xiàn)和信息交互，這是整個CloudSim模擬調(diào)度的核心，這種算法主要是在DataCenterBroker中實現(xiàn)的。這兩個特點很好的體現(xiàn)了改進(jìn)后的遺傳算法的優(yōu)點，使得改進(jìn)后的遺傳算法比傳統(tǒng)的遺傳算法的收斂速度更快，性能更優(yōu)秀。這兩點不僅僅表現(xiàn)在任務(wù)執(zhí)行時間最短上面，同時也表現(xiàn)在能夠滿足資源負(fù)載均衡上面。它可以很好的用于大梁任務(wù)的資源調(diào)度上。而進(jìn)行大量的資源調(diào)度正是云計算環(huán)境的特性以及它被廣泛應(yīng)用在各個領(lǐng)域的主要原因。所以，本位所提出來的遺傳算法能夠很好的使用在云計算環(huán)境中的資源調(diào)度上面。

四、總結(jié)

本文提出了一種改進(jìn)遺傳算法的資源調(diào)度算法，該方法是參考云計算的Map/Reduce模型，在染色體編碼上結(jié)合云計算環(huán)境中海量數(shù)據(jù)處理和大規(guī)模任務(wù)執(zhí)行的特性，設(shè)計合理的染色體編碼方案，通過對目標(biāo)函數(shù)的設(shè)定，設(shè)計出一種基于最有跨度和負(fù)載均衡的雙適應(yīng)度函數(shù)，然后再結(jié)合云計算環(huán)境中的其他系統(tǒng)的配合，通過資源調(diào)度策略達(dá)到遺傳算法的最優(yōu)。

參 考 文 獻(xiàn)

[1] 英海燕，王友波. 基于自適應(yīng)遺傳算法的模板匹配研究[J]. 微電子學(xué)與計算機(jī). 2008（01）

[2] 李冰. 云計算環(huán)境下動態(tài)資源管理關(guān)鍵技術(shù)研究[D]. 北京郵電大學(xué). 2012

[3] 葛新. 基于云計算集群擴(kuò)展中的調(diào)度問題研究[D]. 中國科學(xué)技術(shù)大學(xué). 2011

[4] 李棟. 基于經(jīng)濟(jì)原則的網(wǎng)格調(diào)度系統(tǒng)研究[D]. 北京化工大學(xué)，2012年