云計(jì)算環(huán)境中優(yōu)化混合遺傳算法的資源調(diào)度研究

王靜++陳家琪

摘 要：將云計(jì)算傳統(tǒng)的遺傳算法應(yīng)用到任務(wù)調(diào)度中，存在迭代次數(shù)多、資源利用率低、執(zhí)行時(shí)間長(zhǎng)等問(wèn)題。因此，提出貪心算法來(lái)初始化種群，以避免隨機(jī)初始化種群時(shí)基因的低表現(xiàn)性，并且引進(jìn)精英因子到傳統(tǒng)遺傳算法中以優(yōu)化收斂速度。設(shè)計(jì)出雙適應(yīng)度函數(shù)，兼顧考慮用戶對(duì)執(zhí)行時(shí)間和帶寬的要求，通過(guò)采用可適應(yīng)交叉和變異方法，提升算法的全局收斂能力。仿真實(shí)驗(yàn)結(jié)果表明，在云計(jì)算的任務(wù)調(diào)度中使用優(yōu)化混合遺傳算法能更加有效地解決資源調(diào)度問(wèn)題。

關(guān)鍵詞關(guān)鍵詞：混合遺傳算法；云計(jì)算；資源調(diào)度；精英因子

DOIDOI：10.11907/rjdk.162082

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：16727800（2016）011005303

0 引言

云計(jì)算是一種新型計(jì)算模型，它在提供靈活、高性能、可支付、按需傳達(dá)的服務(wù)上具有很大優(yōu)勢(shì)[1]。如果工作花費(fèi)時(shí)間太長(zhǎng)，將會(huì)降低用戶滿意度[2]。因此，高效率實(shí)現(xiàn)任務(wù)調(diào)度成為云計(jì)算中需要解決的核心問(wèn)題之一。遺傳算法作為啟發(fā)式算法，在組合優(yōu)化方面顯示了特殊優(yōu)勢(shì)[3]。近年來(lái)，對(duì)遺傳算法的應(yīng)用發(fā)展迅速，尤其適用于解決科學(xué)和工程領(lǐng)域中的復(fù)雜問(wèn)題。然而，在解決高維函數(shù)優(yōu)化問(wèn)題中，由于存在一些嚴(yán)格的限制條件，導(dǎo)致了傳統(tǒng)遺傳算法的低效。因此，本文提出一種優(yōu)化混合遺傳算法，它能在一定程度上解決傳統(tǒng)遺傳算法在資源調(diào)度上的收斂時(shí)間長(zhǎng)、資源利用率低、平均任務(wù)花費(fèi)時(shí)間長(zhǎng)等問(wèn)題[4]。

1 任務(wù)模型及其建立

1.1 任務(wù)模型

分析云計(jì)算模型是為了理清任務(wù)之間的關(guān)系（優(yōu)先關(guān)系），以便于將其充分地并行化。云計(jì)算數(shù)據(jù)中心可以實(shí)現(xiàn)任務(wù)的并行化執(zhí)行，由此提高運(yùn)行效率。為了簡(jiǎn)單描述，建立以下數(shù)學(xué)模型：假設(shè)任務(wù)集用戶提交的：T={t1、t2......tn}，ti是第i個(gè)子任務(wù)。因?yàn)檫\(yùn)行是并行執(zhí)行的，總運(yùn)行時(shí)間由最長(zhǎng)運(yùn)行時(shí)間的資源決定。

云計(jì)算任務(wù)關(guān)系可以分為兩種：依賴(lài)與沖突[5]。前者指任務(wù)在數(shù)據(jù)和控制上的相關(guān)。例如，當(dāng)作函數(shù)依賴(lài)相關(guān)測(cè)試時(shí)，t1將調(diào)用t2的函數(shù)，或t2是否被執(zhí)行由t1決定。后者意味著環(huán)境的沖突或任務(wù)間的并發(fā)沖突。如在性能測(cè)試中，t1應(yīng)該被Apache服務(wù)器支持，但t2想要IIS服務(wù)器，或t1和t2有著一樣的網(wǎng)絡(luò)端口。因此，對(duì)于獨(dú)立任務(wù)，中心將在一樣的資源上被調(diào)度，否則不僅浪費(fèi)了網(wǎng)絡(luò)帶寬，也會(huì)在數(shù)據(jù)傳輸過(guò)程中出現(xiàn)錯(cuò)誤。但為了避免一些不必要的錯(cuò)誤，對(duì)于沖突的任務(wù)，它們會(huì)被在不同的并行資源上執(zhí)行。

1.2 任務(wù)模型建立

對(duì)于集合T，假設(shè)存在n*n的相關(guān)性矩陣，該矩陣是由第k個(gè)任務(wù)和第1個(gè)任務(wù)的關(guān)系所建立。它的元素值是-1、0、1。1代表tK和t1是獨(dú)立的，0代表tk和t1之間無(wú)關(guān)，-1代表tk和t1之間相互沖突。根據(jù)相關(guān)性矩陣，數(shù)據(jù)中心可以創(chuàng)建一個(gè)新集合T′={t1′，t2′，....，ts′}，s≤n，稱(chēng)其為并行向量集。ts′是一個(gè)向量，它包括集合T的一個(gè)或多個(gè)元素。集合T′是任務(wù)組項(xiàng)目，它有著最大并行度，數(shù)據(jù)中心可以分配任務(wù)ts′到一個(gè)計(jì)算結(jié)點(diǎn)，以實(shí)現(xiàn)有效率的并行計(jì)算。例如，假設(shè)一個(gè)集合T（T={t1，t2，t3，t4，t5，t6}），相關(guān)性矩陣定義如下：

2 優(yōu)化混合遺傳算法資源調(diào)度

2.1 染色體編碼

根據(jù)基因算法準(zhǔn)則，首先應(yīng)該編碼染色體。本文使用間接編碼，染色體長(zhǎng)度是任務(wù)的量，在染色體中每一個(gè)基因值被相應(yīng)任務(wù)分配資源標(biāo)識(shí)。

假設(shè)有6個(gè)任務(wù)，T′={t1′={t1，t2}，t2′={t3，t4}，t3′={t5}，t4′={t6}}，所以有4個(gè)并行組等待調(diào)度。假設(shè)有3個(gè)在系統(tǒng)中的計(jì)算資源，染色體長(zhǎng)度為3，每一個(gè)染色體表示1～3的排列。例如，染色體{1，2，2，3}代表t1′在第1號(hào)資源上執(zhí)行，t2′和t3′在第2號(hào)資源上執(zhí)行，t4′在第3號(hào)資源上執(zhí)行。

編碼之后，在各個(gè)資源上的任務(wù)分配則是明確的。基于此，數(shù)據(jù)中心將預(yù)測(cè)任務(wù)執(zhí)行時(shí)間和創(chuàng)建預(yù)測(cè)執(zhí)行時(shí)間矩陣ET。ET（i，j）代表第j個(gè)計(jì)算節(jié)點(diǎn)花費(fèi)在第i個(gè)并行任務(wù)上的預(yù)測(cè)執(zhí)行時(shí)間。

2.2 適應(yīng)度函數(shù)

基因算法模擬自然界中最佳適應(yīng)的原則進(jìn)行搜索過(guò)程，在該過(guò)程中，適應(yīng)度函數(shù)是群體中個(gè)體質(zhì)量的準(zhǔn)則[6]。云計(jì)算資源調(diào)度是一個(gè)多目標(biāo)優(yōu)化問(wèn)題。本文定義了兩個(gè)適應(yīng)度函數(shù)，擁有較少帶寬負(fù)載和時(shí)間花費(fèi)的個(gè)體具有更好的適應(yīng)度。采用一個(gè)權(quán)重向量來(lái)衡量用戶對(duì)兩個(gè)目標(biāo)的重視程度不同：

2.3 交叉與變異

交叉操作指兩個(gè)匹配的個(gè)體根據(jù)一定模式交換基因的一部分，從而產(chǎn)生兩個(gè)新個(gè)體，其目的在于提升基因算法的全局搜索能力[7]。變異意味著子代中染色體編碼值的改變，它可以探索出新的搜索空間和局部最優(yōu)解的收斂。本文使用可適應(yīng)的基因算法，交叉幾率函數(shù)和變異幾率函數(shù)定義如下：

2.4 優(yōu)化混合基因算法實(shí)現(xiàn)

本文使用貪心算法進(jìn)行群體初始化。假設(shè)被處理的工作是充足的，沒(méi)有優(yōu)先級(jí)。為了限制大量數(shù)據(jù)遷移，數(shù)據(jù)的本地性也應(yīng)被考慮進(jìn)去。

在初始群體被創(chuàng)造以后，經(jīng)過(guò)一代代的適應(yīng)度篩選，進(jìn)化得越來(lái)越好，越來(lái)越近似于最優(yōu)解。然后通過(guò)選擇、交叉和變異，新一代產(chǎn)生，它代表一個(gè)新的解決方法。最好的解決方法將作為精英因子被選擇，在若干代進(jìn)化之后，不好的解決方法將會(huì)減少。優(yōu)化混合遺傳算法的基本步驟如下：

2.5 算法流程

算法流程如下：①根據(jù)待解問(wèn)題的任務(wù)模型進(jìn)行編碼；②利用貪心算法初始化群體；③計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度值；④按照由個(gè)體適應(yīng)值所決定的某個(gè)規(guī)則選擇進(jìn)入下一代的個(gè)體；⑤引入精英因子，將高適應(yīng)度的個(gè)體直接選擇出來(lái)不參與下一次迭代；⑥按交叉概率Pc進(jìn)行交叉操作；⑦按變異概率Pm進(jìn)行變異操作；⑧如果沒(méi)有滿足迭代次數(shù)要求，則轉(zhuǎn)到第3步，否則進(jìn)入第9步；⑨輸出種群中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿意解或最優(yōu)解。

3 仿真實(shí)驗(yàn)與結(jié)果分析

本文使用CloudSim作為仿真平臺(tái)，實(shí)驗(yàn)?zāi)康氖菍⒈疚牡膬?yōu)化混合遺傳算法和傳統(tǒng)遺傳算法進(jìn)行對(duì)比實(shí)驗(yàn)。初始實(shí)驗(yàn)參數(shù)設(shè)置如下：最大迭代次數(shù)200，資源個(gè)數(shù)50，作業(yè)總數(shù)30，每個(gè)作業(yè)被劃分為任務(wù)的數(shù)量范圍是[1，90]，初始交叉概率0.8，初始變異概率0.2，設(shè)置（w1，w2）={0.4，0.6}。

由圖1可以看出，隨著遺傳迭代次數(shù)增加，平均任務(wù)運(yùn)行時(shí)間也逐漸減少，但改進(jìn)后的優(yōu)化混合遺傳算法變化率曲線整體上要低于原始的收斂性曲線。并且可以看出，傳統(tǒng)遺傳算法最終收斂于局部最優(yōu)值220，而優(yōu)化混合遺傳算法的收斂速度比原始收斂速度快，平均執(zhí)行時(shí)間比原始平均執(zhí)行時(shí)間短，與理論分析一致。

對(duì)于用戶而言，適應(yīng)度值大于等于0是可以接受的。由圖2可以看出，隨著遺傳迭代次數(shù)增加，群體適應(yīng)度越來(lái)越好，但改進(jìn)后的優(yōu)化混合遺傳算法變化率曲線整體上要高于原始收斂性曲線。傳統(tǒng)遺傳算法最終收斂于0.1，而優(yōu)化混合遺傳算法最終收斂于0.4。也即是說(shuō)，優(yōu)化混合遺傳算法平均適應(yīng)度值要高于原始遺傳算法。并且在相同的遺傳迭代次數(shù)下，優(yōu)化混合遺傳算法的收斂速度比原始收斂速度快，與理論分析一致。

4 結(jié)語(yǔ)

本文提出了引入精英因子的混合遺傳算法，并將其應(yīng)用于云計(jì)算的資源調(diào)度中，設(shè)計(jì)了同時(shí)考慮時(shí)間和帶寬的雙適應(yīng)度函數(shù)，并使用貪心算法初始化群體。仿真實(shí)驗(yàn)表明，在云環(huán)境下，將該算法應(yīng)用于資源調(diào)度中具有一定優(yōu)勢(shì)。然而，本文的資源調(diào)度策略只考慮了當(dāng)下的系統(tǒng)狀態(tài)，沒(méi)有考慮到系統(tǒng)變量與歷史數(shù)據(jù)，這可能導(dǎo)致系統(tǒng)負(fù)載失衡，相關(guān)工作還有待下一步研究。

參考文獻(xiàn)：

[1] 江建.精英自適應(yīng)混合遺傳算法及其實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（27）：3435.

[2] 馮龍華.云環(huán)境下基于貪心模型的作業(yè)調(diào)度算法研究與實(shí)現(xiàn)[D].重慶：重慶大學(xué)，2014.

[3] W LIN，C LIANG，J Z WANG，et al. Bandwidthaware divisible task scheduling for cloud computing[J].Software：Practice and Experience，2014（2）：163174.

[4] HU BAOFANG，SUN XIULI，LI YING，et al.An improved adaptive genetic algorithm in cloud computing[C].Parallel and Distributed Computing，Applications and Technologies （PDCAT），13th International Conference on，2012：294，297.

[5] 周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2002.

[6] ORVOSH D，DAVIS L.Using a genetic algorithm to optimize problems with feasibility constraints[C].Proc of 1st IEEE Conf on Evolutionary Computation，1994：548553.

[7] 李敏強(qiáng)，寇紀(jì)淞.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2004.

（責(zé)任編輯：黃 ?。?