優化粒子群的云計算任務調度算法

譚文安,查安民,陳森博

(1.南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016; 2.上海第二工業大學 計算機與信息學院，上海 201209)

優化粒子群的云計算任務調度算法

譚文安1,2,查安民1,陳森博1

(1.南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016; 2.上海第二工業大學 計算機與信息學院，上海 201209)

任務調度作為云計算的關鍵技術之一,卻一直沒有得到很好的解決。針對云任務調度的特點,基于基本粒子群優化(PSO)算法,文中提出了一種帶極值擾動的相關性粒子群優化(EDCPSO)算法。該算法采用Copula函數去刻畫隨機因子間的相關結構,支持粒子合理利用自身經驗信息和群體共享信息,解決了粒子群優化算法在尋優過程中沒有考慮隨機因子作用而造成全局優化能力不足的缺陷;采用添加極值擾動算子的策略,進一步改進粒子群優化算法,避免了粒子群優化算法在進化后期容易陷入局部尋優現象。仿真結果表明,在相同條件下,帶極值擾動的相關性粒子群優化算法優于基本粒子群優化算法和Cloudsim原有調度算法,任務總的完成時間明顯減少。

任務調度；云計算；粒子群優化；相關性；極值擾動

1 概 述

為了解決“大用戶”、“大數據”和“大系統”帶來的一系列挑戰,云計算技術應運而生。云計算作為當今信息領域的重大成果,發展迅速。任務調度是云計算的關鍵技術之一。一個好的任務調度算法,不僅有助于打造一個穩定、健壯、節能的云計算環境,還可以提高用戶使用云計算服務的滿意度。智能優化算法近年來受到廣泛關注,成為解決調度問題的新工具。

1995年,Kennedy等提出粒子群優化(PSO)算法[1]。其基本思想是粒子在尋優過程中,不但要考慮自身的局部認識,而且要考慮種群的全局認識,即每個粒子是在充分利用這兩個認知信息的基礎上決定下一次的進化方向。由于該算法具有簡單、高效、智能背景深刻等優點,被廣泛應用于任務調度、機器學習、數據聚類、流程規劃等方面。

PSO算法的數學描述如下:

設有一種群,其粒子的個數為m,粒子的維數為n,則有：

第i個粒子的速度表示為:vi={vi1,vi2,…,vid},

1≤i≤m,1≤d≤n；

第i個粒子的位置表示為:xi={xi1,xi2,…,xid},

1≤i≤m,1≤d≤n；

第i個粒子的個體最優解表示為:pi={pi1,pi2,…,pid},1≤i≤m,1≤d≤n；

整個種群的全局最優解表示為:pg={pg1,pg2,…,pgd},1≤i≤m,1≤d≤n。

粒子速度和位置的更新方程如下:

vid(t+1)=ωvid(t)+c1r1(t)(pid(t)-xid(t))+c2r2(t)(pgd(t)-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1)

(2)

其中,ω為慣性權重;c1和c2為加速系數;r1和r2為隨機因子。

但是,要將PSO算法運用于云計算任務的調度,需要對其進行改進。

PSO算法在搜索最優解過程中,需要利用個體最優解pi和全局最優解pg。由更新方程可知,二者的利用率依賴于加速系數和隨機因子兩大因素。為了提高PSO算法的全局尋優能力,文獻[2-5]分別針對加速系數進行了改進。但是,目前很少有人對隨機因子進行研究。在經典PSO算法中,r1和r2是兩個相互獨立的隨機數。為了深入研究粒子對pi和pg的利用,需要研究一下隨機因子。

PSO算法在迭代后期收斂速度變慢,這是PSO算法的一大缺點。文獻[6]通過動態修改ω值,兼顧了搜索速度和精度；但對復雜的云計算任務的調度,這種通過改進慣性權重所達到的優化力度和實際效果都有待進一步提高。文獻[7]在PSO算法中引入遺傳算法,雖然在一定程度上達到了優化目的，但也增加了自身的復雜度。

文中通過優化PSO算法,提出了相關性PSO(CPSO)算法。該算法運用Copular函數建立隨機因子之間的相關性,解決了粒子群算法在尋優過程中沒有考慮隨機因子作用而造成全局優化能力不足的缺陷。之后提出基于前者的帶極值擾動的相關性PSO(EDCPSO)算法,解決了PSO算法在迭代后期收斂速度變慢的問題。

2 云計算任務調度問題描述

用戶對調度結果的評價依據有很多,文中主要研究如何減少任務的完成時間。

2.1 粒子編碼

目前存在多種編碼方式,文中選擇直接法。

設有t個任務,r個資源,且t>r。當t=10,r=3時,編碼序列(3,2,2,1,3,2,3,1,1,2)即為一個粒子。其中,每個任務對應一個資源,例如,任務3對應資源1。

接著是對粒子進行解碼,目的在于獲取每個資源運行的所有任務。例如,資源1上運行的所有任務有{4,8,9}。

定義矩陣matrix[i,j],用于記錄任務i在資源j上的執行時間。則資源j上完成所有任務的總時間為：

(3)

其中,i表示資源j上執行的任務個數;n表示資源j上執行的任務總數。

系統完成所有任務的總時間為：

taskTime=max(resourceTime(j)) (1≤j≤r)

(4)

2.2 種群初始化

2.3 適應度函數

文中主要研究如何優化能夠減少任務的執行時間,因此將適應度函數定義為:

(5)

3 相關性PSO算法

3.1 隨機因子的認知分析

根據PSO算法的心理學假設,隨機因子體現了粒子在認知過程中的非理性行為,反映出粒子作為認知主體的情緒,而加速系數視為粒子對這種情緒的心理效應[8-9]。

由此可知:將隨機因子r1和r2設為兩個相互獨立的隨機數,沒有考慮粒子在尋優過程中對個體最優解pi和全局最優解pg認知的聯系。因此,需要建立認知信息彼此之間的內在關系,即r1和r2之間的相關性。

線性相關系數是一種常見的相關性分析[9]方法,計算公式為：

從上式可知,要求隨機變量x和y的相關系數，必須知道它們的期望與方差。然而,有些變量的期望和方差是不存在的。另外,相關系數不能用于描述非線性關系。Copula理論為分析變量之間的相關性開辟了一條新的思路。該理論雖然早在1959年就誕生了,但是一直沒有受到大家的關注。直到最近幾年才被廣泛應用于金融、保險、投資等領域的相關性分析。

3.2 基于Copula的相關性PSO算法

文中使用二元Copula函數可刻畫兩個變量r1和r2之間的相關性。當然,該函數可推廣到多元形式。

3.2.1 二元Copula的相關知識

定義1[10]：如果二元函數C:[0,1]2→[0,1],滿足下列兩個條件:

(1)對于?t∈[0,1]，C(t,0)=C(0,t)=0且C(t,1)=C(1,t)=t;

(2)對于u1,u2,v1,v2∈[0,1]且u1≤u2,v1≤v2，有C(u2,v2)-C(u1,v2)-C(u2,v1)-C(u1,v1)≥0,則稱函數C為一個Copula。

Sklar定理是一個非常重要的定理,下面給出它的數學描述。

定理1[10]：設隨機變量x,y的聯合分布函數為H:R2→[0,1],其邊緣分布函數分別為Fx,Fy,則存在一個CopulaC:[0,1]2→[0,1],對任意x=(x1,x2)∈R2,有：

H(x1,x2)=C(Fx(x1),Fy(x2))

(6)

由定理1可得下面推論。

推論1[10]：如果C:[0,1]2→[0,1]是一個Copula函數,Fx,Fy分別是隨機變量x,y的分布函數,那么存在一個以Fx,Fy為邊緣分布的聯合分布函數H,滿足對任意的(u1,u2)∈[0,1]2,有：

(7)

定理1和推論1的作用在于說明Copula函數的存在性以及它的生成方法。

Copula函數類型很多,使用較多且應用較廣的一個當屬GaussianCopula，定義如下:

定義2[10]：對任意(u,v)∈[0,1]2,二元GaussianCopula可定義為:

Cρ(u,v)=Φρ(Φ-1(u),Φ-1(v))

(8)

其中，Φ是標準正態分布函數;Φρ是二維正態變量的聯合分布函數;Φ-1是Φ的逆函數;ρ是隨機變量間的線性相關系數,且1≤ρ≤1。

3.2.2CPSO算法實現

假設隨機變量x和y滿足x,y～U(0,1),由推論1可知,它們的二元Copula函數實際上為x和y的聯合分布函數。因此,文中采用Copula函數研究隨機變量r1和r2之間的相關性是可行的,具體定義如下:

H(r1,r2)=C(r1,r2)

(9)

其中,H為隨機因子r1,r2的聯合分布函數;C為相應的Copula函數。

定義3：在PSO算法基礎上,且由式(1)、(2)和(9)共同描述粒子運動軌跡的算法稱為CPSO算法。

在CPSO算法中,兩大隨機因子是服從[0,1]均勻分布且相關的隨機變量。因此,CPSO算法實現的難點是如何生成滿足給定Copula函數的r1和r2。

CPSO算法實現如下所述：

輸入:隨機產生的初始種群；

輸出:全局最優解pg。

(1)給出算法中所有參數的值;

(2)按照2.1與2.2的要求對粒子進行編碼并初始化種群;

(3)根據已知的相關系數ρ,按照步驟(4)～(7)生成相互關聯且服從[0,1]均勻分布的隨機數;

(4)隨機生成相互獨立且服從[0,1]均勻分布的變量u1,u2;

(5)根據x=Φ-1(u1),y=Φ-1(u2)計算x,y，其中,Φ是標準正態分布函數;

(7)根據r1=Φ(x),r2=Φ(y)計算r1和r2,則二者即為滿足GaussianCopula定義的兩個相關隨機數;

(8)使用式(5)計算粒子的適應值;

(9)更新粒子的個體最優解pi;

(10)更新種群的全局最優解pg;

(11)按照式(1)、式(2)分別更新粒子的速度和位置;

(12)判斷算法是否停止;

(13)若否,則返回步驟(3);若是,取迭代停止時的pg作為最優解。

4 CPSO算法的多樣性分析

4.1 粒子認知策略分析

由定義2及正態分布的對稱性可以看出:

Cρ(r1,r2)=Φρ(Φ-1(r1),Φ-1(r2))=Cρ(r2,r1)

(10)

上式表明,對于?ρ,r1,r2具有對稱性,其對稱軸為直線r1=r2。當ρ在[-1,1]范圍內逐漸增大時,r1,r2的取值逐漸向對稱軸靠攏。當ρ=1時,r1,r2的取值將會分布在對稱軸之上。

CPSO算法中,r1,r2取值的對稱性,反映出粒子在迭代過程中對pi和pg的利用率是相同的。隨著ρ的增大,r1,r2取值的集中分布性,反映出粒子在迭代過程中對pi和pg的利用率隨ρ的增大而增大。

4.2 群體多樣性分析

群體多樣性反映了種群中每個粒子的差異性,是描述種群進化過程中粒子多樣性的一個關鍵指標。

定理2[11]：CPSO算法中,種群多樣性的期望與相關系數ρ(0≤ρ≤1)具有正比例關系。

由定理2可知,為了在尋優過程中始終保持種群較好的多樣性,CPSO算法應該給定較大的相關系數ρ。

由定理2可得下面的推論：

推論2：CPSO算法中,種群多樣性的期望正相關于粒子對個體最優解和全局最優解的利用率。

5 帶極值擾動的CPSO算法

在CPSO算法中,個體最優解pi和全局最優解pg決定了粒子位置的收斂極值。如果每個粒子在逼近收斂極值的過程中不能發現比pg更優的位置,則之后的所有迭代都將無效,因為進化過程已經結束。

5.1 極值擾動

對式(1)和(2)添加擾動算子后變為:

vid(t+1)=ωvid(t)+c1r1(t)(αti>Tipid(t)-xid(t)) +c2r2(t)(βtg>Tgpgd(t)- xid(t))

(11)

xid(t+1)=xid(t)+vid(t+1)

(12)

5.2 EDCPSO算法實現

定義4：在CPSO算法基礎上,由式(11)、(12)和式(9)共同描述粒子運動軌跡的算法稱為帶極值擾動的CPSO(EDCPSO)算法。

修改CPSO算法的第11步:按照式(12)、(13)對粒子的速度和位置進行更新,其他步驟不變,則可得到EDCPSO算法。

6 仿真實驗與分析

6.1 仿真實驗環境與算法參數

利用Cloudsim構建云計算環境,Eclipse作為開發平臺,將文中提出的EDCPSO算法與Cloudsim原有調度算法FIFO、基本PSO算法進行對比分析。其中,算法參數見表1。

表1 EDCPSO算法參數

6.2 實驗結果和性能分析

每個實驗分別設置5組不同的用戶任務、50個資源節點,實驗過程中需要記錄每次實驗結束后任務的總完成時間。所有實驗各運行20次,取20次的平均結果作為最終結果。最后得出各個算法的任務完成時間，如圖1～3所示。由圖可見,EDCPSO算法相比其他兩種調度算法更加高效。

7 結束語

文中在分析云計算環境及其PSO算法的基礎上,提出了帶極值擾動的相關性PSO(EDCPSO)算法。仿真結果表明:該算法相比于Cloudsim原有調度算法和基本PSO調度算法,具有更高的效率,能夠減少任務總的完成時間。

文中工作處于理論分析與仿真測試階段,還需在實際的云計算平臺上應用驗證；同時EDCPSO算法只是優化了任務的完成時間,而在真實環境中還需考慮其他因素,如平均完成時間、經濟效益、負載均衡等。因此，有必要進一步研究和改進該算法,以便拓寬其應用場景。

圖1 t=50時的任務總完成時間

圖2 t=100時的任務總完成時間

圖3 t=500時的任務總完成時間

[1]KennedyJ,EberhartRC,ShiY.Swarmintelligence[M].Singapore:ElsevierSciencePress,2001:202-210.

[2]ParsopoulosKE,VrahatisMN.Recentapproachestoglobaloptimizationproblemsthroughparticleswarmoptimization[J].NaturalComputing,2002,1(2-3):235-306.

[3]RatnaweeraA,HalgamugeSK,WatsonHC.Self-organizinghierarchicalparticleswarmoptimizerwithtime-varyingaccelerationcoefficients[J].IEEETransactionsonEvolutionaryComputation,2010,8(3):240-255.

[4]ArumugamMS,RaoMVC,TanAWC.Anovelandeffectiveparticleswarmoptimizationlikealgorithmwithextrapolationtechnique[J].AppliedSoftComputing,2009,9(1):308-320.

[5] 介 婧,曾建潮,韓崇昭.基于群體多樣性反饋控制的自組織微粒群算法[J].計算機研究與發展,2008,45(3):464-471.

[6]ShiY,EberhartRC.Fuzzyadaptiveparticleswarmoptimization[C]//Procofthecongressonevolutionarycomputation.Piscataway:IEEE,2001:101-106.

[7]AngelinePJ.Evolutionaryoptimizationversusparticleswarmoptimization:philosophyandperformancedifferences[C]//Procofthe7thannualconferenceonevolutionaryprogramming.Berlin:Springer-Verlag,1998:601-610.

[8] 王 沛.社會認知心理學[M].北京:中國社會科學出版社,2006:72-86.

[9]EmbrechtsP,McneilAJ,StraumannD.Correlationanddependencyinriskmanagement:propertiesandpitfalls[C]//Procoftheriskmanagement:valueatriskandbeyond.Cambridge:CambridgeUniversityPress,2001:176-223.

[10]NelsenRB.Anintroductiontocopulas[M].2nded.NewYork:Springer-Verlag,2006:10-28.

[11] 申元霞,王國胤,曾傳華.相關性粒子群優化模型[J].軟件學報,2011,22(4):695-708.

[12]ShiYH,EberhartRC.Populationdiversityofparticleswarms[C]//ProcoftheIEEEworldcongressoncomputationalintelligence.HongKong:IEEEPress,2008:1063-1067.

[13]ClercM,KennedyJ.Theparticleswarm:explosionstabilityandconvergenceinamulti-dimensionalcomplexspace[J].IEEETransactionsonEvolutionComputer,2002,6(1):58-73.

[14] 呂振肅,侯志榮.自適應變異的粒子群優化算法[J].電子學報,2004,32(3):416-420.

[15] 胡 旺,李志蜀.一種更簡化而高效的粒子群優化算法[J].軟件學報,2007,18(4):861-868.

Task Scheduling Algorithm of Cloud Computing Based on Particle Swarm Optimization

TAN Wen-an1,2，ZHA An-min1，CHEN Sen-bo1

(1.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016，China; 2.School of Computer and Information,Shanghai Second Polytechnic University,Shanghai 201209,China)

How to schedule cloud tasks efficiently is one of the important issues to be resolved in cloud computing.The Extremum Disturbed Correlative Particle Swarm Optimization (EDCPSO) algorithm based on basic Particle Swarm Optimization (PSO) is proposed for the characteristics of cloud environment.It uses the Copular function to measure correlation structures among random factors,support of particles properly using the individual experience and social sharing information,resolving the demerit that the PSO algorithm lacks of the global optimization ability because of not considering the function of the random factors in the optimization process.Moreover,it uses the strategy of adding extremum disturbed arithmetic operators to improve further the PSO,which resolves the demerit of falling into local extremum in the late evolution for PSO.Simulation shows that EDCPSO is better than PSO and Cloudsim original scheduling algorithm in the same experiment conditions.That is to say,the algorithm can reduce the total completion time of tasks.

task scheduling;cloud computing;PSO;correlation;disturbed extremum

2015-10-15

2016-01-21

時間：2016-06-22

國家自然科學基金資助項目(6127036)；上海第二工業大學重點學科(XXKZD1301)

譚文安(1965-)，男，博士，教授，CCF高級會員，通訊作者，研究方向為軟件構架技術、協同計算、服務計算與知識管理、信息化工程及其支持環境研究等；查安民(1987-)，男，碩士研究生，研究方向為云計算、工作流調度與服務計算領域。

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

TP301.6

A

1673-629X(2016)07-0006-05

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