應(yīng)用改進粒子群算法在云計算任務(wù)調(diào)度中的應(yīng)用及其仿真研究

摘 要：本文主要是針對計算“云”中的資源進行合理高效的調(diào)度分析，提出一種改進算法的且具有雙適應(yīng)度的粒子群優(yōu)化調(diào)度算法（DFPSO），優(yōu)化后的算法能夠?qū)崿F(xiàn)最小執(zhí)行時間以及平衡資源負載，并且最后通過仿真實驗來驗證改進后算法的有效性。

關(guān)鍵詞：PSO；DFPSO；云計算任務(wù)調(diào)度

中圖分類號：TP301.6

1 傳統(tǒng)粒子群算法的不足

粒子群算法（Particle Swarm Optimization，PSO）是可以全面的實現(xiàn)自適應(yīng)搜索過程的種群優(yōu)化算法，因為PSO本身的參數(shù)并不多以及其內(nèi)部結(jié)構(gòu)也是屬于十分簡單的，同時也是粒子群算法的優(yōu)點所在。然而PSO算法有著其天然的不足之處，由于其在迭代過程中容易使收斂速度變慢，還有其魯棒性也很差等。

因為傳統(tǒng)的粒子群算法主要是從資源時間的應(yīng)用來處理，并且其本身是沒有很好地考慮到資源存在的不足因素。從而造成了資源負載不均衡的現(xiàn)象，這是作為傳統(tǒng)PSO調(diào)度算法中最大的不足之處。

2 改進后具有雙適應(yīng)度的粒子群算法

雙適應(yīng)度的粒子群算法（DFPSO），是屬于一種具有群種智能化算法，從某一方面講遺傳算法與粒子群算法有一定相似之處。它們之間最大的共性就是需要事先對這一些種群進行初始化，然后經(jīng)過不斷的迭代過程來實現(xiàn)最優(yōu)解，但這兩種算法之間各有各的優(yōu)勢，由于粒子群算法它本身是不存在交叉的，同時也沒有變異的操作，這樣可以使它能夠?qū)崿F(xiàn)起來變得十分的簡單，同時需要調(diào)整的參數(shù)也很少，DFPSO就有這些優(yōu)點，粒子群算法在現(xiàn)實的求解云計算中的任務(wù)調(diào)度具有最佳的優(yōu)勢。

粒子的編碼（公式1）與解碼（公式1）方式以及種群初始化方式具體如下。

（1）

（2）

上述公式（1）中主要是代表完成總?cè)蝿?wù)所需要占用到的時間。其中將這些任務(wù)分配到第r個計算資源上的子任務(wù)的數(shù)量是n，而resource（r，i）函數(shù)則是代表了第r個計算資源上處理分配到這些資源中的第i個子任務(wù)所需要的具體時間。從公式（2）中我們可以出資源等級差異的任務(wù)完成過程中所需要的“總時間”。其中β（r）屬于第r個資源的資源等級。那么定義任務(wù)完成總時間的適應(yīng)度函數(shù)是這樣的：

（3）

公式（3）中第i個粒子的任務(wù)總共所需要的時間是用 表示，它的值是通過公式（1）來計算得出的。另外，定義考慮資源等級差異的適應(yīng)度函數(shù)是：

（4）

公式（4）中RSFTi是代表第i個粒子在考慮資源差異的任務(wù)完成所需要的“總時間”，它的值可以由公式（2）來求得。

3 改進后的實驗仿真與性能分析

3.1 實驗仿真環(huán)境和參數(shù)的設(shè)置

應(yīng)用MATLAB軟件對這兩種調(diào)度算法進行云計算環(huán)境下的實驗?zāi)M，然后在相同的實驗平臺上對比出這兩種調(diào)度的算法。表1是基本參數(shù)信息：

表1 算法的基本參數(shù)設(shè)置

名稱種群規(guī)模

S資源數(shù)

Resource任務(wù)數(shù)

Task慣性因子

w學(xué)習(xí)因子

c1學(xué)習(xí)因子

c2最大迭代次數(shù)tmax

取值1005050、100、2000.922200

3.2 仿真結(jié)果分析

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

從上圖1中我們可以知道，粒子在前期實現(xiàn)迭代的過程中，傳統(tǒng)的PSO算法與改進后的DFPSO調(diào)度算法之間最終實現(xiàn)的結(jié)果是一樣的，兩種算法所用的時間也是相當(dāng)接近的。隨著后面迭代次數(shù)的不斷累加，其數(shù)值就會越來越大，當(dāng)其值等于23時就會自動收斂，它調(diào)度生成的任務(wù)所需要的總時間約是77s，而DFPSO調(diào)度算法在整個迭代過程中就會自動實現(xiàn)跳出這兩個局部的最優(yōu)解，然后實現(xiàn)收斂，雖然其迭代的次數(shù)達到了73次，但是這種算法完成總時間只需要67s，通過比較后就可以看出改進后的算法比傳統(tǒng)的PSO算法明顯提高了11s。

圖2 Task=100時的任務(wù)總完成時間 圖3 Task=200時的任務(wù)總完成時間

如果當(dāng)任務(wù)數(shù)增加至100時，比較圖1與圖2我們可以知道，這兩種算法需要完成任務(wù)的總時間差距會隨之增大，其中PSO算法收斂速度也會變快，在迭代到32次之后，它就可以收斂于自己的最優(yōu)調(diào)度結(jié)果，但是所需要完成的任務(wù)總時間依然會大些；而改進后的DFPSO算法雖然在迭代到118次時就會收斂，其收斂速度比PSO算法相對慢一些，但是所需要完成任務(wù)的總時間會比PSO算法要少了30s。那么當(dāng)整個任務(wù)數(shù)繼續(xù)增加到200時，從圖3中我們可以看出，這兩種算法在調(diào)度任務(wù)時所需要的總時間差達到了100s。

從上面的仿真結(jié)果我們可以看出，改進的DFPSO算法優(yōu)于傳統(tǒng)的PSO算法。

參考文獻：

[1]李寧，孫德寶，鄒彤.基于差分方程的PSO算法粒子運動軌跡分析[J].計算機學(xué)報，2006（11）：2052?2061.

[2]孫瑞鋒，趙政文.基于云計算的資源調(diào)度策略[J].航空計算技術(shù)，2010（03）：103-105.

[3]左利云，左利鋒.云計算中基于預(yù)先分類的調(diào)度優(yōu)化算法[J].計算機工程與設(shè)計，2012（04）：1357-1361.

作者單位：廣東省高級技工學(xué)校，廣東惠州 516100