云計(jì)算調(diào)度算法綜述

楊威

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

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

1.引言

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

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

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

1 遺傳算法[2][3]

1.1 遺傳算法的概念

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

1.2 遺傳算法的主要求解過(guò)程

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

遺傳算法的基本運(yùn)算過(guò)程如下：

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

（2）個(gè)體評(píng)價(jià)：計(jì)算群體P（t）中各個(gè)個(gè)體的適應(yīng)度。

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

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

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

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

1.3 遺傳算法的主要特點(diǎn)

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

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

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

1.4 遺傳操作的三個(gè)基本遺傳算子

1.4.1 選擇

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

1.4.2 交叉

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

1.4.3 變異

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

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

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

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

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

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

2.2 算法原理

將每個(gè)個(gè)體看作是D維搜索空間中的一個(gè)沒(méi)有體積的微粒，在搜索空間中以一定的速度飛行。第i個(gè)微粒表示為Xi=（xi1，xi2，...，xiD），它經(jīng)歷過(guò)的最好位置記為Pi=（pi1，pi2，...，piD），也稱為pbest。在群體所有微粒經(jīng)歷過(guò)的最好位置的索引號(hào)用符號(hào)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（）為兩個(gè)在[0，1]范圍里變化的隨機(jī)值。

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

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

（2）評(píng)價(jià)每個(gè)微粒的適應(yīng)度；

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

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

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

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

3 總結(jié)和展望

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

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

參考文獻(xiàn)

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

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

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

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

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

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