劉春燕，楊巍巍

(1.武漢理工大學華夏學院 信息工程系，湖北 武漢 430070; 2.中國五環(huán)工程有限公司 設備室，湖北 武漢 430070)

云計算基于遺傳粒子群算法的多目標任務調度

劉春燕1，楊巍巍2

(1.武漢理工大學華夏學院 信息工程系，湖北 武漢 430070; 2.中國五環(huán)工程有限公司 設備室，湖北 武漢 430070)

合理地進行任務調度是云計算長期以來存在的挑戰(zhàn)。云任務的調度過程具有動態(tài)性的特點，僅從單一方面來優(yōu)化調度策略已不能滿足用戶需求。針對上述問題，從任務完成時間、任務完成成本、資源利用率三個方面出發(fā)，提出一種基于遺傳與粒子群算法融合的多目標任務調度算法。在遺傳算法的變異操作中引入粒子群算法，既可以發(fā)揮遺傳算法全局搜索能力強的優(yōu)勢，又可以利用粒子群算法的反饋特性改善變異操作提高收斂速度。通過CloudSim平臺進行云環(huán)境仿真實驗，將此算法與遺傳算法(GA)和粒子群算法(PSO)進行比較。實驗結果表明，在相同的條件設置下，該算法在用戶滿意度和資源利用率方面都優(yōu)于遺傳算法和粒子群算法，是一種云計算環(huán)境下有效的任務調度算法。

云計算；任務調度；多目標；遺傳算法；粒子群算法

0 引 言

近年來，云計算以其獨特的方式成為互聯網發(fā)展的熱門話題。云計算主要是利用虛擬化技術，通過網絡將龐大的計算處理任務分拆成多個較小的子任務，再交由多部服務器所組成的龐大系統，經搜尋、計算之后將處理結果回傳給用戶[1-2]。

在云計算中，任務調度策略直接影響到用戶的任務執(zhí)行效率以及云環(huán)境下資源的使用效率。當前許多研究者提出將智能算法引入到云任務調度中，收到了一定的成效。其中,李建鋒等設計了一種基于雙適應度遺傳算法的任務調度算法，不但把總任務的完成時間作為調度策略的優(yōu)化目標，同時還兼顧了任務的平均完成時間，最大限度地提高了云計算的效率[3]；封良良等在綜合考慮了總任務完成時間和總任務完成成本兩個因素的前提下，提出了基于改進粒子群的任務調度算法[4]；樓濤等提出了基于混合蟻群遺傳算法的Hadoop集群作業(yè)調度，一定程度上解決了傳統遺傳算法的“早熟”問題，加快了收斂速度[5]；朱宗斌等提出了改進GA的云計算任務調度算法，綜合考慮了任務調用的時間和成本[6]。以上各種任務調度算法絕大多數都存在目標單一、收斂早熟等問題。

針對上述問題，文中設計了一種基于遺傳粒子群算法的多目標任務調度算法(GA-PSO)，從時間、成本、資源利用率三方面均衡考慮，以期達到最小的完成時間兼顧成本最少，同時最大限度保證云環(huán)境整體的資源使用效率的目的。該算法的關鍵是將粒子間信息傳遞的特性引入遺傳算法影響變異因子，避免變異的盲目性。在PSO粒子的作用下，有效解決了傳統GA的不足。

1 云計算的任務調度分析

云環(huán)境下物理資源的服務能力相差甚遠，隨著云計算的快速發(fā)展，云用戶對計算資源的需求逐日遞增，隨之增加的必然是虛擬機數量。當虛擬機數量遠大于云環(huán)境中的物理資源時，虛擬機需按照一定的調度順序逐個進行處理，怎樣合理分配云計算虛擬機任務，并且極大程度地滿足用戶需求是資源分配亟待解決的新問題。虛擬化技術將云環(huán)境下差異巨大的物理資源統一整合，在云用戶和云計算資源之間搭建共享虛擬資源池。首先將云用戶的任務拆分成若干子任務分配給合適的虛擬機，再由虛擬機匹配物理資源，完成虛擬機到云計算資源的映射，以此保證整個用戶需求的服務質量最優(yōu)。結合云計算的結構特點，虛擬機資源調度采用兩級模式，實現以用戶為中心的虛擬機任務調度策略。第一級調度是劃分用戶任務找到合適的虛擬資源，第二級調度是將虛擬資源池中的虛擬機匹配給物理資源。兩級調度是一個不可分割的整體，在資源分配策略的指導下，根據用戶對任務的需求，將任務合理地分配到合適的虛擬機上運行，并結合當前物理資源的負載狀況和計算能力，在物理資源中尋找合適的資源分配給虛擬機。通過兩級調度，用戶的需求得到了很好的滿足，而且對物理資源進行了整體統籌，不會造成資源浪費。

文中的研究重點為第二級調度，即通過調度算法將虛擬機上的任務分配到物理機上執(zhí)行，保證分配的最優(yōu)性。

2 基于遺傳粒子群算法的多目標調度

2.1 問題描述

云環(huán)境下任務調度問題實質是多目標組合優(yōu)化問題。目標是建設合理數量的虛擬機，將多個虛擬機分配到物理資源節(jié)點上，使得云用戶任務的完成時間和成本耗費最低，并兼顧被分配物理資源的服務能力，達到最大的資源利用率。例如，云用戶提交任務的預期完成時間為p(i)，預期完成成本為w(i)，云環(huán)境下的物理資源A,B,C，它們的服務能力等級分別為高，中，低。當云用戶任務被拆分成子任務分配到5個虛擬機上執(zhí)行時，虛擬機與物理機的配置會存在多種不同的情況，第一種映射：A{1，2，3，4，5}，第二種映射：B{1,5}，C{2,3,4}。第一種映射任務執(zhí)行時間time

2.2 設計思想

針對云計算環(huán)境下的任務調度問題，參照Map/Reduce模型[7-9]。為了能得到總任務完成效率最優(yōu)的任務調度結果，充分發(fā)揮遺傳算法和粒子群算法的優(yōu)點，將遺傳算法與粒子群算法進行有效融合，構造一種遺傳粒子群算法。

遺傳粒子群算法(GA-PSO)的主要思想是在任務調度的前期階段，利用遺傳算法群體性全局搜索能力強的優(yōu)勢，通過選擇、交叉、變異等遺傳操作找到任務分配的較優(yōu)解，在變異操作中引入粒子群算法，更有效地產生接近目標的新個體。

2.3 遺傳編碼

遺傳算法是由John Holland教授于1975年首先提出的一類仿生型優(yōu)化算法，具有并行搜索、群體尋優(yōu)的特點,但對系統中的反饋信息利用不夠，當求解到一定范圍時出現大量的冗余迭代，求精確解的效率低下，容易出現局部最優(yōu)解[10-14]。

為解決云環(huán)境下的任務調度問題，首先需要將調度方案編碼成染色體。文中采用間接編碼方式。即對每個任務占用的資源進行編碼，染色體的長度等于總的子任務數，每個基因位的位置編號代表子任務的編號，基因位的數值表示所占用的資源編號。

2.4 目標函數與適應值函數

目標函數定義為：

(1)

(2)

(3)

(4)

其中，m表示物理資源數量；n表示總的任務數；Timei表示第i個任務通過虛擬機調度在第m個物理資源上執(zhí)行的時間；Costi表示第i個任務所使用物理資源上的成本費用；s(i)表示物理機ri的服務能力；rtime表示物理機ri的計算能力；rcost表示物理機ri的耗能。

2.5 遺傳操作

遺傳算法的遺傳操作主要包括選擇、交叉和變異，通過這些操作不斷產生新個體，從而搜索出最優(yōu)解。

(1)選擇操作。

根據適應度函數值在種群中按照式(5)計算出每個個體的選擇概率。

(5)

(2)交叉操作。

文中采用自適應交叉方法。首先在個體間按較大交叉概率交換個體間的某些位，為了避免早熟現象的發(fā)生，在算法后期，交叉概率相應減小，這樣有利于優(yōu)良新個體的產生，加快了算法的收斂速度。

(3)變異操作。

(6)

(7)

這樣的變異操作具備了感應信息的能力，能夠根據歷史最佳值和個體最佳值影響變異的方向和幅度，提高個體對進化環(huán)境的適應能力。

3 實驗結果及分析

3.1 實驗仿真環(huán)境及參數設置

為了驗證GA-PSO算法的可行性和有效性，主要從任務調度性能和資源利用率對其進行仿真。實驗利用CloudSim模擬器構建了云環(huán)境任務調度模擬平臺，并在相同仿真平臺下對文中提出的GA-PSO算法、雙適應度GA算法[3]和改進PSO算法[4]進行任務調度對比分析測試。編寫繼承CloudSim基類的方法。具體實現如下：Host類可以獲取各物理資源的重要信息，VmAllocationPolicy抽象類用于實現虛擬機的分配，CloudSim只實現了簡單的虛擬機分配策略，通過自定義VmAllocationPolicyADpso類實現多目標虛擬機分配，方法adpdoallocate(p,v)是該類的核心，重寫該方法實現云計算虛擬機分配算法。

CloudSim仿真程序模擬出30臺物理機，分別部署30,50，100個虛擬機,任務數分別設置為100，200，300，400，500時進行測試?；谶z傳算法與粒子群算法各自的搜索和求解優(yōu)勢，結合反復的實驗測試，文中為遺傳粒子群算法設置的參數見表1。

表1 參數設置

3．2 性能分析

根據以上參數進行仿真實驗，每組實驗仿真10次求平均值，得到三種算法資源利用率對比圖，如圖1所示。

圖1 三種算法資源利用率對比

從圖1可以看出，當任務數量小于200時，云環(huán)境中的網絡資源充裕，三種算法的資源利用率均達到90%以上，GA-PSO略優(yōu)于PSO和GA,但差距不明顯。隨著任務數量的不斷增加，基于云資源處理能力的差異，三種算法的資源利用率均有所下降，但GA-PSO在任務分配時考慮了云資源的差異性，資源利用率明顯優(yōu)于GA和PSO，性能改進的效果明顯。

圖2和圖3分別比較了三種算法的任務完成時間和任務耗費成本。

圖2 三種算法任務調度總時間對比

從圖2可以看出，GA-PSO算法的任務調度總時間最少，且收斂最快。但在搜索前期優(yōu)勢并不明顯，隨著迭代次數的增加，在遺傳算法中加入PSO的信息素影響變異操作，隨著信息素的積累，搜索最優(yōu)解的速度迅速得到提升。

圖3 三種算法任務調度時間總費用對比

從圖3可以看出，GA-PSO的總費用最少，其次是GA，最高的是PSO。因為雙適應度GA以任務完成時間和任務使用費用為雙目標；而GA-PSO也同時考慮了時間和費用兩方面，并且注重了資源利用率，使得虛擬機在分配任務時會優(yōu)先選擇成本和處理能力較均衡的物理機執(zhí)行。

4 結束語

文中對云環(huán)境下的任務調度問題進行了研究。針對云任務調度中普遍存在的目標單一問題，提出多目標云任務調度，綜合考慮任務完成時間、任務完成費用和云資源利用率三個因素，針對遺傳算法前期搜索能力強，但迭代過程反饋信息利用不夠引起的最優(yōu)解質量不高的問題，提出了改進方法。在遺傳算法的變異操作中引入粒子群算法，利用粒子群體間的反饋信息影響變異因子，避免盲目變異產生新個體，從而加快了算法的收斂速度。CloudSim模擬仿真實驗證明，GA-PSO在云任務調度的總體性能上優(yōu)于GA和PSO。

[1] Abadi D J.Data management in the cloud:limitations and op-

portunities[J]. IEEE Data Engineering Bulletin,2010,32(1):3-12.

[2] Lee Y C,Zomaya A Y.Energy efficient utilization of resources in cloud computing systems[J].Journal of Supercomputing,2012,60(2):268-280.

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

[4] 封良良,張 陶,賈振紅,等.云計算環(huán)境下基于改進粒子群的任務調度算法[J].計算機工程,2013,39(5):183-186.

[5] 樓 濤,杜文才,鐘杰卓.基于混合蟻群算法的Hadoop集群作業(yè)調度[J].海南大學學報:自然科學版,2015,33(4):340-346.

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

[7] Bhandarkar M. MapReduce programming with apache Ha-doop,parallel & distributed processing[C]//Proceedings of IEEE international symposium on digital object identifier.[s.l.]:IEEE,2010.

[8] 尚宏佳,周 萍,楊 青,等.融合多核和MapReduce的連接聚集查詢優(yōu)化[J].計算機研究與發(fā)展,2015,52(S):9-18.

[9] Prabhavathi P,Nithyanandan L.Network selection in wireless heterogeneous networks[C]//Proceedings of 2013 international conference on communications and signal processing.Melmarunathur:[s.n.],2013:357-361.

[10] 劉衛(wèi)寧，靳洪兵，劉 波.基于改進量子遺傳算法的云計算資源調度[J].計算機應用,2013,33(8):2151-2153.

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

[12] 倪 霖,段 超,賈春蘭.差分進化混合粒子群算法求解項目調度問題[J].計算機應用研究,2011,28(4):1286-1289.

[13] 賈建芳,楊瑞峰,王 莉.混合遺傳粒子群優(yōu)化算法的研究[J].自動化儀表,2013,34(9):1-3.

[14] 靳其兵,張 建,權 玲,等.基于混合PSO-SQP算法同時實現多變量的結構和參數辨識[J].控制與決策,2011,26(9):1373-1376.

A Multi-objective Task Scheduling Based on Genetic and Particle Swarm Optimization Algorithm for Cloud Computing

LIU Chun-yan1,YANG Wei-wei2

(1.Department of Information Engineering,Huaxia College of Wuhan University of Technology, Wuhan 430070,China; 2.Department of Equipment,Wuhuan Engineering Co.,Ltd.,Wuhan 430070,China)

How to schedule tasks reasonably remains a long-standing challenge in cloud computing.The process of the cloud task scheduling has the characteristics of dynamic,so to optimize the scheduling strategy only from a single aspect cannot meet the needs of users.To solve the above problem,from three aspects of task completion time,task completion cost and resource utilization,a multi-objective task scheduling algorithm based on genetic algorithm and particle swarm optimization algorithm is proposed.Particle swarm optimization algorithm is introduced into mutation operation of genetic algorithm which can not only give play to advantage of quick global searching speed for genetic algorithm,but also apply particle swarm optimization algorithm’s feedback characteristic to improve mutation operation and convergence rate.CloudSim is adopted to simulate the cloud environment,and the GA and PSO is compared.The simulation results show that under the same conditions,the combined algorithm outperforms other two algorithms on task completion time,task completion cost and resource utilization.It is an efficient task scheduling algorithm in the cloud computing environment.

cloud computing;task scheduling;multi-objective;genetic algorithm;particle swarm optimization algorithm

2016-04-13

2016-08-10

時間：2017-01-10

湖北省教育科研計劃指導性項目(B2015373)

劉春燕(1983-)，女，碩士，講師，研究方向為云計算、智能優(yōu)化算法。

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

TP391

A

1673-629X(2017)02-0056-04

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