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

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

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

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

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

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

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

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

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

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

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

00000000…00000000=0 umin

00000000…00000001=1 umin+δ

……

11111111…11111111=2l–1 umax

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

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

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

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

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

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

三、算法性能的正確評(píng)估

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

四、總結(jié)

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

參 考 文 獻(xiàn)

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

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

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

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