【摘 要】本文借鑒了面向分組的調(diào)度算法的優(yōu)點(diǎn)，深入分析了遺傳算法中編碼串各個(gè)位的權(quán)重特點(diǎn)及個(gè)體的模式規(guī)律，對(duì)傳統(tǒng)遺傳算法進(jìn)行了改進(jìn)，新的算法具有面向分組、有針對(duì)性、同時(shí)又能夠借助優(yōu)良個(gè)體特征模式進(jìn)行變異的特征，所以能夠自適應(yīng)地、并且有方向性地進(jìn)行變異，從而增加了種群的多樣性、提高了收斂速度。通過(guò)在本文后面的對(duì)比實(shí)驗(yàn)，證明了當(dāng)標(biāo)準(zhǔn)遺傳算法（GA）調(diào)度算法與改進(jìn)遺傳算法（MGA）同時(shí)應(yīng)用在相同（資源數(shù)和任務(wù)數(shù)相同）的網(wǎng)格調(diào)度系統(tǒng)中時(shí)，后者使網(wǎng)格調(diào)度的總體響應(yīng)時(shí)間有了明顯的減少；并且當(dāng)調(diào)度的規(guī)模增大時(shí)，具有更好的性能。

【關(guān)鍵詞】網(wǎng)格調(diào)度；遺傳算法；GridSim；GridBroker；仿真

1.網(wǎng)格資源調(diào)度簡(jiǎn)介

在網(wǎng)格系統(tǒng)中，調(diào)度是其重要的組成部分，它要根據(jù)任務(wù)信息采用適當(dāng)?shù)牟呗园巡煌娜蝿?wù)分配到相應(yīng)的資源結(jié)點(diǎn)上去運(yùn)行。由于網(wǎng)格系統(tǒng)的異構(gòu)性和動(dòng)態(tài)性，以及運(yùn)行于網(wǎng)格系統(tǒng)之中的應(yīng)用程序?qū)τ谫Y源的不同需求，使得資源調(diào)度變得極其復(fù)雜[1][2]。

一般的網(wǎng)格資源調(diào)度問題已被證明是一個(gè)NP完全問題[3][4]，因此引起了更多學(xué)者的關(guān)注，成為目前網(wǎng)格計(jì)算研究領(lǐng)域中的一個(gè)焦點(diǎn)[5]。

1.1 網(wǎng)格調(diào)度數(shù)學(xué)模型

該數(shù)學(xué)模型定義調(diào)度算法的主要術(shù)語(yǔ)，不假設(shè)不支持搶先調(diào)度。并且該模型是針對(duì)已經(jīng)分解的應(yīng)用，即假設(shè)應(yīng)用已經(jīng)分解成N個(gè)任務(wù)，這些任務(wù)之間的關(guān)系分為兩種情況，即有依賴和沒有依賴。為說(shuō)明問題，本文只討論簡(jiǎn)單的無(wú)依賴的情況，數(shù)學(xué)模型假設(shè)所有的機(jī)器都是調(diào)度器可以控制的，多個(gè)任務(wù)不能在同一個(gè)計(jì)算節(jié)點(diǎn)之上并發(fā)執(zhí)行。

（1）自治域中存在著多個(gè)市場(chǎng)，每個(gè)市場(chǎng)可以看作是一個(gè)虛擬組織。借助文獻(xiàn)[6]中的面向分組的思想，將多個(gè)任務(wù)相似的任務(wù)歸類到相同的分組。

（2）自治域內(nèi)網(wǎng)格節(jié)點(diǎn)間通信延遲較小；在本文中的一個(gè)創(chuàng)新想法的出處來(lái)自于文獻(xiàn)[6]的面向粗粒度的調(diào)度算法，在面向粗粒度的調(diào)度中，運(yùn)用了一種分組調(diào)度策略，將相似作業(yè)進(jìn)行分組，再將分組提交到合適的運(yùn)算資源。在建立模型的時(shí)候，在此思想的基礎(chǔ)之上，引入分組的思想，有效地把遺傳算法和分組（分區(qū)）結(jié)合起來(lái)，經(jīng)本文后面部分的模擬實(shí)驗(yàn)驗(yàn)證，是一種有效可行的方法。

（3）網(wǎng)格自治域中的節(jié)點(diǎn)數(shù)維持在一個(gè)恒定的水平上；

由以上分析，抽象出如數(shù)學(xué)公式1.2所示：

公式1.2

1.2 抽象調(diào)度數(shù)學(xué)模型

h≥0 //任務(wù)j的需求量要大于0；

以上式中，N為一個(gè)市場(chǎng)（虛擬組織）中計(jì)算資源的個(gè)數(shù)；M為任務(wù)的個(gè)數(shù)；變量i用于指示網(wǎng)格計(jì)算資源；變量j用于指示任務(wù)；變量k用于指示評(píng)價(jià)指標(biāo)；為任務(wù)j到計(jì)算資源i的單位運(yùn)輸成本；為任務(wù)j的需求量；為第k項(xiàng)因素在選擇模型中的影響權(quán)重，在本文中它是由專家意見以及經(jīng)驗(yàn)預(yù)測(cè)等獲得的權(quán)重值；為整數(shù)變量，當(dāng)=1時(shí)，表示第i個(gè)計(jì)算資源被選中，反之當(dāng)=0時(shí)，表示未被選中。

2.基于MGA的網(wǎng)格資源調(diào)度

2.1 改進(jìn)遺傳算法（MGA）

本文在深入研究了基于傳統(tǒng)遺傳算法后[7]，提出了一種面向分組的，并且基于優(yōu)良個(gè)體特征方向來(lái)變異的變異算子。這樣，可以改進(jìn)傳統(tǒng)遺傳算法的一些缺陷，使其能夠有目的地、自適應(yīng)地、有方向地進(jìn)行變異，以此增加種群的多樣性并提高其收斂速度。

2.1.1 理論來(lái)源

在“模式定理”及“積木塊假設(shè)”基礎(chǔ)上，本文認(rèn)為每一個(gè)個(gè)體之所以能夠保持其優(yōu)良與否的地位，原因就是其模式中具有一些一定的特征，對(duì)一般的二進(jìn)制和級(jí)連交叉二進(jìn)制編碼來(lái)說(shuō)，碼的前面部分的變動(dòng)使該個(gè)體在解空間內(nèi)移動(dòng)的范圍(距離)比較大，而后面部分段卻恰恰相反，它們只能使得個(gè)體的解空間在該個(gè)體附近稍作變動(dòng)。

比如：在1011中，從左至右階碼分別為8，4，2，1，所以如果最左邊的1變?yōu)?的時(shí)候，解空間的變化幅度就是8。而同是從1變?yōu)?，在最右邊的1所能引起的解空間變化幅度是1。

所以，可以先找出一定的優(yōu)良個(gè)體，然后從這些優(yōu)良個(gè)體中提取一些特征模式，建立起來(lái)小環(huán)境，接下來(lái)讓這些優(yōu)良個(gè)體通過(guò)小（范圍）區(qū)間的變異尋優(yōu)，對(duì)于那些劣質(zhì)個(gè)體，就需要借鑒優(yōu)良個(gè)體的特征模式從而來(lái)進(jìn)行較大區(qū)間的變異。實(shí)現(xiàn)有目的、帶權(quán)重的變異。

2.1.2 總體思路

若有兩個(gè)染色體：

A＝()

B=()

＝（）

則分段海明距（Segment-Hamming）：

只取染色體部分編碼來(lái)計(jì)算兩個(gè)體的海明距離。對(duì)種群進(jìn)行交叉操作后，從中選取一定數(shù)量的優(yōu)良個(gè)體建立小環(huán)境。

通過(guò)上面的分析，可以看出，前段的編碼對(duì)個(gè)體影響相對(duì)較大，因此，取前面一部分的編碼用來(lái)計(jì)算兩個(gè)體的分段海明距離。用這種方式來(lái)比較兩個(gè)體是否在同一個(gè)小環(huán)境中，若有兩個(gè)個(gè)體分段海明距離為零，則認(rèn)為這樣的個(gè)體是在同一小環(huán)境中，則只取其中一個(gè)作為這個(gè)小環(huán)境的代表。通過(guò)對(duì)種群中提出一定數(shù)量的這樣的優(yōu)良個(gè)體，能夠建立起若干個(gè)小環(huán)境。對(duì)于這些小環(huán)境，在每個(gè)局部范圍內(nèi)進(jìn)行變異搜索，采用后段編碼進(jìn)行窮舉變異，找到每個(gè)小環(huán)境局部的最優(yōu)(當(dāng)然全局最優(yōu)可能在其中)。

具體方法如下；如編碼長(zhǎng)為12位，若為111111111010，取分段海明距離為8(指前段，即加了下畫線的那一段不作變異)，那么后面的4位碼長(zhǎng)可能就有24個(gè)個(gè)體，即從0000到1111，我們窮舉這些個(gè)體(111111110000～111111111111)計(jì)算每一個(gè)的適應(yīng)度，找出它們中的最優(yōu)。

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

本文模型是一個(gè)求最大值問題，為此建立如下適應(yīng)度函數(shù)：

公式2.1.2適應(yīng)度函數(shù)公式

其中，是網(wǎng)格調(diào)度的數(shù)學(xué)模型公式，其形式見1.2節(jié)。是是到當(dāng)前所有代的最小值，且隨著代數(shù)變化。

2.2 資源調(diào)度實(shí)現(xiàn)過(guò)程

由上節(jié)中的數(shù)學(xué)模型知：設(shè)參與調(diào)度的任務(wù)集合為S，S={S[0]，S[1]，…S[N-1]}，其中N為任務(wù)的總數(shù)，參與調(diào)度的異構(gòu)機(jī)器集合為H，H={H[0]，H[1]，…H[M-1]}，其中M為機(jī)器的數(shù)量。如果我們以調(diào)度長(zhǎng)度為優(yōu)化性能指標(biāo)，則任務(wù)分配與調(diào)度的目標(biāo)是將這N個(gè)計(jì)算機(jī)任務(wù)分配給這M個(gè)資源并安排好它們的執(zhí)行順序，使整個(gè)任務(wù)的完成時(shí)間最短。

對(duì)任務(wù)分配與調(diào)度的影響因素歸納起來(lái)有四類，即任務(wù)間的約束關(guān)系、任務(wù)計(jì)算時(shí)間等時(shí)間屬性、資源之間的數(shù)據(jù)傳輸延遲和數(shù)據(jù)分配策略。

結(jié)合數(shù)學(xué)模型，資源調(diào)度中的MGA算法應(yīng)用要遵循如下步驟：

步驟1：初始化執(zhí)行開銷矩陣E和通信開銷矩陣c；

步驟2：讀入DAG圖，生成每個(gè)子任務(wù)之間的邏輯關(guān)系；

步驟3：按照初始種群生成算法產(chǎn)生大小為N的初始種群；

步驟4：計(jì)算每條染色體的適應(yīng)值；

步驟5：判斷是否滿足遺傳算法的終止條件，如果滿足，則停止計(jì)算，輸出最優(yōu)調(diào)度長(zhǎng)度和對(duì)應(yīng)的染色體。

●選擇、交叉設(shè)計(jì)

用連續(xù)的整數(shù)為每一個(gè)計(jì)算資源賦一個(gè)ID號(hào)，采用二進(jìn)制編碼方法，編碼位串的長(zhǎng)度為計(jì)算資源的個(gè)數(shù)N，以N=8為例，則編碼串00110100表示ID為3，4，6的計(jì)算資源被選中。

在本文中，選擇算法過(guò)程為首先確定每個(gè)個(gè)體的適應(yīng)度，然后選出最優(yōu)個(gè)體直接進(jìn)入下一代(精英保存策略)，再按照輪盤賭策略進(jìn)行選擇操作。

Selectionoperator() //選擇

{

CopyBestChrom(newpop)//保存最優(yōu)個(gè)體到newpop

select()；//輪盤賭策略

{…}

}

交叉算子采用兩點(diǎn)交叉，交叉點(diǎn)的位置隨機(jī)確定。經(jīng)過(guò)交叉生成的兩個(gè)個(gè)體，分別對(duì)它們計(jì)算適應(yīng)值。如果生成的子個(gè)體的適應(yīng)值大于父?jìng)€(gè)體，則按照一定的概率替換父染色體。反之，則選擇原種群中適應(yīng)值最小的染色體比較，如果新子個(gè)體的適應(yīng)值大于最低適應(yīng)值，則替換原染色體；否則舍棄生成的子染色體，并重新選擇父染色體進(jìn)行交叉操作。本文采用的的這種交叉策略，這樣有利于新個(gè)體的產(chǎn)生又不容易使遺傳算法陷入早熟。

CrossoverOperator()//交叉操作

{for(i=0；i

{

random(pop，*parent1，*parent2)；//當(dāng)前種群中隨機(jī)抽取父代個(gè)體

cross(*parentl，*parent2，*ehild1，*child2，Pc)；//根據(jù)Pc確定交叉點(diǎn)，進(jìn)行父代個(gè)體的交叉重組獲取子代個(gè)體

insert(*childl，*child2，newpop)；//將新個(gè)體插入新種群

}}

●改進(jìn)變異操作設(shè)計(jì)

本文變異操作采用前文提出的基于優(yōu)良個(gè)體特征模式的方向變異算子，該算子通過(guò)計(jì)算種群個(gè)體的適應(yīng)度，再?gòu)闹谐槌鲞m應(yīng)度較高的個(gè)體并分析、選擇其特征基因位，然后將適應(yīng)度較低的個(gè)體按照這些特征基因位進(jìn)行變異，以控制種群的變異方向。實(shí)質(zhì)上就是將某個(gè)子任務(wù)遷移到另一個(gè)資源上執(zhí)行。為了防止子任務(wù)在遷移后，執(zhí)行的時(shí)間增大而造成種群退化，在此規(guī)定，遷移后子任務(wù)占用的資源不是隨機(jī)產(chǎn)生的，而是在除了該子任務(wù)目前占用的資源外的資源集中，選擇使該子任務(wù)執(zhí)行時(shí)間最短的資源，并將其遷移到該資源上進(jìn)行執(zhí)行。

該變異過(guò)程需要保證劣質(zhì)個(gè)體的方向變異所用的碼長(zhǎng)和用來(lái)衡量的分段海明距離所用的碼長(zhǎng)和交叉點(diǎn)前段的碼長(zhǎng)不能相同，否則這種變異就成為了一種變相的交叉，會(huì)抑制種群的多樣性，由此，在變異算子中給出其控制約束函數(shù)：

CrossDMMutation

在此，Cross表示通過(guò)交叉算子獲得的交叉位，DMMutation表示經(jīng)過(guò)變異過(guò)程發(fā)生變異的位。

MutationOperatior()//變異操作

{Sort(pop)；

//種群內(nèi)個(gè)體按適應(yīng)度大小進(jìn)行排序

findbestpop()；

//按比例選擇出最佳個(gè)體放入newpop

findworstpop()；

//按比例選出最差個(gè)體放入worstpop

int haiming=random()；

//隨機(jī)獲取一個(gè)整數(shù)做為海明距離

mutation(oldpop，newpop，haiming)；

//根據(jù)newpop與haiming對(duì)oldpop內(nèi)個(gè)體進(jìn)行變異操作，并將新產(chǎn)生的個(gè)體加入新種群}

改進(jìn)后算法的好處顯而易見：一方面，這樣作可以增加種群的多樣性，從而加大了其在解空間上的尋優(yōu)能力，另一方面，這樣作還增加了有方向的變異，目的明確，所以可提高算法的收斂速度。對(duì)于網(wǎng)格調(diào)度系統(tǒng)的總體響應(yīng)時(shí)間的縮短起了十分重要的作用。

3.模擬實(shí)驗(yàn)

本論文采用GridSim模擬器進(jìn)行仿真實(shí)驗(yàn)。

GridSim網(wǎng)格仿真模擬器是由Melbo-

urne大學(xué)的網(wǎng)格計(jì)算和分布式系統(tǒng)實(shí)驗(yàn)室(GRIDS)領(lǐng)導(dǎo)的gridbus項(xiàng)目中開發(fā)的網(wǎng)格仿真工具集。

3.1 參數(shù)選擇

在開始驗(yàn)證本論文提出的改進(jìn)遺傳算法前，要對(duì)遺傳算法的參數(shù)進(jìn)行設(shè)定，這包括種群大小，交叉概率，和變異概率的設(shè)定。對(duì)于交叉算子和變異算子，根據(jù)參考文獻(xiàn)[8]的方法，選擇按照DAG圖結(jié)構(gòu)的10個(gè)具有50個(gè)任務(wù)的作業(yè)進(jìn)行實(shí)驗(yàn)，初始種群為100?？梢园l(fā)現(xiàn)在交叉概率取為0.74和0.76間時(shí)，適應(yīng)度函數(shù)比較穩(wěn)定，且是最優(yōu)值，故在本實(shí)驗(yàn)中，取交叉概率為0.75。

同時(shí)對(duì)于變異概率，參考文獻(xiàn)[8]實(shí)驗(yàn)表明只有設(shè)為0.01時(shí)能夠收斂。如果選取比0.01大的變異概率，無(wú)論交叉概率為多大，都不可能收斂。所以本論文中把變異概率設(shè)為0.01。

對(duì)于初始種群大小設(shè)為100。

3.2 仿真代碼嵌入

前面已經(jīng)給出了改進(jìn)算法的代碼，現(xiàn)在需要將這些代碼嵌入到模擬工具當(dāng)中：

文獻(xiàn)[9]對(duì)GridSim的Jar包里面一些主要類進(jìn)行介紹，并指出：

“對(duì)Gridbroker的Jar包部分的修改，就集中在對(duì)broker類的修改上了，因?yàn)檫@個(gè)類涉及到了算法的部分?！币罁?jù)此，本文將上一章中設(shè)計(jì)的算法分別放入相應(yīng)的broker類中。

用可視化工具Visualmodeler設(shè)置好資源數(shù)和任務(wù)數(shù)以及對(duì)應(yīng)的屬性，再自動(dòng)生成Gridbroker所需要的JAVA文件。在本實(shí)驗(yàn)中設(shè)置兩種情況：

1:3資源，20任務(wù)；

2:5資源，50任務(wù)；

前面已經(jīng)分析了各個(gè)步驟的實(shí)現(xiàn)過(guò)程，下面給出改進(jìn)遺傳算法應(yīng)用于網(wǎng)格調(diào)度的主調(diào)程序的偽代碼：

…//定義算法的控制參數(shù)（略）

Void main(void)//主程序

{

Generation=0：

Generatelnitia1_Populatlon()；//產(chǎn)生初始群體

Ca1culate_object_value()；//計(jì)算目標(biāo)函數(shù)值

Calculate_Fitness_Value()；//計(jì)算個(gè)體適應(yīng)度

Find_Best_And_worst_Individual()；//找出最優(yōu)和最差個(gè)體

while(generation

generation++；//下一代

Selection_operator()；//選擇操作

Crossover_operator()；//交叉操作

Mutation_operator()；//變異操作

Calculate_objectvalue()；//計(jì)算目標(biāo)函數(shù)值

Ca1culate_FitnessValue()；//計(jì)算個(gè)體適應(yīng)度

Find_Best_And_worst_lndividual()；//找出最優(yōu)和最差個(gè)體

Perform_Evolution()；//最優(yōu)個(gè)體保存

Output_TextReport()；//結(jié)果輸出

}

3.3 實(shí)驗(yàn)結(jié)果及對(duì)比分析

實(shí)驗(yàn)結(jié)果如圖3.3.1及圖3.3.2所示。

由圖3.3.1（3資源，20任務(wù)）看來(lái)，粗黑曲線大體均處于細(xì)黑曲線之下，這說(shuō)明，當(dāng)使用改進(jìn)的MAG之后，算法的平均完成時(shí)間大部分情況下均要小于沒有改進(jìn)前。從而體現(xiàn)了改進(jìn)遺傳算法應(yīng)用于網(wǎng)格資源調(diào)度更為有效。這種難點(diǎn)在圖3.3.2中（5資源，50任務(wù)）得到了更明顯的體現(xiàn)，在圖3.3.2當(dāng)中，不僅平均完成時(shí)間有明顯的下降，并且可以看出粗黑色曲線更為平緩，這說(shuō)明了當(dāng)任務(wù)數(shù)和資源數(shù)同時(shí)增大即調(diào)度規(guī)模變大時(shí)，改進(jìn)的MGA算法更趨于穩(wěn)定。從而證明了改進(jìn)算法比傳統(tǒng)算法性能有了較大提升。為什么會(huì)有這種提升呢？筆者認(rèn)為可以從以下幾個(gè)方面來(lái)分析。

（1）在設(shè)計(jì)改進(jìn)算法的時(shí)候，根據(jù)編碼位的權(quán)重不同，進(jìn)行了有目的的交叉和變異操作，這樣可以大幅提高算法的性能，反映到實(shí)驗(yàn)結(jié)果上就是完成時(shí)間有了明顯的縮短；

（2）借鑒了面向粗粒度的分組調(diào)度算法，在改進(jìn)算法中加入了面向分組的思想。與傳統(tǒng)算法相對(duì)比，作業(yè)能以細(xì)分的形式執(zhí)行并最終返還用戶。該策略能有效減少開銷，提高處理能力。

（3）根據(jù)模理定理，具有低階和短定義距以及適應(yīng)度高于平均適應(yīng)度的模式在后代中將以指數(shù)級(jí)增長(zhǎng)，在改進(jìn)的遺傳算法MGA中，對(duì)于劣質(zhì)個(gè)體，是按優(yōu)良個(gè)體的特征模式進(jìn)行變異的，所以在一定程度上可以說(shuō)優(yōu)良個(gè)體就是那些具有適應(yīng)度高于種群平均適應(yīng)度模式的個(gè)體集合，這樣加快了算法的方向制導(dǎo)速度；由于在MGA算法中采用了小環(huán)境技術(shù)，并且由上點(diǎn)分析可以知道劣質(zhì)個(gè)體的變異不是隨機(jī)的，而是據(jù)優(yōu)良個(gè)體的特征模式所建立的小環(huán)境來(lái)進(jìn)行有方向有目的的變異的，這樣有利于種群的多樣性形成，因此可以擴(kuò)大其在解空間里的搜索能力，不易陷人局部最優(yōu)。

參考文獻(xiàn)：

[1]都志輝，陳渝，劉鵬.網(wǎng)格計(jì)算[M].北京，清華大學(xué)出版社，2002:3-25.

[2]羅紅，慕德俊，鄧智群，王曉東.網(wǎng)格計(jì)算中資源調(diào)度研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2005，22(5):16-19.

[3]Abraham A，Buyya R，Nath B.Nature’s Heuristics for Scheduling Jobs on Computational Grids.In:Proc of the 8th Int’l Conf.on Advanced Computing and Communications(ADCOM 2000).New Delhi:Tata McGraw-Hill Publishing，2000:45-52.

[4]The DOE Common Component Architecture Project.http://www.extreme.indiana.edu/～gannon/eea_report.html.

[5]Fangpeng Dong，Selim G.Akl.Scheduling algorithms for grid computing:state of the art and open problems.Technical Report，2006.http://www.cs.queensu.ca/TechReports/Reports/2006-504.pdf.

[6]陳為，楊壽保，申凱.面向粗粒度網(wǎng)格應(yīng)用的分組調(diào)度算法[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2006(S1).

[7]林劍檸，吳慧中.基于遺傳算法的網(wǎng)格資源調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展，2004，41(12):2195-2199.

[8]M.Aggarwal，R.D.Kent and A.Ngom，Genetic Algorithm Based Scheduler for Computational Grids，inProe.Of the 19th Annual International Symposium on High Performance ComPuting Systems and Applications(HPCS’05)，PP.209-215，GuelPh，Ontario Canada，May2005.

[9]徐益強(qiáng)，王志堅(jiān).網(wǎng)格環(huán)境下作業(yè)調(diào)度算法的研究[J].河海大學(xué)，2007.

作者簡(jiǎn)介：袁馳（1980—），男，河南南陽(yáng)人，碩士研究生，高級(jí)工程師，現(xiàn)供職于河南省工商局信息中心，研究方向：信息安全、物聯(lián)網(wǎng)。