摘 要： 為了提高遺傳算法的搜索性能，同時滿足網(wǎng)格資源的優(yōu)化分配，提出了一種帶過濾機制的遺傳算法，使其適用于網(wǎng)格任務(wù)調(diào)度問題的優(yōu)化處理。仿真研究表明該算法更符合網(wǎng)格調(diào)度的復(fù)雜環(huán)境，能得到較短的任務(wù)執(zhí)行時間和較好的負載均衡性。
關(guān)鍵詞： 遺傳算法；網(wǎng)格；任務(wù)調(diào)度；完成時間
網(wǎng)格任務(wù)調(diào)度的基本思想是把分布在不同地理位置上的計算資源、存儲資源、通信資源、軟件資源、信息資源和知識資源等通過Internet整合成一臺巨大的超級計算機，實現(xiàn)各種資源的全面共享[1]。網(wǎng)格技術(shù)的關(guān)鍵是資源管理，即有效地分配和使用網(wǎng)格資源。
用戶通過向網(wǎng)格系統(tǒng)提交計算任務(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)的使用率，實現(xiàn)經(jīng)濟系統(tǒng)和用戶的約束條件，以實現(xiàn)在整個系統(tǒng)中網(wǎng)格應(yīng)用任務(wù)的完成時間最短。
另外，在網(wǎng)格環(huán)境中，由于任務(wù)到達的隨機性以及各節(jié)點處理能力上的差異，會造成某些節(jié)點分配的任務(wù)過重，而另外一些節(jié)點卻是空閑的，即出現(xiàn)負載不均衡現(xiàn)象[3]。因此，考察調(diào)度算法的性能時，也應(yīng)考慮負載均衡性問題。
遺傳算法（GA）是建立一個調(diào)度的集合并從其中找出優(yōu)化的調(diào)度，將這種特性遺傳給下一代。遺傳算法通過適應(yīng)度函數(shù)交叉和重組得出最優(yōu)的調(diào)度。這是一種迭代的算法，它的優(yōu)點是在不斷進化的過程中吸收系統(tǒng)發(fā)生改變，能夠適應(yīng)動態(tài)變化的網(wǎng)格系統(tǒng)。
本文將改進的遺傳算法（IGA）用于網(wǎng)格任務(wù)調(diào)度，用IGA尋找滿足完成所有任務(wù)時間最短的優(yōu)化方案，仿真實驗表明，該方案性能良好。
1 問題描述
網(wǎng)格是一個集成的計算與資源環(huán)境，網(wǎng)格技術(shù)作為一種高性能廣域分布式計算模型，已經(jīng)成為眾多研究機構(gòu)的研究熱點。
在網(wǎng)格技術(shù)的眾多問題中，網(wǎng)格計算中的任務(wù)調(diào)度在一般形式下是一個NP問題，沒有最優(yōu)解。在調(diào)度算法的高效性、資源的異構(gòu)性以及資源分配決策的并行性和分布性等方面，傳統(tǒng)的調(diào)度算法并不能很好地適應(yīng)網(wǎng)格資源的特點。因此，如何對網(wǎng)格資源進行合理分配和管理，滿足各種應(yīng)用的服務(wù)需求，實現(xiàn)資源的優(yōu)化利用，就成為該領(lǐng)域的研究關(guān)鍵。
網(wǎng)格任務(wù)調(diào)度根據(jù)任務(wù)間是否存在通信關(guān)系可以分為對相互間存在通信任務(wù)的任務(wù)組的調(diào)度和對相互獨立的任務(wù)組的調(diào)度[4]。在算法實現(xiàn)中都假定資源的信息是可獲取的。
網(wǎng)格任務(wù)調(diào)度的實質(zhì)就是在一個由m個需要調(diào)度的任務(wù)、n個可用的任務(wù)執(zhí)行單元(主機或集群)、k個數(shù)據(jù)存儲單元構(gòu)成的網(wǎng)格環(huán)境下，把m個任務(wù)T={t1，t2，…，tm}以合理的方式調(diào)度到n臺主機的過程，目的是得到盡可能短的總完成時間（makespan）。把每個執(zhí)行單元廣義地當(dāng)作一臺主機來看待，把k個數(shù)據(jù)存儲單元當(dāng)成一個存儲系統(tǒng)整體來看待。
m個任務(wù)在n臺不同主機上的預(yù)測執(zhí)行時間EET是一個m×n的矩陣。矩陣中的每一行代表某一個任務(wù)在n臺機器上的不同執(zhí)行時間，每一列代表在同一臺機器上的m個任務(wù)的不同執(zhí)行時間。
通信開銷矩陣CCT描述了網(wǎng)格環(huán)境下，不同“任務(wù)對”在各主機之間進行數(shù)據(jù)傳輸?shù)耐ㄐ砰_銷。任務(wù)必須分配到一臺主機上，所需要的數(shù)據(jù)也必須從它的父任務(wù)發(fā)送過來，父任務(wù)可能有多個。第一個任務(wù)沒有通信開銷，其后的所有任務(wù)都可能有通信開銷，因此CCT是一個m×m的矩陣。
m個任務(wù)在n臺不同機器上的預(yù)測最短完成時間MCT是一個m×n的矩陣，MCT(i，j)除了包含EET（i，j）外，還應(yīng)考慮通信和等待通信的時間開銷T（i，j），T（i，j）=max（（CCT（i，v）+TW（i，k）），k=1，2，…，i-1），TW（i，k）為第i個任務(wù)等待其父任務(wù)準(zhǔn)備好數(shù)據(jù)的時間。
調(diào)度的目標(biāo)是在考慮通信開銷和給定代價及約束集合現(xiàn)狀之下，任務(wù)集合總的完成時間最短。
負載均衡性可以用每個調(diào)度方案中各臺主機的最長執(zhí)行時間與最短執(zhí)行時間的比值來衡量，該值越小，則該調(diào)度方案中各臺主機的負載均衡性越好。
2 改進遺傳算法在網(wǎng)格任務(wù)調(diào)度中的應(yīng)用
2.1 改進遺傳算法
遺傳算法是Holland于1975年受生物進化論的啟發(fā)而提出的。并行性和全局解空間搜索是遺傳算法的兩個最顯著的特點[5]。
遺傳算法求解問題的基本步驟為：
(1)定義適應(yīng)度函數(shù)和相應(yīng)的隸屬度函數(shù)；
(2)確定算法的初值和初始種群；
(3)對種群進行選擇、交叉、變異操作，產(chǎn)生新的種群；
(4)循環(huán)遺傳操作，直到達到進化的最大代數(shù)。
適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的選擇方法，即輪盤賭選擇法。在該方法中，各個個體（染色體）的選擇概率和其適應(yīng)度值成比例，適應(yīng)度高的個體被選中的可能性大。
交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。兩點交叉是遺傳算法中比較常用的交叉方法。在相互配對的兩個個體編碼串中隨機設(shè)置兩個交叉點，然后在兩個交叉點之間進行基因交換，以產(chǎn)生新的個體。
在群體的所有個體中隨機地確定基因座，以事先設(shè)定的變異概率來對這些基因座上的基因值進行變異。當(dāng)進行變異操作時，所有基因座上的基因值的變異必須是合法的，并且必須在可選擇的范圍內(nèi)[6]進行。
改進遺傳算法的基本思想是對種群中染色體進行過濾。首先計算出種群中每一個個體所對應(yīng)的適應(yīng)度函數(shù)值及負載均衡度值，剔除負載均衡度值低的部分染色體，再從剩余的染色體中選出一些適應(yīng)度高的個體，其數(shù)量等于剔除掉染色體的數(shù)量。使這些個體在種群中復(fù)制一次，以保持種群大小不變。這樣，高適應(yīng)度的染色體取代負載均衡度值不良的染色體，使得高適應(yīng)度染色體在種群中所占比例增大，從而使選擇操作中有更多的優(yōu)良個體被選中，提高搜索性能。
2.2 改進遺傳算法在網(wǎng)格任務(wù)調(diào)度中的應(yīng)用
在網(wǎng)格任務(wù)調(diào)度模型中，設(shè)x={x1，x2，…，xm}，其中m是任務(wù)數(shù)，xi是介于1～n之間的一個整數(shù)，即主機編號。因此用x來表示一種選擇方案，在遺傳算法中它表示一個染色體。例如由10個任務(wù)和5臺主機組成的系統(tǒng)中，方案[2，1，5，4，2，3，5，1，4，5]表示第1個任務(wù)由第2臺主機完成，第2個任務(wù)由第1臺主機完成，第3個任務(wù)由第5臺主機完成，依次類推。
遺傳算法通過適應(yīng)度函數(shù)來確定染色體的優(yōu)劣，所以必須根據(jù)實際問題的需要選擇適應(yīng)值函數(shù)。由于一次調(diào)度過程中，求解的任務(wù)總完成時間makespan是一個最小值，故定義適應(yīng)度函數(shù)為：
其中，ms為對應(yīng)某一染色體編碼的任務(wù)總完成時間，是makespan的縮寫，msmin為總完成時間的最小估算值，msmax為總完成時間的最大估算值，msmin和msmax適當(dāng)取值，使0<fit(ms)<1。總完成時間ms越小，適應(yīng)度fit(ms)越大，該染色體被選中的可能性就越大。
改進遺傳算法的流程如下：
(1)隨機產(chǎn)生滿足染色體定義的初始種群，種群大小為popsize；定義進化代數(shù)的初值和最大值，設(shè)定交叉概率、變異概率等初始參數(shù)；
(2)計算種群中每一個個體所對應(yīng)的適應(yīng)度函數(shù)值及負載均衡度值；
(3)將種群中負載均衡度值最低的部分個體剔除掉，并對適應(yīng)度值高的個體復(fù)制，以補充被剔除掉的個體，保證總的染色體數(shù)為popsize不變；
(4)采用輪盤賭法進行選擇操作；
(5)隨機配對，按照給定的概率進行單點交叉、交叉點隨機設(shè)置；
(6)對個體的每一個基因座，根據(jù)變異概率指定其變異點，對每一指定的變異點的基因值由除該基因值以外的隨機產(chǎn)生的[1，n]之間的數(shù)值代替；
(7)尋找種群中最大適應(yīng)度值和與之對應(yīng)的最小完成時間；
(8)判斷算法是否達到最大迭代次數(shù)，如未滿足條件，則轉(zhuǎn)步驟(2)繼續(xù)搜索；否則輸出全局最優(yōu)適應(yīng)值及其對應(yīng)的染色體，將該任務(wù)選擇方案賦給網(wǎng)格調(diào)度模型。
為了驗證本文提出的IGA算法的有效性，用IGA算法與基本遺傳算法及經(jīng)典的Min-Min算法進行對比仿真研究。
Min-Min算法[7]是網(wǎng)格調(diào)度算法的研究基礎(chǔ)，該算法的目的是將大量的任務(wù)指派給完成最早、執(zhí)行最快的機器。算法的思想為：對等待分配的每一個任務(wù)，分別計算出該任務(wù)分配到n臺機器上的最早完成時間；從中找出具有最小最早完成時間的任務(wù)，并將該任務(wù)分配給對應(yīng)的機器；分配完成后，更新機器期望就緒時間并刪除已經(jīng)分配的任務(wù)。重復(fù)上面的過程，直到分配完所有的任務(wù)。
3 仿真實驗及結(jié)果分析
在Matlab環(huán)境下設(shè)計一個網(wǎng)格任務(wù)調(diào)度系統(tǒng)模擬程序，該程序可以根據(jù)仿真的需要生成不同的主機處理能力、主機數(shù)量、任務(wù)數(shù)量、每個任務(wù)的預(yù)測執(zhí)行時間、通信開銷及其他時間開銷等參數(shù)。在用改進的遺傳算法尋找任務(wù)調(diào)度的最佳方案時，種群規(guī)模為40，最大允許迭代次數(shù)為400。在本文的所有仿真實驗中，針對每種問題都重復(fù)進行10次獨立實驗，并對實驗得到的各項數(shù)據(jù)求平均值。
(1)產(chǎn)生一個任務(wù)數(shù)為80、主機數(shù)為8的模型，將IGA、GA和Min-Min算法同時用于該模型的任務(wù)調(diào)度，圖1和圖2分別表示采用IGA和GA算法時每臺主機的執(zhí)行時間以及完成所有任務(wù)總的執(zhí)行時間情況。而圖3則表示采用Min-Min算法時的仿真結(jié)果。
從仿真結(jié)果可以看出，采用IGA進行任務(wù)調(diào)度時的makespan是22.573 1，采用GA進行任務(wù)調(diào)度時的makespan是23.611 2，而采用Min-Min算法得到的調(diào)度方案的makespan是24.100 9，采用IGA算法比采用GA算法節(jié)省了4.40%的執(zhí)行時間，采用IGA算法比采用Min-Min算法節(jié)省了6.34%的執(zhí)行時間。圖1中主機1、4、8的負載略高，總的負載均衡性較好；圖2中主機3、8的負載低，主機2負載最高，負載均衡性不如圖1；但在圖3中，主機1、3、6、8負載明顯高于其他主機，負載均衡性不如圖1，也不如圖2，這就是Min-Min算法的主要缺陷。另外，應(yīng)用IGA進行調(diào)度時，負載最大的主機與負載最小的主機的負載比值為1.085 1；采用GA算法時，這個數(shù)據(jù)為1.160 6，而采用Min-Min算法時，這個比值則為1.247 9。
(2)在主機數(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ù)量固定的情況下，主機數(shù)量從8臺均勻遞增至20臺，分別應(yīng)用IGA、GA和Min-Min算法尋找最優(yōu)調(diào)度方案，并計算三種方案的makespan，將仿真結(jié)果列于表2中，結(jié)果顯示IGA算法比GA算法和Min-Min算法得到的任務(wù)完成時間短。
在分析網(wǎng)格任務(wù)調(diào)度問題和基本遺傳算法的基礎(chǔ)上，提出了一種帶過濾機制的改進遺傳算法，并用于網(wǎng)格任務(wù)調(diào)度模型的優(yōu)化。用Matlab進行仿真實驗，仿真結(jié)果表明文中所提算法有很好的特性，得到了較基本遺傳算法和Min-Min算法更為滿意的結(jié)果，可以實現(xiàn)網(wǎng)格資源之間公平有效的任務(wù)調(diào)度。
參考文獻
[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.