摘 要： 為了提高遺傳算法的搜索性能，同時(shí)滿足網(wǎng)格資源的優(yōu)化分配,，提出了一種帶過濾機(jī)制的遺傳算法,，使其適用于網(wǎng)格任務(wù)調(diào)度問題的優(yōu)化處理。仿真研究表明該算法更符合網(wǎng)格調(diào)度的復(fù)雜環(huán)境,，能得到較短的任務(wù)執(zhí)行時(shí)間和較好的負(fù)載均衡性,。
關(guān)鍵詞： 遺傳算法；網(wǎng)格,；任務(wù)調(diào)度,；完成時(shí)間
網(wǎng)格任務(wù)調(diào)度的基本思想是把分布在不同地理位置上的計(jì)算資源、存儲資源,、通信資源,、軟件資源、信息資源和知識資源等通過Internet整合成一臺巨大的超級計(jì)算機(jī),，實(shí)現(xiàn)各種資源的全面共享[1],。網(wǎng)格技術(shù)的關(guān)鍵是資源管理，即有效地分配和使用網(wǎng)格資源,。
用戶通過向網(wǎng)格系統(tǒng)提交計(jì)算任務(wù)來共享網(wǎng)格資源,，網(wǎng)格調(diào)度程序再按照某種策略把這些任務(wù)分配給合適的資源[2]。高效的調(diào)度策略或算法可以充分利用網(wǎng)格系統(tǒng)的處理能力,，從而提高應(yīng)用程序的性能,。目前在網(wǎng)格調(diào)度算法研究中，其目標(biāo)主要是增加吞吐率和系統(tǒng)的使用率,，實(shí)現(xiàn)經(jīng)濟(jì)系統(tǒng)和用戶的約束條件,，以實(shí)現(xiàn)在整個(gè)系統(tǒng)中網(wǎng)格應(yīng)用任務(wù)的完成時(shí)間最短。
另外,，在網(wǎng)格環(huán)境中,，由于任務(wù)到達(dá)的隨機(jī)性以及各節(jié)點(diǎn)處理能力上的差異，會造成某些節(jié)點(diǎn)分配的任務(wù)過重,，而另外一些節(jié)點(diǎn)卻是空閑的,，即出現(xiàn)負(fù)載不均衡現(xiàn)象[3],。因此，考察調(diào)度算法的性能時(shí),，也應(yīng)考慮負(fù)載均衡性問題。
遺傳算法（GA）是建立一個(gè)調(diào)度的集合并從其中找出優(yōu)化的調(diào)度,，將這種特性遺傳給下一代,。遺傳算法通過適應(yīng)度函數(shù)交叉和重組得出最優(yōu)的調(diào)度。這是一種迭代的算法,，它的優(yōu)點(diǎn)是在不斷進(jìn)化的過程中吸收系統(tǒng)發(fā)生改變,，能夠適應(yīng)動態(tài)變化的網(wǎng)格系統(tǒng)。
本文將改進(jìn)的遺傳算法（IGA）用于網(wǎng)格任務(wù)調(diào)度,，用IGA尋找滿足完成所有任務(wù)時(shí)間最短的優(yōu)化方案,，仿真實(shí)驗(yàn)表明，該方案性能良好,。
1 問題描述
網(wǎng)格是一個(gè)集成的計(jì)算與資源環(huán)境,，網(wǎng)格技術(shù)作為一種高性能廣域分布式計(jì)算模型，已經(jīng)成為眾多研究機(jī)構(gòu)的研究熱點(diǎn),。
在網(wǎng)格技術(shù)的眾多問題中,，網(wǎng)格計(jì)算中的任務(wù)調(diào)度在一般形式下是一個(gè)NP問題，沒有最優(yōu)解,。在調(diào)度算法的高效性,、資源的異構(gòu)性以及資源分配決策的并行性和分布性等方面，傳統(tǒng)的調(diào)度算法并不能很好地適應(yīng)網(wǎng)格資源的特點(diǎn),。因此,，如何對網(wǎng)格資源進(jìn)行合理分配和管理，滿足各種應(yīng)用的服務(wù)需求,，實(shí)現(xiàn)資源的優(yōu)化利用,，就成為該領(lǐng)域的研究關(guān)鍵。
網(wǎng)格任務(wù)調(diào)度根據(jù)任務(wù)間是否存在通信關(guān)系可以分為對相互間存在通信任務(wù)的任務(wù)組的調(diào)度和對相互獨(dú)立的任務(wù)組的調(diào)度[4],。在算法實(shí)現(xiàn)中都假定資源的信息是可獲取的,。
網(wǎng)格任務(wù)調(diào)度的實(shí)質(zhì)就是在一個(gè)由m個(gè)需要調(diào)度的任務(wù)、n個(gè)可用的任務(wù)執(zhí)行單元(主機(jī)或集群),、k個(gè)數(shù)據(jù)存儲單元構(gòu)成的網(wǎng)格環(huán)境下,，把m個(gè)任務(wù)T={t1，t2,，…,，tm}以合理的方式調(diào)度到n臺主機(jī)的過程，目的是得到盡可能短的總完成時(shí)間（makespan）,。把每個(gè)執(zhí)行單元廣義地當(dāng)作一臺主機(jī)來看待,，把k個(gè)數(shù)據(jù)存儲單元當(dāng)成一個(gè)存儲系統(tǒng)整體來看待,。
m個(gè)任務(wù)在n臺不同主機(jī)上的預(yù)測執(zhí)行時(shí)間EET是一個(gè)m×n的矩陣。矩陣中的每一行代表某一個(gè)任務(wù)在n臺機(jī)器上的不同執(zhí)行時(shí)間,，每一列代表在同一臺機(jī)器上的m個(gè)任務(wù)的不同執(zhí)行時(shí)間,。
通信開銷矩陣CCT描述了網(wǎng)格環(huán)境下，不同“任務(wù)對”在各主機(jī)之間進(jìn)行數(shù)據(jù)傳輸?shù)耐ㄐ砰_銷,。任務(wù)必須分配到一臺主機(jī)上,，所需要的數(shù)據(jù)也必須從它的父任務(wù)發(fā)送過來，父任務(wù)可能有多個(gè),。第一個(gè)任務(wù)沒有通信開銷,，其后的所有任務(wù)都可能有通信開銷，因此CCT是一個(gè)m×m的矩陣,。
m個(gè)任務(wù)在n臺不同機(jī)器上的預(yù)測最短完成時(shí)間MCT是一個(gè)m×n的矩陣,，MCT(i，j)除了包含EET（i,，j）外,，還應(yīng)考慮通信和等待通信的時(shí)間開銷T（i，j）,，T（i,，j）=max（（CCT（i，v）+TW（i,，k））,，k=1，2,，…,，i-1），TW（i,，k）為第i個(gè)任務(wù)等待其父任務(wù)準(zhǔn)備好數(shù)據(jù)的時(shí)間,。
調(diào)度的目標(biāo)是在考慮通信開銷和給定代價(jià)及約束集合現(xiàn)狀之下，任務(wù)集合總的完成時(shí)間最短,。
負(fù)載均衡性可以用每個(gè)調(diào)度方案中各臺主機(jī)的最長執(zhí)行時(shí)間與最短執(zhí)行時(shí)間的比值來衡量,，該值越小，則該調(diào)度方案中各臺主機(jī)的負(fù)載均衡性越好,。
2 改進(jìn)遺傳算法在網(wǎng)格任務(wù)調(diào)度中的應(yīng)用
2.1 改進(jìn)遺傳算法
遺傳算法是Holland于1975年受生物進(jìn)化論的啟發(fā)而提出的,。并行性和全局解空間搜索是遺傳算法的兩個(gè)最顯著的特點(diǎn)[5]。
遺傳算法求解問題的基本步驟為：
(1)定義適應(yīng)度函數(shù)和相應(yīng)的隸屬度函數(shù),；
(2)確定算法的初值和初始種群,；
(3)對種群進(jìn)行選擇、交叉,、變異操作,，產(chǎn)生新的種群,；
(4)循環(huán)遺傳操作，直到達(dá)到進(jìn)化的最大代數(shù),。
適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的選擇方法,，即輪盤賭選擇法。在該方法中,，各個(gè)個(gè)體（染色體）的選擇概率和其適應(yīng)度值成比例,，適應(yīng)度高的個(gè)體被選中的可能性大。
交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征,，在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法,。兩點(diǎn)交叉是遺傳算法中比較常用的交叉方法,。在相互配對的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，然后在兩個(gè)交叉點(diǎn)之間進(jìn)行基因交換,，以產(chǎn)生新的個(gè)體,。
在群體的所有個(gè)體中隨機(jī)地確定基因座，以事先設(shè)定的變異概率來對這些基因座上的基因值進(jìn)行變異,。當(dāng)進(jìn)行變異操作時(shí),，所有基因座上的基因值的變異必須是合法的，并且必須在可選擇的范圍內(nèi)[6]進(jìn)行,。
改進(jìn)遺傳算法的基本思想是對種群中染色體進(jìn)行過濾,。首先計(jì)算出種群中每一個(gè)個(gè)體所對應(yīng)的適應(yīng)度函數(shù)值及負(fù)載均衡度值，剔除負(fù)載均衡度值低的部分染色體,，再從剩余的染色體中選出一些適應(yīng)度高的個(gè)體,，其數(shù)量等于剔除掉染色體的數(shù)量。使這些個(gè)體在種群中復(fù)制一次,，以保持種群大小不變,。這樣，高適應(yīng)度的染色體取代負(fù)載均衡度值不良的染色體,，使得高適應(yīng)度染色體在種群中所占比例增大,，從而使選擇操作中有更多的優(yōu)良個(gè)體被選中，提高搜索性能,。
2.2 改進(jìn)遺傳算法在網(wǎng)格任務(wù)調(diào)度中的應(yīng)用
在網(wǎng)格任務(wù)調(diào)度模型中,，設(shè)x={x1，x2,，…,，xm}，其中m是任務(wù)數(shù),，xi是介于1～n之間的一個(gè)整數(shù),，即主機(jī)編號,。因此用x來表示一種選擇方案，在遺傳算法中它表示一個(gè)染色體,。例如由10個(gè)任務(wù)和5臺主機(jī)組成的系統(tǒng)中,，方案[2，1,，5,，4，2,，3,，5，1,，4,，5]表示第1個(gè)任務(wù)由第2臺主機(jī)完成，第2個(gè)任務(wù)由第1臺主機(jī)完成,，第3個(gè)任務(wù)由第5臺主機(jī)完成,，依次類推。
遺傳算法通過適應(yīng)度函數(shù)來確定染色體的優(yōu)劣,，所以必須根據(jù)實(shí)際問題的需要選擇適應(yīng)值函數(shù),。由于一次調(diào)度過程中，求解的任務(wù)總完成時(shí)間makespan是一個(gè)最小值,，故定義適應(yīng)度函數(shù)為：
其中,，ms為對應(yīng)某一染色體編碼的任務(wù)總完成時(shí)間，是makespan的縮寫,，msmin為總完成時(shí)間的最小估算值,，msmax為總完成時(shí)間的最大估算值，msmin和msmax適當(dāng)取值,，使0<fit(ms)<1,。總完成時(shí)間ms越小,，適應(yīng)度fit(ms)越大,，該染色體被選中的可能性就越大。
改進(jìn)遺傳算法的流程如下：
(1)隨機(jī)產(chǎn)生滿足染色體定義的初始種群,，種群大小為popsize,；定義進(jìn)化代數(shù)的初值和最大值，設(shè)定交叉概率,、變異概率等初始參數(shù),；
(2)計(jì)算種群中每一個(gè)個(gè)體所對應(yīng)的適應(yīng)度函數(shù)值及負(fù)載均衡度值；
(3)將種群中負(fù)載均衡度值最低的部分個(gè)體剔除掉，并對適應(yīng)度值高的個(gè)體復(fù)制,，以補(bǔ)充被剔除掉的個(gè)體,，保證總的染色體數(shù)為popsize不變；
(4)采用輪盤賭法進(jìn)行選擇操作,；
(5)隨機(jī)配對,，按照給定的概率進(jìn)行單點(diǎn)交叉、交叉點(diǎn)隨機(jī)設(shè)置,；
(6)對個(gè)體的每一個(gè)基因座,，根據(jù)變異概率指定其變異點(diǎn)，對每一指定的變異點(diǎn)的基因值由除該基因值以外的隨機(jī)產(chǎn)生的[1,，n]之間的數(shù)值代替,；
(7)尋找種群中最大適應(yīng)度值和與之對應(yīng)的最小完成時(shí)間；
(8)判斷算法是否達(dá)到最大迭代次數(shù),，如未滿足條件,，則轉(zhuǎn)步驟(2)繼續(xù)搜索；否則輸出全局最優(yōu)適應(yīng)值及其對應(yīng)的染色體,，將該任務(wù)選擇方案賦給網(wǎng)格調(diào)度模型。
為了驗(yàn)證本文提出的IGA算法的有效性,，用IGA算法與基本遺傳算法及經(jīng)典的Min-Min算法進(jìn)行對比仿真研究,。
Min-Min算法[7]是網(wǎng)格調(diào)度算法的研究基礎(chǔ)，該算法的目的是將大量的任務(wù)指派給完成最早,、執(zhí)行最快的機(jī)器,。算法的思想為：對等待分配的每一個(gè)任務(wù)，分別計(jì)算出該任務(wù)分配到n臺機(jī)器上的最早完成時(shí)間,；從中找出具有最小最早完成時(shí)間的任務(wù),，并將該任務(wù)分配給對應(yīng)的機(jī)器；分配完成后,，更新機(jī)器期望就緒時(shí)間并刪除已經(jīng)分配的任務(wù),。重復(fù)上面的過程，直到分配完所有的任務(wù),。
3 仿真實(shí)驗(yàn)及結(jié)果分析
在Matlab環(huán)境下設(shè)計(jì)一個(gè)網(wǎng)格任務(wù)調(diào)度系統(tǒng)模擬程序,，該程序可以根據(jù)仿真的需要生成不同的主機(jī)處理能力、主機(jī)數(shù)量,、任務(wù)數(shù)量,、每個(gè)任務(wù)的預(yù)測執(zhí)行時(shí)間、通信開銷及其他時(shí)間開銷等參數(shù),。在用改進(jìn)的遺傳算法尋找任務(wù)調(diào)度的最佳方案時(shí),，種群規(guī)模為40，最大允許迭代次數(shù)為400,。在本文的所有仿真實(shí)驗(yàn)中,，針對每種問題都重復(fù)進(jìn)行10次獨(dú)立實(shí)驗(yàn),，并對實(shí)驗(yàn)得到的各項(xiàng)數(shù)據(jù)求平均值。
(1)產(chǎn)生一個(gè)任務(wù)數(shù)為80,、主機(jī)數(shù)為8的模型,，將IGA、GA和Min-Min算法同時(shí)用于該模型的任務(wù)調(diào)度,，圖1和圖2分別表示采用IGA和GA算法時(shí)每臺主機(jī)的執(zhí)行時(shí)間以及完成所有任務(wù)總的執(zhí)行時(shí)間情況,。而圖3則表示采用Min-Min算法時(shí)的仿真結(jié)果。
從仿真結(jié)果可以看出,，采用IGA進(jìn)行任務(wù)調(diào)度時(shí)的makespan是22.573 1,，采用GA進(jìn)行任務(wù)調(diào)度時(shí)的makespan是23.611 2，而采用Min-Min算法得到的調(diào)度方案的makespan是24.100 9,，采用IGA算法比采用GA算法節(jié)省了4.40%的執(zhí)行時(shí)間,，采用IGA算法比采用Min-Min算法節(jié)省了6.34%的執(zhí)行時(shí)間。圖1中主機(jī)1,、4,、8的負(fù)載略高，總的負(fù)載均衡性較好,；圖2中主機(jī)3,、8的負(fù)載低，主機(jī)2負(fù)載最高,，負(fù)載均衡性不如圖1,；但在圖3中，主機(jī)1,、3,、6、8負(fù)載明顯高于其他主機(jī),，負(fù)載均衡性不如圖1,，也不如圖2，這就是Min-Min算法的主要缺陷,。另外,，應(yīng)用IGA進(jìn)行調(diào)度時(shí)，負(fù)載最大的主機(jī)與負(fù)載最小的主機(jī)的負(fù)載比值為1.085 1,；采用GA算法時(shí),，這個(gè)數(shù)據(jù)為1.160 6，而采用Min-Min算法時(shí),，這個(gè)比值則為1.247 9,。
(2)在主機(jī)數(shù)量不變的情況下，改變?nèi)蝿?wù)數(shù)量，分別應(yīng)用IGA,、GA和Min-Min算法尋找最優(yōu)調(diào)度方案,，表1給出了兩種算法對應(yīng)的makespan的仿真結(jié)果對比，結(jié)果顯示IGA優(yōu)于GA和Min-Min算法,。
(3)在任務(wù)數(shù)量固定的情況下,，主機(jī)數(shù)量從8臺均勻遞增至20臺，分別應(yīng)用IGA,、GA和Min-Min算法尋找最優(yōu)調(diào)度方案,，并計(jì)算三種方案的makespan，將仿真結(jié)果列于表2中,，結(jié)果顯示IGA算法比GA算法和Min-Min算法得到的任務(wù)完成時(shí)間短,。
在分析網(wǎng)格任務(wù)調(diào)度問題和基本遺傳算法的基礎(chǔ)上，提出了一種帶過濾機(jī)制的改進(jìn)遺傳算法,，并用于網(wǎng)格任務(wù)調(diào)度模型的優(yōu)化,。用Matlab進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果表明文中所提算法有很好的特性,，得到了較基本遺傳算法和Min-Min算法更為滿意的結(jié)果,，可以實(shí)現(xiàn)網(wǎng)格資源之間公平有效的任務(wù)調(diào)度。
參考文獻(xiàn)
[1] BHARADWAJ V,，GHOSE D,，ROBERTAZZI T G.Divisible load theory：a new paradigm for load scheduling in distributed systems[J].Cluster Comput.,2003,6(1):7-17.
[2] FOSTER I.The grid: blueprint for a new computing infrastructure(2nd Edition)[M].Morgan Kaufmann Publishers Inc., ISBN:1-55860-993-4, 2004.
[3] BRAUN T D,SIEGEL H J,BECK N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[J]. Journal of Parallel and Distributed Computing, 2001,61(1):810-837.
[4] NORIYUKI F,KENICHI H.A comparison among grid scheduling algorithms for independent coarse-grained tasks [C].Proceedings of the International Symposium on Applications and the Internet Workshops (SAINTW’04), 2004：674-680.
[5] CAO H Y，WANG D W.A simulation based genetic algorithm for risk-based partner selection in new product development. International Journal of Industrial Engineering,2003,10(1):16-25.
[6] ?魻ZDAMAR L.A genetic algorithm approach to a general category project scheduling problem[J]. IEEE Trans. Syst., Man, Cybern. C., 1999, 29(2): 44-59.
[7] HE Xiao Shan, SUN X H.VON L G.QoS guided Min-Min heuristic for grid task scheduling[J].Journal of Computer Science & Technology, 2003(5):442-451.