多目標(biāo)Memetic算法在網(wǎng)格作業(yè)調(diào)度中的應(yīng)用研究.pdf

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

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

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

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