趙 斌，宿玉佩，蔣念平

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

0 前言

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

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

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

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

1 問(wèn)題描述

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

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

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

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

圖1 基于DAG的工作流模型

2 改進(jìn)型算法

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

2.1 代碼設(shè)計(jì)

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

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

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

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

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

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

2.3 選擇

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

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

其中，pSize是種群的大小。

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

2.4 交叉運(yùn)算

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

2.5 變異運(yùn)算

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

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

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

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

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

3 研究結(jié)果

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

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

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

圖2 改進(jìn)型遺傳算法的操作過(guò)程

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

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

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

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

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

4 結(jié)論

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

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

［2］葉春曉，陸杰.基于改進(jìn)遺傳算法的網(wǎng)格任務(wù)調(diào)度研究［J］.計(jì)算機(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.