1、StudyonimprovedGridTaskschedulingbasedonHybridGeneticAlgorithmbyHuTingtingAthesissubmittedinpartialsatisfactionoftheRequirementsforthedegreeofMasterofEngineeringinComputerApplicationTechnologyinCentralSouthUniversityofFo

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

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

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

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