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

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

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

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

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