基于改進遺傳算法的網(wǎng)格任務調度算法.pdf

1、網(wǎng)格是一個集成的計算與資源環(huán)境，它能充分吸納各種計算資源，并將它們轉化成一種隨處可得的、可靠的、標準的同時還是經(jīng)濟的計算能力，實現(xiàn)資源的全面共享。網(wǎng)格任務調度是網(wǎng)格研究的核心內容之一，如何合理地將任務分配給不同資源，使整個網(wǎng)格系統(tǒng)達到最佳的性能，這是任務調度需要解決的問題。由于網(wǎng)格自身的分布性、異構性、動態(tài)性和自治性，使得傳統(tǒng)的調度算法面臨新的挑戰(zhàn)。因此，如何在現(xiàn)有調度算法的基礎上提出一個更好的調度算法，盡可能提高網(wǎng)格系統(tǒng)的吞吐量，是一

2、個重要而現(xiàn)實的問題。遺傳算法是近年興起的一種用于解決優(yōu)化問題的啟發(fā)式算法，被廣泛應用于解決各類NP問題和任務調度問題。有仿真實驗證明：在處理調度問題時，遺傳算法與傳統(tǒng)調度算法相比更具優(yōu)越性。由于基本遺傳算法SGA（Simple Genetic Algorithm）本身存在一定的缺陷，比如“早熟”收斂和“欺騙”問題，因此大批學者都致力于改進遺傳算法的探索和研究中。而傳統(tǒng)自適應遺傳算法AGA（Adaptive Genetic Algorit

3、hm），雖能有效提高收斂速度，卻難以增強算法的魯棒性。 本文深入解析了遺傳算法和云模型的基本原理，針對SGA及AGA的不足，提出了一種云模型自適應遺傳算法CMAGA（Cloud Model Adaptive Genetic Algorithm）。CMAGA在SGA和AGA的基礎上，主要改進了以下幾個方面：選擇操作采用精英選擇與最優(yōu)保留的策略，提高了種群的多樣性，同時交叉變異操作借鑒了云模型中云滴的隨機性和穩(wěn)定傾向性特點，由云模型

4、云發(fā)生器算法產生交叉概率和變異概率，使概率值既具有傳統(tǒng)AGA的趨勢性，滿足快速尋優(yōu)能力；又具有隨機性，在適應度最大時并非絕對的零值，從而提高了避免陷入局部最優(yōu)的能力。根據(jù)網(wǎng)格任務調度的特點，設計了改進遺傳算法的各個組成部分。采用Matlab語言編寫基于改進遺傳算法的任務調度方法，對改進的遺傳算法與傳統(tǒng)遺傳算法進行比較。實驗數(shù)據(jù)證明了改進后的遺傳算法既具有全局搜索能力，又具有較快的收斂速度，具有較好的性能，該實驗達到了本文以實現(xiàn)任務調度的