一種基于改進(jìn)遺傳算法的網(wǎng)格調(diào)度算法?

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

（黑龍江工業(yè)學(xué)院 雞西 158100）

1 引言

網(wǎng)格計(jì)算是一種將異構(gòu)、動(dòng)態(tài)資源進(jìn)行共享，利用不同網(wǎng)絡(luò)環(huán)境下的計(jì)算資源來(lái)解決同一任務(wù)的技術(shù)。該技術(shù)可整合孤立閑置的計(jì)算資源，形成一個(gè)計(jì)算能力比擬超級(jí)計(jì)算機(jī)的虛擬系統(tǒng)，以此來(lái)進(jìn)行復(fù)雜的計(jì)算［1～5］。因此，網(wǎng)格計(jì)算實(shí)際上打破了計(jì)算資源的空間限制，將閑置資源再利用，可以節(jié)約大量的時(shí)間和財(cái)力的有前景的技術(shù)［6～8］。

根據(jù)資源的分配時(shí)間，可以將網(wǎng)格算法分為靜態(tài)和動(dòng)態(tài)兩種。靜態(tài)調(diào)度是在開(kāi)始調(diào)度之前，將資源預(yù)先分配到相應(yīng)到網(wǎng)格任務(wù)的方法；動(dòng)態(tài)調(diào)度則是在調(diào)度之后，根據(jù)算法將資源分配給相應(yīng)的網(wǎng)格任 務(wù)［9～10］。 常 用 算 法 包 括 OLB，MET，MCT，Min-min，Max-min，RASA，Duplex、遺傳調(diào)度算法和蟻群調(diào)度算法等。經(jīng)過(guò)對(duì)一些算法的比較，TBraun等得出遺傳算法在一定規(guī)模時(shí)較優(yōu)，但隨著規(guī)模擴(kuò)大導(dǎo)致其性能下降［11～15］。本文針對(duì)這個(gè)問(wèn)題，提出了結(jié)合Min-min算法的改進(jìn)遺傳算法。經(jīng)驗(yàn)證，該算法較單純的遺傳調(diào)度算法有了較大的提升。

2 網(wǎng)格調(diào)度問(wèn)題的描述

在計(jì)算資源為有限的m個(gè)，需要完成的任務(wù)有n個(gè)的情況，為了達(dá)到在單位時(shí)間內(nèi)盡量利用當(dāng)前資源盡可能多地完成調(diào)度任務(wù)的目的，將n個(gè)子任務(wù)以一定的方式方法分配給m個(gè)資源，即是網(wǎng)格調(diào)度需要處理的問(wèn)題。具體分析可分以下幾點(diǎn)：

1）J代表待調(diào)度的n個(gè)任務(wù)的集合，Ji代表其中的第i個(gè)任務(wù)，規(guī)定其中的每個(gè)任務(wù)都在一個(gè)資源上執(zhí)行并完成。

2）R代表m個(gè)空閑可用的計(jì)算資源集合，其中用Rj來(lái)表示第j個(gè)資源。

3）通過(guò)矩陣來(lái)表示n個(gè)任務(wù)在m個(gè)不同資源上的預(yù)測(cè)執(zhí)行時(shí)間（ETC）。矩陣的行表示任務(wù)在m個(gè)計(jì)算資源上的執(zhí)行時(shí)間，列則表示一個(gè)資源上n個(gè)任務(wù)的不同執(zhí)行時(shí)間。由此，ETC（i，j）代表第j個(gè)資源上第i個(gè)任務(wù)的執(zhí)行時(shí)間。

4）數(shù)據(jù)從任務(wù)i傳輸?shù)劫Y源j上的所用時(shí)間為T(mén)RANS（i，j）。

5）第j個(gè)資源上第i個(gè)任務(wù)的預(yù)測(cè)最小完成時(shí)間為 MCT（i，j）=STARTTIME（j）+TRANS（i，j）+ETC（i，j）。

6）任務(wù)i的最小完成時(shí)間為Ci，當(dāng)任務(wù)分配給第j個(gè)資源時(shí)，Ci=MCT（i，j）。

3 設(shè)計(jì)與實(shí)現(xiàn)

經(jīng)典的遺傳算法在全局搜索方面具有能夠快速進(jìn)行搜索的能力，其缺點(diǎn)是在搜索過(guò)程中，不能夠及時(shí)地根據(jù)一些運(yùn)行時(shí)信息進(jìn)行調(diào)節(jié)相應(yīng)的進(jìn)化過(guò)程，由此導(dǎo)致隨著迭代次數(shù)的增加，收斂性能變差。因此本文根據(jù)在搜索過(guò)程中的一些反饋信息，提出了將遺傳算法和Min-min算法相結(jié)合，一種基于雙適應(yīng)度函數(shù)的混合遺傳算法來(lái)完成網(wǎng)格系統(tǒng)的調(diào)度。

3.1 編碼策略

常用的編碼方式包括二進(jìn)制編碼、格雷碼編碼和實(shí)數(shù)編碼等。本文根據(jù)網(wǎng)格任務(wù)的調(diào)度特點(diǎn)采用實(shí)數(shù)編碼的方式，具體定義如下：

n個(gè)子任務(wù) J={J1，J2，…，Jn}以一定方式分配到m個(gè)資源上，使任何和資源能夠合理地進(jìn)行匹配。如圖1，染色體及資源一一對(duì)應(yīng)，按照下述的編碼規(guī)則：染色體長(zhǎng)度對(duì)應(yīng)任務(wù)數(shù)量，各基因位置上的正整數(shù)代表任務(wù)編號(hào)，資源編號(hào)用其中的值來(lái)表示。

圖1 染色體及資源編碼

3.2 目標(biāo)函數(shù)

網(wǎng)格任務(wù)的調(diào)度需要把任務(wù)執(zhí)行開(kāi)銷、任務(wù)間通信開(kāi)銷、以及各種開(kāi)銷之間的差異因素進(jìn)行綜合考慮。本文調(diào)度策略以網(wǎng)格任務(wù)的所有任務(wù)的時(shí)間跨度timespan為其目標(biāo)函數(shù)。

3.3 種群初始化算法改進(jìn)

在遺傳算法中，通常會(huì)面對(duì)過(guò)早收斂和局部收斂的問(wèn)題，為了解決該問(wèn)題，可通過(guò)使用動(dòng)態(tài)交叉和變異操作的方法，另外也可采用改進(jìn)初始化種群的方法。本文通過(guò)對(duì)初始種群的平均適應(yīng)度值的提高來(lái)改進(jìn)產(chǎn)生子代，方法分為兩個(gè)主要方面，第一，是將Min-min算法和變異算子相結(jié)合，使得產(chǎn)生的個(gè)體較優(yōu)，有較高的適應(yīng)度值。第二，為保證種群的多樣性，大部分個(gè)體是隨機(jī)產(chǎn)生的。種群初始化個(gè)體的具體步驟如下：

第一步：利用Min-min算法產(chǎn)生一個(gè)個(gè)體，之后對(duì)該個(gè)體進(jìn)行k-1次的變異操作，每次產(chǎn)生一個(gè)新的個(gè)體，會(huì)產(chǎn)生k-1個(gè)新個(gè)體；

第二步：隨機(jī)生成2m個(gè)新個(gè)體；

第三步：將通過(guò)前兩步生成的2m+k個(gè)的個(gè)體的適應(yīng)度值計(jì)算出來(lái)，進(jìn)行排序，將其中前m個(gè)個(gè)體設(shè)置為初始種群。

m的值由種群規(guī)模scale決定，一般情況下使m小于scale/4。經(jīng)改進(jìn)后，初始種群中會(huì)存在質(zhì)量較好的個(gè)體，同時(shí)也有隨機(jī)產(chǎn)生的多樣性個(gè)體，這樣種群多樣性會(huì)更好。通過(guò)其中的高質(zhì)量個(gè)體來(lái)引導(dǎo)搜索，同時(shí)降低低質(zhì)量個(gè)體的變異操作產(chǎn)生的影響，以此來(lái)減少迭代次數(shù)提高算法性能。

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

適應(yīng)度函數(shù)是用于判定種群中個(gè)體的適應(yīng)程度，其依據(jù)目標(biāo)函數(shù)建立的某種映射關(guān)系來(lái)進(jìn)行求解。在任務(wù)調(diào)度中要求所有任務(wù)的時(shí)間跨度要小，任務(wù)花費(fèi)的平均時(shí)間要短。所以問(wèn)題轉(zhuǎn)化為：總體任務(wù)完成快且完成任務(wù)的平均時(shí)間小，據(jù)此定義兩個(gè)適應(yīng)度函數(shù)，公式如下：

函數(shù)1：其中，種群規(guī)模為scale，子任務(wù)總數(shù)為N，資源s的數(shù)量為m，則初始化描述為系統(tǒng)隨機(jī)生成長(zhǎng)度為n的染色體scale個(gè)，基因的取值范圍是［1，m］，在其中隨機(jī)取值。

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

在遺傳算法中，選擇運(yùn)算以適應(yīng)度函數(shù)的值為根據(jù)來(lái)?yè)駜?yōu)。式（1）和式（2）給出兩個(gè)適應(yīng)度函數(shù)來(lái)進(jìn)行下一代的選擇進(jìn)化操作，即完成總?cè)蝿?wù)的時(shí)間越短，同時(shí)所花費(fèi)的平均所用時(shí)間也更短的個(gè)體，將其適應(yīng)度值設(shè)為越大，從而使該個(gè)體更容易被選擇。

3.5 收斂判斷函數(shù)算法改進(jìn)

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

最優(yōu)個(gè)體適應(yīng)度值為 fmax，定義 fmax與之間的差值：

Δ表征種群過(guò)早收斂，可利用Δ過(guò)濾掉適應(yīng)度值較低的個(gè)體，若Δ值很小或者其值的變化很小則表示較優(yōu)個(gè)體趨同，此時(shí)需及時(shí)更新種群個(gè)體來(lái)保證種群的多樣性。

3.6 選擇過(guò)程

采用輪盤(pán)賭方法，先將群體中的個(gè)體進(jìn)行排序，排序的依據(jù)是個(gè)體的適應(yīng)度值的大小，然后據(jù)此來(lái)確定每個(gè)個(gè)體被選中的幾率。其公式如下所示：

在種群第i代個(gè)體進(jìn)化中，利用c1和c2的概率來(lái)選擇 Ps1和 Ps2（其中 0＜c1＜1，c1+c2=1），并將其中一個(gè)設(shè)置為下一代個(gè)體的選擇概率，利用該方式，保證i+1代種群中包括總?cè)蝿?wù)完成時(shí)間較短的個(gè)體和任務(wù)平均所用時(shí)間較短的優(yōu)良個(gè)體，提高全局收斂性能。

3.7 交叉和變異

本文基于雙適應(yīng)度函數(shù)的交叉與變異概率設(shè)置分別為

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

對(duì)于k1、k2、k3和k4的設(shè)定，若 Pc值大會(huì)導(dǎo)致種群中優(yōu)良個(gè)體被過(guò)濾掉造成局部收斂；Pc值小會(huì)增加種群迭代次數(shù)；同理，Pm大也會(huì)造成局部收斂使得遺傳算法失去效用。在試驗(yàn)中，在前期經(jīng)過(guò)多次嘗試來(lái)確定合理的k1、k2、k3和k4。

3.8 整體流程

結(jié)合上面的方法，改進(jìn)遺傳算法的具體過(guò)程，如圖2所示。

圖2 改進(jìn)算法的流程

4 實(shí)驗(yàn)結(jié)果

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

圖3 改進(jìn)GA算法與傳統(tǒng)GA算法的比較

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

5 結(jié)語(yǔ)

本文探討了網(wǎng)格任務(wù)調(diào)度中會(huì)遇到的一些問(wèn)題，并介紹了常見(jiàn)的網(wǎng)格調(diào)度任務(wù)。尤其對(duì)遺傳算法在網(wǎng)格調(diào)度中的使用，進(jìn)行了分析。在規(guī)模比較小的時(shí)候，遺傳算法的優(yōu)勢(shì)比較明顯。但是隨著規(guī)模的擴(kuò)大，迭代次數(shù)增多，遺傳算法的性能開(kāi)始降低。針對(duì)這個(gè)問(wèn)題，本文提出了一種結(jié)合Min-min算法改進(jìn)的遺傳算法。該算法被證明在規(guī)模較大，迭代次數(shù)較多的時(shí)候，仍然具有很好的性能。另外，模擬退火算法、蟻群算法等在網(wǎng)格任務(wù)調(diào)度過(guò)程中各有優(yōu)缺點(diǎn)，如何將各個(gè)算法之間的優(yōu)缺點(diǎn)進(jìn)行綜合，提升網(wǎng)格調(diào)度的性能，將是筆者的下一步研究目標(biāo)。