一種改進型遺傳算法的網(wǎng)格工作流調(diào)度研究

趙 斌，宿玉佩，蔣念平

(1.洛陽師范學(xué)院計算機系，河南洛陽471022;2.重慶醫(yī)科大學(xué)附屬第一醫(yī)院，重慶400016;3.上海理工大學(xué)光電信息與計算機工程學(xué)院，上海200093)

0 前言

網(wǎng)格技術(shù)是互聯(lián)網(wǎng)計算技術(shù)的一個重要發(fā)展方向。作為網(wǎng)格計算的重要部分，借助于工作流技術(shù)，人們提出用網(wǎng)格工作流來解決網(wǎng)格環(huán)境方面遇到的問題。

網(wǎng)格工作流是多項網(wǎng)格服務(wù)的綜合。這些網(wǎng)格服務(wù)以一種預(yù)設(shè)順序分布在各種分布式網(wǎng)格節(jié)點予以執(zhí)行，以最終完成一項具體任務(wù)。任務(wù)調(diào)度是網(wǎng)格工作流研究方面的一個重要話題，與一般的任務(wù)調(diào)度不同，網(wǎng)格工作流調(diào)度必須考慮的是不僅要為任務(wù)選擇最優(yōu)資源，而且還需考慮各任務(wù)之間的用時或因果約束條件。任務(wù)與各節(jié)點之間的映射關(guān)系由此構(gòu)成網(wǎng)格工作流調(diào)度方案。

目前，網(wǎng)格任務(wù)調(diào)度集中在改進調(diào)度算法上。而Globus網(wǎng)格環(huán)境主要處理標識問題與資源發(fā)現(xiàn)，對任務(wù)調(diào)度與提交算法都不很完善。任務(wù)調(diào)度采用輪循方法，任務(wù)提交采用命令行方式，容錯性差，對負載平衡沒有考慮。如Min-Min等是比較老的算法，一般網(wǎng)格任務(wù)調(diào)度算法多數(shù)是與這些算法相比較。但根據(jù)網(wǎng)格計算任務(wù)調(diào)度系統(tǒng)的特點，這些傳統(tǒng)調(diào)度算法不能很好的適應(yīng)網(wǎng)格資源的要求。高效任務(wù)調(diào)度算法可提高整個計算網(wǎng)格計算效率，但網(wǎng)格計算系統(tǒng)中某資源出現(xiàn)故障可能性較高，系統(tǒng)資源會不斷增長，系統(tǒng)性能和結(jié)構(gòu)會不斷發(fā)生變化，這就要求資源管理程序能很好的動態(tài)監(jiān)視與管理網(wǎng)格資源，從可利用資源中選取最佳資源服務(wù)，減小這種故障或失敗、整體結(jié)構(gòu)和性能發(fā)生變化等問題對網(wǎng)格整體性能的影響［1-2］。

本文提出一種基于改進型遺傳算法的資源調(diào)度算法。為了避免收斂速度過慢且不那么容易局限在局部最小范圍內(nèi)，該算法增加了二級優(yōu)先雜交和二級優(yōu)先變異運算，表現(xiàn)出良好的收斂特性和效率。

1 問題描述

網(wǎng)格工作流建模允許網(wǎng)格工作流任務(wù)或工作量操作根據(jù)他們之間命令的執(zhí)行情況建立相應(yīng)模型。把實際問題通過建模語言轉(zhuǎn)化成對應(yīng)的任務(wù)序列，再通過任務(wù)序列之間的關(guān)系進一步轉(zhuǎn)化成對編程語言的描述［3］。本文的網(wǎng)格工作流模型是基于有向無環(huán)圖(DAG)模型而創(chuàng)建的。圖1給出了一個由有向無環(huán)圖來表示的網(wǎng)格工作流。DAG工作流模型將工作流描述成一系列的子任務(wù)。子任務(wù)之間的依賴關(guān)系和優(yōu)先關(guān)系構(gòu)成一個有向無環(huán)圖G=(V，E，W)，其中，V代表圖中的所有節(jié)點，即工作流的所有子任務(wù);E是圖的有向邊，即各任務(wù)之間的依賴關(guān)系和優(yōu)先關(guān)系;W是有向邊的權(quán)重，即任務(wù)Vi所需的執(zhí)行成本。

運行時間最長的路徑是關(guān)鍵性路徑。在圖1中將最大的Σ W設(shè)為關(guān)鍵路徑，并選擇(V1→V3→V5→V6)為關(guān)鍵路徑，(V1→V2→V4→V6)為非關(guān)鍵路徑。這樣一來，關(guān)鍵路徑上就存在子任務(wù)((V1→V3)，(V3→V5)，(V5→ V6))，非關(guān)鍵路徑上就存在((V1→ V2)，(V2→V4)，(V4→V6))。然后，將快速運行的資源配置給關(guān)鍵路徑上的各任務(wù)，將成本低的資源配置給非關(guān)鍵路徑上的各任務(wù)［4］，因此，網(wǎng)格工作流任務(wù)調(diào)度的總計算成本得以降低。

工作流調(diào)度的本質(zhì)在于將關(guān)鍵路徑或非關(guān)鍵路徑上合適的子任務(wù)分配給一個特定的網(wǎng)格資源以執(zhí)行操作，使得整個任務(wù)的計算成本總數(shù)控制在最低。

假設(shè)有 n 個子任務(wù) Ti=(i=1，2，3，…，n)和 m 個可用網(wǎng)格資源 Rj=(j=1，2，3，…，m)。根據(jù)任務(wù)之間的優(yōu)先關(guān)系和約束關(guān)系，工作流調(diào)度將n個子任務(wù)分配給m個可用網(wǎng)格資源以充分利用它們。Ci是完成工作Ti所需的用時。調(diào)度的目標在于使Σ Ci控制在最低，從而降低計算成本。

圖1 基于DAG的工作流模型

2 改進型算法

任務(wù)調(diào)度問題是一個典型的NP-完全問題。如果應(yīng)用標準的遺傳算法來進行調(diào)度，存在兩大缺陷:(1)容易陷入局部最優(yōu)解;(2)收斂速度慢。鑒于此，本文對傳統(tǒng)的遺傳算法做了改進。新算法對自然數(shù)進行編碼，并增加了二級優(yōu)先雜交和二級優(yōu)先變異過程，然后保留每一代的最優(yōu)個體，從而有效地保障了全局搜索和局部搜索的強大性能。

2.1 代碼設(shè)計

為了比二進制編碼的染色體更能維持物種的多樣性，同時使得編碼和解碼過程簡單化，新算法對帶有自然數(shù)的染色體進行編碼［5］。

染色體的長度等于分配任務(wù)的個數(shù)，用Y=(X1，X2，X3，…，Xi，…，Xn)來表示一條染色體。每條染色體的每個節(jié)點可以表示為一個二元Xi(Si，pi)(i=1，2，…，n)，Si是分配到任務(wù)i的資源，任務(wù)個數(shù)i是唯一的，每項任務(wù)獲取到一個資源，不同的任務(wù)可以獲取到相同的資源;pi是該任務(wù)的優(yōu)先值。

為了改善個體庫存的覆蓋數(shù)，采取隨機初始化方法，即隨機選擇一個資源來運行任務(wù)i。

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

適應(yīng)度函數(shù)用來評估當(dāng)前染色體的適應(yīng)能力，它可以有效地反映每條染色體與最優(yōu)解染色體之間的差距。適應(yīng)度函數(shù)的值對問題的解決起著決定性的作用。建立預(yù)測值Value=［Ti，Rj］的二維列陣，其中，Ti是任務(wù)i;Rj是資源j。通過獲悉Ti的分配任務(wù)和Rj的計算能力之間的關(guān)系可以計算出相應(yīng)的理論期望值。本文中的適應(yīng)度函數(shù)取決于所有任務(wù)的調(diào)度的預(yù)計完成用時。將這個預(yù)計完成用時的倒計時視為評估條件，即

式(1)是染色體的適應(yīng)度評估，其中，n是染色體的長度;Yi是i-位染色體對應(yīng)資源的值。如果適應(yīng)度越大，表明染色體更優(yōu)越，反之，就越低劣。

2.3 選擇

選擇算子決定的是哪些染色體可以保留到下一代。本文應(yīng)用輪盤賭法來進行選擇。輪盤賭法選擇的目的在于將集合中的元素映射到一個范圍內(nèi)。然后分成多個子分段(每個分段對應(yīng)一個元素)，由此便會出現(xiàn)n個有效隨機個數(shù)，統(tǒng)計好每個頻率出現(xiàn)的隨機個數(shù)，然后選出出現(xiàn)頻率最高的那個分段的元素［6］。

該算法基于染色體的適應(yīng)度值來決定所選染色體的概率。如果染色體的適應(yīng)度值較大，那么被選中的概率也就大。為了實現(xiàn)輪盤賭選擇，每輪會生成［0，1］范圍內(nèi)的隨機數(shù)字，以作為參考概率。被選個體ri的概率表示為

其中，pSize是種群的大小。

每條染色體被選的概率決定好后，將參考概率與選擇概率進行對照，如果前者大于后者，該染色體就入選;否則，就放棄。

2.4 交叉運算

交叉運算可以改變兩個父代個體的部分結(jié)構(gòu)并將它們組合成一個新個體。新個體遺傳這兩個個體的特征。此時，問題變成了尋找最優(yōu)方向。在這一算法里，為確保種群的多樣性，交叉會出現(xiàn)在隨機位置，隨后就需要對新個體的適應(yīng)度值進行評估。根據(jù)評估結(jié)果，算法會進行合理調(diào)整。為了提高解空間的收斂速度，二級優(yōu)先雜交只會發(fā)生在適應(yīng)度值低于平均適應(yīng)度值的個體和種群的最優(yōu)個體方面。交叉概率是Rs，通常為0.4～0.9，隨機挑選兩個個體，生成隨機個數(shù)r［7］。

2.5 變異運算

通過變異，可以稍微改變?nèi)旧w被選中的概率，從而保障染色體的多樣性，判定遺傳算法的局部搜索能力。

該算法存在變異概率很小的染色體，然后需要對新個體進行適應(yīng)度值評估。該算法基于評估結(jié)果進行二級優(yōu)先變異。為了維持染色體的多樣性、改善最優(yōu)生成能力，單點變異只發(fā)生在適應(yīng)度值小于平均值的個體和種群的最優(yōu)個體方面。變異概率Rc，通常為0.001～0.100［8］，獲取新個體。

2.6 保留全局最優(yōu)個體

每一代繁殖結(jié)束后，就獲取到當(dāng)前的最優(yōu)個體，是一個近似最優(yōu)解。然后比較當(dāng)前生成的最優(yōu)個體與全局最優(yōu)個體的適應(yīng)度值。如果前者大于后者，就替換掉全局的最優(yōu)個體;否則維持不變。這個生成的個體如果符合替換條件，就停止繁殖，否則繼續(xù)繁殖。

通過上述步驟，可以判斷模塊之間的運算關(guān)系并采用流程圖來表示。改進型算法的運算過程如圖2所示。

3 研究結(jié)果

本文使用Gridsim［9］工具在異構(gòu)網(wǎng)格環(huán)境下進行模擬試驗。Gridsim為網(wǎng)格有效資源分配技術(shù)提供模擬環(huán)境。它是網(wǎng)格計算平臺，它能夠模擬異構(gòu)、進行簡單的網(wǎng)絡(luò)任務(wù)的虛擬處理等。

在應(yīng)用改進遺傳算法前，先對遺傳算法參數(shù)進行配置，如種群大小，交叉與變異概率設(shè)置。試驗初始種群為100?？砂l(fā)現(xiàn)交叉概率取0.74～0.76時，適應(yīng)度函數(shù)較穩(wěn)定且最優(yōu)［10］，如圖3所示。

對改進型遺傳算法和標準遺傳算法進行分析后再作比較。有關(guān)模擬參數(shù)有:機器、處理元素和每秒百萬指令。所以本論文中主要參數(shù)是:種群大小100、種群迭代次數(shù)50、交叉概率0.80、變異概率0.01。仿真結(jié)果如圖4和圖5所示。圖4是不同任務(wù)在100種資源之間調(diào)度的結(jié)果。圖5是100個任務(wù)在不同資源之間調(diào)度的結(jié)果。每個坐標點的值即是當(dāng)前連續(xù)10次調(diào)度的平均值。

圖2 改進型遺傳算法的操作過程

圖4 是在保持網(wǎng)格資源個數(shù)不變的情況下，通過改變?nèi)蝿?wù)的個數(shù)而進行的模擬試驗。通過對比兩組試驗數(shù)據(jù)，可知改進型遺傳算法的完成用時比標準遺傳算法的少，且成本也低。圖5是在保持任務(wù)個數(shù)不變的情況下通過改變網(wǎng)格資源的個數(shù)而進行的模擬試驗。通過對比兩組試驗數(shù)據(jù)，可知改進型遺傳算法的完成用時比標準遺傳算法的少，且成本也低。

通過對兩種情況的仿真試驗結(jié)果相比較可得出:改進后遺傳算法網(wǎng)格工作流調(diào)度算法與傳統(tǒng)遺傳算法的網(wǎng)格工作流調(diào)度算法相比，具有更好的尋優(yōu)能力，在全局收斂方面顯示出了良好的性能。改進后調(diào)度算法能夠縮短整個任務(wù)的總體執(zhí)行時間，并且在大規(guī)模網(wǎng)格工作流調(diào)度環(huán)境下得到了較好的性能和效果，能夠在實際網(wǎng)格中加以應(yīng)用。

圖3 遺傳算法的交叉概率效果

圖4 不同任務(wù)在100種資源之間的調(diào)度

圖5 100個任務(wù)在不同資源之間的調(diào)度

4 結(jié)論

基于二級優(yōu)先雜交和二級優(yōu)先變異，本文提出了改進型的遺傳算法，結(jié)果表明:該算法在維持種群多樣性的情況下具有良好的效率和收斂性，能夠更有效地解決網(wǎng)格工作流調(diào)度問題。最終，通過模擬試驗，證實該法比標準的GA算法更有效。當(dāng)然，這方面的研究還存在諸多問題需要深入探討，例如，如何解決網(wǎng)格工作流的工作量的平衡問題。

［1］吳高鋒，蔣玉明.基于QoS改進的Min-Min網(wǎng)格調(diào)度算法［J］.微計算機信息，2009，9(3):110-112.

［2］葉春曉，陸杰.基于改進遺傳算法的網(wǎng)格任務(wù)調(diào)度研究［J］.計算機科學(xué)，2010，37(7):233-235.

［3］Jia Y，Rajkumar B.A Novel Architecture for Realizing Grid Workflow Using Tuple Spaces［C］//Fifth IEEE/ACM International Workshop on Grid Computing IEEE.2004:119-128.

［4］Fen H，Wang L，Yang H.Grid Workflow Technology and Its Application in Teacher Professional Development［J］.Audio-Visual Education Research，2007，5(2):32-35.

［5］Yuan Y C，Li X P，Wan Q，et al.Bottom Level Based Heuristic for Workflow Scheduling in Grids［J］.Computers，2008，2(5):67-70.

［6］Srinivas M，Patnaik L M.Genetic Algorithms:Asurvey［C］//IEEE Comput.1994:17-26.

［7］Wang X P，Cao L M.Genetic Algorithm［M］.Xi’an:Xi’an Jiaotong University Press，2002.

［8］Wu X Q，Zeng W H.Grid Resource Scheduling Algorithm Based on Improved Genetic Algorithm［J］.Microelectronics and Computer，2006，23(9):26-29.

［9］Anthony S，Chen S Y，Rajkumar B.Visual Model for Grid Modeling and Simulation(GridSim)Toolkit［C］//ICCS.2003:1123-1132.

［10］陸杰.基于遺傳算法的網(wǎng)格任務(wù)調(diào)度研究［D］.重慶:重慶大學(xué)，2010.