一種基于云遺傳算法的網(wǎng)格任務(wù)調(diào)度算法

摘要：首先對網(wǎng)格資源調(diào)度的特點，現(xiàn)有遺傳算法的局限性進行了分析，為了克服傳統(tǒng)遺傳算法搜索速度慢、易陷入局部最優(yōu)解的缺陷，借鑒遺傳算法的思想，利用云模型云滴的隨機性和穩(wěn)定傾向性的特點，提出了一種新的遺傳算法—云遺傳算法(CGA)，并與標(biāo)準(zhǔn)遺傳算法(SGA)和自適應(yīng)遺傳算法(AGA)進行網(wǎng)格任務(wù)調(diào)度進行了比較，以證明其有效性。

關(guān)鍵詞：網(wǎng)格；資源調(diào)度；遺傳算法；云理論；云遺傳算法

中圖分類號：TP183 文獻標(biāo)識碼：A 文章編號：1009-3044(2009)05-1181-02

Grid Task Scheduling with an Cloud Theory-Based Genetic Algorithm

WANG Chun-lian， QIU Hong-ze

(School of Computer Science and Technology， Shandong University， Jinan 250100， China)

Abstract: First， the characteristic of grid resource scheduling and limitation of current genetic algorithm are analyzed. To overcome the shortcomings of a genetic algorithm (GA). i. e. ， low convergence speedand easily getting a local optimum solution， a novel genetic algorithm， cloud theory-based geneticalgorithm ( CGA ) ， was proposed. CGA is based on both the idea of GA and the properties ofrandomness and stable tendency of a normal cloud model.

Key words: grid; resource scheduling; Genetic Algorithm( GA) ; cloud theory; cloud genetic algorithm

1 引言

隨著網(wǎng)格技術(shù)的不斷發(fā)展，網(wǎng)格資源調(diào)度技術(shù)逐漸成為網(wǎng)格研究的重點之一。本文根據(jù)網(wǎng)格資源特點，提出一種基于改進遺傳算法的網(wǎng)格資源調(diào)度策略。該策略主要針對網(wǎng)格資源的各種屬性以及用戶的QoS需求而提出，利用啟發(fā)式相關(guān)技術(shù)，綜合考慮了任務(wù)的截止時間、預(yù)算約束、最早可執(zhí)行時間等參數(shù)，在滿足各種約束條件的情況下，減小總體時間耗費，提高了資源調(diào)度的效率。

2 資源調(diào)度特點及遺傳算法局限性分析

網(wǎng)格資源調(diào)度和傳統(tǒng)分布式調(diào)度相比，有以下特點：

1) 平臺異構(gòu)性。網(wǎng)格系統(tǒng)包括各類主機、工作站甚至PC機等，由分布在Internet上的各類資源組成，可運行不同操作系統(tǒng)上，它們是異構(gòu)的。

2) 松耦合性。由于網(wǎng)格本身是一個大規(guī)模的、非集中式的系統(tǒng)，網(wǎng)格的資源調(diào)度系統(tǒng)要松耦合方式進行資源的管理與調(diào)度。

3) 可擴展性。在網(wǎng)格資源規(guī)模不斷擴大、應(yīng)用不斷增長的情況下，網(wǎng)格系統(tǒng)的資源調(diào)度必須具有可擴展性，不至于降低網(wǎng)格系統(tǒng)的性能。

4) 動態(tài)自適應(yīng)性。有的資源出了故障，有的新資源要加入到網(wǎng)格中，有些資源要重新開始工作等。網(wǎng)格中的資源不但是異構(gòu)的，而且網(wǎng)格的結(jié)構(gòu)總是不停地改變。

因此使用有效的解空間搜索技術(shù)確定解空間中的最優(yōu)方案，是解決網(wǎng)格資源調(diào)度的有效方法。

遺傳算法是一種基于空間搜索的算法，它通過選擇、交叉、變異以及適者生存的理論，模擬自然進化過程來尋找所求問題的答案。因此，遺傳算法的求解過程也稱優(yōu)化過程。

但基本遺傳算法(SGA， Simple Genetic Algorithm)都是基于初始種群即進化代數(shù)無限大為前提，這些條件實際是不能實現(xiàn)的，所以并不能保證全局最優(yōu)解的收斂性[2]，因此，對SGA的全局收斂性進行改進是一個研究方向。初始種群的產(chǎn)生方法與初始種群的規(guī)模對初始種群的個體分布情況有著相當(dāng)?shù)挠绊懀跏挤N群的個體分布情況直接影響算法的全局收斂性，而選擇、交叉、變異等算子操作又決定算法的收斂方向，對全局收斂性具有一定的影響，所以從這些方面改進遺傳算法的收斂性是較好的研究出發(fā)點。

3 基于改進遺傳算法的資源調(diào)度算法

3.1 問題描述

本文主要討論的是當(dāng)子任務(wù)數(shù)量遠大于資源數(shù)量時的調(diào)度策略，如何獲取資源信息、子任務(wù)的分解方法不在討論范圍之內(nèi)，不做詳細討論。首先假設(shè)：

1)某一個大型的計算程序已經(jīng)被分解為若干個子任務(wù)，而且每個子任務(wù)間的數(shù)據(jù)依賴關(guān)系已知？

2)資源的實時狀態(tài)已知，每個子任務(wù)在每一個資源上執(zhí)行的代價已知？

3)子任務(wù)的執(zhí)行時間比調(diào)度算法的執(zhí)行時間長得多，使得調(diào)度算法執(zhí)行的時間和子任務(wù)間網(wǎng)絡(luò)通信的時間可以忽略不計？

3.2 云模型簡介

云模型是用自然語言值表示的定性概念與其定量數(shù)據(jù)表示之間的不確定性轉(zhuǎn)換模型，主要反映客觀世界事物或人類知識中概念的模糊性和隨機性，并把二者完全集成在一起，為定性與定量相結(jié)合的信息處理提供了有力手段。

3.2.1 基本概念

1) 隸屬云、正態(tài)云模型 設(shè)T為論域u上的語言值，映射CT(x):u→[0，1]，Px∈u，x→CT(x)，則CT(x)在u上的分布稱為T的隸屬云，簡稱云。當(dāng)CT(x)服從正態(tài)分布時，稱為正態(tài)云模型。正態(tài)云模型是遵循正態(tài)分布規(guī)律的、具有穩(wěn)定傾向的隨機數(shù)集，用期望值Ex、熵En和超熵He表征。

2) 期望Ex(Expectation)：在數(shù)域空間最能夠代表定性概念A(yù)～的點，即這個概念量化的最典型樣本點。

3) 熵En(Entropy)：熵反映定性概念A(yù)～的不確定性。一方面，熵反映了在數(shù)域空間可以被語言值A(chǔ)～接受的云滴群的范圍的大小，即模糊度，是定性概念亦此亦彼性的度量；另一方面，熵還反映了代表定性概念的云滴出現(xiàn)的隨機性；此外，熵還揭示了模糊性和隨機性的關(guān)聯(lián)性。熵可以用來代表一個定性概念的粒度。通常，熵越大，概念越宏觀，模糊性和隨機性也越大，確定性量化越難。

4) 超熵He(Hyperentropy)：超熵是熵的不確定性的度量，即熵的熵。

3.2.2 正態(tài)云發(fā)生器

為了實現(xiàn)從定性語言值到其定量表示之間的不確定轉(zhuǎn)換，文獻提出了正態(tài)云發(fā)生器，具體算法為：

1) 生成以En為期望值，He為標(biāo)準(zhǔn)差的一個正態(tài)隨機數(shù)En′；

2) 生成以Ex為期望值，En′的絕對值為標(biāo)準(zhǔn)差的一個正態(tài)隨機數(shù)x，x稱為論域空間中的一個云滴；

3) 計算y=e-(x-Ex)22(En′)2，令y為x屬于定性概念A(yù)～的確定度；

4) 重復(fù)1)～3)，直到產(chǎn)生N個云滴為止。

3.3 混合遺傳算法的設(shè)計

3.3.1 自適應(yīng)交叉和變異概率

云遺傳算法結(jié)合遺傳算法思想，沿用GA的交叉、變異操作概念，由正態(tài)云模型的Y條件云生成算法實現(xiàn)交叉操作，基本云生成算法實現(xiàn)變異操作．由于正態(tài)云模型具有隨機性和穩(wěn)定傾向性的特點，隨機性可以保持個體多樣性從而避免搜索陷人局部極值，而穩(wěn)定傾向性又可以很好地保護較優(yōu)個體從而對全局最值進行自適應(yīng)定位。CGA以采用實數(shù)編碼，由云模型進行個體更新．

3.3.2 混合遺傳算法的基本流程

算法1云遺傳算法

1) 初始化種群

2) 計算適應(yīng)度

3) 選擇操作

4) 交叉

①隨機生成或人為指定確定度μ;

②Ex=Ff/(Ff+Fm)*xf+Fm/(Ff+Fm)*xm;

③En=變量搜索范圍/c1;

④He=En/c2;

⑤由算法2-3產(chǎn)生一對兒女.

5) 變異

①Ex取原個體;

②En=變量搜索范圍/c3;

③He=En/c4(注：C1-4為控制系數(shù))

④執(zhí)行算法2-1，并生成隨機數(shù)Temp，當(dāng)μ>Temp時，更新個體.

6) 轉(zhuǎn)2)，直到滿足停止條件.

式（1）中，xf和xm分別為加查操作的父個體和母個體；Ff和Fm則分別對應(yīng)它們的適應(yīng)度，這意味著叫查操作中的Ex由父母雙方按適應(yīng)度大小加權(quán)確定，并向適應(yīng)度大的一方靠攏。

顯然，交叉操作實現(xiàn)了染色體（個體）的整體進化，而變異操作則是反映染色體中某個基因在一定范圍內(nèi)的突變。CGA不再引入交叉變異概率。

4 結(jié)束語

本文利用正態(tài)云模型云滴的隨機性和穩(wěn)定傾向性特點，結(jié)合遺傳算法交叉、變異思想，由云模型的Y條件云生成算法實現(xiàn)交叉操作，基本云發(fā)生器算法實現(xiàn)變異操作，巧妙地完成進化過程，提出了全新的云遺傳算法。

CGA利用了正態(tài)云模型的穩(wěn)定傾向性、隨機性特點和基于種群的進化體制。穩(wěn)定傾向性可以較好地保護較佳個體從而實現(xiàn)對最優(yōu)值的自適應(yīng)定位，隨機性可以保持個體多樣性從而提高算法防止陷人局部極值的能力。基于種群的進化體制結(jié)合正態(tài)云模型的確定度特性，使適應(yīng)度較大的個體在較小的鄰域內(nèi)進行搜索，適應(yīng)度較小的個體在較大的鄰域內(nèi)進行搜索。從而，CGA能較好地保持“勘探”和“開采”間的平衡，具備較好的搜索性能。

參考文獻：

[1] 戴朝華，朱云芳，陳維榮.云遺傳算法[J].西南交通大學(xué)學(xué)報，2006，12(6).

[2] 王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社，2002.

[3] 李德毅，孟海軍，史雪梅.隸屬云和隸屬云發(fā)生器[J].計算機研究與發(fā)展，1995，32(6).

[4] 馬學(xué)彬，溫濤，郭權(quán)，等.一種基于遺傳算法的網(wǎng)格任務(wù)調(diào)度算法[J].東北大學(xué)學(xué)報(自然科學(xué)版)，2007，6(6).

[5] Gen M，Cheng R W.Genetic algorithms and engineering optimization[M].Indianapolis:John Wiley Sons Inc，2000:59-68.

[6] 鐘求喜，謝濤，陳火旺.基于遺傳算法的任務(wù)分配與調(diào)度[J].計算機研究與發(fā)展，2000，37(10):1197-1203.