一種基于云遺傳算法的網格任務調度算法

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

關鍵詞：網格；資源調度；遺傳算法；云理論；云遺傳算法

中圖分類號：TP183 文獻標識碼：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 引言

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

2 資源調度特點及遺傳算法局限性分析

網格資源調度和傳統分布式調度相比，有以下特點：

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

2) 松耦合性。由于網格本身是一個大規模的、非集中式的系統，網格的資源調度系統要松耦合方式進行資源的管理與調度。

3) 可擴展性。在網格資源規模不斷擴大、應用不斷增長的情況下，網格系統的資源調度必須具有可擴展性，不至于降低網格系統的性能。

4) 動態自適應性。有的資源出了故障，有的新資源要加入到網格中，有些資源要重新開始工作等。網格中的資源不但是異構的，而且網格的結構總是不停地改變。

因此使用有效的解空間搜索技術確定解空間中的最優方案，是解決網格資源調度的有效方法。

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

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

3 基于改進遺傳算法的資源調度算法

3.1 問題描述

本文主要討論的是當子任務數量遠大于資源數量時的調度策略，如何獲取資源信息、子任務的分解方法不在討論范圍之內，不做詳細討論。首先假設：

1)某一個大型的計算程序已經被分解為若干個子任務，而且每個子任務間的數據依賴關系已知？

2)資源的實時狀態已知，每個子任務在每一個資源上執行的代價已知？

3)子任務的執行時間比調度算法的執行時間長得多，使得調度算法執行的時間和子任務間網絡通信的時間可以忽略不計？

3.2 云模型簡介

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

3.2.1 基本概念

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

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

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

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

3.2.2 正態云發生器

為了實現從定性語言值到其定量表示之間的不確定轉換，文獻提出了正態云發生器，具體算法為：

1) 生成以En為期望值，He為標準差的一個正態隨機數En′；

2) 生成以Ex為期望值，En′的絕對值為標準差的一個正態隨機數x，x稱為論域空間中的一個云滴；

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

4) 重復1)～3)，直到產生N個云滴為止。

3.3 混合遺傳算法的設計

3.3.1 自適應交叉和變異概率

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

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

算法1云遺傳算法

1) 初始化種群

2) 計算適應度

3) 選擇操作

4) 交叉

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

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

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

④He=En/c2;

⑤由算法2-3產生一對兒女.

5) 變異

①Ex取原個體;

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

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

④執行算法2-1，并生成隨機數Temp，當μ>Temp時，更新個體.

6) 轉2)，直到滿足停止條件.

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

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

4 結束語

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

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

參考文獻：

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

[2] 王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安:西安交通大學出版社，2002.

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

[4] 馬學彬，溫濤，郭權，等.一種基于遺傳算法的網格任務調度算法[J].東北大學學報(自然科學版)，2007，6(6).

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

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