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

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

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

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

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