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