羅 云,唐麗晴

(武警海警學(xué)院 計(jì)算機(jī)教研室,寧波 315801)

引言

云計(jì)算環(huán)境中存在著諸多不同類型的計(jì)算資源,各種類型的資源之間存在著一定的差異.云計(jì)算資源調(diào)度問題正是將云環(huán)境中的各類資源進(jìn)行合理調(diào)度,以達(dá)到縮短計(jì)算時(shí)間且提高資源利用率等目的的復(fù)雜調(diào)度問題.隨著“互聯(lián)網(wǎng)+”和“自媒體”概念的日益升溫,長期以來被應(yīng)用的調(diào)度效率較低的云計(jì)算資源調(diào)度算法不再能夠滿足人們的現(xiàn)實(shí)需求[1].

云計(jì)算資源調(diào)度算法研究已成為云計(jì)算領(lǐng)域的研究熱點(diǎn)之一.云計(jì)算資源調(diào)度需要同時(shí)兼顧計(jì)算效率和負(fù)載均衡,這依賴于具有強(qiáng)大搜索能力的智能優(yōu)化算法.目前,已經(jīng)有諸多的智能優(yōu)化算法應(yīng)用于云計(jì)算資源調(diào)度中.針對(duì)云計(jì)算服務(wù)集群資源調(diào)度和負(fù)載平衡的優(yōu)化問題,劉萬軍[2]等提出了一種適用于云計(jì)算資源調(diào)度的粒子群改進(jìn)算法.針對(duì)目前靜態(tài)的網(wǎng)絡(luò)資源調(diào)度算法不能滿足動(dòng)態(tài)的云計(jì)算資源調(diào)度要求的問題,周文俊[3]等提出了一種基于預(yù)測及蟻群算法的云計(jì)算資源調(diào)度策略.為了提高云計(jì)算資源的利用率,以保持負(fù)載平衡,孟令璽[4]等提出一種適用于云計(jì)算資源調(diào)度的文化粒子群算法.為了提高云計(jì)算資源的調(diào)度效率,袁浩[5]等提出了一種適合于云計(jì)算資源調(diào)度的社會(huì)力群智能優(yōu)化算法.針對(duì)傳統(tǒng)資源調(diào)度算法中存在資源利用率低等缺陷,卓濤[6]等提出一種基于改進(jìn)人工蜂群算法的云計(jì)算資源調(diào)度模型(Improved Artificial Bee Colony,IABC).盡管上述的改進(jìn)算法在一定程度上能夠提升云計(jì)算資源調(diào)度的效率和精度,但仍有一些不足之處.

云計(jì)算調(diào)度問題極難求得令人滿意的解.這一方面是因?yàn)樵朴?jì)算資源問題具有大規(guī)模、非線性、邏輯復(fù)雜的特點(diǎn),另一方面則是由于現(xiàn)有的智能優(yōu)化算法及其改進(jìn)策略都存在著對(duì)模型參數(shù)敏感、迭代后期容易陷入局部收斂等缺陷.為有效彌合智能優(yōu)化算法的缺陷以改善其優(yōu)化性能,本文提出了一種云計(jì)算調(diào)度粒子群改進(jìn)算法.基于云資源調(diào)度優(yōu)化模型,本文將混沌隨機(jī)數(shù)擾動(dòng)引入現(xiàn)有的慣性權(quán)重線性遞減(LDW)粒子群算法中,且結(jié)合了蟻群算法的尋優(yōu)策略.基于2 種測試函數(shù)和1 個(gè)云計(jì)算資源調(diào)度實(shí)際算例對(duì)3 種不一樣的優(yōu)化算法進(jìn)行比對(duì)試驗(yàn),其對(duì)比試驗(yàn)結(jié)果表明,本文提出的粒子群改進(jìn)算法的算法性能更佳.

1 云計(jì)算資源調(diào)度問題的優(yōu)化模型

云計(jì)算資源調(diào)度問題的核心是節(jié)約其執(zhí)行任務(wù)的時(shí)間.因此,云計(jì)算資源調(diào)度問題中最重要的優(yōu)化目標(biāo)即是其最大任務(wù)的執(zhí)行時(shí)間,記為Tmax.此外,云計(jì)算資源調(diào)度的重要優(yōu)化目標(biāo)是負(fù)載不平衡程度,記為Bdegree.具體的以花費(fèi)時(shí)間和負(fù)載平衡作為優(yōu)化目標(biāo)的優(yōu)化模型為[7]:

式(2)中,M={1,2,3,···,m}為 任務(wù)集合,含m個(gè)不同的任務(wù)；N={1,2,3,···,n}為 節(jié)點(diǎn)集合,含n個(gè)不同的節(jié)點(diǎn)；tij為第i個(gè)任務(wù)在第j個(gè)計(jì)算節(jié)點(diǎn)上的估算執(zhí)行時(shí)間；eij是決策變量,為第j個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行第i個(gè)任務(wù),若是,則eij=1,否則,eij=0.

最大任務(wù)的執(zhí)行時(shí)間Tmax采用下述公式計(jì)算得到:

負(fù)載不平衡程度Bdegree采用下述公式計(jì)算得到:

式(3) 中,enum={e1num,e2num,···,ennum,} 為n個(gè)不同節(jié)點(diǎn)的執(zhí)行次數(shù)的集合,E(X) 為 集合X的方差.

上述優(yōu)化模型求得最優(yōu)需使得任務(wù)完成時(shí)間最短,也即:

式中,cost為最短的任務(wù)完成時(shí)間.

由上述云計(jì)算資源調(diào)度問題的優(yōu)化模型可知,采用傳統(tǒng)的梯度下降算法等常規(guī)算法是不易求得滿意的優(yōu)化解的,因此,一般會(huì)采用粒子群算法等智能優(yōu)化算法進(jìn)行求解.

2 改進(jìn)的粒子群算法

2.1 粒子群算法

美國心理學(xué)家Kennedy 和電氣工程師Eberhart 于1995年共同提出了粒子群算法(PSO)[8].假設(shè)群體規(guī)模為N,目標(biāo)空間維度為D,第i個(gè)粒子的坐標(biāo)位置向?yàn)?(xi1,xi2,···,xiD)T、 速度向量為=(vi1,vi2,···,viD)T,個(gè)體極值和全局極值分別為=(pi1,pi2,···,piD)T、=(pg1,pg2,···,pgD)T.具體的粒子群算法的更新迭代計(jì)算公式如式(5)所述.

式中,i=1,2,···,N為粒子序號(hào),t為 粒子維度,d為迭代次數(shù),w為權(quán)重因子,c1,c2為加速隨機(jī)數(shù),一般來說,c1,c2∈[0,2],rand∈[0,1],也為隨機(jī)數(shù).

2.2 慣性權(quán)重線性遞減的粒子群算法

為改善粒子群算法極易陷入局部收斂的缺陷,眾多學(xué)者考慮了一種慣性權(quán)重系數(shù) ω 線性遞減的改進(jìn)策略.具體的慣性權(quán)重線性遞減的粒子群算法更新迭代計(jì)算公式如式(6)所述.

式中,ωmax為慣性權(quán)重最大值,ωk為慣性權(quán)重遞減斜率.

慣性權(quán)重ω 是一個(gè)粒子群算法的重要參數(shù).其能夠使粒子保持運(yùn)動(dòng)慣性,從而有能力對(duì)新區(qū)域進(jìn)行搜索.慣性權(quán)重的增大對(duì)全局搜索有幫助,有助于加快其收斂速度,但不利于尋到精確解；慣性權(quán)重的減小對(duì)局部搜索有幫助,從而可以獲得到更精確的解,但代價(jià)卻是降低了算法的收斂速度和增加了算法局部收斂的概率.因此,慣性權(quán)重的取值需要同時(shí)兼顧收斂速度和尋優(yōu)精度.由上述分析可知,對(duì)于粒子群算法而言,其迭代前期,收斂速度的重要性較大；隨著迭代次數(shù)的增加,尋優(yōu)精度的重要性越來越大.

慣性權(quán)重線性遞減(Linear Decreasing inertia Weight,LDW)的具體策略如下所述:在LDW 粒子群算法的整個(gè)過程中,以進(jìn)化代數(shù)為標(biāo)準(zhǔn),慣性權(quán)重以ωk的遞減斜率線性遞減.其慣性權(quán)重 ω和進(jìn)化代數(shù)t的關(guān)系曲線如圖1所述.

圖1 慣性權(quán)重線性遞減下的慣性權(quán)重ω 和進(jìn)化代數(shù)t的關(guān)系曲線

2.3 增加混沌隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重線性遞減粒子群算法

慣性權(quán)重線性遞減(LDW)粒子群算法較基本粒子群算法而言,具有更好的尋優(yōu)性能.然而,由于粒子群算法實(shí)際搜索過程具有非線性的特點(diǎn),于是慣性權(quán)重 ω線性遞減不能體現(xiàn)實(shí)際搜索過程的非線性的特點(diǎn),因而導(dǎo)致得不到足夠理想的優(yōu)化效果[9].因此,粒子群算法實(shí)際計(jì)算過程中,若算法通過長時(shí)間的計(jì)算都無法獲得更理想的全局極值,即迅速加入合理范圍內(nèi)的混沌隨機(jī)數(shù)擾動(dòng),以使得慣性權(quán)重 ω突然增大,從而起到抑制粒子群算法局部收斂的作用[10].其增加混沌隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重線性遞減的粒子群算法更新迭代計(jì)算公式如式(7)所述.

式中,At為慣性權(quán)重的混沌擾動(dòng)隨機(jī)數(shù),在一定的擾動(dòng)概率下,At∈{0,0.1},其余,At=0.混沌現(xiàn)象是非線性系統(tǒng)中一種普遍的現(xiàn)象,它的變化過程看似混亂,實(shí)際上其內(nèi)在具有規(guī)律性,能夠在一定范圍之內(nèi),按照自身規(guī)律不重復(fù)地遍歷所有狀態(tài).具體的慣性權(quán)重的混沌擾動(dòng)隨機(jī)數(shù)At的隨機(jī)公式如下所示:

其增加混沌隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重 ω和進(jìn)化代數(shù)t的關(guān)系曲線如圖1所述.

圖2 增加混沌隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重線性遞減下的慣性權(quán)重ω 和進(jìn)化代數(shù)t 的關(guān)系曲線

2.4 蟻群算法

1992年,意大利學(xué)者Dorigo 提出了蟻群算法[11].在蟻群算法中,每只螞蟻均在進(jìn)行路徑搜索后獨(dú)立的產(chǎn)生一個(gè)可行解,并產(chǎn)生信息素.假設(shè)當(dāng)前共有m個(gè)節(jié)點(diǎn)等待螞蟻訪問及選擇,在t時(shí) 刻,第k只螞蟻正處于節(jié)點(diǎn)i處,即將選擇下一節(jié)點(diǎn)j進(jìn)行移動(dòng),其移動(dòng)規(guī)則如下:

每只螞蟻在構(gòu)建可行解的同時(shí)分泌信息素,局部信息素更新方式如下式所示:

當(dāng)一次循環(huán)中的所有螞蟻均構(gòu)建了可行解后,對(duì)該次循環(huán)產(chǎn)生的最優(yōu)解與已知的最優(yōu)解進(jìn)行比較,判斷是否產(chǎn)生了新的當(dāng)前的最優(yōu)解,若產(chǎn)生,則對(duì)該解上的弧信息素進(jìn)行更新,如下式所示:

式(8)-(10)中,蟻群算法主要變量如下:τij為 弧(i,j)上的螞蟻信息素密度,初始值為 τ0；dij為弧(i,j)上的歐式長度；ηij為弧(i,j)上 的啟發(fā)函數(shù)值,通常ηij=1/dij；α為螞蟻信息素密度的相對(duì)重要性,α ≥0；β為啟發(fā)函數(shù)的相對(duì)重要性,β≥0；ρ為螞蟻信息素的衰減參數(shù),0＜ρ＜1；Lbest為當(dāng)前最優(yōu)解的路徑長度；Vbest為當(dāng)前最優(yōu)解.

2.5 混合優(yōu)化算法改進(jìn)策略

粒子群算法和蟻群算法的尋優(yōu)模式相對(duì)單一,總是全部個(gè)體向最優(yōu)個(gè)體進(jìn)行學(xué)習(xí),其最優(yōu)解對(duì)種群的進(jìn)化方向的影響是很大的.為了克服采用單一的有相對(duì)固定尋優(yōu)指引方向的尋優(yōu)模式導(dǎo)致的算法容易陷入局部最優(yōu)的缺點(diǎn),本文提出了一種同時(shí)混入蟻群優(yōu)化策略的改進(jìn)LDW 粒子群優(yōu)化策略的混合優(yōu)化算法,記為Improved PSO.目的在于在保持原有粒子群算法和蟻群算法搜索性能的同時(shí),防止算法因?yàn)閷?yōu)模式單一而導(dǎo)致的陷入局部收斂的缺點(diǎn).具體的計(jì)算步驟如下所述:

Step1.初始化混合優(yōu)化算法的各項(xiàng)參數(shù):種群規(guī)模m+N、粒子群規(guī)模(粒子數(shù)量)N、迭代次數(shù)d、最大慣性權(quán)重ωmax、慣性權(quán)重系數(shù)的遞減斜率 ωk、學(xué)習(xí)因子c1,c2、蟻群規(guī)模(螞蟻數(shù)量)m、螞蟻信息素密度的相對(duì)重要性 α、啟發(fā)函數(shù)的相對(duì)重要性 β、螞蟻信息素的衰減參數(shù) ρ等,其中的粒子群規(guī)模與蟻群規(guī)模相同m=N；

Step2.隨機(jī)生成m+N種不同的解,也即生成初始種群,初始種群包含初始粒子群和初始蟻群；

Step3.計(jì)算N種解的適應(yīng)度函數(shù)值,并基于此對(duì)當(dāng)前粒子群進(jìn)行排序,以得到個(gè)體極值和全局極值；

Step4.采用增加混沌隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重的線性遞減(LDW)粒子群算法的更新規(guī)則對(duì)所有粒子進(jìn)行更新；

Step5.將這m只 “螞蟻”置于起始結(jié)點(diǎn)0 上,采用蟻群算法的信息素更新規(guī)則對(duì)所有螞蟻進(jìn)行更新；

Step6.粒子群和蟻群交換一定數(shù)目k的個(gè)體,其交換數(shù)目要小于粒子群規(guī)模和蟻群規(guī)模k＜min(m,N)；

Step7.查看是否達(dá)到最大迭代次數(shù),如果是則轉(zhuǎn)步驟Step5,否則轉(zhuǎn)步驟Step2；

Step8.輸出計(jì)算得到的最優(yōu)解的適應(yīng)度函數(shù)值.

本文中,粒子群算法和蟻群算法的主要參數(shù)如下:粒子群規(guī)模N為30、迭代次數(shù)d為50、最大慣性權(quán)重ωmax為0.85、慣性權(quán)重系數(shù)的遞減斜率 ωk為0.001、學(xué)習(xí)因子c1,c2均為0.5、螞蟻信息素密度的相對(duì)重要性 α為1、啟發(fā)函數(shù)的相對(duì)重要性 β為0.9、螞蟻信息素的衰減參數(shù)ρ 為0.2.

3 仿真實(shí)驗(yàn)

基于2 種不同的測試函數(shù),采用粒子群改進(jìn)算法(IPSO)、增加混沌隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重線性遞減(LDW) 的粒子群算法[12](linear decreasing inertia weight PSO with chaotic constant disturbance,CLDWPSO)和普通的慣性權(quán)重線性遞減粒子群算法[13](Linear Decreasing inertia Weight PSO,LDWPSO)求極小值.具體的仿真結(jié)果如下所述.

(1) De jong 函數(shù),最優(yōu)解為0.0.其De jong 函數(shù)的解析式為F(x1,x2)=100?(x1-x2)2+(1-x1)2.

具體的De jong 函數(shù)的仿真測試結(jié)果如圖3和表1所 述.

圖3 采用De jong 函數(shù)的仿真測試收斂曲線

由圖3和表1可知,相比于其它算法,粒子群改進(jìn)算法(IPSO) 最優(yōu),尋優(yōu)得到的最優(yōu)解為:(x1,x2)=(0.9928,0.9984)；最優(yōu)解函數(shù)值F(x1,x2)=0.0032.與此同時(shí),粒子群改進(jìn)算法(IPSO) 的收斂時(shí)間最短,為2 0.21 秒.

表1 采用De jong 函數(shù)的仿真測試結(jié)果

(2) Schaffer 函數(shù),最優(yōu)解0.0.其Schaffer 函數(shù)的解析式為

具體的Schaffer 函數(shù)的仿真測試結(jié)果如圖4和表2所述.

表2 采用Schaffer 函數(shù)的仿真測試結(jié)果

由圖4和表2可知,粒子群改進(jìn)算法(IPSO)同樣最優(yōu),尋優(yōu)得到的最優(yōu)解為:(x1,x2)=(2.8×10-4,2.2×10-4) ；最優(yōu)解函數(shù)值F(x1,x2)=3.62×10-4.與此同時(shí),粒子群改進(jìn)算法(IPSO) 的收斂時(shí)間最短,為43.86 秒.

4 實(shí)際算例測試

為了驗(yàn)證算法的改進(jìn)效果,本文采用粒子群改進(jìn)算法(IPSO)、增加混沌隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重線性遞減的粒子群算法(CLDWPSO)和普通的慣性權(quán)重線性遞減粒子群算法(LDWPSO)求解了一個(gè)云資源調(diào)度實(shí)際算例的最短任務(wù)完成時(shí)間及其不平衡程度.實(shí)際算例有10 個(gè)計(jì)算節(jié)點(diǎn)和100 個(gè)任務(wù).具體的云資源調(diào)度問題的估算執(zhí)行時(shí)間表如表3所述[14].

表3 云資源調(diào)度問題的估算執(zhí)行時(shí)間表

具體的云資源調(diào)度問題的實(shí)測收斂曲線如圖5和圖6所述.

圖5 云資源調(diào)度問題任務(wù)完成時(shí)間的實(shí)測收斂曲線

圖6 云資源調(diào)度問題負(fù)載不平衡程度的實(shí)測收斂曲線

由圖5和圖6可知,相比于其它算法,粒子群改進(jìn)算法(IPSO) 最優(yōu),求解得到的任務(wù)執(zhí)行節(jié)點(diǎn)序列為e=[7 4 1 7 5 7 10 ···9],估算的任務(wù)完成時(shí)間為194.4568.與此同時(shí),粒子群改進(jìn)算法(IPSO)尋到的調(diào)度方案的負(fù)載不平衡程度最小,為0.4444,其調(diào)度方案的計(jì)算節(jié)點(diǎn)的執(zhí)行次數(shù)的集合為enum=[10 10 9 ···9].

5 結(jié)論

本文基于云資源調(diào)度問題的優(yōu)化模型,提出了一種粒子群改進(jìn)算法(IPSO).首先,基于慣性權(quán)重線性遞減粒子群算法,引入適當(dāng)?shù)幕煦珉S機(jī)數(shù)擾動(dòng)；其次,將蟻群算法尋優(yōu)策略引入粒子群算法中以改善其全局優(yōu)化性能.本文采用了2 種測試函數(shù)(De jong、Schaffer)和1 個(gè)云計(jì)算資源調(diào)度實(shí)際算例來驗(yàn)證優(yōu)化算法的性能.其驗(yàn)證結(jié)果表明,相比于其他兩種優(yōu)化算法,本文提出的改進(jìn)算法(IPSO)更佳.