楊威

摘 要：任務(wù)調(diào)度是云計算領(lǐng)域所要研究的核心問題，主要研究最優(yōu)的任務(wù)分配策略，以使得任務(wù)得到均衡的分配或使得每個任務(wù)的執(zhí)行代價降到最低或系統(tǒng)的總體性能達(dá)到最優(yōu)。云計算中任務(wù)調(diào)度算法的好壞直接影響云計算系統(tǒng)整體性能。本文對當(dāng)前云計算的調(diào)度算法進(jìn)行了綜述；介紹和分析了在云計算調(diào)度算法領(lǐng)域里比較有代表性的兩個基本的算法--遺傳算法和粒子群優(yōu)化算法。

關(guān)鍵詞：云計算；任務(wù)調(diào)度；遺傳算法；粒子群優(yōu)化算法

1.引言

云計算是一種基于互聯(lián)網(wǎng)的新的服務(wù)模式，這種模式按使用量付費，提供可用的、便捷的、按需的網(wǎng)絡(luò)訪問，它將用戶需求的計算任務(wù)分布在由大量計算機(jī)構(gòu)成的數(shù)據(jù)中心，數(shù)據(jù)中心采用虛擬化技術(shù)，把各種軟硬件資源抽象為虛擬化資源，再通過資源調(diào)度技術(shù)使各種應(yīng)用能夠根據(jù)需要獲取計算能力、存儲空間和信息服務(wù)[1]。

云計算任務(wù)調(diào)度的目的是給需要的用戶分配不同的資源，在滿足用戶需求的前提下，使得任務(wù)完成時間盡量小，且資源利用率盡量高。調(diào)度最終要實現(xiàn)時間跨度、服務(wù)質(zhì)量、負(fù)載均衡、經(jīng)濟(jì)原則最優(yōu)等目標(biāo)。云計算任務(wù)調(diào)度是云計算研究中的重點和難點。任務(wù)調(diào)度算法的優(yōu)劣會影響到云計算系統(tǒng)處理任務(wù)的能力。

本文綜述了云環(huán)境下的任務(wù)調(diào)度算法，分析了近幾年來典型的云計算任務(wù)調(diào)度算法的發(fā)展趨勢。

1 遺傳算法[2][3]

1.1 遺傳算法的概念

遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，它利用一定的編碼技術(shù)和繁殖機(jī)制來處理復(fù)雜現(xiàn)象，適用于處理云計算環(huán)境中大規(guī)模、多種類資源的調(diào)度；是一種較好的云計算調(diào)度算法。

1.2 遺傳算法的主要求解過程

遺傳算法將問題的求解過程表示成"染色體"適者生存的過程，通過"染色體"群的一代代不斷進(jìn)化，包括選擇、交叉和變異等操作，最終收斂到"最適應(yīng)環(huán)境"的個體，從而求得問題的最優(yōu)解或滿意解。

遺傳算法的基本運算過程如下：

（1）初始化：設(shè)置進(jìn)化代數(shù)計數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個個體作為初始群體P（0）。

（2）個體評價：計算群體P（t）中各個個體的適應(yīng)度。

（3）選擇運算：將選擇算子作用于群體。目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。

（4）交叉運算：所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。

（5）變異運算：即對群體中的個體串的某些基因座上的基因值作變動。群體P（t）經(jīng)過選擇、交叉、變異運算之后得到下一代群體P（t1）。

（6）終止條件判斷：若t=T，以進(jìn)化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。

1.3 遺傳算法的主要特點

（1）傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。

（2）遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實現(xiàn)并行化。

（3）遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索時，適應(yīng)度大的個體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。

1.4 遺傳操作的三個基本遺傳算子

1.4.1 選擇

從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫選擇。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的，目前常用的選擇算子有以下幾種：適應(yīng)度比例方法、隨機(jī)遍歷抽樣法、局部選擇法。

1.4.2 交叉

在自然界生物進(jìn)化過程中起核心作用的是生物遺傳基因的重組（加上變異）。遺傳算法中起核心作用的是遺傳操作的交叉算子。交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。

1.4.3 變異

變異算子的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。

遺傳算法引入變異的目的： 一是使遺傳算法具有局部的隨機(jī)搜索能力。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。此時收斂概率應(yīng)取較大值。

遺傳算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力[4]。如何有效地配合使用交叉和變異操作，是目前遺傳算法的一個重要研究內(nèi)容。

2 粒子群優(yōu)化算法[5]

2.1 粒子群優(yōu)化算法的概念

粒子群優(yōu)化又稱粒子群算法，群粒子群優(yōu)化算法是一種模擬鳥群覓食行為的演化計算算法。因其結(jié)構(gòu)簡單、參數(shù)少、易實現(xiàn)，所以受到廣泛重視并被應(yīng)用到了許多自然科學(xué)和工程科學(xué)領(lǐng)域。在云環(huán)境中，用粒子群優(yōu)化算法進(jìn)行資源調(diào)度能得到較好的效果。

2.2 算法原理

將每個個體看作是D維搜索空間中的一個沒有體積的微粒，在搜索空間中以一定的速度飛行。第i個微粒表示為Xi=（xi1，xi2，...，xiD），它經(jīng)歷過的最好位置記為Pi=（pi1，pi2，...，piD），也稱為pbest。在群體所有微粒經(jīng)歷過的最好位置的索引號用符號g表示，即Pg，也稱為gbest。微粒i的速度用Vi=（vi1，vi2，...，viD）表示。它的第d維（1≤d≤D）根據(jù)如下方程進(jìn)行變化：

vid=w*vid+c1*rand（）*（pid-xid）+c2*Rand（）*（pgd-xid）（1）

xid=xid+vid （2）

其中w為慣性權(quán)重，c1和c2為加速常數(shù)，rand（）和Rand（）為兩個在[0，1]范圍里變化的隨機(jī)值。

2.3 標(biāo)準(zhǔn)粒子群算法的算法流程

（1）初始化一群微粒（群體規(guī)模為m），包括隨機(jī)的位置和速度；

（2）評價每個微粒的適應(yīng)度；

（3）對每個微粒，將它的適應(yīng)值和它經(jīng)歷過的最好位置pbest比較，如果較好，則將其作為當(dāng)前的最好位置pbest；

（4） 對每個微粒，將它的適應(yīng)值和全局所經(jīng)歷最好位置gbest比較，如果較好，則重新設(shè)置gbest的索引號；

（5）根據(jù)（1）變化微粒的速度和位置；

（6）如未達(dá)到結(jié)束條件回到（2）。

3 總結(jié)和展望

在云計算中面對的用戶群是龐大的，而遺傳算法主要通過交叉算子繁殖后代，當(dāng)交叉算子所作用的兩個個體相同時，不能產(chǎn)生有意義的新個體，因此要求初始種群具有廣泛的多樣性，所以遺傳算法用在云計算調(diào)度中會產(chǎn)生較好的效果，是一種有效的云計算調(diào)度算法。但是遺傳算法在群體進(jìn)化到其中各個個體均非常相似時，僅靠變異算子產(chǎn)生新的個體，遺傳迭代難以進(jìn)行下去，容易發(fā)生所謂的"早熟收斂"現(xiàn)象，如何有效地配合使用交叉和變異操作以防止這種現(xiàn)象的發(fā)生，是遺傳算法的一個研究重點。

粒子群優(yōu)化算法是一種基于群體的自適應(yīng)搜索優(yōu)化算法，對于云環(huán)境中大規(guī)模、多種類的資源調(diào)度是一種有效的云計算調(diào)度算法。因其結(jié)構(gòu)簡單、參數(shù)少、易實現(xiàn)，所以受到廣泛重視并被應(yīng)用到了許多自然科學(xué)和工程科學(xué)領(lǐng)域。但對于存在較多局部極值的搜索空間，它很容易陷入局部最優(yōu)，在進(jìn)化后期收斂速度慢，如何避免粒子群優(yōu)化算法陷入局部最優(yōu)，是以后研究的一個重要方向。

參考文獻(xiàn)

[1]張艷敏.云計算中任務(wù)調(diào)度算法的研究綜述.[J].電子商務(wù)，2016.7

[2]葛繼科，邱玉輝，吳春明，蒲國林. 遺傳算法研究綜述[ J ] . 計算機(jī)應(yīng)用研究，2008.10

[3]王小平，曹立明.遺傳算法[ M ].西安：西安交通大學(xué)出版社，2002.

[4]劉東山，周顯春.云計算調(diào)度算法綜述.[J]計算機(jī)安全，2012.10

[5]楊偉新，張曉森.甘肅科技[J].2012.5

本文是安徽財經(jīng)大學(xué)科研項目：《自適應(yīng)云服務(wù)組合優(yōu)化算法研究》（ACKY1435）的研究成果。