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

金智

（長沙醫(yī)學院，湖南 長沙 410219）

1 引言

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

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

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

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

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

在有方向無環(huán)路任務(wù)圖表中，對每個網(wǎng)格任務(wù)的深度值進行計算，通過以上計算可以得出：若任務(wù)圖表中的最大深度值為h，則該網(wǎng)格的任務(wù)集合就有h個。從圖1中可以看出：{T1，T2}深度值為1，{T3，T4}、{T4，T5}的深度值為 2，{T6，T7}的深度值為3。若該網(wǎng)格中有R1、R2兩個資源集合，則需要對圖1的h個任務(wù)集合進行兩兩排列，則總的任務(wù)執(zhí)行序列為{T1，T2，T3，T4，T5，T7，T6}，也就是按照{(diào)R1R2，R1R2，R1R2，R1}的資源分配方式進行分配。在該網(wǎng)格任務(wù)調(diào)度中，主要運用非降序的深度數(shù)值排列方式，進行任務(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è)計

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

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

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

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

3.2.1 遺傳算法的復制與選擇

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

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

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

3.2.3 遺傳算法的變異

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

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

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

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

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

5 結(jié)語

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

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

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

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

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