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

《基于改進(jìn)遺傳算法網(wǎng)格資源調(diào)度探究》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、基于改進(jìn)遺傳算法網(wǎng)格資源調(diào)度探究【摘要】本文借鑒了面向分組的調(diào)度算法的優(yōu)點(diǎn)，深入分析了遺傳算法中編碼串各個位的權(quán)重特點(diǎn)及個體的模式規(guī)律，對傳統(tǒng)遺傳算法進(jìn)行了改進(jìn)，新的算法具有面向分組、有針對性、同時又能夠借助優(yōu)良個體特征模式進(jìn)行變異的特征，所以能夠自適應(yīng)地、并且有方向性地進(jìn)行變異，從而增加了種群的多樣性、提高了收斂速度。通過在本文后面的對比實(shí)驗(yà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ī)模增大時，具有更好的性能?！娟P(guān)鍵詞】網(wǎng)格調(diào)度；遺傳算法；GridS

2、im；GridBroker；仿真1.網(wǎng)格資源調(diào)度簡介在網(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)性和動態(tài)性，以及運(yùn)行于網(wǎng)格系統(tǒng)之中的應(yīng)用程序?qū)τ谫Y源的不同需求，使得資源調(diào)度變得極其復(fù)雜[1H2]。一般的網(wǎng)格資源調(diào)度問題已被證明是一個NP完全問題[3][4],因此引起了更多學(xué)者的關(guān)注，成為目前網(wǎng)格計算研究領(lǐng)域中的一個焦點(diǎn)［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)系分為兩種情況，即有

3、依賴和沒有依賴。為說明問題，本文只討論簡單的無依賴的情況，數(shù)學(xué)模型假設(shè)所有的機(jī)器都是調(diào)度器可以控制的，多個任務(wù)不能在同一個計算節(jié)點(diǎn)之上并發(fā)執(zhí)行。(1)自治域中存在著多個市場，每個市場可以看作是一個虛擬組織。借助文獻(xiàn)［6］中的面向分組的思想，將多個任務(wù)相似的任務(wù)歸類到相同的分組。(2)自治域內(nèi)網(wǎng)格節(jié)點(diǎn)間通信延遲較??；在本文中的一個創(chuàng)新想法的出處來自于文獻(xiàn)［6］的面向粗粒度的調(diào)度算法，在面向粗粒度的調(diào)度中，運(yùn)用了一種分組調(diào)度策略，將相似作業(yè)進(jìn)行分組，再將分組提交到合適的運(yùn)算資源。在建立模型的時候，在此思想的基礎(chǔ)之上，引入分組的思想，有效地把遺傳算法和分組(分區(qū))結(jié)合起來，經(jīng)本文后面部分

4、的模擬實(shí)驗(yàn)驗(yàn)證，是一種有效可行的方法。(3)網(wǎng)格自治域中的節(jié)點(diǎn)數(shù)維持在一個恒定的水平上;由以上分析，抽象出如數(shù)學(xué)公式1.2所示：公式1.21.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項(xiàng)因素在選擇模型中的影響權(quán)重，在本文中它是由專家意見以及經(jīng)驗(yàn)預(yù)測等獲得的權(quán)重值；為整數(shù)變量，當(dāng)=1時，表示第i個計算資源被選中，反之當(dāng)=0時，表示未被選中。2?基于MGA的網(wǎng)格資源調(diào)度2.1改進(jìn)

5、遺傳算法（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中，從左至右

6、階碼分別為8,4,2,1,所以如果最左邊的1變?yōu)?的時候，解空間的變化幅度就是8o而同是從1變?yōu)?,在最右邊的1所能引起的解空間變化幅度是1O所以，可以先找出一定的優(yōu)良個體，然后從這些優(yōu)良個體中提取一些特征模式，建立起來小環(huán)境，接下來讓這些優(yōu)良個體通過小(范圍)區(qū)間的變異尋優(yōu)，對于那些劣質(zhì)個體,就需要借鑒優(yōu)良個體的特征模式從而來進(jìn)行較大區(qū)間的變異。實(shí)現(xiàn)有目的、帶權(quán)重的變異。1.1.2總體思路若有兩個染色體：A=()B=0=()則分段海明距(Segment-Hamming):只取染色體部分編碼來計算兩個體的海明距離。對種群進(jìn)行交叉操作后，從中選取一定數(shù)量的優(yōu)良個體建立小環(huán)境。通過上面

7、的分析，可以看出，前段的編碼對個體影響相對較大，因此，取前面一部分的編碼用來計算兩個體的分段海明距離。用這種方式來比較兩個體是否在同一個小環(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位，若為