基于遺傳算法的網(wǎng)格資源分配與調(diào)度研究-科技論文發(fā)表

Research on Task Allcation Scheduling Based on  Genetic  Algorithm in Grid

Abstract: Reasonable resource scheduling can greatly improve the utilization of the grid.Based on the research of existing scheduling algorithms,this method described the adaptive selection probability combined with niche technology, PCC(Father And Son Competition) crossover operator and new mutation operator, improved GA algorithm, it keeps the population's convergence and increase the efficiency of local and global search capability. Simulation results show that this algorithm is more effective to the allocation of resources compared with other algorithms,it can be successfully applied to the independent task scheduling in grid .

Key words:grid; genetic algorithm;task scheduling;

1  引言

網(wǎng)格計算是當(dāng)今互聯(lián)網(wǎng)研究中的一個熱點,也是并行和分布處理技術(shù)的一個發(fā)展方向；在網(wǎng)格環(huán)境中,任務(wù)調(diào)度是網(wǎng)格計算研究的核心問題. 在網(wǎng)格環(huán)境下的任務(wù)調(diào)度,?？紤]的是一組相

互獨立彼此間沒有通訊和數(shù)據(jù)依賴的元任務(wù)的調(diào)度,稱為獨立任務(wù)調(diào)度,該模型應(yīng)用于很多方面,比如定積分、生物上的DNA測序、無線傳感器網(wǎng)絡(luò)等,獨立任務(wù)調(diào)度以時間跨度(makespan)為優(yōu)化目標(biāo),其已經(jīng)是一個眾所周知的NP難題, 不存在多項式時間復(fù)雜性的算法找到全局最優(yōu)解. 因此,研究網(wǎng)格下任務(wù)調(diào)度是一項很有意義的工作.

關(guān)于網(wǎng)格環(huán)境下獨立任務(wù)的調(diào)度問題,國內(nèi)外學(xué)者做了大量研究工作,先后提出了許多啟發(fā)式調(diào)度算法.Min-Min算法^[1-2]盡量把更多的任務(wù)分配到執(zhí)行它的速度最快并能最早完成它的機器上, 但可能導(dǎo)致系統(tǒng)負(fù)載很不平衡；Max-Min算法^[2-3]雖然能產(chǎn)生比較平衡的負(fù)載, 但由于有更多的任務(wù)沒有分配到最佳的機器上, 其性能比Min-Min差.文獻(xiàn)^[4]使用了分而治之的思想提出了一個分段Min-Min算法(SMM), 它首先把任務(wù)按最小完成時間從大到小的順序排序, 然后把它們分成4段, 在每段內(nèi)運行Min-Min算法, 這樣在段間先保證了負(fù)載平均, 而段內(nèi)保證有更多的任務(wù)被分配到其最佳的機器上,執(zhí)行速度也更快. Suffrage算法^[5]計算每個任務(wù)的最小完成時間和次小完成時間的差值,選取所有任務(wù)中差值最小的任務(wù)和計算資源.以上經(jīng)典的調(diào)度理論都是基于優(yōu)先級確定性調(diào)度技術(shù),以犧牲全局最優(yōu)解來降低算法的時間復(fù)雜度.近年來,遺傳算法(Genetic Algorithm , GA)因具有強大穩(wěn)健的隱并行解空間搜索功能,被廣泛應(yīng)用于任務(wù)分配和調(diào)度問題的求解. 對GA的研究表明,收斂性和多樣性的平衡是其改進(jìn)的關(guān)鍵,因此，本文從初始種群、選擇、交叉、變異入手改進(jìn)GA的性能，使其成功應(yīng)用于網(wǎng)格任務(wù)調(diào)度.

2  問題的描述

一個網(wǎng)格計算通常由m 臺異構(gòu)處理器組成, 有n 個獨立任務(wù)要競爭使用處理器, 分配的目標(biāo)是把這n個任務(wù)合理地分配到m臺處理器上執(zhí)行, 使總的執(zhí)行時間最短. 由于網(wǎng)格環(huán)境是異構(gòu)的,因此用一個n×m 矩陣EXT來表示任務(wù)的估計執(zhí)行時間, 其中元素EXT(i,j)表示任務(wù)T_i在機器M _j上的估計執(zhí)行時間.定義機器運行時間MAT_j為機器完成分配給它的所有任務(wù)所需的時間, 任務(wù)T_i在機器M_j的完成時間CT_ij= MAT_j+EXT_ij,任務(wù)Ti的最小完成時間MCTi是所有CT_ij中的最小值.

任務(wù)分配的目標(biāo)是使具有最大運行時間的機器的運行時間最短:

3免疫遺傳算法

3.1群體規(guī)模選擇
　　合適的群體規(guī)模對遺傳算法的收斂具有重要意義，群體太小難以求得滿意的結(jié)果,群體太大則計算復(fù)雜.根據(jù)經(jīng)驗,群體規(guī)模一般取10-160.

3.2染色體表示

與文獻(xiàn)^[1]中采用的表示方法相同,染色體采用直接編碼的方案.假設(shè)任務(wù)數(shù)為n機器數(shù)m,染色體上的每個基因的位置編號代表任務(wù)編號, 染色體中的每個基因位表示一個任務(wù),而每個基因位的值就是對應(yīng)任務(wù)被分配的機器編號. 在這種表示方式中, 每個染色體就是一種分配方案,對應(yīng)著一個調(diào)度長度.例如,任務(wù)數(shù)n=10,機器數(shù)m=3, 染色體（1,2,1,3,2,2,3,1,1,2）,表示第1臺機器執(zhí)行第1、3、8、9個任務(wù),第2臺機器執(zhí)行第2、5、6個任務(wù),第3臺機器執(zhí)行第4、7個任務(wù)，算法的初始種群采用隨機方式生成.

3.3 與小生境技術(shù)結(jié)合的自適應(yīng)選擇概率

選擇操作的目標(biāo)就在于使種群中個體的適值增大，即提高解的性能，但由于在遺傳算法執(zhí)行的不同階段，個體間差異也不同，若用相同的選擇策略可能會導(dǎo)致問題的出現(xiàn)：1）當(dāng)個體差異較大時，淘汰掉劣勢個體也就意味著也遺失了存在于劣勢個體中的部分優(yōu)良基因；2）當(dāng)個體差異很小時，使搜索趨于隨機化而導(dǎo)致收斂速度慢。為了解決這些問題,將小生境技術(shù)引入到算法中,采用動態(tài)變化的自適應(yīng)選擇策略，小生境技術(shù)通過個體親合力距離定義的排擠策略能夠在算法的后期仍然維持較高的多樣性。定義個體I_i(P_i1P_i2⋯P_in)和I_j(P_j1P_j2⋯P_jn)的親合力:

n任務(wù)數(shù)m傳感器數(shù).

本文提出的個體親合力不僅比較兩個抗體相同基因位的數(shù)值是否相同,還計算出兩基因位數(shù)值的差距,基因位之間最大差距為m-1. A(i,j)取值范圍0～1,值越大,表示i, j 兩個個體越相似,A(i,j)=1則表示i, j兩者基因完全一致即任務(wù)分配策略相同, A(i,j)=0則表示i, j兩者基因完全不同.當(dāng)A(i,j)<VALVE（VALVE為親合力比較閥值）,比較個體Ai 和個體Aj 的適應(yīng)度大小,并對其中適應(yīng)度比較低的個體處以罰函數(shù):min(F(Ai),F(Aj))=Penalty ，其中Penalty 為一個很小的正數(shù)。自適應(yīng)選擇概率為^[6]：

p_c1=0.7,p_c2=0.3,由式（9）得最優(yōu)個體的交叉概率1.0,當(dāng)個體適應(yīng)度等于平均值時，其交叉概率為0.7，當(dāng)個體適應(yīng)度小于平均值時，交叉概率為0.3.

3.4 交叉算子

交叉方法是模仿自然生態(tài)系統(tǒng)的雙親繁殖機理而獲得新個體的方法,遺傳算法的全局搜索能力能夠得以飛躍地提高它可使父代不同的個體進(jìn)行部分基因交換組合產(chǎn)生新的優(yōu)良個體.交叉概率P_c較大時可以增強算法開辟搜索區(qū)域的能力,但會增加優(yōu)良子代被破壞的可能性.若交叉概率較小,則遺傳算法搜索可能陷入遲鈍狀態(tài).研究結(jié)果表明, 應(yīng)取為0.25-1.00之間對于基因串交叉可以采用部分匹配(PMX)交叉操作、順序交叉(Ordered Crossover,OX)、循環(huán)交叉(Cycle Crossover,CX)等.

算法采用PCC（Parents and Children Competition）交叉算子,三個父代抗體互交叉產(chǎn)生六個子代抗體,從中擇優(yōu)選擇三個最優(yōu)抗體加入到抗體群,在生產(chǎn)子代的過程中綜合更多(相對兩父輩而言)父代個體的信息,提高了解空間搜索效率的同時還增強了收斂性.PCC交叉算子流程如下:

Step1 從抗體群中隨機選取3個父抗體P_1,P_2,P_3,隨機生成交叉位POS_i(1≤POS_i≤n);

Step2 將父抗體P_1,P_2,P₃從交叉位POS_i處拆分成2個基因段,例如父個體P₁被拆分后得到左段基因PL₁和右段基因PR;

Step3 將任一父代左段基因與不同父代的右段基因組合得到2個子代抗體,例如子代抗體C₁=PL₁+PR₂,C₂=PL₁+PR₃,經(jīng)不同交叉組合得到六個子代抗體;

Step4 從六個子代抗體和三個父代抗體中競爭選取三個最優(yōu)秀解.

3.5  變異算子

當(dāng)前任務(wù)調(diào)度算法中可用的變異算子都為交換變異，即相互交換染色體中兩個被選取的基因座之間的基因值，從而產(chǎn)生出一個新的調(diào)度列表。這種變異算子的最大缺點是容易產(chǎn)生無效染色體，這一缺陷降低了遺傳算法在運行時特別是算法運行后期的局部搜索能力。算法將采用一種被稱為插入變異的變異算子，其方法是先在染色體中隨機選取兩個基因座，然后再將其中的一個基因座插入到另一個基因座之后或之前。

3.6 最優(yōu)保存策略 　

用歷代最優(yōu)個體替換掉當(dāng)前群體中的最差個體, 使迄今為止所得到的最優(yōu)個體不會被選擇、交叉、變異等遺傳運算所破壞. 其具體操作如下:

Step1 找出當(dāng)前群體中適應(yīng)度最高的個體和適應(yīng)度最低及次低的個體.

Step2 若當(dāng)前群體中最佳個體的適應(yīng)度比歷代最優(yōu)個體的適應(yīng)度高時,則復(fù)制當(dāng)前群體中的最佳個體取代原先的最優(yōu)個體而成為新的歷代最優(yōu)個體.

Step3添加一個與oldpop 種群的最優(yōu)個體有較大的相異因子的個體,計算它的適應(yīng)值,并將它與種群newpop 的次劣個體進(jìn)行比較,若比次劣個體的適應(yīng)值小的話,則不替換種群newpop 的次劣個體,反之則替換。

3.7  算法流程

step 1  將Min-Min算法產(chǎn)生的解加入隨機在產(chǎn)生的初始種群、初始化控制參數(shù)和記憶庫；

step2  根據(jù)公式（2）、（3）對種群實施選擇操作,得到新的種群；

step3  對新的種群實施PCC交叉操作；

step4  執(zhí)行變異操作；

step5  實施最優(yōu)保存策略；

Step6  檢驗新一代群體適應(yīng)度是否滿足要求或是否已經(jīng)滿足最大世代數(shù)的要求,若滿足則結(jié)束輸出最優(yōu)解,否則轉(zhuǎn)向step2. 

4  對比實驗和結(jié)果分析

4.1 不同算法性能的比較

對于上述設(shè)計的算法進(jìn)行多個n個任務(wù)、m個處理器分配問題的仿真測試,所有仿真實驗運行在P4 1. 8 GHzCPU、內(nèi)存2GB的同一計算機平臺上,采用MATLAB編程進(jìn)行了實現(xiàn).種群規(guī)模為50,表示任務(wù)的估計執(zhí)行時間矩陣EXT隨機生成,EXT（i,j）為1-100均勻分布的隨機值,最大世代數(shù)為300.將本文算法與基本遺傳算法（SGA）、文獻(xiàn)^[7](Min-Min Genetic Algorithm)MMGA算法作比較, MMGA算法是將Min-Min算法生成的最優(yōu)解作為初始種群的一個個體再與遺傳算法結(jié)合, 每個問題各運行100次, 取其最小時間跨度的平均值,仿真實驗結(jié)果如下.

表1：仿真實驗比較結(jié)果(單位時間)

Tab.1 Comparison of simulation results (unit time)

圖1   算法靜態(tài)性能曲線(m = 128, n= 16)              

Fig.1  algorithm static performance curve

從表1和圖1可以看出, 本文算法的性能明顯優(yōu)于SGA和MMGA ,SGA和MMGA由于采用最優(yōu)保存策略，運行到較大代數(shù)時還是無法收斂,本文算法性能曲線在較短的時間內(nèi)就快速收斂，隨著運行代數(shù)的增加,而最小時間跨度曲線幾乎保持水平一段時間,又陡降,曲線保持水平是因為收斂性緣故,而又突發(fā)陡降是采用新變異算子,增加抗體的多樣性,在進(jìn)化過程中找到了更優(yōu)秀的抗體,表現(xiàn)出較強的局部搜索能力,以上特征充分說明了本文提出的算法是成功的.

5 結(jié)論

針對網(wǎng)格計算異構(gòu)環(huán)境下獨立任務(wù)調(diào)度問題, 本文改進(jìn)遺傳算法,繼而提出與小生境技術(shù)相結(jié)合自適應(yīng)選擇概率來提高種群的收斂性、采用父子競爭(PCC)交叉算子和新的變異算子增強多樣性，在空間探索和局部求精間取得了很好的平衡.仿真實驗結(jié)果表明, 本文算法與傳統(tǒng)調(diào)度算法比較,更能有效地實現(xiàn)資源的分配,可以成功應(yīng)用于網(wǎng)格環(huán)境下獨立任務(wù)調(diào)度.

參考文獻(xiàn)：

[ 1 ] Braun T, Siegel H, Beck Netal. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems [ A ]. In: 8th IEEE Heterogeneous Computing Workshop [C].1999,15-29.

[2]Moreno R.Job scheduling and resource management techniques in dynamic grid enviroment[C]//1st European Across Grids Conference,2003.

[3]Yarkhan A,Dongarra J.Experiments with scheduling using simulated annealing in a grid enviroment[C]//Proc of Grid Computing,Baltimore,2002.

[4] Min-You Wu, Wei Shu, Hong Zhang. Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems [ A ]. In: 9th IEEE Heterogeneous  Computing Workshop [C ]. 2000, 375-385.

[5]Yarkhan A,Dongarra J.Experiments with scheduling using simulated annealing in a grid enviroment[C]//Proc of Grid Computing,Baltimore,2002.

[6]葉菁，張瑩，阮一文.一種改進(jìn)型交叉算子和自識別高變異算子新型遺傳算法的研究[J].福州大學(xué)學(xué)報（自然科學(xué)版），2008（6）：808-811.

[7] 馬景奕,隋兵,舒萬能.基于Min-Min遺傳算法的網(wǎng)格任務(wù)調(diào)度方法[J].計算機工程與應(yīng)用.2008,44（23）102-104.