一種改進型遺傳算法的網格工作流調度研究

趙 斌，宿玉佩，蔣念平

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

0 前言

網格技術是互聯網計算技術的一個重要發展方向。作為網格計算的重要部分，借助于工作流技術，人們提出用網格工作流來解決網格環境方面遇到的問題。

網格工作流是多項網格服務的綜合。這些網格服務以一種預設順序分布在各種分布式網格節點予以執行，以最終完成一項具體任務。任務調度是網格工作流研究方面的一個重要話題，與一般的任務調度不同，網格工作流調度必須考慮的是不僅要為任務選擇最優資源，而且還需考慮各任務之間的用時或因果約束條件。任務與各節點之間的映射關系由此構成網格工作流調度方案。

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

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

1 問題描述

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

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

工作流調度的本質在于將關鍵路徑或非關鍵路徑上合適的子任務分配給一個特定的網格資源以執行操作，使得整個任務的計算成本總數控制在最低。

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

圖1 基于DAG的工作流模型

2 改進型算法

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

2.1 代碼設計

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

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

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

2.2 適應度函數

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

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

2.3 選擇

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

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

其中，pSize是種群的大小。

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

2.4 交叉運算

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

2.5 變異運算

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

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

2.6 保留全局最優個體

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

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

3 研究結果

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

在應用改進遺傳算法前，先對遺傳算法參數進行配置，如種群大小，交叉與變異概率設置。試驗初始種群為100。可發現交叉概率取0.74～0.76時，適應度函數較穩定且最優［10］，如圖3所示。

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

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

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

通過對兩種情況的仿真試驗結果相比較可得出:改進后遺傳算法網格工作流調度算法與傳統遺傳算法的網格工作流調度算法相比，具有更好的尋優能力，在全局收斂方面顯示出了良好的性能。改進后調度算法能夠縮短整個任務的總體執行時間，并且在大規模網格工作流調度環境下得到了較好的性能和效果，能夠在實際網格中加以應用。

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

圖4 不同任務在100種資源之間的調度

圖5 100個任務在不同資源之間的調度

4 結論

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

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

［2］葉春曉，陸杰.基于改進遺傳算法的網格任務調度研究［J］.計算機科學，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］陸杰.基于遺傳算法的網格任務調度研究［D］.重慶:重慶大學，2010.