王靜++陳家琪

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

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

DOIDOI：10.11907/rjdk.162082

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：16727800（2016）011005303

0 引言

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

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

1.1 任務(wù)模型

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

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

1.2 任務(wù)模型建立

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

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

2.1 染色體編碼

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

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

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

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

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

2.3 交叉與變異

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

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

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

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

2.5 算法流程

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

3 仿真實驗與結(jié)果分析

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

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

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

4 結(jié)語

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

參考文獻：

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

[2] 馮龍華.云環(huán)境下基于貪心模型的作業(yè)調(diào)度算法研究與實現(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] 周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(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] 李敏強，寇紀淞.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2004.

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