網格環(huán)境中一種改進的蟻群任務調度算法.pdf

1、網格計算環(huán)境日益成為一種不受地域限制的廉價的超級計算環(huán)境,它試圖聚合分布在世界各地的計算、存儲、知識、通信和信息等各類資源,以服務大眾為目的,實現資源共享與協同工作。但由于網格資源具有異構性、動態(tài)性、自治性以及分布性等特點,網格環(huán)境下進行任務調度是一個很具挑戰(zhàn)性的問題。網格任務調度算法直接關系到任務執(zhí)行的速度,在網格技術研究中起著重要作用。
　　 50年代中期仿生學應運而生,人們不斷地從生物進化的機理中得到啟發(fā),提出了許多用于解

2、決復雜優(yōu)化問題的新方法,比如遺傳算法、神經網絡、模擬退火算法等,并成功應用于解決實際問題。近年來,許多學者將蟻群算法應用于網格任務調度技術,并取得了不錯的效果。但是目前研究者較少考慮仿生算法初始參數設置對算法收斂性能的影響。在蟻群算法中存在的信息啟發(fā)因子α、期望因子β、信息素強度因子Q、信息素揮發(fā)因子ρ共四個參數中,α反應了螞蟻受其它螞蟻經過網格資源節(jié)點時留下的信息素影響程度,其值越大,螞蟻越傾向于選擇其他螞蟻選擇過的資源節(jié)點,β反應了

3、螞蟻受資源的固有屬性的影響程度,其值越大,螞蟻越傾向于選擇條件好的資源,這兩個參數的值越大,蟻群算法極易陷入局部最優(yōu)。Q能夠加強正反饋,使搜索朝有利于尋找最優(yōu)解的方向進行,ρ能夠避免信息素無限積累,從而擴大搜索范圍,以提高求解的效率。本文提出了一種新的改進蟻群算法NACA(new ant colony algorithm),先對蟻群算法中的四個參數進行隨機編碼,產生染色體,利用蟻群算法得到一組較優(yōu)解;再利用遺傳算法的優(yōu)點對這組值進行交叉

4、、變異,選擇產生更優(yōu)的解;最后將這組值作為蟻群算法下一輪探索的原始值,進行最大次數的循環(huán)迭代直至停止,即求得參數組合的近似最優(yōu)解。NACA利用遺傳算法快速隨機的全局搜索能力,以探索出蟻群算法中的四個參數α、β、ρ、Q的優(yōu)化組合,將它應用于網格系統(tǒng)任務調度中,系統(tǒng)的性能得到了明顯的改善。
　　 利用網格模擬器GridSim對所提出的算法進行了仿真模擬,結果表明所提出的算法具有更短的調度長度和更寬的適應性,當任務已知時,執(zhí)行時間約縮