基于混合遺傳算法的網(wǎng)格任務(wù)調(diào)度改進(jìn)研究.pdf

1、StudyonimprovedGridTaskschedulingbasedonHybridGeneticAlgorithmbyHuTingtingAthesissubmittedinpartialsatisfactionoftheRequirementsforthedegreeofMasterofEngineeringinComputerApplicationTechnologyinCentralSouthUniversityofFo

2、restryandTechnology498ShaoshanSouthRoad，TianxinDistrictChangshaHunan410004，PRCHINASupervisorAssociateProfessorYUANXiaohongMay，2013碩士學(xué)位論文基于混合遺傳算法的網(wǎng)格任務(wù)調(diào)度改進(jìn)研究摘要網(wǎng)格是一個將空間分布的資源，通信服務(wù)和計(jì)算資源集成而形成的大型的計(jì)算機(jī)系統(tǒng)，以實(shí)現(xiàn)資源共享和協(xié)調(diào)工作。由于網(wǎng)格環(huán)境中的資源具有

3、動態(tài)性、異構(gòu)性、自治性等特點(diǎn)，而任務(wù)調(diào)度是一個NP難解問題，如何對網(wǎng)格的任務(wù)高效調(diào)度，實(shí)現(xiàn)網(wǎng)格系統(tǒng)最佳性能，成為網(wǎng)格研究的重點(diǎn)之一。因此提出一種網(wǎng)格環(huán)境下的高效合理的任務(wù)調(diào)度算法具有十分重要意義。本文在研究網(wǎng)格及任務(wù)調(diào)度現(xiàn)狀的基礎(chǔ)上，基于傳統(tǒng)遺傳算法的任務(wù)調(diào)度分析，針對遺傳算法容易產(chǎn)生早熟收斂的現(xiàn)象，進(jìn)化后期搜索效率低和收斂性差等問題，結(jié)合網(wǎng)格任務(wù)調(diào)度的特點(diǎn)和目標(biāo)，提出一種基于雙適應(yīng)度的改進(jìn)的混合遺傳算法(Double—FitnessH

4、ybridGeneticAlgorithm，即DFHGA)，本文對原算法進(jìn)行以下改進(jìn)：(1)在種群初始化階段，采用兩種方式產(chǎn)生初始種群：minmin算法與遺傳變異相結(jié)合的方式和隨機(jī)方式，提高了初始種群質(zhì)量，減少算法運(yùn)行迭代次數(shù)并提高全局最優(yōu)解的質(zhì)量；(2)基于自適應(yīng)遺傳算法AGA，增加了一個適應(yīng)度，即用兩個適應(yīng)度來選擇種群個體；然后通過設(shè)置適應(yīng)度函數(shù)，利用選擇、交叉和變異概率對每代種群中個體進(jìn)行進(jìn)化，獲得總?cè)蝿?wù)執(zhí)行時間和任務(wù)平均執(zhí)行時間

5、都較短的任務(wù)調(diào)度結(jié)果，通過比較調(diào)度結(jié)果，驗(yàn)證改進(jìn)的算法的有效性。(3)改進(jìn)的算法采用了一種新的局部收斂判斷原則，提前預(yù)測早熟和收斂現(xiàn)象的發(fā)生，及時更新種群中的個體保證不斷加入新個體，有效的防止局部收斂和早熟現(xiàn)象，保證了種群個體多樣性。在算法迭代結(jié)束后結(jié)合鄰域搜索擴(kuò)大尋優(yōu)范圍。利用仿真工具GridSim，對用本文中改進(jìn)的算法進(jìn)行仿真和比較。實(shí)驗(yàn)結(jié)果表明：改進(jìn)后算法能優(yōu)于自適應(yīng)遺傳算法，不但能找到總?cè)蝿?wù)完成時問較短的調(diào)度結(jié)果，而且此調(diào)度結(jié)果