云計算調度粒子群改進算法①

羅 云,唐麗晴

(武警海警學院 計算機教研室,寧波 315801)

引言

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

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

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

1 云計算資源調度問題的優化模型

云計算資源調度問題的核心是節約其執行任務的時間.因此,云計算資源調度問題中最重要的優化目標即是其最大任務的執行時間,記為Tmax.此外,云計算資源調度的重要優化目標是負載不平衡程度,記為Bdegree.具體的以花費時間和負載平衡作為優化目標的優化模型為[7]:

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

最大任務的執行時間Tmax采用下述公式計算得到:

負載不平衡程度Bdegree采用下述公式計算得到:

式(3) 中,enum={e1num,e2num,···,ennum,} 為n個不同節點的執行次數的集合,E(X) 為 集合X的方差.

上述優化模型求得最優需使得任務完成時間最短,也即:

式中,cost為最短的任務完成時間.

由上述云計算資源調度問題的優化模型可知,采用傳統的梯度下降算法等常規算法是不易求得滿意的優化解的,因此,一般會采用粒子群算法等智能優化算法進行求解.

2 改進的粒子群算法

2.1 粒子群算法

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

式中,i=1,2,···,N為粒子序號,t為 粒子維度,d為迭代次數,w為權重因子,c1,c2為加速隨機數,一般來說,c1,c2∈[0,2],rand∈[0,1],也為隨機數.

2.2 慣性權重線性遞減的粒子群算法

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

式中,ωmax為慣性權重最大值,ωk為慣性權重遞減斜率.

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

慣性權重線性遞減(Linear Decreasing inertia Weight,LDW)的具體策略如下所述:在LDW 粒子群算法的整個過程中,以進化代數為標準,慣性權重以ωk的遞減斜率線性遞減.其慣性權重 ω和進化代數t的關系曲線如圖1所述.

圖1 慣性權重線性遞減下的慣性權重ω 和進化代數t的關系曲線

2.3 增加混沌隨機數擾動的慣性權重線性遞減粒子群算法

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

式中,At為慣性權重的混沌擾動隨機數,在一定的擾動概率下,At∈{0,0.1},其余,At=0.混沌現象是非線性系統中一種普遍的現象,它的變化過程看似混亂,實際上其內在具有規律性,能夠在一定范圍之內,按照自身規律不重復地遍歷所有狀態.具體的慣性權重的混沌擾動隨機數At的隨機公式如下所示:

其增加混沌隨機數擾動的慣性權重 ω和進化代數t的關系曲線如圖1所述.

圖2 增加混沌隨機數擾動的慣性權重線性遞減下的慣性權重ω 和進化代數t 的關系曲線

2.4 蟻群算法

1992年,意大利學者Dorigo 提出了蟻群算法[11].在蟻群算法中,每只螞蟻均在進行路徑搜索后獨立的產生一個可行解,并產生信息素.假設當前共有m個節點等待螞蟻訪問及選擇,在t時 刻,第k只螞蟻正處于節點i處,即將選擇下一節點j進行移動,其移動規則如下:

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

當一次循環中的所有螞蟻均構建了可行解后,對該次循環產生的最優解與已知的最優解進行比較,判斷是否產生了新的當前的最優解,若產生,則對該解上的弧信息素進行更新,如下式所示:

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

2.5 混合優化算法改進策略

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

Step1.初始化混合優化算法的各項參數:種群規模m+N、粒子群規模(粒子數量)N、迭代次數d、最大慣性權重ωmax、慣性權重系數的遞減斜率 ωk、學習因子c1,c2、蟻群規模(螞蟻數量)m、螞蟻信息素密度的相對重要性 α、啟發函數的相對重要性 β、螞蟻信息素的衰減參數 ρ等,其中的粒子群規模與蟻群規模相同m=N；

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

Step3.計算N種解的適應度函數值,并基于此對當前粒子群進行排序,以得到個體極值和全局極值；

Step4.采用增加混沌隨機數擾動的慣性權重的線性遞減(LDW)粒子群算法的更新規則對所有粒子進行更新；

Step5.將這m只 “螞蟻”置于起始結點0 上,采用蟻群算法的信息素更新規則對所有螞蟻進行更新；

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

Step7.查看是否達到最大迭代次數,如果是則轉步驟Step5,否則轉步驟Step2；

Step8.輸出計算得到的最優解的適應度函數值.

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

3 仿真實驗

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

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

具體的De jong 函數的仿真測試結果如圖3和表1所 述.

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

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

表1 采用De jong 函數的仿真測試結果

(2) Schaffer 函數,最優解0.0.其Schaffer 函數的解析式為

具體的Schaffer 函數的仿真測試結果如圖4和表2所述.

表2 采用Schaffer 函數的仿真測試結果

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

4 實際算例測試

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

表3 云資源調度問題的估算執行時間表

具體的云資源調度問題的實測收斂曲線如圖5和圖6所述.

圖5 云資源調度問題任務完成時間的實測收斂曲線

圖6 云資源調度問題負載不平衡程度的實測收斂曲線

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

5 結論

本文基于云資源調度問題的優化模型,提出了一種粒子群改進算法(IPSO).首先,基于慣性權重線性遞減粒子群算法,引入適當的混沌隨機數擾動；其次,將蟻群算法尋優策略引入粒子群算法中以改善其全局優化性能.本文采用了2 種測試函數(De jong、Schaffer)和1 個云計算資源調度實際算例來驗證優化算法的性能.其驗證結果表明,相比于其他兩種優化算法,本文提出的改進算法(IPSO)更佳.