基于改進(jìn)遺傳算法的網(wǎng)格資源調(diào)度研究

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

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

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

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

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

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

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

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

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

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

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

公式1.2

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

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

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

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

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

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

2.1.1 理論來源

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

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

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

2.1.2 總體思路

若有兩個染色體：

A＝()

B=()

＝（）

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

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

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

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

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

本文模型是一個求最大值問題，為此建立如下適應(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)度實現(xiàn)過程

由上節(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)度長度為優(yōu)化性能指標(biāo)，則任務(wù)分配與調(diào)度的目標(biāo)是將這N個計算機(jī)任務(wù)分配給這M個資源并安排好它們的執(zhí)行順序，使整個任務(wù)的完成時間最短。

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

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

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

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

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

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

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

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

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

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

Selectionoperator() //選擇

{

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

select()；//輪盤賭策略

{…}

}

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

CrossoverOperator()//交叉操作

{for(i=0；i

{

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

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

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

}}

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

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

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

CrossDMMutation

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

MutationOperatior()//變異操作

{Sort(pop)；

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

findbestpop()；

//按比例選擇出最佳個體放入newpop

findworstpop()；

//按比例選出最差個體放入worstpop

int haiming=random()；

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

mutation(oldpop，newpop，haiming)；

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

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

3.模擬實驗

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

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

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

3.1 參數(shù)選擇

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

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

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

3.2 仿真代碼嵌入

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

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

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

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

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

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

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

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

Void main(void)//主程序

{

Generation=0：

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

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

Calculate_Fitness_Value()；//計算個體適應(yīng)度

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

while(generation

generation++；//下一代

Selection_operator()；//選擇操作

Crossover_operator()；//交叉操作

Mutation_operator()；//變異操作

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

Ca1culate_FitnessValue()；//計算個體適應(yīng)度

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

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

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

}

3.3 實驗結(jié)果及對比分析

實驗結(jié)果如圖3.3.1及圖3.3.2所示。

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

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

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

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

參考文獻(xiàn)：

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

[2]羅紅，慕德俊，鄧智群，王曉東.網(wǎng)格計算中資源調(diào)度研究綜述[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é)報(自然科學(xué)版)，2006(S1).

[7]林劍檸，吳慧中.基于遺傳算法的網(wǎng)格資源調(diào)度算法[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)，王志堅.網(wǎng)格環(huán)境下作業(yè)調(diào)度算法的研究[J].河海大學(xué)，2007.

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