網(wǎng)格環(huán)境中一種改進(jìn)的蟻群任務(wù)調(diào)度算法.pdf

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

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

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

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