優(yōu)化粒子群的云計(jì)算任務(wù)調(diào)度算法

譚文安,查安民,陳森博

(1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016; 2.上海第二工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，上海 201209)

優(yōu)化粒子群的云計(jì)算任務(wù)調(diào)度算法

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

(1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016; 2.上海第二工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，上海 201209)

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

任務(wù)調(diào)度；云計(jì)算；粒子群優(yōu)化；相關(guān)性；極值擾動(dòng)

1 概 述

為了解決“大用戶”、“大數(shù)據(jù)”和“大系統(tǒng)”帶來的一系列挑戰(zhàn),云計(jì)算技術(shù)應(yīng)運(yùn)而生。云計(jì)算作為當(dāng)今信息領(lǐng)域的重大成果,發(fā)展迅速。任務(wù)調(diào)度是云計(jì)算的關(guān)鍵技術(shù)之一。一個(gè)好的任務(wù)調(diào)度算法,不僅有助于打造一個(gè)穩(wěn)定、健壯、節(jié)能的云計(jì)算環(huán)境,還可以提高用戶使用云計(jì)算服務(wù)的滿意度。智能優(yōu)化算法近年來受到廣泛關(guān)注,成為解決調(diào)度問題的新工具。

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

PSO算法的數(shù)學(xué)描述如下:

設(shè)有一種群,其粒子的個(gè)數(shù)為m,粒子的維數(shù)為n,則有：

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

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

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

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

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

整個(gè)種群的全局最優(yōu)解表示為: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)

其中,ω為慣性權(quán)重;c1和c2為加速系數(shù);r1和r2為隨機(jī)因子。

但是,要將PSO算法運(yùn)用于云計(jì)算任務(wù)的調(diào)度,需要對(duì)其進(jìn)行改進(jìn)。

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

PSO算法在迭代后期收斂速度變慢,這是PSO算法的一大缺點(diǎn)。文獻(xiàn)[6]通過動(dòng)態(tài)修改ω值,兼顧了搜索速度和精度；但對(duì)復(fù)雜的云計(jì)算任務(wù)的調(diào)度,這種通過改進(jìn)慣性權(quán)重所達(dá)到的優(yōu)化力度和實(shí)際效果都有待進(jìn)一步提高。文獻(xiàn)[7]在PSO算法中引入遺傳算法,雖然在一定程度上達(dá)到了優(yōu)化目的，但也增加了自身的復(fù)雜度。

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

2 云計(jì)算任務(wù)調(diào)度問題描述

用戶對(duì)調(diào)度結(jié)果的評(píng)價(jià)依據(jù)有很多,文中主要研究如何減少任務(wù)的完成時(shí)間。

2.1 粒子編碼

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

設(shè)有t個(gè)任務(wù),r個(gè)資源,且t>r。當(dāng)t=10,r=3時(shí),編碼序列(3,2,2,1,3,2,3,1,1,2)即為一個(gè)粒子。其中,每個(gè)任務(wù)對(duì)應(yīng)一個(gè)資源,例如,任務(wù)3對(duì)應(yīng)資源1。

接著是對(duì)粒子進(jìn)行解碼,目的在于獲取每個(gè)資源運(yùn)行的所有任務(wù)。例如,資源1上運(yùn)行的所有任務(wù)有{4,8,9}。

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

(3)

其中,i表示資源j上執(zhí)行的任務(wù)個(gè)數(shù);n表示資源j上執(zhí)行的任務(wù)總數(shù)。

系統(tǒng)完成所有任務(wù)的總時(shí)間為：

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

(4)

2.2 種群初始化

2.3 適應(yīng)度函數(shù)

文中主要研究如何優(yōu)化能夠減少任務(wù)的執(zhí)行時(shí)間,因此將適應(yīng)度函數(shù)定義為:

(5)

3 相關(guān)性PSO算法

3.1 隨機(jī)因子的認(rèn)知分析

根據(jù)PSO算法的心理學(xué)假設(shè),隨機(jī)因子體現(xiàn)了粒子在認(rèn)知過程中的非理性行為,反映出粒子作為認(rèn)知主體的情緒,而加速系數(shù)視為粒子對(duì)這種情緒的心理效應(yīng)[8-9]。

由此可知:將隨機(jī)因子r1和r2設(shè)為兩個(gè)相互獨(dú)立的隨機(jī)數(shù),沒有考慮粒子在尋優(yōu)過程中對(duì)個(gè)體最優(yōu)解pi和全局最優(yōu)解pg認(rèn)知的聯(lián)系。因此,需要建立認(rèn)知信息彼此之間的內(nèi)在關(guān)系,即r1和r2之間的相關(guān)性。

線性相關(guān)系數(shù)是一種常見的相關(guān)性分析[9]方法,計(jì)算公式為：

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

3.2 基于Copula的相關(guān)性PSO算法

文中使用二元Copula函數(shù)可刻畫兩個(gè)變量r1和r2之間的相關(guān)性。當(dāng)然,該函數(shù)可推廣到多元形式。

3.2.1 二元Copula的相關(guān)知識(shí)

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

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

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

Sklar定理是一個(gè)非常重要的定理,下面給出它的數(shù)學(xué)描述。

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

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

(6)

由定理1可得下面推論。

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

(7)

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

Copula函數(shù)類型很多,使用較多且應(yīng)用較廣的一個(gè)當(dāng)屬GaussianCopula，定義如下:

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

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

(8)

其中，Φ是標(biāo)準(zhǔn)正態(tài)分布函數(shù);Φρ是二維正態(tài)變量的聯(lián)合分布函數(shù);Φ-1是Φ的逆函數(shù);ρ是隨機(jī)變量間的線性相關(guān)系數(shù),且1≤ρ≤1。

3.2.2CPSO算法實(shí)現(xiàn)

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

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

(9)

其中,H為隨機(jī)因子r1,r2的聯(lián)合分布函數(shù);C為相應(yīng)的Copula函數(shù)。

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

在CPSO算法中,兩大隨機(jī)因子是服從[0,1]均勻分布且相關(guān)的隨機(jī)變量。因此,CPSO算法實(shí)現(xiàn)的難點(diǎn)是如何生成滿足給定Copula函數(shù)的r1和r2。

CPSO算法實(shí)現(xiàn)如下所述：

輸入:隨機(jī)產(chǎn)生的初始種群；

輸出:全局最優(yōu)解pg。

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

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

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

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

(5)根據(jù)x=Φ-1(u1),y=Φ-1(u2)計(jì)算x,y，其中,Φ是標(biāo)準(zhǔn)正態(tài)分布函數(shù);

(7)根據(jù)r1=Φ(x),r2=Φ(y)計(jì)算r1和r2,則二者即為滿足GaussianCopula定義的兩個(gè)相關(guān)隨機(jī)數(shù);

(8)使用式(5)計(jì)算粒子的適應(yīng)值;

(9)更新粒子的個(gè)體最優(yōu)解pi;

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

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

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

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

4 CPSO算法的多樣性分析

4.1 粒子認(rèn)知策略分析

由定義2及正態(tài)分布的對(duì)稱性可以看出:

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

(10)

上式表明,對(duì)于?ρ,r1,r2具有對(duì)稱性,其對(duì)稱軸為直線r1=r2。當(dāng)ρ在[-1,1]范圍內(nèi)逐漸增大時(shí),r1,r2的取值逐漸向?qū)ΨQ軸靠攏。當(dāng)ρ=1時(shí),r1,r2的取值將會(huì)分布在對(duì)稱軸之上。

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

4.2 群體多樣性分析

群體多樣性反映了種群中每個(gè)粒子的差異性,是描述種群進(jìn)化過程中粒子多樣性的一個(gè)關(guān)鍵指標(biāo)。

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

由定理2可知,為了在尋優(yōu)過程中始終保持種群較好的多樣性,CPSO算法應(yīng)該給定較大的相關(guān)系數(shù)ρ。

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

推論2：CPSO算法中,種群多樣性的期望正相關(guān)于粒子對(duì)個(gè)體最優(yōu)解和全局最優(yōu)解的利用率。

5 帶極值擾動(dòng)的CPSO算法

在CPSO算法中,個(gè)體最優(yōu)解pi和全局最優(yōu)解pg決定了粒子位置的收斂極值。如果每個(gè)粒子在逼近收斂極值的過程中不能發(fā)現(xiàn)比pg更優(yōu)的位置,則之后的所有迭代都將無效,因?yàn)檫M(jìn)化過程已經(jīng)結(jié)束。

5.1 極值擾動(dòng)

對(duì)式(1)和(2)添加擾動(dòng)算子后變?yōu)?

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算法實(shí)現(xiàn)

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

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

6 仿真實(shí)驗(yàn)與分析

6.1 仿真實(shí)驗(yàn)環(huán)境與算法參數(shù)

利用Cloudsim構(gòu)建云計(jì)算環(huán)境,Eclipse作為開發(fā)平臺(tái),將文中提出的EDCPSO算法與Cloudsim原有調(diào)度算法FIFO、基本PSO算法進(jìn)行對(duì)比分析。其中,算法參數(shù)見表1。

表1 EDCPSO算法參數(shù)

6.2 實(shí)驗(yàn)結(jié)果和性能分析

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

7 結(jié)束語

文中在分析云計(jì)算環(huán)境及其PSO算法的基礎(chǔ)上,提出了帶極值擾動(dòng)的相關(guān)性PSO(EDCPSO)算法。仿真結(jié)果表明:該算法相比于Cloudsim原有調(diào)度算法和基本PSO調(diào)度算法,具有更高的效率,能夠減少任務(wù)總的完成時(shí)間。

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

圖1 t=50時(shí)的任務(wù)總完成時(shí)間

圖2 t=100時(shí)的任務(wù)總完成時(shí)間

圖3 t=500時(shí)的任務(wù)總完成時(shí)間

[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].計(jì)算機(jī)研究與發(fā)展,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] 王 沛.社會(huì)認(rèn)知心理學(xué)[M].北京:中國社會(huì)科學(xué)出版社,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] 申元霞,王國胤,曾傳華.相關(guān)性粒子群優(yōu)化模型[J].軟件學(xué)報(bào),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] 呂振肅,侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法[J].電子學(xué)報(bào),2004,32(3):416-420.

[15] 胡 旺,李志蜀.一種更簡化而高效的粒子群優(yōu)化算法[J].軟件學(xué)報(bào),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

時(shí)間：2016-06-22

國家自然科學(xué)基金資助項(xiàng)目(6127036)；上海第二工業(yè)大學(xué)重點(diǎn)學(xué)科(XXKZD1301)

譚文安(1965-)，男，博士，教授，CCF高級(jí)會(huì)員，通訊作者，研究方向?yàn)檐浖?gòu)架技術(shù)、協(xié)同計(jì)算、服務(wù)計(jì)算與知識(shí)管理、信息化工程及其支持環(huán)境研究等；查安民(1987-)，男，碩士研究生，研究方向?yàn)樵朴?jì)算、工作流調(diào)度與服務(wù)計(jì)算領(lǐng)域。

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