基于遺傳算法的網(wǎng)格任務(wù)調(diào)度算法的研究

本文共84頁 44159字

摘 要

計(jì)算網(wǎng)格系統(tǒng)實(shí)現(xiàn)了不同地理分布的異構(gòu)資源的共享、選擇和聚合，以解決在科研、工程、經(jīng)濟(jì)學(xué)等領(lǐng)域大規(guī)模的計(jì)算問題。網(wǎng)格資源的異構(gòu)性和地理分布性使得在大規(guī)模分布環(huán)境中的任務(wù)調(diào)度成為一個(gè)復(fù)雜的問題，而任務(wù)調(diào)度算法性能的好壞直接影響著網(wǎng)格系統(tǒng)的使用率和吞吐量。
遺傳算法是建立在自然選擇原理和自然遺傳機(jī)制上的新型優(yōu)化算法，有著簡單、通用、健壯性強(qiáng)、適于并行處理以及高效實(shí)用等顯著特點(diǎn)，因此，我們主要采用遺傳算法來解決網(wǎng)格環(huán)境下的任務(wù)調(diào)度問題。本文對(duì)任務(wù)調(diào)度算法作了如下幾個(gè)方面的改進(jìn)：
1、從考慮網(wǎng)格系統(tǒng)中各臺(tái)機(jī)器的負(fù)載均衡性出發(fā)，提出了基于虛擬截止期的元任務(wù)調(diào)度算法。參考平均閑置時(shí)間來設(shè)定任務(wù)調(diào)度的優(yōu)先級(jí)，從而縮短了任務(wù)的時(shí)間跨度，并使得負(fù)載均衡性得到了提高；
2、提出了結(jié)合免疫原理的遺傳算法。通過重新調(diào)整算法的結(jié)構(gòu)，保證了種群的多樣性；通過接種免疫疫苗，使算法的求精能力得到了顯著的增強(qiáng)。該算法縮短了時(shí)間跨度，并具有很好的收斂性能；
3、研究了信任的定義及信任模型，并針對(duì)特定的信任模型，提出了新的遺傳算法。通過設(shè)計(jì)新的編碼方案，選擇相應(yīng)的交叉、變異算子，實(shí)現(xiàn)種群的多樣化，使算法的平均信任效益值得到了明顯的提高；
4、指出了經(jīng)濟(jì)因素在網(wǎng)格系統(tǒng)中的重要性。針對(duì)本文的經(jīng)濟(jì)模型，提出了確保任務(wù)在截止期內(nèi)完成，同時(shí)盡可能最小化任務(wù)的時(shí)間和費(fèi)用的遺傳算法。算法同時(shí)考慮了子任務(wù)之間的通信和費(fèi)用，彌補(bǔ)了Buyya算法只考慮沒有依賴關(guān)系的任務(wù)調(diào)度以及只能單方面考慮時(shí)間或費(fèi)用的缺陷。

關(guān)鍵詞：網(wǎng)格，任務(wù)調(diào)度，遺傳算法，信任，經(jīng)濟(jì)
目 錄


摘 要 I
ABSTRACT II
第一章 緒論 1
1.1研究背景 1
1.1.1 網(wǎng)格計(jì)算的研究 1
1.1.2 網(wǎng)格計(jì)算與任務(wù)調(diào)度 3
1.2 網(wǎng)格環(huán)境下的任務(wù)調(diào)度 4
1.2.1 任務(wù)調(diào)度系統(tǒng)的特點(diǎn) 4
1.2.2 任務(wù)調(diào)度的模型 5
1.2.3 任務(wù)調(diào)度的算法 8
1.3研究目標(biāo)與思路 10
1.3.1 元任務(wù)調(diào)度算法 11
1.3.2 基于信任機(jī)制的任務(wù)調(diào)度算法 11
1.3.3 基于經(jīng)濟(jì)模型的任務(wù)調(diào)度算法 11
1.4 本文的內(nèi)容組織 12
1.5 本章小結(jié) 13
第二章 遺傳算法 14
2.1 遺傳算法的發(fā)展 14
2.2 遺傳算法的基本流程 14
2.3 遺傳算法的實(shí)現(xiàn)方法 16
2.3.1 編碼 16
2.3.2 適應(yīng)度函數(shù) 16
2.3.3 遺傳操作 17
2.3.4 停止準(zhǔn)則 18
2.3.5 參數(shù)設(shè)定 18
2.4 遺傳算法的基本理論 19
2.4.1模式定理 19
2.4.2 隱含并行性 20
2.4.3 收斂問題 20
2.5遺傳算法的特點(diǎn)及改進(jìn) 21
2.5.1 遺傳算法的優(yōu)缺點(diǎn) 21
2.5.2 遺傳算法的改進(jìn) 22
2.6 發(fā)展方向 23
2.7 本章小結(jié) 24
第三章 元任務(wù)調(diào)度算法 25
3.1相關(guān)工作 25
3.1.1 算法研究現(xiàn)狀 25
3.1.2 異構(gòu)性表示 26
3.2 問題描述與分析 27
3.2.1 問題描述 27
3.2.2 Min-min算法分析 27
3.3基于虛擬截止期的調(diào)度算法 28
3.3.1算法描述 28
3.3.2仿真實(shí)驗(yàn)結(jié)果與分析 30
3.4基于免疫原理的遺傳算法 33
3.4.1算法描述 33
3.4.2仿真實(shí)驗(yàn)結(jié)果與分析 37
3.5 本章小結(jié) 39
第四章 基于信任機(jī)制的任務(wù)調(diào)度算法 40
4.1相關(guān)工作 40
4.1.1信任的定義 40
4.1.2信任模型及量化 41
4.1.3算法研究現(xiàn)狀 42
4.2問題描述 43
4.2.1信任模型 43
4.2.2信任效益函數(shù) 44
4.3改進(jìn)的遺傳算法 45
4.3.1算法描述 45
4.3.2仿真實(shí)驗(yàn)結(jié)果與分析 48
4.4本章小結(jié) 50
第五章 基于經(jīng)濟(jì)模型的相關(guān)任務(wù)圖調(diào)度算法 51
5.1 相關(guān)工作 51
5.1.1 經(jīng)濟(jì)學(xué)模型 51
5.1.2 算法研究現(xiàn)狀 52
5.2問題描述與分析 54
5.2.1 問題描述 54
5.2.2 問題分析 55
5.3 改進(jìn)的遺傳算法 56
5.3.1 算法描述 57
5.3.2 仿真實(shí)驗(yàn)結(jié)果與分析 61
5.4 本章小結(jié) 63
第六章 總結(jié)與展望 64
6.1 本論文的主要成果 64
6.2 現(xiàn)有研究成果存在的問題 65
6.3 展望 65
參考文獻(xiàn) 67
致謝 74
碩士期間的科研項(xiàng)目和發(fā)表的論文 75


參考文獻(xiàn)


[1] 都志輝，陳渝，劉鵬. 網(wǎng)格計(jì)算[M]. 北京:清華大學(xué)出版社,2002,204-211
[2] Foster I. What is the Grid? A Three Point Checklist[M]. Grid Today, July 22,2002, 3-4
[3] 羅紅，幕德俊，鄧智群. 網(wǎng)格計(jì)算中任務(wù)調(diào)度研究綜述[J]. 計(jì)算機(jī)應(yīng)用研究，2005,22(5):16-19
[4] 王德民,劉小靈,劉昕,胡平. 計(jì)算網(wǎng)格中經(jīng)濟(jì)模型調(diào)度算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2006,29:207-209