一種基于改進遺傳算法的網格調度算法?

楊新年 劉 鋒 田鐵剛 湯泰青 李曉艷

（黑龍江工業學院 雞西 158100）

1 引言

網格計算是一種將異構、動態資源進行共享，利用不同網絡環境下的計算資源來解決同一任務的技術。該技術可整合孤立閑置的計算資源，形成一個計算能力比擬超級計算機的虛擬系統，以此來進行復雜的計算［1～5］。因此，網格計算實際上打破了計算資源的空間限制，將閑置資源再利用，可以節約大量的時間和財力的有前景的技術［6～8］。

根據資源的分配時間，可以將網格算法分為靜態和動態兩種。靜態調度是在開始調度之前，將資源預先分配到相應到網格任務的方法；動態調度則是在調度之后，根據算法將資源分配給相應的網格任 務［9～10］。 常 用 算 法 包 括 OLB，MET，MCT，Min-min，Max-min，RASA，Duplex、遺傳調度算法和蟻群調度算法等。經過對一些算法的比較，TBraun等得出遺傳算法在一定規模時較優，但隨著規模擴大導致其性能下降［11～15］。本文針對這個問題，提出了結合Min-min算法的改進遺傳算法。經驗證，該算法較單純的遺傳調度算法有了較大的提升。

2 網格調度問題的描述

在計算資源為有限的m個，需要完成的任務有n個的情況，為了達到在單位時間內盡量利用當前資源盡可能多地完成調度任務的目的，將n個子任務以一定的方式方法分配給m個資源，即是網格調度需要處理的問題。具體分析可分以下幾點：

1）J代表待調度的n個任務的集合，Ji代表其中的第i個任務，規定其中的每個任務都在一個資源上執行并完成。

2）R代表m個空閑可用的計算資源集合，其中用Rj來表示第j個資源。

3）通過矩陣來表示n個任務在m個不同資源上的預測執行時間（ETC）。矩陣的行表示任務在m個計算資源上的執行時間，列則表示一個資源上n個任務的不同執行時間。由此，ETC（i，j）代表第j個資源上第i個任務的執行時間。

4）數據從任務i傳輸到資源j上的所用時間為TRANS（i，j）。

5）第j個資源上第i個任務的預測最小完成時間為 MCT（i，j）=STARTTIME（j）+TRANS（i，j）+ETC（i，j）。

6）任務i的最小完成時間為Ci，當任務分配給第j個資源時，Ci=MCT（i，j）。

3 設計與實現

經典的遺傳算法在全局搜索方面具有能夠快速進行搜索的能力，其缺點是在搜索過程中，不能夠及時地根據一些運行時信息進行調節相應的進化過程，由此導致隨著迭代次數的增加，收斂性能變差。因此本文根據在搜索過程中的一些反饋信息，提出了將遺傳算法和Min-min算法相結合，一種基于雙適應度函數的混合遺傳算法來完成網格系統的調度。

3.1 編碼策略

常用的編碼方式包括二進制編碼、格雷碼編碼和實數編碼等。本文根據網格任務的調度特點采用實數編碼的方式，具體定義如下：

n個子任務 J={J1，J2，…，Jn}以一定方式分配到m個資源上，使任何和資源能夠合理地進行匹配。如圖1，染色體及資源一一對應，按照下述的編碼規則：染色體長度對應任務數量，各基因位置上的正整數代表任務編號，資源編號用其中的值來表示。

圖1 染色體及資源編碼

3.2 目標函數

網格任務的調度需要把任務執行開銷、任務間通信開銷、以及各種開銷之間的差異因素進行綜合考慮。本文調度策略以網格任務的所有任務的時間跨度timespan為其目標函數。

3.3 種群初始化算法改進

在遺傳算法中，通常會面對過早收斂和局部收斂的問題，為了解決該問題，可通過使用動態交叉和變異操作的方法，另外也可采用改進初始化種群的方法。本文通過對初始種群的平均適應度值的提高來改進產生子代，方法分為兩個主要方面，第一，是將Min-min算法和變異算子相結合，使得產生的個體較優，有較高的適應度值。第二，為保證種群的多樣性，大部分個體是隨機產生的。種群初始化個體的具體步驟如下：

第一步：利用Min-min算法產生一個個體，之后對該個體進行k-1次的變異操作，每次產生一個新的個體，會產生k-1個新個體；

第二步：隨機生成2m個新個體；

第三步：將通過前兩步生成的2m+k個的個體的適應度值計算出來，進行排序，將其中前m個個體設置為初始種群。

m的值由種群規模scale決定，一般情況下使m小于scale/4。經改進后，初始種群中會存在質量較好的個體，同時也有隨機產生的多樣性個體，這樣種群多樣性會更好。通過其中的高質量個體來引導搜索，同時降低低質量個體的變異操作產生的影響，以此來減少迭代次數提高算法性能。

3.4 雙適應度函數

適應度函數是用于判定種群中個體的適應程度，其依據目標函數建立的某種映射關系來進行求解。在任務調度中要求所有任務的時間跨度要小，任務花費的平均時間要短。所以問題轉化為：總體任務完成快且完成任務的平均時間小，據此定義兩個適應度函數，公式如下：

函數1：其中，種群規模為scale，子任務總數為N，資源s的數量為m，則初始化描述為系統隨機生成長度為n的染色體scale個，基因的取值范圍是［1，m］，在其中隨機取值。

函數2：其中，Sj為第i個染色體中的第j個資源，SCDi(Sj)是完成第i個染色體任務的時間。TaskTime(t，i)表示完成第i個染色體中第t個任務的時間。

在遺傳算法中，選擇運算以適應度函數的值為根據來擇優。式（1）和式（2）給出兩個適應度函數來進行下一代的選擇進化操作，即完成總任務的時間越短，同時所花費的平均所用時間也更短的個體，將其適應度值設為越大，從而使該個體更容易被選擇。

3.5 收斂判斷函數算法改進

為使種群多樣同時分布合理，收斂加速，盡快得到最優解。使用以下的改進方法：先對早熟收斂進行預判，若有則要及時改進早熟個體，對個體進行變異的操作，同時不斷加入新的個體保證種群的多樣性，從而提高遺傳算法的收斂性。

最優個體適應度值為 fmax，定義 fmax與之間的差值：

Δ表征種群過早收斂，可利用Δ過濾掉適應度值較低的個體，若Δ值很小或者其值的變化很小則表示較優個體趨同，此時需及時更新種群個體來保證種群的多樣性。

3.6 選擇過程

采用輪盤賭方法，先將群體中的個體進行排序，排序的依據是個體的適應度值的大小，然后據此來確定每個個體被選中的幾率。其公式如下所示：

在種群第i代個體進化中，利用c1和c2的概率來選擇 Ps1和 Ps2（其中 0＜c1＜1，c1+c2=1），并將其中一個設置為下一代個體的選擇概率，利用該方式，保證i+1代種群中包括總任務完成時間較短的個體和任務平均所用時間較短的優良個體，提高全局收斂性能。

3.7 交叉和變異

本文基于雙適應度函數的交叉與變異概率設置分別為

其中，用 fmax代表個體的最大適應度值，favg代表每一代個體平均適應度值，f'代表要交叉的兩個個體中較大的適應度值，f代表發生變異的個體的適應度值。然后利用式（7）和式（8）來計算Pc、Pm，并選取其中的最大值作為最終的Pc、Pm。

對于k1、k2、k3和k4的設定，若 Pc值大會導致種群中優良個體被過濾掉造成局部收斂；Pc值小會增加種群迭代次數；同理，Pm大也會造成局部收斂使得遺傳算法失去效用。在試驗中，在前期經過多次嘗試來確定合理的k1、k2、k3和k4。

3.8 整體流程

結合上面的方法，改進遺傳算法的具體過程，如圖2所示。

圖2 改進算法的流程

4 實驗結果

本文使用gridsim進行模擬測試改進遺傳算法的性能。根據經典遺傳算法的參數設置，將參數設置如圖3所示：種群規模為200，迭代次數為100，k1為0.39、k2為0.85、k3為0.096和 k4為0.056，c1為0.7，c2為0.3。圖3為改進GA算法與傳統GA算法的比較。

圖3 改進GA算法與傳統GA算法的比較

從圖3中能夠看出，在初始時候經典遺傳算法的性能要優于改進后的算法，隨著迭代次數增加，個體逐漸趨同，算法進入一種局部收斂的狀態。對于改進的算法，避免了局部收斂，在進行70次左右的迭代后，開始收斂；同時在迭代中期，改進算法無論從整體性能還是平均性能均較優，花費的時間更少；如此到了算法的后期，雖然整體的完成時間沒有明顯提高，但是在任務平均完成時間上有明顯的縮短。算法整體在70次左右迭代后趨于平坦，并得到最優解。因此，在種群規模較大的，問題較為復雜的情況下，改進算法的性能要優于經典遺傳算法的性能。

5 結語

本文探討了網格任務調度中會遇到的一些問題，并介紹了常見的網格調度任務。尤其對遺傳算法在網格調度中的使用，進行了分析。在規模比較小的時候，遺傳算法的優勢比較明顯。但是隨著規模的擴大，迭代次數增多，遺傳算法的性能開始降低。針對這個問題，本文提出了一種結合Min-min算法改進的遺傳算法。該算法被證明在規模較大，迭代次數較多的時候，仍然具有很好的性能。另外，模擬退火算法、蟻群算法等在網格任務調度過程中各有優缺點，如何將各個算法之間的優缺點進行綜合，提升網格調度的性能，將是筆者的下一步研究目標。