一種改進(jìn)的遺傳算法在云計(jì)算中的應(yīng)用

陳曉燕，姚高偉，張 鯤，王海豐

(1. 瓊州學(xué)院 計(jì)算機(jī)工程學(xué)院，海南 三亞 572022；2. 信陽師范學(xué)院 城市與環(huán)境科學(xué)學(xué)院，河南 信陽 464000)

0 引言

隨著計(jì)算機(jī)的發(fā)展，人們對(duì)其存儲(chǔ)和傳輸能力的要求也隨之變高，云計(jì)算應(yīng)運(yùn)而生.云計(jì)算是一種大規(guī)模的分布式計(jì)算模型，它把存儲(chǔ)于個(gè)人電腦、移動(dòng)電話和其他設(shè)備上的大量信息和處理器資源集中在一起，協(xié)同工作.它充分利用虛化技術(shù)，將用戶從軟件、硬件和資源的管理中解放出來，并將這些負(fù)擔(dān)轉(zhuǎn)移給云計(jì)算服務(wù)供應(yīng)商[1].

為了充分利用云計(jì)算的各種優(yōu)勢(shì)，將人們從繁重的資源管理中解脫出來，人們已經(jīng)將所有的任務(wù)放在了云環(huán)境下執(zhí)行.大量的任務(wù)放在云環(huán)境下，使得云計(jì)算系統(tǒng)每時(shí)每刻都處在海量任務(wù)之中[2-3].因此，對(duì)用戶提交的海量任務(wù)進(jìn)行有效的調(diào)度，使得用戶提交的任務(wù)處理時(shí)間短，所需的費(fèi)用低，并且保證云系統(tǒng)負(fù)載均衡，是云計(jì)算技術(shù)中研究的重點(diǎn)問題.

目前解決云環(huán)境下的任務(wù)調(diào)度問題主要是從任務(wù)執(zhí)行所花費(fèi)的時(shí)間以及執(zhí)行任務(wù)所需的費(fèi)用方面展開的，國內(nèi)外對(duì)于云環(huán)境下任務(wù)調(diào)度問題的算法研究成果還比較少.文獻(xiàn)[4]提出了基于蟻群算法的云計(jì)算資源調(diào)度算法，在算法的設(shè)計(jì)中，只考慮了對(duì)任務(wù)執(zhí)行時(shí)間進(jìn)行優(yōu)化，沒有考慮到任務(wù)調(diào)度中其他的問題.文獻(xiàn)[5-6]提出了多目標(biāo)遺傳算法，算法中涉及的任務(wù)調(diào)度優(yōu)化目標(biāo)過多，在遺傳算法下，優(yōu)化目標(biāo)過多，會(huì)造成局部收斂，而難以達(dá)到全局優(yōu)化.本文將任務(wù)調(diào)度中執(zhí)行任務(wù)所需時(shí)間和執(zhí)行任務(wù)所需費(fèi)用這兩個(gè)重要的因素作為優(yōu)化目標(biāo)，提出了改進(jìn)的遺傳算法，仿真實(shí)驗(yàn)驗(yàn)證了其良好的性能.

1 任務(wù)調(diào)度與遺傳算法

1.1 任務(wù)調(diào)度概述

目前云計(jì)算中的調(diào)度方式大多采用的是預(yù)分配機(jī)制下的靜態(tài)資源調(diào)度方法，這種方式下的任務(wù)調(diào)度，沒有體現(xiàn)“按需分配”的思想，會(huì)出現(xiàn)小任務(wù)調(diào)用大資源的情況，造成資源的不必要浪費(fèi)[7].在云計(jì)算中，任務(wù)調(diào)度的核心技術(shù)在于所采用的調(diào)度算法.國內(nèi)外的很多專家、學(xué)者針對(duì)云計(jì)算中的任務(wù)調(diào)度，提出了一些算法，如蟻群算法、粒子群算法、遺傳算法，其中用得最為廣泛的是遺傳算法.但是傳統(tǒng)的遺傳算法自身有缺陷，如迭代次數(shù)多，算法運(yùn)行耗時(shí)長，這樣大大降低了整個(gè)云計(jì)算環(huán)境的性能.云計(jì)算中的任務(wù)調(diào)度如圖1所示.

圖1 云計(jì)算中任務(wù)調(diào)度圖

云計(jì)算的任務(wù)調(diào)度過程分三個(gè)階段，其中最重要的階段就是調(diào)度技術(shù)所處的階段，調(diào)度技術(shù)的優(yōu)劣直接關(guān)系到任務(wù)調(diào)度的結(jié)果.云計(jì)算中所采用的任務(wù)調(diào)度技術(shù)，就是把不同的任務(wù)分配到合適的虛擬機(jī)上的方式，具體的過程如下：(1)給所有的任務(wù)開始分配虛擬機(jī)；(2)任務(wù)分配結(jié)束后，虛擬機(jī)開始執(zhí)行任務(wù)；(3)任務(wù)執(zhí)行出相應(yīng)的結(jié)果(即調(diào)度結(jié)果).所得出的調(diào)度結(jié)果就是評(píng)價(jià)這個(gè)調(diào)度技術(shù)優(yōu)劣的標(biāo)準(zhǔn).

1.2 遺傳算法

遺傳算法(Genetic Algorithm，簡稱GA)起源于20世紀(jì)60年代，借鑒生物學(xué)中進(jìn)化論的思想，從中提取的一種進(jìn)化算法，借助計(jì)算機(jī)模擬在種群的繁殖過程中，父代遺傳基因的重組和優(yōu)勝劣汰，主要用來解決科學(xué)研究中的復(fù)雜問題[8].遺傳算法的步驟如圖2所示.

對(duì)于云計(jì)算中的資源，最完美的狀態(tài)是用戶的請(qǐng)求得到滿足，并且處理速度快，所花的費(fèi)用少，所用的資源管理代價(jià)最小.這對(duì)云計(jì)算中的任務(wù)調(diào)度來說，是一個(gè)NP難問題[9].遺傳算法是一種仿生型優(yōu)化算法，通過生物學(xué)中的優(yōu)勝劣汰原理，將最優(yōu)的個(gè)體遺傳到下一代，這種算法思想使得算法的并行性和全局尋優(yōu)能力得到了最大的體現(xiàn)，也使得遺傳算法在解決NP難問題中有絕對(duì)的優(yōu)勢(shì)[10].

云環(huán)境下的任務(wù)調(diào)度是保證用戶服務(wù)質(zhì)量，提高云環(huán)境下資源利用率的關(guān)鍵.因此，針對(duì)傳統(tǒng)遺傳算法存在的問題，本文結(jié)合遺傳算法的全局尋優(yōu)能力，提出了一種改進(jìn)的遺傳算法，將其應(yīng)用于云計(jì)算中的任務(wù)調(diào)度，主要從執(zhí)行時(shí)間以及執(zhí)行任務(wù)所需的費(fèi)用這兩個(gè)方面來進(jìn)行優(yōu)化，用此算法去求解云環(huán)境下的任務(wù)調(diào)度問題.

圖2 遺傳算法流程圖

2 改進(jìn)的遺傳算法在云計(jì)算中的設(shè)計(jì)

在云環(huán)境下，將任務(wù)執(zhí)行所花費(fèi)的時(shí)間以及所需的費(fèi)用作為適應(yīng)度函數(shù)，充分考慮了云環(huán)境的彈性功能，避免了在無限資源的云環(huán)境下，將初始問題變成單一標(biāo)準(zhǔn)問題或單一約束問題.本文選取的時(shí)間函數(shù)和費(fèi)用函數(shù)雖然忽略了云環(huán)境下的能量消耗、網(wǎng)絡(luò)可靠性，但從總的來說，是從用戶的角度來看待問題的，考慮的是用戶最關(guān)心的問題，讓用戶得到了更好的體驗(yàn)，體現(xiàn)了云計(jì)算面向服務(wù)的宗旨.

2.1 任務(wù)調(diào)度模型設(shè)計(jì)

對(duì)于云環(huán)境中的任務(wù)、虛擬機(jī)以及任務(wù)與虛擬機(jī)之間的關(guān)系進(jìn)行數(shù)學(xué)描述如下.

(1)任務(wù)序列為task={t1,t2,…，tm},其中t1代表第1個(gè)任務(wù)，依次類推，tm代表第m個(gè)任務(wù).

(2)虛擬機(jī)序列為vm={vm1,vm2,…,vmn},其中vm1代表第1個(gè)虛擬機(jī)，依次類推，vmn代表第n個(gè)虛擬機(jī).

(3)任務(wù)與虛擬機(jī)的關(guān)聯(lián),vm(ti)表示執(zhí)行任務(wù)(ti)的虛擬機(jī).

2.2 染色體編碼

在遺傳算法中用染色體編碼表示種群中的個(gè)體，在云環(huán)境下的任務(wù)需要分配到虛擬資源上，一個(gè)染色體表示一種任務(wù)分配方案.每個(gè)染色體中，基因數(shù)目和任務(wù)數(shù)量相等，基因的值最高為虛擬機(jī)數(shù)量.本文使用二維串的方法作為調(diào)度方案：一維表示任務(wù)到資源當(dāng)中的映射,另一維則表示任務(wù)的執(zhí)行順序.編碼前，先對(duì)任務(wù)建立一個(gè)關(guān)系矩陣JZ,用JZij來表示任務(wù)ti和tj之間的關(guān)系.如果JZij=1，ti是tj的父任務(wù)；如果JZij=0，則表示任務(wù)ti與任務(wù)tj沒有關(guān)系.

先對(duì)任務(wù)到資源當(dāng)中的映射進(jìn)行編碼，然后再對(duì)第二維進(jìn)行編碼，具體的操作步驟如下：

(1)初始化.假定集合set為空，存放始任務(wù)(即沒有父任務(wù)的任務(wù)).

(2)依據(jù)關(guān)系矩陣JZ，將父任務(wù)已經(jīng)調(diào)度完的任務(wù)，或者是沒有父任務(wù)的任務(wù)放入集合set中，通過JZij的值來判斷任務(wù)的調(diào)度情況.

(3)對(duì)二維串上第一個(gè)沒有被調(diào)度的任務(wù)進(jìn)行判斷，如果它在集合set中，就把它放進(jìn)調(diào)度序列中去.

(4)將步驟(3)中被調(diào)度的任務(wù)從集合set中除去.

(5)重復(fù)步驟(2)至步驟(4)，直到調(diào)度完所有的任務(wù).

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

在遺傳算法中，各個(gè)解的優(yōu)劣是通過適應(yīng)度函數(shù)來衡量的，適應(yīng)度值高的個(gè)體將會(huì)遺傳到下一代中去，而適應(yīng)度值低的個(gè)體則在遺傳的過程中被淘汰掉.因此，適應(yīng)度函數(shù)其實(shí)就是目標(biāo)優(yōu)化函數(shù).然而，傳統(tǒng)的遺傳算法一般是以單個(gè)目標(biāo)來設(shè)計(jì)適應(yīng)度函數(shù)的，而云環(huán)境比較復(fù)雜，所要考慮的目標(biāo)不再是單一的，因此，傳統(tǒng)的遺傳算法不適用于云環(huán)境中的任務(wù)調(diào)度.

本文主要考慮的是云環(huán)境下任務(wù)調(diào)度中兩個(gè)重要的優(yōu)化目標(biāo)：時(shí)間目標(biāo)和費(fèi)用目標(biāo).

本文改進(jìn)的遺傳算法用在云計(jì)算中，使得云環(huán)境下任務(wù)調(diào)度完成任務(wù)的時(shí)間最短，所需的費(fèi)用最低，因此，約束函數(shù)由兩個(gè)組成:一個(gè)是時(shí)間目標(biāo)函數(shù)，一個(gè)是費(fèi)用目標(biāo)函數(shù).

(1)時(shí)間目標(biāo)函數(shù)

最早開始執(zhí)行時(shí)間設(shè)為ts,最早結(jié)束時(shí)間設(shè)為tf,進(jìn)入系統(tǒng)的任務(wù)設(shè)定為tinput,對(duì)于ts和tf,可建立如下的關(guān)系式：

ts(tinput)=0,

(1)

tf(tinput)=ts(tinput)+te(ti,vmj),

(2)

其中：te為任務(wù)執(zhí)行時(shí)間，vmj表示在虛擬機(jī)上執(zhí)行的第j個(gè)任務(wù).

對(duì)于其他任務(wù)來說，ts和tf的值可以通過遞歸的方式進(jìn)行計(jì)算得出，式子如下：

tf(ti)=ts(ti)+te(ti,vm(ti)),

(3)

(4)

其中：set(ti)是任務(wù)ti父結(jié)點(diǎn)的集合，一個(gè)任務(wù)可以有很多個(gè)父節(jié)點(diǎn)，子節(jié)點(diǎn)執(zhí)行任務(wù)，必須等到所有父節(jié)點(diǎn)執(zhí)行完之后，子任務(wù)開始執(zhí)行的時(shí)間為集合set(ti)中數(shù)據(jù)最晚到達(dá)子任務(wù)的時(shí)間；tt為傳輸時(shí)間.

(2)費(fèi)用目標(biāo)函數(shù)

云環(huán)境下執(zhí)行任務(wù)的費(fèi)用由兩部分組成：數(shù)據(jù)傳輸所需的費(fèi)用、虛擬機(jī)執(zhí)行任務(wù)所需的費(fèi)用.費(fèi)用目標(biāo)函數(shù)表示如下：

(5)

其中：ec為單個(gè)任務(wù)執(zhí)行的費(fèi)用，vm(ti)表示執(zhí)行任務(wù)(ti)的虛擬機(jī)，tc表示在虛擬機(jī)vm(ti)上執(zhí)行的任務(wù)(ti)產(chǎn)生的數(shù)據(jù)傳輸給在虛擬機(jī)vm(tp)上執(zhí)行的任務(wù)(tp)所產(chǎn)生的費(fèi)用.

2.4 界限函數(shù)

對(duì)于時(shí)間目標(biāo)函數(shù)和費(fèi)用目標(biāo)函數(shù)，關(guān)鍵在于求其下限，下限的求解方法如下：

(1)時(shí)間界限函數(shù)

時(shí)間界限函數(shù)求解的是在虛擬機(jī)上執(zhí)行任務(wù)的時(shí)間最小值，計(jì)算方法如下：

tt(ti,tj)=et(tj,vm(ti))-et(tj,vm(tj)),

(6)

其中：tt為傳輸時(shí)間，et為單個(gè)任務(wù)的執(zhí)行時(shí)間，tj表示任務(wù)j，vm(ti)表示執(zhí)行任務(wù)(ti)的虛擬機(jī).

(2)費(fèi)用界限函數(shù)

費(fèi)用界限函數(shù)求解的是在虛擬機(jī)上執(zhí)行任務(wù)的費(fèi)用最小值，計(jì)算方法如下：

tc(ti,tj)=ec(tj,vm(tj))-ec(ti,vm(ti)),

(7)

其中：tc為傳輸費(fèi)用，ec為單個(gè)任務(wù)執(zhí)行的費(fèi)用.

對(duì)于云計(jì)算環(huán)境下的用戶來說，任務(wù)調(diào)度所需的時(shí)間和費(fèi)用是越少越好，綜合上文的時(shí)間目標(biāo)函數(shù)和費(fèi)用目標(biāo)函數(shù)，適應(yīng)度函數(shù)如下：

f=ωts(ti)+(1-ω)cost，

(8)

其中：ω為權(quán)重系數(shù)，其值在0到1之間，任務(wù)執(zhí)行的時(shí)間越少，ω越大；任務(wù)執(zhí)行所需的費(fèi)用越少，ω越小.當(dāng)ω=1時(shí)，則是從時(shí)間的角度進(jìn)行優(yōu)化；當(dāng)ω=0時(shí)，則是從費(fèi)用的角度進(jìn)行優(yōu)化.

2.5 遺傳操作

(1)選擇算子

本文改進(jìn)的遺傳算法主要是從時(shí)間函數(shù)和費(fèi)用函數(shù)這兩個(gè)角度來考慮的，算子的選擇既要維持多樣性，又要保證收斂性.在遺傳算法中,是通過輪盤賭的方式來表示選擇算子，個(gè)體的適應(yīng)度值越大，則被選中遺傳到下一代的概率就越大；個(gè)體適應(yīng)度值越小,則被選中的概率越小.

染色體的適應(yīng)度值為f,選擇概率為g，則可建立如下的式子：

(9)

(2)交叉算子

交叉算子是遺傳算法中重要的操作，交叉操作在一定程度上克服了遺傳算法的早熟收斂問題，可以保證種群中個(gè)體多樣性.

交叉操作的本質(zhì)是希望通過組合的方式，產(chǎn)生比較優(yōu)秀的個(gè)體.本文進(jìn)行交叉操作的具體步驟如下：

(i)從所有的任務(wù)資源中隨機(jī)選取兩個(gè)任務(wù)作為父代個(gè)體.

(ii)從(i)中產(chǎn)生的父代個(gè)體中選取一個(gè)作為交叉點(diǎn)，進(jìn)行變異的部分即為交叉點(diǎn)之前的任務(wù)和處于交叉點(diǎn)的任務(wù).

(iii)根據(jù)矩陣JZ，重新分配任務(wù)的執(zhí)行順序，產(chǎn)生兩個(gè)新的個(gè)體.

(3)變異算子

變異是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個(gè)新的個(gè)體.變異操作的具體步驟如下：

(i)從所有的任務(wù)資源中隨機(jī)的選取一個(gè)任務(wù)作為父代個(gè)體.

(ii)從(i)中產(chǎn)生的父代個(gè)體中隨機(jī)選擇變異點(diǎn)，然后將一個(gè)可執(zhí)行的虛擬資源分配給處于這個(gè)變異點(diǎn)的任務(wù).

(iii)根據(jù)矩陣JZ，重新分配任務(wù)的執(zhí)行順序，產(chǎn)生兩個(gè)新的個(gè)體.

2.6 算法終止條件

同其他算法一樣，云環(huán)境下的任務(wù)調(diào)度算法同樣需要有算法終止條件來終止算法.在云環(huán)境下的任務(wù)調(diào)度，時(shí)間與花費(fèi)成反比的關(guān)系，本文采用迭代的次數(shù)作為算法終止條件，當(dāng)?shù)螖?shù)達(dá)到一定數(shù)量，就是算法預(yù)期的結(jié)果.

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

仿真實(shí)驗(yàn)主要目的是將本文的改進(jìn)遺傳算法應(yīng)用到不同的云計(jì)算模擬場景中，對(duì)改進(jìn)的遺傳算法與傳統(tǒng)的遺傳算法進(jìn)行對(duì)比實(shí)驗(yàn)，分析實(shí)驗(yàn)的結(jié)果，以驗(yàn)證該改進(jìn)的遺傳在云計(jì)算中的有效性.

3.1 實(shí)驗(yàn)設(shè)備

本實(shí)驗(yàn)用到的設(shè)備有：操作系統(tǒng)Windows XP，MyEclipse，云仿真模擬器CloudSim.

3.2 參數(shù)設(shè)計(jì)

云環(huán)境下，假設(shè)資源是無限的，可以按照實(shí)際的需求使用，虛擬機(jī)上能執(zhí)行任何任務(wù).驗(yàn)證算法在云環(huán)境中所起到的作用，假設(shè)種群的規(guī)模為20，任務(wù)數(shù)為20，虛擬機(jī)個(gè)數(shù)為5，變異概率為0.1，迭代次數(shù)為100，在算法結(jié)束后，對(duì)最后一代中各個(gè)解個(gè)體的分布情況進(jìn)行驗(yàn)證.圖3和圖4是將改進(jìn)的遺傳算法用于任務(wù)調(diào)度與傳統(tǒng)遺傳算法的任務(wù)調(diào)度，所需的平均等待時(shí)間以及所需費(fèi)用的對(duì)比圖.

從圖3中看出，在任務(wù)數(shù)目同等的情況下，改進(jìn)的遺傳算法下的平均等待時(shí)間比傳統(tǒng)遺傳算法相對(duì)來說所需少些.從圖4中可以看出，時(shí)間相同的情況下，改進(jìn)的遺傳算法下的任務(wù)調(diào)度所需要的費(fèi)用要比傳統(tǒng)遺傳算法下的低.

圖3 平均等待時(shí)間對(duì)比圖

圖4 執(zhí)行任務(wù)所產(chǎn)生的費(fèi)用對(duì)比圖

4 結(jié)論

本文提出了改進(jìn)的遺傳算法應(yīng)用于云計(jì)算中的任務(wù)調(diào)度，并針對(duì)任務(wù)調(diào)度中的執(zhí)行時(shí)間和費(fèi)用，設(shè)計(jì)了適應(yīng)度函數(shù)、交叉算子、變異算子.實(shí)驗(yàn)結(jié)果表明，在云環(huán)境下，該算法應(yīng)用于任務(wù)調(diào)度有一定的優(yōu)勢(shì).