并行遺傳算法及其在網(wǎng)格任務(wù)調(diào)度中的應(yīng)用研究.pdf

1、網(wǎng)格是當(dāng)前并行計(jì)算技術(shù)的一個(gè)重要發(fā)展方向，其目標(biāo)是實(shí)現(xiàn)對(duì)地理上廣泛分布的大量異構(gòu)資源的資源共享。其中，任務(wù)調(diào)度是實(shí)現(xiàn)高性能網(wǎng)格計(jì)算的核心服務(wù)技術(shù)，也是保證應(yīng)用程序有效執(zhí)行的重要組成部分。
　　 網(wǎng)格任務(wù)調(diào)度是將并行程序任務(wù)分配到網(wǎng)格系統(tǒng)的處理節(jié)點(diǎn)上，涉及到程序模型和并行計(jì)算系統(tǒng)模型，算法的設(shè)計(jì)要綜合考慮程序和目標(biāo)系統(tǒng)的特點(diǎn)，是一種典型的NP完全問題。遺傳算法由于具有良好的全局搜索能力，在處理任務(wù)調(diào)度算法時(shí)比傳統(tǒng)調(diào)度算法更具優(yōu)越性

2、。但是，應(yīng)用基本的遺傳算法容易陷入“過早收斂”的誤區(qū)，同時(shí)求解精度不高。本文針對(duì)網(wǎng)格任務(wù)調(diào)度問題，提出了一種基于MPI的并行遺傳算法處理方式。
　　 文章首先簡(jiǎn)述了一下遺傳算法的基本原理，針對(duì)傳統(tǒng)遺傳算法自身的并行性，從全局并行的角度出發(fā)提出了一種粗粒度的并行遺傳算法。該算法采用分布式并行模式，通過子種群的個(gè)體遷移策略，緩解“早斂”和求解精度不高的問題，同時(shí)精英保留機(jī)制的引入，讓調(diào)度策略有更好的收斂性。
　　 然后，研究

3、了任務(wù)調(diào)度的機(jī)理、調(diào)度過程和調(diào)度模型，通過與現(xiàn)有調(diào)度算法的比較，確定了采用并行遺傳算法的任務(wù)調(diào)度方案，并規(guī)劃了任務(wù)調(diào)度的目標(biāo)，在滿足任務(wù)優(yōu)先約束關(guān)系的前提下實(shí)現(xiàn)最優(yōu)跨度。
　　 最后，針對(duì)網(wǎng)格動(dòng)態(tài)的、異構(gòu)的、分布的計(jì)算環(huán)境，采用C語言和消息傳遞接口MPI實(shí)現(xiàn)了本文算法，在建立的模擬網(wǎng)格環(huán)境PC機(jī)群中分別對(duì)本文算法、傳統(tǒng)遺傳算法進(jìn)行了不同分組的任務(wù)調(diào)度仿真實(shí)驗(yàn)，通過不同規(guī)模的調(diào)度時(shí)間性能進(jìn)行對(duì)比分析，結(jié)果表明，本文提出的改進(jìn)遺傳算