基于遺傳算法的網(wǎng)格任務(wù)調(diào)度方法分析

金智

（長(zhǎng)沙醫(yī)學(xué)院，湖南 長(zhǎng)沙 410219）

1 引言

隨著互聯(lián)網(wǎng)信息技術(shù)的發(fā)展，網(wǎng)格系統(tǒng)也在大量的資源計(jì)算中投入使用。網(wǎng)格任務(wù)調(diào)度能夠把各種資源形成一個(gè)整體，通過互聯(lián)網(wǎng)絡(luò)進(jìn)行資源的合理分配與共享，從而完成用戶的資源請(qǐng)求。而遺傳算法是基于生物雜交與變異的研究方法，通過搜索方式、獲取過程的優(yōu)化，來達(dá)到全局搜索最優(yōu)解的目的[1]。遺傳算法突破了求導(dǎo)和函數(shù)連續(xù)性的規(guī)則限制，在多種智能信息處理領(lǐng)域得到廣泛應(yīng)用。

2 網(wǎng)格任務(wù)調(diào)度的問題描述與定義

在任務(wù)信息、資源信息和任務(wù)時(shí)限確定的情況下，運(yùn)用遺傳算法進(jìn)行任務(wù)的執(zhí)行之前，本文主要進(jìn)行以下的問題定義：在NxM的矩陣[N,M]中，Time[i,j]代表任務(wù)Ti在資源Rj上中的任務(wù)處理時(shí)限。T={T1、T2、T3、……、Tm}，代表任務(wù)集合；R={R1、R2、R3、……、Rn}，代表資源集合。

網(wǎng)格任務(wù)間的依賴關(guān)系，可以用有方向無環(huán)路的圖表進(jìn)行表示。在G=(T，E，V)這一有方向無環(huán)路圖表中，T代表任務(wù)集合，E代表網(wǎng)格任務(wù)關(guān)系圖中的邊數(shù)集合，V代表給定邊的權(quán)合集。G=(T，E，V)上的一個(gè)割將該圖的頂點(diǎn)分成兩個(gè)子集：V＝A＋B，而（Ti，Tj）∈E代表Ti任務(wù)先執(zhí)行，Ti執(zhí)行完畢后再執(zhí)行Tj，其中Ti和Tj屬于前項(xiàng)與后項(xiàng)的關(guān)系。將A設(shè)置為有方向無環(huán)路圖表的調(diào)度方案，WAS(A)代表A調(diào)度方案中資源集合所耗費(fèi)的任務(wù)時(shí)限，公式為WAS(A)=max{WA(Ri)，i=1，……，n}。因此在網(wǎng)格任務(wù)調(diào)度中，需要選擇恰當(dāng)?shù)恼{(diào)度方案，以盡可能降低資源集合所耗費(fèi)的任務(wù)時(shí)限[2]。

對(duì)于有方向無環(huán)路的任務(wù)圖表，其中頂端階段的深度值為1，由根節(jié)點(diǎn)往下每增加一層深度值也相應(yīng)加1，而任務(wù)圖表的高度值則與深度值的算法相反。設(shè)Ti為有方向無環(huán)路數(shù)據(jù)結(jié)構(gòu)中的某一節(jié)點(diǎn)，Ti的前項(xiàng)可以用固定在前面的pre（Ti）表示，Ti的深度值用 H（Ti）表示。

在有方向無環(huán)路任務(wù)圖表中，對(duì)每個(gè)網(wǎng)格任務(wù)的深度值進(jìn)行計(jì)算，通過以上計(jì)算可以得出：若任務(wù)圖表中的最大深度值為h，則該網(wǎng)格的任務(wù)集合就有h個(gè)。從圖1中可以看出：{T1，T2}深度值為1，{T3，T4}、{T4，T5}的深度值為 2，{T6，T7}的深度值為3。若該網(wǎng)格中有R1、R2兩個(gè)資源集合，則需要對(duì)圖1的h個(gè)任務(wù)集合進(jìn)行兩兩排列，則總的任務(wù)執(zhí)行序列為{T1，T2，T3，T4，T5，T7，T6}，也就是按照{(diào)R1R2，R1R2，R1R2，R1}的資源分配方式進(jìn)行分配。在該網(wǎng)格任務(wù)調(diào)度中，主要運(yùn)用非降序的深度數(shù)值排列方式，進(jìn)行任務(wù)依賴關(guān)系的表示，因此該排序?qū)儆诤侠淼娜蝿?wù)調(diào)度方法。網(wǎng)格任務(wù)調(diào)度的圖1如下所示[3]：

圖1 網(wǎng)格任務(wù)依賴關(guān)系圖

3 基于遺傳算法的任務(wù)調(diào)度算法設(shè)計(jì)

3.1 網(wǎng)格任務(wù)調(diào)度的編碼

在網(wǎng)格任務(wù)調(diào)度的二進(jìn)制編碼中，由于存在能夠復(fù)制的對(duì)偶基因，而產(chǎn)生相應(yīng)的任務(wù)調(diào)度問題。所以運(yùn)用實(shí)數(shù)1和0的字符串進(jìn)行編碼，能夠有效解決等位基因的問題。實(shí)數(shù)1和0的字符串編碼，其主要存在搜索范圍廣、搜索精度高等特征。米凱利維茨在《遺傳算法和數(shù)據(jù)編碼結(jié)合》一書中表明：二進(jìn)制編碼是具有層次性的進(jìn)化個(gè)體，而實(shí)數(shù)編碼的每個(gè)基因位用某一范圍內(nèi)的一個(gè)浮點(diǎn)來表示，個(gè)體的編碼長(zhǎng)度取決于決策量的個(gè)數(shù)[4]。

網(wǎng)格任務(wù)調(diào)度的編碼規(guī)則為：假設(shè)網(wǎng)格有m個(gè)任務(wù)集合、n個(gè)資源集合，選擇[1,n]之間的m個(gè)整數(shù)集合，共同組成G染色體集合G=[g1，g2，g3，……，gn]其中g(shù)[j]代表染色體中單個(gè)基因的編號(hào)，g[j]可以是[1,n]集合中的任意一組數(shù)值，[1,n]代表資源集合編號(hào)。大多數(shù)染色體中的基因數(shù)值都不相同，但也有某些基因數(shù)值是相同的，相同的基因數(shù)值代表不同任務(wù)在相同資源集合中完成。

3.2 網(wǎng)格任務(wù)調(diào)度的遺傳操作

3.2.1 遺傳算法的復(fù)制與選擇

根據(jù)以上公式計(jì)算出網(wǎng)格任務(wù)適應(yīng)度數(shù)值后，將各個(gè)適應(yīng)度數(shù)值采用輪賭盤進(jìn)行群體中的個(gè)體選擇。例如：個(gè)體1、2、3對(duì)應(yīng)的適應(yīng)度分別為2、3、1，則相應(yīng)累計(jì)概率為2/6、(2+3)/6和(2+3+1)/6，生成一個(gè)隨機(jī)函數(shù)為rand()。如果rand()<2/6則選中個(gè)體1，如果2/6

遺傳算法的雜交，主要為模擬基因進(jìn)化的有性繁殖過程。其通過基因重組將良性基因傳遞給下一代，并完成復(fù)雜的基因重組操作。遺傳算法的雜交主要包括以下幾方面內(nèi)容：(1)設(shè)定交叉概率Pc；(2)隨機(jī)生成[0，1]間的數(shù)b，若b

本文使用均勻雜交的遺傳算法，對(duì)實(shí)數(shù)1和0的字符串進(jìn)行同概率雜交。設(shè)生成的新雜交個(gè)體為：s1'={a11，a12，……，a1L}，s2'={a21，a22，……，a2L}，具體公式如下所示 U(Pc，x)：均勻分布的變量）

3.2.3 遺傳算法的變異

遺傳算法的變異，主要仿照同一基因庫中不同個(gè)體之間的分子差異，而進(jìn)行實(shí)數(shù)1和0的字符串進(jìn)化的方法。遺傳算法將變異算子作用于群體，對(duì)群體中個(gè)體串某些基因座上的基因值進(jìn)行變動(dòng)，其變動(dòng)的概率也為P。但遺傳算法的變異，主要為了改善個(gè)體雜交后的適應(yīng)度數(shù)值，從而幫助全局進(jìn)化達(dá)到最優(yōu)解。因此遺傳算法變異對(duì)個(gè)體基因信息的改動(dòng)很小，通過彌補(bǔ)對(duì)偶基因的丟失，來促進(jìn)群體中個(gè)體差異的增大。因此雜交操作后引入變異，能夠有效提升遺傳算法的搜索性能。

4 基于遺傳算法的仿真實(shí)驗(yàn)及結(jié)果分析

遺傳算法仿真實(shí)驗(yàn)的主要參數(shù)為：交叉概率Pc=0.8、變異概率Pm=0.15、種群個(gè)數(shù)P=80和迭代次數(shù)G=300。同時(shí)將一致雜交與精英選擇、一致雜交、單點(diǎn)雜交與精英選擇的數(shù)值，放入任務(wù)數(shù)據(jù)圖表中，具體如圖2所示：

圖2 任務(wù)調(diào)度數(shù)據(jù)圖

從以上數(shù)據(jù)表中可以得出：遺傳算法在進(jìn)化代數(shù)較小的時(shí)候，三種數(shù)據(jù)的適應(yīng)度收斂的速度很快。而隨著優(yōu)良個(gè)體的篩選與排除，多個(gè)種群的適應(yīng)度數(shù)值開始增大，但其收斂速度則開始減小。通過遺傳算法變異對(duì)個(gè)體基因信息的改動(dòng)，使得算法的全局進(jìn)化達(dá)到最優(yōu)解。而且一致雜交與精英選擇相結(jié)合的遺傳算法，適應(yīng)度收斂速度明顯高于其他兩個(gè)種群，遺傳變異也最可能達(dá)到全局最優(yōu)解。而單單使用一致雜交的遺傳算法，其種群適應(yīng)度數(shù)值的波動(dòng)性較小，這表明一致雜交的遺傳算法最可能達(dá)到局部最優(yōu)解。而單點(diǎn)雜交與精英選擇的遺傳算法，其達(dá)到最優(yōu)解的可能性較低，一般不采取該算法進(jìn)行任務(wù)執(zhí)行。

5 結(jié)語

本文在網(wǎng)格任務(wù)調(diào)度中只考慮簡(jiǎn)單的任務(wù)執(zhí)行過程，只對(duì)規(guī)劃模型中的決策變量、目標(biāo)函數(shù)和約束條件進(jìn)行分析。而遺傳算法的雜交交叉操作與變異的結(jié)合，最可能達(dá)到局部或者全局的最優(yōu)解。

[1]常瑞生．基于改進(jìn)遺傳算法的網(wǎng)格任務(wù)調(diào)度[J]．信息通信，2016(3)：56-58．

[2]熊聰聰，馮龍，陳麗仙，等．云計(jì)算中基于遺傳算法的任務(wù)調(diào)度算法研究[J]．華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2012(S 1)：1-4．

[3]潘利強(qiáng)，張燕琴．基于改進(jìn)遺傳算法的網(wǎng)格任務(wù)調(diào)度模型構(gòu)建[J].軟件導(dǎo)刊，2017(1)：18-20．

[4]王波，張曉磊．基于粒子群遺傳算法的云計(jì)算任務(wù)調(diào)度研究[J]．計(jì)算機(jī)工程與用，2015(6)：84-88．