多目標Memetic算法在網格作業(yè)調度中的應用研究.pdf

1、在互聯(lián)網和Web之后，網格計算成為了網絡互聯(lián)時代的又一次技術革新。網格計算試圖把全球互聯(lián)網范圍內的各種資源按需求進行共享與整合，其中的資源包括計算資源、數據資源、存儲資源和通信資源等等。而這些資源有效地聚合和廣泛地共享正是網格區(qū)別于以往其它各種共享技術的顯著特征。網格的本質是在動態(tài)、跨機構的虛擬組織中協(xié)調資源共享和協(xié)同解決問題，也就是資源提供者和消費者協(xié)商資源的共享和管理，然后資源池協(xié)同解決問題。由于網格所具有的動態(tài)性、多樣性與自相似性

2、、自治性等多重特性，網格環(huán)境下的作業(yè)調度已經成為了研究網格系統(tǒng)性能的熱點與重點。
　　 網格調度在網格系統(tǒng)中是非常重要的一種機制，也是網格技術的核心之一。網格調度性能的好壞會直接影響到網格系統(tǒng)運行效率的好壞。網格調度的主要任務是通過對資源、任務等的優(yōu)選，建立從任務集合到資源集合的映射關系，也被稱為網格資源調度、資源選擇或分配。網格調度是典型的NP完全問題，現(xiàn)如今也有比較多的方法能夠解決該問題，如遺傳算法等。這些算法通過實踐證明能

3、夠縮短任務的完成時間，并提高網格資源調度的效率。但隨著網格系統(tǒng)的發(fā)展，出現(xiàn)了很多影響網格調度系統(tǒng)效率的因素，并使得已有的方法并不能完全滿足所需要的調度性能。
　　 本文首先介紹了網格調度的相關概念、計算網格中的作業(yè)調度問題以及多目標優(yōu)化的問題，并且介紹了進化算法的基本理論與框架。在文中，針對網格系統(tǒng)中的調度問題提出了兩個優(yōu)化目標，makespan和flowtime，并由此構建了網格系統(tǒng)環(huán)境中的多目標優(yōu)化模型。本文還介紹了Meme

4、tic算法的基本理論及執(zhí)行流程，并提出一種基于網格環(huán)境中的Memetic算法來優(yōu)化前面提到的兩個目標。在該算法中，根據網格系統(tǒng)調度的特性重新設計并提出了相關適應度函數、交叉和變異算子、局部搜索策略等。在局部搜索策略中采用了兩個局部搜索算法，爬山算法和禁忌搜索算法，并針對特定的網格環(huán)境進行了相應的實驗，實驗結果表明，把本文中提出的Memetic(禁忌搜索)算法應用于網格調度系統(tǒng)中相對遺傳算法和Memetic(爬山法)算法來說有更好的收斂性