基于遺傳算法的網格任務調度算法的研究

本文共84頁 44159字

摘 要

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

關鍵詞：網格，任務調度，遺傳算法，信任，經濟
目 錄


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


參考文獻


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