高 原顧文杰彭 暉陳 鵬

（1.南瑞集團(tuán)有限公司（國(guó)網(wǎng)電力科學(xué)研究院） 南京 211106）（2.國(guó)電南瑞科技股份有限公司 南京 211106）（3.智能電網(wǎng)保護(hù)和運(yùn)行控制國(guó)家重點(diǎn)實(shí)驗(yàn)室 南京 211106）

1 引言

隨著網(wǎng)絡(luò)和云計(jì)算［1～2］技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)正以幾何級(jí)數(shù)的方式迅速增長(zhǎng)，為了解決對(duì)海量數(shù)據(jù)的存儲(chǔ)與處理，云計(jì)算海量數(shù)據(jù)處理平臺(tái)（如Hadoop［3］、Dryad［4］等）應(yīng)運(yùn)而生。同時(shí)IT基礎(chǔ)設(shè)施發(fā)展也呈現(xiàn)CPU、內(nèi)存速度得到快速提升，而存儲(chǔ)設(shè)備的速度提升相對(duì)緩慢的狀態(tài)。如何在這些云平臺(tái)上利用有效的資源管理與調(diào)度策略提高處理效率成為一個(gè)非常重要的問題。

國(guó)內(nèi)外已有學(xué)者或者技術(shù)領(lǐng)先的IT公司研究任務(wù)調(diào)度技術(shù)。如Google的Borg［5］任務(wù)調(diào)度系統(tǒng)、Yahoo公司開發(fā)的新一代MapReduce框架YARN［6］和誕生于加州大學(xué)伯克利分校的Mesos系統(tǒng)［7］。它們的特點(diǎn)是只針對(duì)CPU、內(nèi)存資源進(jìn)行調(diào)度，容易造成其他類型的資源如磁盤IO在各個(gè)節(jié)點(diǎn)的不均衡使用。因?yàn)镮O速度相對(duì)于CPU和內(nèi)存有數(shù)量級(jí)差異，它的不均衡會(huì)造成整個(gè)系統(tǒng)的效率低下。

任務(wù)調(diào)度問題是經(jīng)典的NP-Hard問題［8］，許多學(xué)者提出了多種啟發(fā)式算法來進(jìn)行解決。文獻(xiàn)［9～10］提出使用遺傳算法解決網(wǎng)格任務(wù)調(diào)度問題，但是尋找最優(yōu)解時(shí)只考慮了任務(wù)的執(zhí)行時(shí)間這一個(gè)目標(biāo)。文獻(xiàn)［11］雖然提出了兩個(gè)適應(yīng)度函數(shù)，但本質(zhì)上還都是執(zhí)行時(shí)間這一種屬性。文獻(xiàn)［12］提出的多目標(biāo)遺傳算法以執(zhí)行時(shí)間最短和執(zhí)行費(fèi)用最低為目標(biāo)，但是與文獻(xiàn)［9～11］一樣，算法的輸入?yún)?shù)只有任務(wù)的執(zhí)行時(shí)間，沒有考慮到分布式任務(wù)調(diào)度中多種資源的負(fù)載均衡問題，比如CPU、內(nèi)存（下簡(jiǎn)稱MEM）、磁盤IO（下簡(jiǎn)稱IO）等。文獻(xiàn)［13］的蟻群算法以任務(wù)延遲時(shí)間最短為目標(biāo)。但是算法中的參數(shù)是在大量實(shí)驗(yàn)基礎(chǔ)上的經(jīng)驗(yàn)值，不具備通用性。文獻(xiàn)［14］中的粒子群算法仍然僅以任務(wù)的總完成時(shí)間最短作為調(diào)度目標(biāo)，而且由于沒有進(jìn)行局部最優(yōu)處理，算法很快便收斂到局部最優(yōu)。綜上所述，在求解分布式任務(wù)調(diào)度問題時(shí)，多數(shù)啟發(fā)式算法的研究文獻(xiàn)存在以下不足：1）大多選擇執(zhí)行時(shí)間作為適應(yīng)度函數(shù)，但是實(shí)際工程中任務(wù)的執(zhí)行時(shí)間是一個(gè)預(yù)先很難確定，也容易受到環(huán)境影響而變化的量，導(dǎo)致算法的實(shí)用性不高。并且執(zhí)行時(shí)間參數(shù)不適合調(diào)度常駐進(jìn)程；2）算法初始解和參數(shù)的優(yōu)化力度不足，算法隨機(jī)性較大；3）由于啟發(fā)式算法固有的特點(diǎn)，求解容易陷入局部最優(yōu)，往往不能得到問題最優(yōu)的解決方案；4）沒有考慮資源使用的負(fù)載均衡，特別是沒有考慮使用更容易造成任務(wù)延遲的IO資源作為調(diào)度參數(shù)。

考慮到上述調(diào)度系統(tǒng)和調(diào)度算法的不足，本文提出一種基于CPU、MEM、IO三種資源維度的遺傳算法用于任務(wù)調(diào)度，并對(duì)初始種群提出三種優(yōu)化方法，對(duì)遺傳變異過程也進(jìn)行了改進(jìn)?？紤]到硬件資源的爭(zhēng)搶會(huì)拖慢任務(wù)的執(zhí)行速度，本文采用在實(shí)際系統(tǒng)中較為實(shí)用的各類資源占用均方差作為多目標(biāo)的適應(yīng)度函數(shù)，目的在于使任務(wù)調(diào)度后的整個(gè)系統(tǒng)的資源使用更加負(fù)載均衡，減少任務(wù)之間的資源沖突，提高任務(wù)的執(zhí)行速度。最后用測(cè)試數(shù)據(jù)說明了本算法在收斂性和優(yōu)化目標(biāo)方面都有良好的表現(xiàn)。

2 支持多資源維度的分布式任務(wù)調(diào)度模型

2.1 任務(wù)調(diào)度的軟件框架

基于本文調(diào)度算法實(shí)現(xiàn)的軟件框架由資源管理器、節(jié)點(diǎn)管理器、任務(wù)管理器等模塊組成，如圖1所示。

圖1 任務(wù)調(diào)度的軟件框架

首先是由用戶定義需要被調(diào)度的任務(wù)的屬性，如各類資源的需求等。然后資源管理器中含有的調(diào)度器會(huì)根據(jù)本文的算法將任務(wù)調(diào)度到具體的節(jié)點(diǎn)，由節(jié)點(diǎn)管理器將任務(wù)實(shí)例啟動(dòng)。

2.2 任務(wù)調(diào)度的數(shù)學(xué)模型

本文任務(wù)調(diào)度算法中的各個(gè)參數(shù)的數(shù)學(xué)描述如下：

1）N個(gè)任務(wù)的集合T=｛T1，T2，T3，…，TN｝；

2）資源類型的集合R=｛CPU，MEM，IO｝；

3）M個(gè)節(jié)點(diǎn)第i種資源總量的集合Rti=｛Rti1，Rti2，Rti3，…，RtiM｝，i∈R；

4）M個(gè)節(jié)點(diǎn)第i種資源已使用量的集合Rui=｛Rui1，Rui2，Rui3，…，RuiM｝，i∈R；

5）負(fù)載均衡值：

式（1）中的負(fù)載均衡值σi是第i種資源已使用量的均方差，用來衡量該資源的使用分布情況。其中Ruij是第j個(gè)節(jié)點(diǎn)的第i種資源的使用量，Riavg是所有節(jié)點(diǎn)上第i種資源使用量的平均值。均方差越小，資源使用分布越平均，任務(wù)之間的資源競(jìng)爭(zhēng)越少，系統(tǒng)的整體運(yùn)行效率越高。

3 基于多維度資源需求的遺傳調(diào)度算法

本文對(duì)遺傳算法做了多個(gè)方面的優(yōu)化，首先任務(wù)的參數(shù)使用實(shí)際可測(cè)得的CPU、MEM和IO屬性，沒有使用不確定的執(zhí)行時(shí)間，這樣常駐類型的任務(wù)也可進(jìn)行調(diào)度；然后對(duì)初始種群使用三種方法進(jìn)行了優(yōu)化；并對(duì)算法的遺傳操作進(jìn)行了改進(jìn)；算法的適應(yīng)度函數(shù)也采用多目標(biāo)進(jìn)行了優(yōu)化。改進(jìn)后的遺傳算法流程圖如圖2所示。

圖2 改進(jìn)遺傳算法的流程圖

3.1 染色體編碼

在任務(wù)調(diào)度的遺傳算法中，一個(gè)染色體代表一種任務(wù)調(diào)度方案。如圖3所示，染色體的長(zhǎng)度是任務(wù)總數(shù)的2倍，虛線左側(cè)是任務(wù)調(diào)度的序列，左側(cè)基因的值為任務(wù)的序號(hào)。虛線右側(cè)是資源節(jié)點(diǎn)的選擇序列，右側(cè)基因的值是節(jié)點(diǎn)的序號(hào)。圖中整個(gè)染色體表示8個(gè)任務(wù)被分別調(diào)度到4個(gè)可用的資源上去執(zhí)行，其中任務(wù)T1被調(diào)度到R3即第三個(gè)節(jié)點(diǎn)上，任務(wù)T3被調(diào)度到R4，依次類推。

圖3 染色體示例

也可用｛1，3，4，8，6，5，2，7；3，4，1，2，4，2，1，3｝的形式表示，染色體的長(zhǎng)度由待調(diào)度任務(wù)的數(shù)量確定。

3.2 初始種群優(yōu)化

對(duì)初始種群的優(yōu)化思想是染色體表示的任務(wù)調(diào)度方案能夠使得各維度的資源均方差盡量小，即各個(gè)節(jié)點(diǎn)的資源使用更加均衡。本文首先使用改進(jìn)的主資源公平算法（詳見3.2.1）得到1個(gè)精英染色體；然后使用單資源維度的貪心算法（詳見3.2.2）得到3個(gè)精英染色體；最后采用讓初始種群在可能取值的范圍內(nèi)盡可能均勻分布的方法（詳見3.2.3）產(chǎn)生多個(gè)隨機(jī)均勻分布的染色體。這些染色體組成初始種群，作為遺傳算法的初始解集。

3.2.1 CMI-DRF算法

本文將IO與CPU、MEM資源統(tǒng)一考慮，設(shè)計(jì)了一種支持三維度的主資源公平算法，下稱為CMI-DRF（CPU，Memory，IO based-Dominant Resource Fairness）算法，此算法用于遺傳算法的初始種群優(yōu)化。并通過Linux操作系統(tǒng)的/proc文件系統(tǒng)采集CPU、MEM和IO資源的狀態(tài)。包括系統(tǒng)總資源容量和每個(gè)進(jìn)程資源使用的狀態(tài)。本文使用每個(gè)任務(wù)的IO需求占整個(gè)系統(tǒng)總IO容量的比值進(jìn)行調(diào)度。

以下舉例說明多資源維度DRF算法的執(zhí)行過程。假設(shè)系統(tǒng)中有4臺(tái)服務(wù)器，每臺(tái)服務(wù)器有24個(gè)CPU核心、16G的內(nèi)存，單機(jī)IO能力設(shè)定為10個(gè)單位。假設(shè)有三種類型的任務(wù)，每個(gè)任務(wù)需要在調(diào)控系統(tǒng)中啟動(dòng)4個(gè)實(shí)例，每個(gè)實(shí)例需要的資源量為

A：<2CPU，2GB，4IO>

B：<3CPU，4GB，2IO>

C：<4CPU，1GB，1IO>

對(duì)于A任務(wù)，每個(gè)實(shí)例要消耗系統(tǒng)總體CPU的1/48、內(nèi)存的1/32和IO的1/10，所以A的主消耗資源（以下簡(jiǎn)稱為主資源）為IO；同理可得B的主資源為內(nèi)存，C的主資源為CPU。

算法的調(diào)度過程如下：

初始化狀態(tài)下所有任務(wù)的主資源比例都為0，先選取A任務(wù)進(jìn)行調(diào)度，部署在node1上；然后是B和C分布在node2和node3上部署一個(gè)實(shí)例。此時(shí)三種任務(wù)的主資源使用量分別是1/10、1/16、1/24，因此下一個(gè)部署的實(shí)例應(yīng)該是任務(wù)C，部署在node4。此時(shí)C的主資源變?yōu)?/12，B的主資源份額變?yōu)樽钚?，因此?yīng)該部署一個(gè)B的實(shí)例，B的主資源是內(nèi)存，考慮到負(fù)載均衡，選擇一個(gè)內(nèi)存消耗最小的node3進(jìn)行部署。因此直到全部12個(gè)任務(wù)實(shí)例部署完成，可得到調(diào)度序列如表1。

任務(wù)在4節(jié)點(diǎn)的集群中的調(diào)度結(jié)果如圖4所示，圖中圓括號(hào)中的數(shù)字代表調(diào)度序列中的步驟編號(hào)。

圖4 多資源維度DRF算法的調(diào)度結(jié)果

將圖4的調(diào)度結(jié)果轉(zhuǎn)換為染色體的的表達(dá)方式則為：｛1，2，3，3，2，3，1，2，3，2，1，1；1，2，3，4，3，1，4，1，2，4，2，3｝。

表1 CMI-DRF算法的調(diào)度序列

3.2.2 貪心算法

本文使用貪心算法產(chǎn)生初始種群中的精英染色體，目的是使得初始種群中部分個(gè)體適應(yīng)度大，因而能更好地指導(dǎo)種群的尋優(yōu)過程。但是與DRF不同，貪心算法每次只能處理一類資源，所以需要執(zhí)行三次得到三個(gè)精英染色體加入到初始種群中，算法的流程如下：

1）如果待調(diào)度任務(wù)集合不為空，選取本次算法指定資源需求最大的任務(wù)i，否則調(diào)度完成；

2）選取該項(xiàng)資源已使用量最小的節(jié)點(diǎn)j，如果任務(wù)i的各項(xiàng)資源需求均小于節(jié)點(diǎn)j的資源空閑量，將任務(wù)調(diào)度到該節(jié)點(diǎn)，否則算法結(jié)束；

3）Di←任務(wù)i的資源需求；

4）Ruj←Ruj+Di（更新節(jié)點(diǎn)j的資源使用量）；

5）返回1）。

理論上，通過貪心算法得到的3個(gè)染色體并非最優(yōu)解，但是都是比較優(yōu)秀的可行解，它們都將被加入到本文遺傳算法的初始種群中。

3.2.3 均勻分布算法

初始種群的數(shù)量越大，遺傳算法越容易找到最優(yōu)解，但是算法的執(zhí)行時(shí)間也越長(zhǎng)。隨著待調(diào)度的任務(wù)數(shù)量增加，排列組合形成的全體染色體的數(shù)量呈指數(shù)級(jí)增長(zhǎng)。在保證算法的執(zhí)行時(shí)間可接受的同時(shí)，如何保證初始種群的多樣性是影響遺傳算法性能的一個(gè)關(guān)鍵問題，本文采用的是一種讓初始種群盡量均勻分布在全局解空間范圍內(nèi)的方法，盡最大可能保證算法能夠搜索到最優(yōu)解。

因?yàn)槌跏挤N群規(guī)模太大會(huì)讓遺傳算法執(zhí)行時(shí)間過長(zhǎng)，但是隨機(jī)生成初始種群染色體的時(shí)間是較快的。本優(yōu)化方法的思想就是盡可能多地在全局解空間內(nèi)產(chǎn)生染色體，然后在其中根據(jù)均勻分布的原則選取一個(gè)染色體子集參與遺傳算法運(yùn)算，即在全局解空間內(nèi)進(jìn)行均勻的采樣。假設(shè)有8個(gè)任務(wù)要部署在8個(gè)節(jié)點(diǎn)上，所有的部署方法組成的集合就是這個(gè)問題的全局解空間，染色體后半段的隨機(jī)值介于｛0，0，0，0，0，0，0，0｝和｛7，7，7，7，7，7，7，7｝之間（節(jié)點(diǎn)號(hào)在實(shí)際編程時(shí)采用從0開始）。圖5是一個(gè)全局解空間大體形狀的示意圖，是32個(gè)任務(wù)部署在8個(gè)節(jié)點(diǎn)上的8196個(gè)染色體的分布圖。橫坐標(biāo)是染色體個(gè)數(shù)，縱坐標(biāo)是染色體在解空間中的位置。圖中可以看出在縱軸方向分為較明顯的8段，是因?yàn)楣?jié)點(diǎn)數(shù)為8，染色體中8和9的數(shù)值不可能存在。

圖5 染色體全局解空間示意圖

從中按照均勻分布原則抽取128個(gè)染色體加入到初始種群中，這128個(gè)染色體的分布圖如圖6所示。

圖6 優(yōu)化后的初始種群示意圖

在128個(gè)均勻分布染色體的基礎(chǔ)上，用CMI-DRF算法和貪心算法產(chǎn)生的4個(gè)精英個(gè)體替換掉其中的4個(gè)染色體，組成新的既有精英個(gè)體，分布又較為均勻的初始種群。

3.3 適應(yīng)度函數(shù)設(shè)計(jì)

為了將問題的目標(biāo)函數(shù)轉(zhuǎn)換為指導(dǎo)遺傳算法尋優(yōu)的適應(yīng)度函數(shù)，本文的適應(yīng)度函數(shù)由三個(gè)部分組成，分別是σCPU、σMEM以及σIO，如下所示：

式（2）、（3）、（4）分別衡量CPU、MEM、IO的負(fù)載均衡狀態(tài)。在處理多目標(biāo)規(guī)劃問題時(shí)，一般需要將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)問題，類似地，遺傳算法的適應(yīng)度函數(shù)的設(shè)計(jì)也遵循這個(gè)原則。

假設(shè)LoadBalance（i）為第i條染色體的整體資源負(fù)載均衡值，那么它可以表示為

其中，σCPU(i)、σMEM(i)和*σIO(i)是第i條染色體的CPU、MEM和IO部分的負(fù)載均衡值。w1+w2+w3=1，且w1≥0，w2≥0，w3≥0。這里，w1、w2、w3分別為CPU、MEM和IO負(fù)載均衡部分的權(quán)重。

如果集群整體資源的負(fù)載均衡值越小，那么該任務(wù)調(diào)度方案越好。因此，本文的適應(yīng)度函數(shù)為

其中，F(xiàn)itness（i）為第i條染色體的適應(yīng)值。

3.4 遺傳操作改進(jìn)

選擇：選擇操作是為了有效地選出優(yōu)秀個(gè)體進(jìn)行交叉，將其優(yōu)秀基因遺傳到下一代，本文根據(jù)每個(gè)個(gè)體適應(yīng)度在整個(gè)種群總適應(yīng)度中所占的比例，采用輪盤賭選擇機(jī)制；

交叉：交叉操作的作用是使得算法能遍歷更大的解空間，本文采用了基于交叉點(diǎn)的多點(diǎn)交叉的方式，即對(duì)一對(duì)染色體交叉點(diǎn)的后半部分基因進(jìn)行交叉；

變異：變異操作是一種預(yù)防算法陷入局部最優(yōu)的手段，本文采用的變異方式是，基于變異點(diǎn)的單點(diǎn)隨機(jī)變異；

局部最優(yōu)處理：在一般啟發(fā)式算法中，在迭代過程中，算法容易陷入局部最優(yōu)，導(dǎo)致最優(yōu)個(gè)體的搜尋陷入停滯狀態(tài)，如果沒有干預(yù)，算法得到的解質(zhì)量并不會(huì)很高。遺傳算法也有同樣的問題，雖然變異操作也可以預(yù)防局部最優(yōu)，但是由于變異概率較小，而且變異點(diǎn)多為單點(diǎn)變異，跳出局部最優(yōu)也需要較長(zhǎng)的時(shí)間開銷。為了處理該問題：本文提出了一種基于適應(yīng)度大小的大變異。

Step1：比較當(dāng)代最優(yōu)個(gè)體適應(yīng)值與上代最優(yōu)個(gè)體適應(yīng)值大小，如果相等，更新計(jì)數(shù)器：SAME_GEN，SAME_GEN←SAME_GEN+1；否則，繼續(xù)下一輪迭代；

Step2：比較SAME_GEN與MAX_SAME_GEN大小，如果相等，則進(jìn)入Step3；否則，繼續(xù)下一輪迭代；

Step3：將當(dāng)代所有個(gè)體按照適應(yīng)值從大到小進(jìn)行排序，找到排在后面的REPLACE_NUM個(gè)個(gè)體，替換其所有基因，替換方式為隨機(jī)替換，形成新一代種群；

Step4：將Step3中形成的新一代種群替換當(dāng)前種群，繼續(xù)參與迭代計(jì)算。

由于新的種群既保留了前面迭代后遺傳下來的優(yōu)秀個(gè)體基因，又加入了新的個(gè)體，因此，能更好地跳出局部最優(yōu)。

4 實(shí)驗(yàn)結(jié)果與分析

本文的算法實(shí)現(xiàn)采用C++編程語(yǔ)言，分別實(shí)現(xiàn)了基本遺傳算法以及改進(jìn)后的遺傳算法，在任務(wù)數(shù)量固定和不固定場(chǎng)景下共進(jìn)行了數(shù)百次實(shí)驗(yàn)，對(duì)兩種算法的性能進(jìn)行對(duì)比，驗(yàn)證了改進(jìn)算法的有效性和在任務(wù)調(diào)度方面的性能提高情況。

4.1 任務(wù)數(shù)固定情況下的實(shí)驗(yàn)

在任務(wù)數(shù)固定的情況下，進(jìn)行100次實(shí)驗(yàn)，比較基本遺傳算法和改進(jìn)遺傳算法得到的最終可行解的適應(yīng)值。

考慮到磁盤IO對(duì)性能影響較大，在實(shí)驗(yàn)中，我們給予了IO較高的權(quán)重，具體的實(shí)驗(yàn)參數(shù)設(shè)置如下。

任務(wù)數(shù)量：32，每次實(shí)驗(yàn)迭代次數(shù)：100，處理機(jī)數(shù)量：8，種群規(guī)模：128，遺傳選擇：輪盤賭選擇，交叉概率：0.75，變異概率：0.05，CPU權(quán)重系數(shù)：0.1，內(nèi)存權(quán)重系數(shù)：0.1，IO權(quán)重系數(shù)：0.8。

圖7是100次實(shí)驗(yàn)后，基本遺傳算法（BGA）和改進(jìn)遺傳算法（IGA）的適應(yīng)值大小對(duì)比圖。

圖7 任務(wù)數(shù)固定情況下，多次實(shí)驗(yàn)的最終適應(yīng)值對(duì)比圖

由圖7可以看出，在任務(wù)數(shù)量固定的場(chǎng)景中，改進(jìn)后的遺傳算法在100次實(shí)驗(yàn)中，最終的適應(yīng)值絕大部分都大于基本遺傳算法（下稱BGA）得出的值，改進(jìn)遺傳算法（下稱IGA）的平均適應(yīng)值大約是基本算法的2.5倍。說明精英個(gè)體的加入以及局部最優(yōu)處理確實(shí)可以起到指導(dǎo)種群向更好方向進(jìn)化的作用，因而得到的可行解的質(zhì)量也更好。

4.2 任務(wù)數(shù)變化情況下的實(shí)驗(yàn)

本次實(shí)驗(yàn)測(cè)試在不同任務(wù)數(shù)量的場(chǎng)景中，基本遺傳算法和改進(jìn)遺傳算法的性能。考慮到遺傳算法的隨機(jī)性，本實(shí)驗(yàn)每組數(shù)據(jù)是連續(xù)10次實(shí)驗(yàn)結(jié)果的平均值。

實(shí)驗(yàn)參數(shù)設(shè)置如下：

每次實(shí)驗(yàn)迭代次數(shù)：100，處理機(jī)數(shù)量：8，種群規(guī)模：128，遺傳選擇：輪盤賭選擇，交叉概率：0.75，變異概率：0.05，CPU權(quán)重系數(shù)：0.1，內(nèi)存權(quán)重系數(shù)：0.1，IO權(quán)重系數(shù)：0.8。

實(shí)驗(yàn)中被調(diào)度的任務(wù)類型有8種，每種任務(wù)對(duì)CPU、MEM和IO的需求如表2所示，其中CPU單位是核心、內(nèi)存是G字節(jié)、IO是一個(gè)比值。

表2 每種任務(wù)的資源需求

每輪實(shí)驗(yàn)通過增加任務(wù)的實(shí)例個(gè)數(shù)達(dá)到任務(wù)數(shù)量遞增的效果，如每種任務(wù)部署5個(gè)實(shí)例則共有40個(gè)任務(wù)。每輪測(cè)試的結(jié)果如圖8所示。

圖8 不同任務(wù)數(shù)量下，兩種算法最終適應(yīng)值對(duì)比圖

由圖8可以看出：隨著調(diào)度任務(wù)數(shù)量的增加，基本遺傳算法的適應(yīng)值有下降的趨勢(shì)，BGA得到的最終可行解的質(zhì)量并不高；但是與BGA不同的是，IGA在待調(diào)度任務(wù)數(shù)量增加時(shí)，依然可以得到較優(yōu)的可行解，在0-120個(gè)任務(wù)的范圍內(nèi)，改進(jìn)遺傳調(diào)度算法的平均適應(yīng)值大約是基本算法的2.6倍，表現(xiàn)出了更好的負(fù)載均衡性能。這是因?yàn)椴徽撊蝿?wù)調(diào)度的規(guī)模如何，IGA算法的初始種群要優(yōu)于BGA，而且IGA在迭代過程中會(huì)根據(jù)適應(yīng)值的變化情況，適時(shí)地進(jìn)行局部最優(yōu)處理，保證了后代種群向著全局最優(yōu)解的方向不斷進(jìn)化。與BGA相比，IGA不會(huì)因?yàn)檎{(diào)度任務(wù)規(guī)模的增大而出現(xiàn)適應(yīng)值降低的情況，因此使用IGA算法進(jìn)行任務(wù)調(diào)度時(shí)，能夠獲得更好的系統(tǒng)級(jí)負(fù)載均衡的效果。

5 結(jié)語(yǔ)

本文提出的基于多維度資源需求的改進(jìn)遺傳調(diào)度算法能夠支持使用CPU、內(nèi)存、磁盤IO三個(gè)維度的資源進(jìn)行調(diào)度，使得任務(wù)對(duì)系統(tǒng)中各個(gè)節(jié)點(diǎn)資源的使用更加負(fù)載均衡，并能同時(shí)支持調(diào)度常駐和非常駐任務(wù)。算法通過初始種群的優(yōu)化和局部最優(yōu)處理，引導(dǎo)種群向更好的方向發(fā)展。實(shí)驗(yàn)結(jié)果表明，本文的改進(jìn)遺傳算法相對(duì)于傳統(tǒng)的遺傳算法取得了更好的效果。