基于變異算子的云計算任務調度算法

陳超，蔡樂才，高祥

（四川理工學院a.自動化與電子信息學院；b.計算機學院；c.機械工程學院，四川自貢643000）

基于變異算子的云計算任務調度算法

陳超a，蔡樂才b，高祥c

（四川理工學院a.自動化與電子信息學院；b.計算機學院；c.機械工程學院，四川自貢643000）

為了高效調度云計算中海量的任務，提出一種改進遺傳算法（IGA），將變異操作分為兩種:變異操作a和變異操作b。變異操作a為隨機位置的基因值變異，而變異操作b則是先找出滿足一定條件的基因位置，再將該位置的基因值變異成目標基因值，使得每次變異后的染色體都優于變異前的染色體。在算法的前期使用變異操作a，在算法后期即將收斂于最優解時，采用變異操作b以加快收斂的速度。為了避免改進變異操作使算法陷入局部解，在種群初始化時，采用染色體匹配率的方式選擇初始化種群，使其均勻的分布在整個解空間上。實驗仿真結果表明，改進算法不但使最終完成時間更短，收斂效率更高，而且可以在一定程度上均衡負載，能更有效地實現任務調度。

云計算；任務調度；遺傳算法；匹配率；變異

引言

云計算作為一種全新的超級計算模式，其目的是通過網絡將大量分散的資源集中于互聯網的數據中心，并由數據中心提供計算、軟件、數據訪問及存儲服務等。在云計算中，計算能力作為一種資源，通過互聯網按需分配給用戶［1］。其中，用什么樣的方法去分配計算資源就變得非常重要了，它決定著計算能力的好與壞。對于云計算服務提供商來說，其關鍵技術就是如何有效利用“云”中的資源，使大量任務進行合理高效的調度和分配，其分配效率直接影響到整個云計算環境的性能以及企業經濟效益，因此找出更好的分配方法是非常有應用價值的。

目前，國內外涌現出了大量的云計算資源分配算法，但方法理論還不是十分成熟完善，缺乏一個統一的科學方法。一些簡單的資源分配方法，如輪轉法、哈希法、最小負載優先法等，其結果往往不夠理想，并且很容易造成物理服務器的服務性能不均衡等問題。這就使得越來越多的學者開始關注神經網絡、禁忌搜索、蟻群算法［2-4］、遺傳算法等現代優化算法。而其中，將遺傳算法作為云計算環境下的任務調度算法已漸漸成為研究的熱點。一些改進的遺傳算法被提出，如以任務總完成時間和平均時間為適應度的雙適應度遺傳算法（DFGA）［5］、動態調整任務分配的遺傳算法［6］、基于染色體編碼方式和適應度函數的改進遺傳算法［7］、時間—成本約束的遺傳算法（TCGA）［8］等。現已提出的改進遺傳算法中，收斂速度都還有待提高，同時，負載均衡也應該是考慮的重要因素。本文基于遺傳變異算子思想，提出一種改進遺傳算法（IGA），以能更好適應具有海量任務的云環境的任務調度。

1 遺傳算法與任務調度

1.1 任務調度描述

根據調度層面的不同，云計算中的任務調度方法可以分為兩大類∶資源層面的調度和應用層面的調度。資源層面的調度問題實際上是云計算環境中應用的需求怎樣得到滿足的問題；應用層面的調度方法把底層看成許多計算節點，在應用層面對用戶提交的作業進行分解，把分解后的子任務合理分配給不同的節點來實現。

本文中采用的遺傳算法則是屬于應用層面的調度方法。在Map/Reduce模型下，把任務分割成多個較小的子任務，然后分配給多個計算節點并行執行，如何給眾多子任務合理分配資源是個復雜的問題。在云環境中，假設有R個資源∶｛VM1，VM2，...，VMR｝；用戶提交的任務為M個，表示為｛J1，J2，...，JM｝，MapReduce模型［9］將M個任務分割成N個子任務，表示為｛T1，T2，...，TN｝。則云計算環境下應用層面的調度問題［10］即可描述為∶在有限的R個資源情況下，高效合理的調度N個子任務，使任務總完成時間最小，并且在占用帶寬、費用、可靠性等方面都能達到滿意的效果。

1.2 遺傳算法

遺傳算法（Genetic Algorithm）是一種模擬生物進化論中自然選擇過程的計算模型，是較經典的搜索最優解的方法。遺傳算法中，首先會生成一組候選解，然后根據適應度函數計算每個候選解的適應度，并依據適應度的大小對群體進行選擇操作，適應度大者生存，適應度小者淘汰。最后，對保留的個體進行交叉、變異操作，以產生出更優的個體。傳統遺傳算法具有全局解空間搜索和并行性兩個顯著優點，同時也存在早熟等現象。本文將結合云環境下任務調度的特點以及遺傳算法自身的特點，提出一種改進遺傳算法，作為云計算環境下的任務調度算法。改進的遺傳算法在算法的前期與后期采用不同的變異操作，促進算法加速收斂。為了避免算法陷入局部解，在初始化階段采用染色體匹配率［8］來選擇初始種群，使初始群體均勻遍布于整個解空間上。

2 采用改進遺傳算法進行云任務調度

2.1 染色體編碼與解碼

遺傳算法中常用的編碼的方式有兩種∶實數制編碼與二進制編碼。為使算法在遺傳操作中的計算更簡單方便，本文中采用資源—任務直接編碼方式，即染色體長度為任務總數，而其中每個基因的取值為該位置對應的任務分配到資源的資源編號。

2.2 產生初始群體

實際云計算中的任務數非常龐大，因此會存在許多不同的解。當遺傳算法中初始種群個體數遠遠小于解空間中解的數量時，即初始解不能均勻分布于解空間，算法很容易陷入局部解。因此本文在產生初始群體時將采用文獻［8］提出的方法∶計算染色體的匹配率，通過調節匹配率的大小來選擇初始染色體，使得初始種群個體均勻地分布在解空間上。

若種群規模為S，子任務總數（染色體長度）為L，資源數為W。染色體yi和染色體yj的匹配率為

其中，i∈（1，2，...，S），j∈（1，2，...，S），且i≠j；Sumgene（yi，yj）為yi與yj中相同等位基因的個數。

在選擇初始化種群個體時，通過調節匹配率的大小選擇，能夠保證初始種群個體的多樣性，使其均勻遍布在整個解空間上，促使算法收斂于全局解。該方法不僅克服了標準遺傳算法易陷入局部解的缺點，并且可以避免本文中改進變異操作使算法陷入局部解，保證了改進變異操作的效率的和正確性。

2.3 構造適應度函數

遺傳算法遵循生物進化中優勝劣汰的原則，適應度大的個體最終被保留下來，適應度小的個體會因無法適應環境而被淘汰掉。遺傳算法就是通過多次的優勝劣汰，最終找到最優解。因此適應度函數的選取非常重要，決定了算法的性能。

云計算環境下任務調度的最重要的目標是任務總完成時間。本文中任務總完成時間不僅是任務在計算資源上的執行時間，還包括了任務傳輸時間。任務執行時間主要取決于計算資源的計算能力，而傳輸時間主要取決于計算資源的帶寬。因此，第i個任務被分配到第j個資源上的總完成時間可以用公式（2）來衡量∶

其中，Inputfilesizei表示第任務i輸入文件的大小，Outputsizei表示任務i輸出文件的大小。Lengthi表示任務i的長度。表示資源j的通訊帶寬。表示資源j的計算能力，其計算公式為∶

其中，Numj（Pe）表示資源j處理器的數目，Mipsj（Pe）表示資源j處理器的平均速度。

假設分配到資源j上的任務數為n，則資源節點j完成所分配任務的時間為∶

其中，表示第k個染色體，k∈（1，2，...，S）。

2.4 選擇操作

選擇的目的是為了保存優良基因，淘汰掉適應度低的個體。本文中通過計算適應度值比例來作為選擇標準。對于給定規模為S的種群（x1，x2，...，xS），染色體xi的適應度值為f（xi），則其入選概率為∶

由于各個計算資源是并行處理任務序列的，所以任務的總完成時間為最后完成任務的資源節點所用的時間，即求的最大值。因此，基于任務總完成時間的適應度函數定義為∶

2.5 交叉操作

交叉操作是遺傳算法中起核心作用的遺傳算子，所謂交叉就是替換重組兩個父代個體的部分結構，從而生成新個體的操作，即基因重組的過程。交叉操作是產生新個體最主要的方法，通過交叉可以將父代群體的優良基因遺傳給下一代，并使新一代個體擁有更好的基因。交叉算子是決定遺傳算法全局搜索能力的關鍵，通過交叉，遺傳算法的搜索能力可以得到飛躍式的提高。交叉概率一般在0.3～0.9之間，本文將以一定概率Pn（0.3＜Pn＜0.9）進行交叉操作，從種群中選擇兩個個體，然后隨機選擇交叉點，交換交叉點后的基因。

2.6 變異操作

遺傳算法中，變異算子的作用有兩個。一是維持種群的多樣性。交叉算子用以產生新個體，而變異算子則是產生新個體的輔助方法。通過變異可以拓寬解的搜索空間，促進算法在全局上搜索最優解，防止出現早熟現象或陷入局部解，這種情況下變異概率應該取較大值。二是增加算法的局部搜索能力。在算法后期，算法已接近最優解領域，此時通過交叉操作很難完成局部的細節搜索，而利用變異操作就可以從局部加速收斂于最優解。此時變異概率應取較小值，以防止最優解領域因變異而遭到破壞。

基于上述變異算子的特點，本文將變異操作歸結為變異操作a和變異操作b。

變異操作a∶對要變異的個體隨機選擇一個變異點，隨機選取一個值替代該位置上的基因值。

變異操作b∶云計算環境下有著海量的數據，任務數非常巨大，遠遠大于資源數，因此，資源上的任務分部不均。此變異操作就是在滿足條件（7）下，將有最多任務的資源上的其中一個任務放到任務數最少的資源上去。

基于此，變異操作過程為∶在算法的前期，以較大概率Pm1對群體執行變異操作a，增加群體的多樣性，使搜索遍布于整個解空間上。在算法的后期，以較小概率Pm2對群體執行變異操作b。此時算法已接近最優解，但是由于個體的適應度值較為接近，以至于進化困難，收斂速度變慢，因此本文通過變異操作b來促進算法加速收斂于最優解。

例如染色體｛3，1，2，3，2，4，3，1，2，2，4，2，1，3，2｝，解碼后如圖1所示。

由圖1可看出，任務數最多的是Vm2，任務數最少是Vm4。Vm2完成它所有任務的時間為T（Vm2），Vm4完成它所有任務的時間為T（Vm4），對于Vm2上的任務，如任務3，若滿足

T（Vm2）＞T（Vm4）+T（3，4）（7）其中T（3，4）是任務3在Vm4上的完成時間，則將任務3移到Vm4上，即染色體變異成｛3，1，4，3，2，4，3，1，2，2，4，2，1，3，2｝。若Vm2上的任務沒有滿足此條件的，就隨機在Vm2上選取一個任務移到Vm4上。通過此變異操作可以使每次變異后的染色體比變異前的染色體更優，同時，還可以在一定程度上均衡負載。

3 實驗仿真分析

采用云計算仿真平臺CloudSim［11-12］對算法進行仿真分析。CloudSim是澳大利亞墨爾本大學網格實驗室和Gridbus項目共同提出的一種云仿真軟件，它是在離散事件模擬包SimJava上開發出來的函數庫，其體系結構組件包括四個層次∶Sim Java、GridSim、CloudSim、User-Code。通過CloudSim仿真平臺，在相同的環境條件下，對改進的遺傳算法（IGA）與傳統遺傳算法（GA）進行對比實驗。種群規模為200，交叉概率為0.25，變異操作a的變異概率取0.1，變異操作b的變異概率取0.05，染色體匹配率取0.05。算法終止條件為∶（1）如果連續50代適應度值不再變化；（2）達到最大迭代次數gnMax（這里取gnMax=200）。

（1）當資源數為10時，任務數分別取20、40、80、150、300、600，對改進遺傳算法和傳統遺傳算法進行對比仿真。記錄每次任務總完成時間，統計結果見表1。

從表1可以看出，采用改進遺傳算法作為任務調度算法時，任務的完成時間要短很多，優勢較明顯。

（2）任務數為2000，資源數為20時，改進遺傳算法與傳統算法的收斂情況如圖2所示。

從圖2可看出，在同樣的條件下，改進遺傳算法在迭代120次就已基本收斂，而標準遺傳算法要迭代到180次左右才開始呈收斂趨勢。這是因為改進遺傳算法在迭代的后期采用了變異操作b，加快了收斂速度，而標準遺傳算法由于在迭代后期染色體適應度值較為接近，進化困難，導致收斂速度非常慢。同時還可以看出，改進遺傳算法的最后任務完成時間比標準遺傳算法更短，結果更為理想。

（3）任務數為2000，資源數為3時，并且調整資源的性能參數，使資源節點的處理能力有較大差異，這時資源節點Vm1、Vm2、Vm3上的負載情況如圖3所示。

從圖3可以看到，當有大量任務而資源節點數有限并且資源節點運算能力差異較大時，改進遺傳算法的負載較均衡，而原算法中資源節點分配到的任務數有較大差異，負載情況表現的不太理想。由此可看出，改進遺傳算法的負載情況在一定程度上要優于標準遺傳算法。

4 結束語

提出了一種改進遺傳算法作為云計算環境下的任務調度算法，通過兩種變異操作促使算法加速收斂，同時，采用染色體匹配率來初始化種群，通過調節匹配率使初始群體均勻的分布在整個解空間上。最后，通過Cloudsim仿真分析表明，該改進算法不僅使得任務完成時間更短、收斂速度更快，而且在一定程度上改善了資源節點的負載情況，是一種云計算環境下有效的任務調度算法。

［1］Foster I'Zhao Y'Raicu I'et al.Cloud computing and grid computing 360-degree compared［C］//Proceedings of the 2008 Grid Computing Environments Workshop.Washington'DC:IEEE Computer Society'2008:1-10.

［2］張春燕'劉清林'孟珂.基于蟻群優化算法的云計算任務分配［J］.計算機應用'2012'32(5）:1418-1420.

［3］劉永'王新華'邢長明'等.云環境下基于蟻群優化算法的資源調度策略［J］.計算機技術與發展'2011'21 (9）:19-27.

［4］范杰'彭艦'黎紅友.基于蟻群算法的云計算需求彈性算法［J］.計算機應用'2011'31(增刊1）:1-3.

［5］李劍鋒'彭艦.云計算環境下基于改進遺傳算法的任務調度算法［J］.計算機應用'2011'31(1）:184-186.

［6］王文楓'帥建梅.一種云計算環境下任務調度策略［J］.電子技術'2012(7）'35-38.

［7］劉愉'趙志文'李小蘭'等.云計算環境中優化遺傳算法的資源調度策略［J］.北京師范大學學報:自然科學版'2012'48(4）:378-384.

［8］熊聰聰'馮龍'陳麗仙'等.云計算中基于遺傳算法的任務調度算法研究［J］.華中科技大學學報:自然科學版'2012'40(增刊1）:1-4.

［9］Dean J'Ghemawat S.MapReduce:simplified data processing on large clusters［C］//Proceedings of the 6th Symposium on Operating System Design and Implementation.New York:ACM'2004:137-150.

［10］Pham H.Springer Handbook of Engineering Statistics［M］.New York:Springer'2006:229-247.

［11］Callheiro R N'Ranjan R'Rose C A FD'etal.Cloudsim: a novel framework for modeling and simulation of cloud computing infrastructures and services［J］.Computing Research Repository'2009(1）:1-9.

［12］Calheiros N'Rajiv R'Belogazov A'et al.CloudSim:a toolkit formodeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］.Journal of Software:Practice and Experience'2011'41:23-50.

Task Scheduling Algorithm Based on Mutation Operator in Cloud Computing

CHEN Chaoa，CAILecaib，GAO Xiangc
（a.Department of Automation&Electronic Information；b.Department of Computer；c.College ofmechanical engineering，Sichuan University of Science&Engineering，Zigong 643000，China）

In order to dispatch a huge number of tasks efficiently，an improved genetic algorithm which includes two types ofmutation operations:mutation operation a and mutation operation b，is put forward.Mutation operation a is the genovariation on random position.And in mutation operation b，a gene position thatmeets certain conditions is found out first，then the value of this position is replaced by the target gene value.The chromosome aftermutation operation b is always superior to that beforemutation.Mutation operation a is used in earlier time of the algorithm.In later period，algorithm tends to converge to the optimal solution，somutation operation b is used to improve the convergence speed.To avoid algorithm falling into local solution due to the improved mutation operations，themethod that use thematching ratio of chromosomes to select initial population is adopted in the process of population initialization，for which the population can distribute in the whole solution space uniformly.The simulation results show that，the improved algorithm not only makes the final completion time shorter and convergence efficiency higher，but also balances the load to some extent.It can realize task schedulingmore effectively.

cloud computing；task scheduling；genetic algorithm；matching ratio；mutation

TP393

A

1673-1549（2014）01-0032-05

10.11863/j.suse.2014.01.09

2013-12-06

物聯網技術與應用四川省青年科技創新團隊項目（2011JTD0031）；四川省教育廳重點科研項目（09Z087）；四川理工學院研究生創新基金項目（B20306）

陳超（1988-），女，四川什邡人，碩士生，主要從事物聯網與云計算方面的研究，（E-mail）236537194@qq.com