基于改進遺傳算法的云計算任務調度算法

胡艷華,唐新來,2

(1.廣西科技大學鹿山學院 電氣與計算機工程系，廣西 柳州 545616；2.廣西科技大學 教務處，廣西 柳州 545616)

基于改進遺傳算法的云計算任務調度算法

胡艷華1,唐新來1,2

(1.廣西科技大學鹿山學院 電氣與計算機工程系，廣西 柳州 545616；2.廣西科技大學 教務處，廣西 柳州 545616)

任務調度是云計算的核心問題。云計算中的任務調度算法要求在提高系統吞吐量和最大跨度的同時又要兼顧資源的安全與負載均衡問題。傳統遺傳算法因具有強大的并行空間搜索能力而在云計算中得到廣泛應用，但其亦存在明顯不足，即隨著計算機規模的不斷擴大，收斂性逐漸降低，存在易早熟等不足，限制了其調度性能。而Min-Min和Max-Min算法簡單易行，且具有較好的時間跨度，可以較好地彌補傳統算法的不足。在傳統遺傳算法的基礎上，結合Min-Min和Max-Min算法，提出了一種新的云計算任務調度算法，在產生初始化種群時引入Min-Min和Max-Min算法，并選取任務完成時間和負載均衡作為雙適應度函數，提高了初始化種群的質量、算法搜索能力以及收斂速度。仿真結果表明，該算法優于傳統遺傳算法，是一種有效的云計算任務調度算法。

云計算;遺傳算法;任務調度;Min-Min算法;Max-Min算法

0 引 言

作為一種新興技術,云計算已成為當今計算機領域的一個研究熱點。云計算是在分布式處理、并行處理和網格計算等技術的基礎上[1-2]，整合了虛擬化、效用計算、IaaS、PaaS及SaaS等諸多概念發展而來[3]。所謂的“云”實際上是一個龐大的網絡，該網絡將用戶請求拆分成若干個子任務，交由至一個龐大服務器群構成的高效處理系統進行搜索并分析計算，然后再返回至用戶。它所面向的用戶群數量是巨大的，需要高效地處理海量的任務，故如何進行合理而高效的任務調度是云計算的重點與難點。

由于云計算環境中資源的動態異構性，大規模的任務調度要求在盡量提高系統的吞吐量和最優跨度的同時也要考慮資源的安全與負載均衡等問題。目前應用較多的云計算調度算法主要有經典的遺傳算法、Min-Min、Max-Min、Suffrage及蟻群算法等。異構環境下的資源調度是個NP問題，在求解NP問題時，遺傳算法能夠得到很好的解，其在異構環境下任務調度方面的研究較多，與模擬退火、蟻群等算法相比，遺傳算法能夠得到更優的解。但傳統的遺傳算法亦存在明顯的不足，即隨著計算規模的不斷擴大，其收斂性逐漸降低[4]。Min-Min和Max-Min這兩種算法的優點是比較簡單且容易實現，同時具有較好的時間跨度。因此，文中在傳統遺傳算法的基礎上，結合Min-Min和Max-Min兩種算法的優點，提出了將Min-Min算法與Max-Min算法和遺傳算法(Genetic Algorithm,GA)相結合的改進遺傳算法(MMGA算法)。該算法主要對初始種群的生成進行了改進，并設計出了與傳統自適應遺傳算法不同的選擇和交叉算子，從而提高了算法的搜索能力和收斂速度。在CloudSim平臺下[5]的仿真實驗證明此算法明顯優于傳統遺傳算法。

1 云環境中的任務調度問題描述

目前，云計算的編程模式大多采用Google提出的Map/Reduce模型[6]，其主要原理是將要執行的問題分解成Map和Reduce，通過Map程序將數據分割成若干獨立區域，再將其調度給大量的計算機處理，實現并行計算，然后通過Reduce程序匯整計算結果，最后輸出用戶需要的結果。顯然，在此模型中，合理的任務調度至關重要。盡量縮短用戶的響應時間，同時也要達到良好的資源動態負載均衡，這是文中要考慮的重點問題。傳統GA算法雖然在異構環境下有著較好的調度性能，但有其天生的缺點，即收斂速度緩慢、易早熟等；而Min-Min算法和Max-Min算法都較易實現，同時又具有較好的時間跨度、良好的調度性能。文中以經典的遺傳算法為基礎，引入Min-Min及Max-Min算法，提出了一種改進遺傳算法，并考慮了響應時間和負載均衡問題，旨在建立一個更優的分配調度策略。

文中將云計算中的資源(包括處理器、存儲器、網絡等)統一視為計算資源，同時假定任務的輸入是由若干較大任務分解成的一批子任務，子任務數量遠遠大于資源數量，各個子任務所需的計算時間已知，且各個子任務的運行時間差異不大。假如用T表示大型任務的數量，N表示子任務的總數量，M表示計算資源的數量，并用M*N的ETC(ExpectTimetoComplete)矩陣來計算各個計算資源上任務隊列完成所需時間，其中ETC(i,j)表示第j個子任務在第i個計算資源上運行完成所需的時間。至此，將云計算中的任務調度問題定義為如何合理地將子任務分配到各個計算資源，使得任務運行完成所需的時間最短、負載均衡最小。

2 云環境中遺傳調度算法的改進

GA是根據生物遺傳和進化規律提出的一種用于復雜系統的自適應概率優化技術。由于GA具有全局解空間搜索及并行性等優勢，該算法以及以該算法為基礎的諸多算法在云計算任務調度中得到了廣泛應用[7]。文獻[8]提出了一種雙適應度的遺傳算法(DFGA)，在考慮最小任務完成時間的同時，亦兼顧了子任務平均完成時間，然而該算法求解效率不高；另外，目前多數改進遺傳算法尚未考慮資源的負載均衡情況[9-11]。

文中參照Map/Reduce模型[6]，結合已有云計算環境下的改進遺傳算法[9,12]，同時考慮到任務完成時間和負載均衡，將Min-Min與Max-Min算法引入到傳統遺傳算法中，提出了一種改進遺傳算法，以提高云計算環境下的任務調度效率。

2.1 染色體編碼與染色體解碼

染色體的編碼方式包括直接與間接編碼。文中考慮到大規模任務處理的特性以及云計算環境的動態異構性等特點，采用間接編碼的染色體編碼方式，即任務-資源映射模式，對每個子任務所占資源進行編碼，每條染色體的總長等于子任務的總數量，染色體中的每一位基因都為正整數，代表子任務編號，此位置上的值代表該子任務所占資源編號，如圖1所示。

圖1 任務-資源編碼

圖中，Ti表示任務編號；Rj表示任務Ti執行時所占第j個資源編號。

若有10個子任務，3個可用資源，則染色體長度為10，每個基因取值為1～3之間的隨機數，例如隨機產生以下的染色體編碼：

則此染色體代表第2個資源運行第1個子任務，第3個資源運行第2個子任務，以此類推。得到染色體后，還須解碼，以得到各個資源上子任務分布的情況。上述染色體可解碼為：

R1:{T5,T6,T9}

R2:{T1,T3,T7,T10}

R3:{T2,T4,T8}

通過解碼，求得每個計算資源上的子任務序列，然后通過ETC矩陣，計算出每個子任務序列所需的完成時間，進而得到總任務完成時間函數為：

(1)

其中，time(i,j)為被分配到計算資源Ri上第j個子任務執行所用的時間；n為分配到該計算資源Ri上的子任務數量。

2.2 改進的初始種群生成

初始種群在遺傳算法中具有極為重要的作用，其生成方式是首要解決的問題。初始種群的平均適應度越高，較優個體就能越快地引導種群向理想的方向發展而得到最優解，從而使其迭代過程變短、收斂性提高。獲取一個具有高平均適應度值的初始種群，是文中的研究重點之一。

圖2 改進后的種群初始化

2.3 適應度函數

在進化搜索中，遺傳算法一般單純使用適應度函數為依據，使用個體的適應度值進行搜索。所以適應度函數的選擇至關重要，將直接影響到收斂速度以及最終能否找到最優解[13]。最優跨度，即使任務的總執行時間(makespan)最小，是文中調度算法涉及的一個重要內容。故文中選用任務的總執行時間函數作為遺傳算法的適應度函數之一：即

(2)

(3)

其中，uLB為文中定義的平衡任務負載因子，代表各個計算資源的利用率情況。uLB的值越大，表示計算資源的利用率越高，那么F1(x)的值就相對越小。

資源負載均衡問題是資源調度中要考慮的另外一個重要方面，它能大大提高資源的利用效率。在設計適應度函數時也應考慮到資源負載均衡問題。文中參考文獻[12]，采用染色體上資源節點任務分配數標準差來衡量資源負載均衡。種群初始化后，設種群大小為Scale，子任務總個數為N，計算資源數即worker的個數為M，則每個染色體的資源節點平均分配任務數AT=N/M。對于任一個染色體，基于資源節點任務分配數標準差的適應度函數為：

(4)

其中，AT'(j,i)為第j個染色體第i個資源節點所分配到的任務數。

由于在選擇復制階段必須選擇任務標準差較小的染色體，因此設定基于任務分配數標準差的適應度函數為：

設計咨詢企業在履行合同的過程中，相關輔助人員及部分管理人員的投入，應盡可能的增加當地用工比例。一方面，可滿足當地移民簽證管理部門要求。另一方面，可使得中方員工盡快融入當地文化環境，為設計咨詢服務的本土化帶來優勢。最重要的是，適用當地員工，可最大化的節約合同成本，雇傭當地員工節約工作簽證辦理費用的同時，增大了境外可列賬成本范圍，減少了當地社保與中國社保重復繳納的損失。

(5)

2.4 遺傳操作

2.4.1 選擇操作

選擇操作是指根據“優勝劣汰”的法則，在種群中不斷選取適應度較強的個體，逐漸用以產生新種群的過程。個體的適應度越高，被篩選到下一代的概率就越大；反之亦然。如此反復，得到種群中個體的適應度值的最優解。

假設文中算法的種群大小為Scale，首先選擇父代中的最優個體和Min-Min算法、Max-Min算法產生的個體，以保留較優個體，其他的Scale-3個體則采用輪盤賭方式作為選擇操作算子，通過式(2)、(5)得出個體選擇概率為：

(6)

(7)

選擇下一代個體時，先以c1和c2的概率分別選擇P1和P2(其中0

2.4.2 交叉與變異操作

普通自適應算法中，當個體適應度值趨向最大適應度值時，交叉概率與變異概率減小。這對于種群進化后期較為有利，但不利于初期進化，因其能增加進化走向局部最優的幾率。因此，需要做進一步修改，修改后的公式為：

(8)

(9)

當f'=fmax時,Pc=Pc2>0;當f=fmax時,Pm=Pm2>0。

這樣，種群中的較優個體之間擁有更高的交叉與變異概率。同時采用最優保存策略，將每一代的最優個體直接復制到下一代中而保證其不被破壞。上述公式中，一般取Pc1=0.9;Pc2=0.6;Pm1=0.1;Pm2=0.001。

3 算法仿真結果與分析

文中采用云仿真器CloudSim[5]對上述提出的MMGA進行驗證和分析。

同時，在相同的環境條件下，對GA和MMGA進行了比較實驗，主要參數如表1所示。

算法初始條件：Scale取值為100，M取值為5～50，N取值為1 000～5 000。

算法終止條件：文中設最大進化代數為200，當算法連續50代沒有找到更好的解，認定算法為基本收斂，將終止算法。

(1)若取M=20，N取1 000～5 000，實驗過程中多次跟蹤記錄任務的完成時間，結果如圖3所示。

表1 實驗參數設置

圖3 任務的完成時間曲線(時間單位：104 ms)

由圖3可以看出，與GA相比，MMGA的任務完成時間明顯較短。

(2)若N=4 000，M=20，考察算法的收斂迭代情況，如圖4所示。

圖4 算法的收斂結果比較(時間單位：104 ms)

由圖4可知，在算法進化初期，GA和MMGA得出的任務完成時間相差不大，但MMGA算法在初始化種群產生時引入Min-Min算法和Max-Min算法，較好地提高了初始化種群的質量，使收斂速度加快，縮短了尋找最優解時間，MMGA在140次就開始收斂；隨著進一步的進化，在GA初始階段出現的超常個體誤導了種群的進化方向，因而陷入了局部收斂，而MMGA隨著進一步進化，同任務完成時間明顯低于GA，得到的最優解更好。

(3)若N=5 000，將任務分配到M=5個資源節點(R1,R2,R3,R4,R5)上，若其處理能力為(120,200,150,340,500)MFLOPS，實驗過程中分別記錄5個資源節點上的資源負載情況，其結果如圖5所示。

圖5 多任務情況下節點的資源負載情況

由圖5可知，在任務量大、資源節點運算能力差異較大的情況下，MMGA的資源負載均衡程度明顯好于GA。

綜上所述，文中提出的MMGA比GA收斂速度更快，且可以使得任務執行時間較短，資源負載較均衡，能較好地應用在云計算資源環境中。

4 結束語

文中在充分考慮大規模任務處理特性和云計算環境動態異構性的基礎上，提出了一種基于傳統遺傳算法的改進任務調度算法-MMGA。該算法既可以保證種群具有較高的平均適應度，又可以維護種群個體的多樣性；同時，算法中采用任務執行時間和負載均衡作為雙適應度函數，使得在提高收斂速度的同時，兼顧資源均衡。仿真結果表明，該改進算法收斂性能較好、資源負載較均衡，具有良好的效率，能更有效地解決云計算環境下的任務調度問題。

[1]ChienA,CalderB,ElbertS,etal.Entropia:architectureandperformanceofanenterprisedesktopgridsystem[J].JournalofParallelandDistributedComputing, 2003, 63(5): 597-610.

[2]KimJS,NamB,MarshM,etal.Creatingarobustdesktopgridusingpeer-to-peerservices[EB/OL].[2009-10-16].ftp://ftp.cs.umd.edu/pub/hpsl/papers/papers-pdf/ngs07.pdf.

[3]ArmbrustM,FoxA,GriffithR,etal.Aviewofcloudcomputing[J].CommunicationsoftheACM,2009,53(4):50-58.

[4]CarreteroJ,XhafaF.Usegeneticalgorithmsforschedulingjobsinlargescalegridapplications[J].TechnologiesandEconomicDevelopmentofEconomy,2006,12(1):11-17.

[5]BuyyaR,RanjanR,CalheirosRN.ModelingandsimulationofscalablecloudcomputingenvironmentsandtheCloudSimToolkit:challengesandopportunities[C]//Proceedingsoftheseventhhighperformancecomputingandsimulationconference.NewYork,USA:IEEEPress,2009:21-24.

[6]DeanJ,GhemawatS.MapReduce:simplifieddataprocessingonlargeclusters[C]//Proceedingsofthe6thsymposiumonoperatingsystemdesignandimplementation.NewYork:ACM,2004:137-150.

[7] 王小平,曹立明.遺傳算法[M].西安:西安交通大學出版社,2002.

[8] 李建鋒,彭 艦.云計算環境下基于改進遺傳算法的任務調度算法[J].計算機應用,2011,31(1):184-186.

[9] 朱宗斌,杜中軍.基于改進GA的云計算任務調度算法[J].計算機工程與應用,2013,49(5):77-80.

[10] 葉春曉,陸 杰.基于改進遺傳算法的網格任務調度研究[J].計算機科學,2010,37(7):233-235.

[11] 王春蓮.基于改進遺傳算法的網格任務調度算法[D].濟南:山東大學,2009.

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

[13] 段衛軍,付學良,王 芳,等.云計算環境下融合遺傳算法和蟻群算法QoS約束任務調度[J].計算機應用,2014,34(S2):66-69.

[14] 鄒偉明,于 炯.云計算環境下基于用戶滿意度的遺傳算法[J].計算機應用研究,2014,31(1):85-88.

A Task Scheduling Algorithm Based on Improved Genetic Algorithm in Cloud Computing Environment

HU Yan-hua1，TANG Xin-lai1,2

(1.Department of Electrical and Computer Engineering,Lushan College of Guangxi University of Science and Technology,Liuzhou 545616,China; 2.Office of Academic Affairs,Guangxi University of Science and Technology,Liuzhou 545616,China)

Task scheduling mechanism is one of the core issues in cloud computing.The task scheduling algorithm in cloud computing requires improvement of the system throughput and the largest span while considering resources security and load balancing problems.As a classical task scheduling algorithm with powerful and implicit parallel space search capability,genetic algorithm is widely used in cloud computing.However,it has many deficiencies,such as slow convergence and premature with the increasing calculation scale.Min-Min algorithm and Max-Min algorithm are simple and practicable with better makespan,which can well make up the deficiencies of traditional genetic algorithm.On this basis,an improved algorithm is put forward,which introduces Min-Min algorithm and Max-Min algorithm in the process of population initialization,and uses the minimizing makespan and the load balancing of resource as double-fitness function meanwhile.The simulation shows that this algorithm can elevate the quality of initial population,the search capability and the convergence rate,which is more efficient.

cloud computing;genetic algorithm;task scheduling;Min-Min algorithm;Max-Min algorithm

2015-12-22

2016-04-12

時間：2016-09-19

廣西壯族自治區自然科學基金項目(2013GXNSFAA019347);廣西科技大學鹿山學院科學基金項目(2015LSKY05)

胡艷華(1980-)，女，碩士研究生，講師，研究方向為云計算和計算機網絡；唐新來，博士，教授，研究方向為云計算。

http://www.cnki.net/kcms/detail/61.1450.TP.20160919.0839.010.html

TP393

A

1673-629X(2016)10-0137-05

10.3969/j.issn.1673-629X.2016.10.030