基于雙粒子群LDW粒子群改進(jìn)算法的云計(jì)算任務(wù)調(diào)度算法

吳宇星，劉媛華 （上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

云計(jì)算是一種多種技術(shù)融合的基于網(wǎng)絡(luò)的商業(yè)服務(wù)模式[1]?？焖俸侠淼慕o出計(jì)算資源調(diào)度方案是云計(jì)算中的核心內(nèi)容之一。當(dāng)前，云資源調(diào)度算法研究已廣泛受到相關(guān)科研領(lǐng)域?qū)W者的關(guān)注。采用一種合適的優(yōu)化算法對(duì)其進(jìn)行高效的調(diào)度，縮短任務(wù)完成時(shí)間并提高資源利用率，一直是云計(jì)算科研人員不懈追求的目標(biāo)。就云計(jì)算資源而言，具有異構(gòu)和動(dòng)態(tài)的特點(diǎn)，進(jìn)行大規(guī)模的資源調(diào)度，不僅需要考慮時(shí)間因素，還要兼顧負(fù)載均衡。由此可知，云計(jì)算任務(wù)調(diào)度問(wèn)題是一種特別復(fù)雜的NP問(wèn)題，極難求得令人滿意的解。

近年來(lái)，企業(yè)業(yè)務(wù)需求逐漸向“資源共享與工作協(xié)同”的方向躍進(jìn)，網(wǎng)絡(luò)技術(shù)越來(lái)越受到科研人員的關(guān)注。其主要研究?jī)?nèi)容即將把某龐大的計(jì)算問(wèn)題拆分細(xì)化為小規(guī)模的計(jì)算任務(wù)，并分配多個(gè)計(jì)算節(jié)點(diǎn)予以處理，再匯總得到最終結(jié)果?；诖?，國(guó)內(nèi)外不同學(xué)者在云計(jì)算方面提出了不同方法并應(yīng)用到了不同領(lǐng)域。在文獻(xiàn)[2]中，作者提出了一種同時(shí)考慮可靠性、運(yùn)行時(shí)間以及資源調(diào)度失敗系統(tǒng)方法，同時(shí)，使用了一種反射機(jī)制分離資源調(diào)度過(guò)程，并成功應(yīng)用于云計(jì)算資源調(diào)度中。文獻(xiàn)[3]的作者提出了一種網(wǎng)絡(luò)服務(wù)器的動(dòng)態(tài)模型以及性能控制，同時(shí)，設(shè)計(jì)了增益線性二次型調(diào)節(jié)器控制器，改進(jìn)了系統(tǒng)性能的質(zhì)量，最后，實(shí)驗(yàn)證明所提方法的有效性。由于在云計(jì)算服務(wù)調(diào)度環(huán)境下，大多數(shù)算法收斂速度慢，容易陷入局部最優(yōu)，為此，文獻(xiàn)[4]的作者介紹一種貪婪粒子群優(yōu)化算法來(lái)解決任務(wù)調(diào)度問(wèn)題，該算法源于一種虛擬機(jī)云平臺(tái)，相比于傳統(tǒng)的粒子群算法，所提出算法能夠很快求解出粒子群算法的粒子初始值，使系統(tǒng)性能得到改善。以上方法能夠有效解決云計(jì)算資源調(diào)度問(wèn)題，然而，很少文獻(xiàn)考慮利用改進(jìn)的慣性權(quán)重線性遞減的粒子群算法解決云計(jì)算資源調(diào)度問(wèn)題。

為將優(yōu)化計(jì)算的相關(guān)研究成果更適宜地應(yīng)用于云計(jì)算資源調(diào)度，本文提出了一種改進(jìn)的雙粒子群LDW粒子群算法。針對(duì)粒子群算法不易全局收斂的問(wèn)題，本文基于云資源調(diào)度問(wèn)題的數(shù)學(xué)模型，在慣性權(quán)重粒子群算法的基礎(chǔ)上，加入隨機(jī)數(shù)擾動(dòng)，且采用雙粒子群的進(jìn)化機(jī)制。并基于2種測(cè)試函數(shù)和云計(jì)算資源調(diào)度問(wèn)題的實(shí)際算例，在Matlab GUI平臺(tái)下采用不同的粒子群算法進(jìn)行對(duì)比試驗(yàn)，以驗(yàn)證算法的有效性。

1 云計(jì)算資源調(diào)度問(wèn)題的數(shù)學(xué)模型

云計(jì)算資源調(diào)度是一個(gè)整數(shù)規(guī)劃問(wèn)題。通過(guò)預(yù)先知道某個(gè)任務(wù)在某個(gè)計(jì)算節(jié)點(diǎn)的執(zhí)行時(shí)間，來(lái)實(shí)現(xiàn)資源的優(yōu)化調(diào)度。根據(jù)不同計(jì)算節(jié)點(diǎn)的每秒可處理的百萬(wàn)指令數(shù)（MIPS），估算其任務(wù)執(zhí)行時(shí)間。具體的以花費(fèi)時(shí)間作為優(yōu)化目標(biāo)的約束目標(biāo)模型為：

式中，M=｛1,2,3,…,m ｝為任務(wù)集合，m為任務(wù)數(shù)；N=｛1,2,3,…,n ｝為節(jié)點(diǎn)集合，n為節(jié)點(diǎn)數(shù)；tij為第i個(gè)任務(wù)在第j個(gè)計(jì)算節(jié)點(diǎn)上的估算執(zhí)行時(shí)間；Tmax為最大任務(wù)執(zhí)行時(shí)間；eij為第j個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行第i個(gè)任務(wù)，若是，則eij=1，反之，eij=0。

具體的最大任務(wù)執(zhí)行時(shí)間Tmax的定義如下所述：

具體的目標(biāo)函數(shù)為任務(wù)完成時(shí)間最短，具體定義如下所述：

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

對(duì)于上述云資源調(diào)度問(wèn)題，eij組成的向量是決策變量。當(dāng)系統(tǒng)具有一定的計(jì)算規(guī)模時(shí)，即是一個(gè)特別復(fù)雜的NP問(wèn)題。難于采用諸如線性規(guī)劃法、單純形法、牛頓法等常規(guī)方法進(jìn)行求解。粒子群算法由于結(jié)構(gòu)簡(jiǎn)單，尋優(yōu)能力強(qiáng)，因而廣泛應(yīng)用于這類復(fù)雜的NP問(wèn)題的求解中[5]。

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

2.1 粒子群算法

粒子群優(yōu)化算法是美國(guó)心理學(xué)家Kennedy和電氣工程師Eberhart于1995年首次提出的智能算法[6]。粒子群算法是模擬鳥(niǎo)群捕食的仿真優(yōu)化算法。設(shè)群體規(guī)模為N，目標(biāo)搜索空間的維度為D，第i個(gè)粒子的坐標(biāo)位置向量為速度向量為，粒子群全局極值記為

基本粒子群算法更新迭代計(jì)算公式如式（5）所示。

式中：i=1,2,…,N為粒子序號(hào)，t為粒子維度，d為迭代次數(shù)，c1,c2為加速隨機(jī)數(shù)，一般在0～2之間取值，rand為0～1之間的隨機(jī)實(shí)數(shù)。

粒子群算法極易局部收斂。為抑制粒子群算法局部收斂，各種文獻(xiàn)對(duì)基本粒子群算法進(jìn)行了不同程度的改進(jìn)。其中，基于慣性權(quán)重系數(shù)ω的改進(jìn)是非常重要的一類改進(jìn)。具體的包含慣性權(quán)重系數(shù)ω的粒子群算法更新迭代計(jì)算公式如式（6）所示。

這種改進(jìn)的算法被廣泛應(yīng)用于各個(gè)優(yōu)化領(lǐng)域。因其與基本算法的計(jì)算復(fù)雜度類似，但尋優(yōu)性能卻大幅提升。

2.2 慣性權(quán)重線性遞減策略

慣性權(quán)重ω是粒子群算法的重要參數(shù)之一。其能夠使粒子保持運(yùn)動(dòng)慣性，以有能力探索新區(qū)域。慣性權(quán)重較高，利于全局搜索，能夠加快收斂速度，但不易尋到精確解；慣性權(quán)重較小，利于局部搜索，容易得到精確度更佳的解，但會(huì)降低其收斂速度并增大粒子群算法局部收斂的概率。合適的慣性權(quán)重在同時(shí)兼顧收斂速度和尋優(yōu)精度。在粒子群算法的迭代初期，偏重于提升收斂速度；在粒子群算法的迭代末期，偏重于增加尋優(yōu)[7]。粒子群算法的慣性權(quán)重的線性遞減（LDW）策略是這樣的：整個(gè)搜索過(guò)程中，慣性權(quán)重與進(jìn)化代數(shù)呈現(xiàn)線性遞減的關(guān)系。其慣性權(quán)重ω和粒子群進(jìn)化代數(shù)t的關(guān)系曲線如圖1所示。

具體的引入慣性權(quán)重系數(shù)ω的粒子群算法更新迭代計(jì)算公式如式（7）所示。

式中：ωmax為初始的最大慣性權(quán)重，ωk為慣性權(quán)重系數(shù)的遞減斜率。

2.3 粒子群算法的改進(jìn)策略

盡管慣性權(quán)重線性遞減（LDW）的粒子群改進(jìn)策略能夠大幅提升粒子群算法的尋優(yōu)性能。然而，粒子群算法的實(shí)際搜索過(guò)程具有非線性和高度復(fù)雜的特點(diǎn)，所以慣性權(quán)重ω線性遞減不能真實(shí)反映其實(shí)際搜索過(guò)程，故而優(yōu)化效果的改善狀況大大受限[8]。因此，粒子群算法迭代過(guò)程中，當(dāng)算法長(zhǎng)時(shí)間不能得到更佳的最優(yōu)解時(shí)，加入合理范圍內(nèi)的隨機(jī)數(shù)擾動(dòng)，令慣性權(quán)重ω短暫的突然增大，從而抑制粒子群算法局部收斂。具體的增加隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重的線性遞減（LDW）粒子群算法的更新迭代計(jì)算公式如式（8） 所示。

式中：At為慣性權(quán)重?cái)_動(dòng)隨機(jī)數(shù)，在一定的擾動(dòng)概率下，At∈｛0,0.1 ｝，其余，At=0。

具體的慣性權(quán)重ω和粒子群進(jìn)化代數(shù)t的關(guān)系曲線如圖2所示。

圖1 LDW策略下的慣性權(quán)重ω和粒子群進(jìn)化代數(shù)t的關(guān)系曲線

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

2.4 雙種群粒子群算法

圖3 雙粒子群最優(yōu)粒子被交換

盡管粒子群優(yōu)化算法有著極高的優(yōu)化搜索能力，但和眾多覓食類的生物優(yōu)化算法相同，粒子群優(yōu)化算法易于陷入局部收斂。粒子群進(jìn)化環(huán)境和初代粒子群具有一定程度的局限性，當(dāng)普通粒子群算法進(jìn)入迭代后期，就會(huì)顯現(xiàn)出進(jìn)化緩慢或停滯的不利現(xiàn)象。為此，本文考慮了雙粒子群同時(shí)進(jìn)化并進(jìn)行信息交流的一種改進(jìn)思路。雙粒子群進(jìn)化機(jī)制是一種并行機(jī)制，它使用兩個(gè)粒子群同時(shí)進(jìn)化，并交換粒子群之間優(yōu)秀個(gè)體所攜帶的進(jìn)化信息，以打破粒子群內(nèi)的平衡態(tài)以達(dá)到更高的平衡態(tài)，從而跳出局部最優(yōu)。粒子群算法在長(zhǎng)時(shí)間的迭代過(guò)程中，最優(yōu)粒子會(huì)對(duì)粒子群形成一定程度的“統(tǒng)治”，從而使其極易陷入局部最優(yōu)。倘若雙粒子群同時(shí)進(jìn)化并進(jìn)行信息交流，那么隨著粒子群演化環(huán)境的改變，單一粒子群里漫長(zhǎng)進(jìn)化時(shí)間里所建立的“統(tǒng)治”權(quán)威極易被打破。具體的雙粒子群最優(yōu)粒子被交換的示意圖如圖3所示：

雙粒子群算法的進(jìn)化流程如下所述：

Step1：隨機(jī)生成2N個(gè)粒子，分別作為初始粒子群1和初始粒子群2。

Step2：分別計(jì)算兩個(gè)粒子群的各個(gè)粒子的適應(yīng)度函數(shù)值。

Step3：按照適應(yīng)度函數(shù)值分別對(duì)兩個(gè)粒子群的粒子進(jìn)行排序。

Step4：查看是否達(dá)到最大迭代次數(shù)，是則轉(zhuǎn)為Step7，否則轉(zhuǎn)為Step5。

Step5：兩個(gè)粒子群進(jìn)行信息交流，也即交換其最優(yōu)粒子。

Step6：按照粒子群優(yōu)化算法的更新規(guī)則對(duì)粒子群的全部個(gè)體進(jìn)行更新，之后轉(zhuǎn)入Step2。Step7：將迭代計(jì)算的優(yōu)化結(jié)果輸出。

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

3.1 基于測(cè)試函數(shù)的仿真對(duì)比

為考察本文提出的粒子群算法的改進(jìn)策略是否具有優(yōu)越性。本文采用2種不同的測(cè)試函數(shù)對(duì)本文提出的改進(jìn)策略、增加隨機(jī)數(shù)擾動(dòng)的慣性權(quán)重線性遞減（LDW）策略和普通的慣性權(quán)重線性遞減（LDW）策略這3種不同的粒子群算法進(jìn)行對(duì)比測(cè)試。以下是具體的測(cè)試結(jié)果。

（1）De jong函數(shù)，又稱Rosonbrock馬鞍函數(shù)，最優(yōu)解為0.0。具體的De jong函數(shù)的公式如下所述。

具體的De jong函數(shù)的仿真測(cè)試結(jié)果如圖4所示。

圖中，本文提出的改進(jìn)的LDW策略的粒子群算法最優(yōu)，求得的近似最優(yōu)解為： （x1,x2）=（0.9929,0.9994）；最優(yōu)解函數(shù)值F（x1,x2）=0.0181。

（2） Schaffer函數(shù)，最優(yōu)解0.0。

具體的Schaffer函數(shù)的仿真測(cè)試結(jié)果如圖5所示。

圖4 采用De jong函數(shù)的仿真測(cè)試結(jié)果圖

圖5 采用Schaffer函數(shù)的仿真測(cè)試結(jié)果圖

圖中，本文提出的改進(jìn)的LDW策略的粒子群算法最優(yōu)，求得的近似最優(yōu)解為： （x1,x2）=（0.9984,0.9847）；最優(yōu)解函數(shù)值F（x1,x2）=0.0022。

3.2 基于實(shí)際算例的仿真對(duì)比

為驗(yàn)證本文提出的粒子群算法的改進(jìn)策略相較于其他粒子群算法的改進(jìn)策略較優(yōu)。本文采用實(shí)際算例對(duì)本文提出的改進(jìn)的慣性權(quán)重線性遞減（LDW）策略和普通的慣性權(quán)重線性遞減（LDW）策略的粒子群算法進(jìn)行測(cè)試。本文選用的實(shí)際云資源調(diào)度問(wèn)題有4個(gè)計(jì)算節(jié)點(diǎn)和10個(gè)任務(wù)。以下是具體的測(cè)試結(jié)果如表1所示。

具體的云資源調(diào)度問(wèn)題的測(cè)試結(jié)果如圖6所示。

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

圖6 云資源調(diào)度問(wèn)題的仿真測(cè)試結(jié)果圖

圖6中，本文提出的改進(jìn)的LDW策略的粒子群算法較優(yōu)。普通的LDW策略的粒子群算法求解得到各個(gè)任務(wù)的執(zhí)行節(jié)點(diǎn)序列為e=［4 3 2 1 4 1 1 3 42］，估算任務(wù)完成時(shí)間為51.488。本文改進(jìn)的LDW策略的粒子群算法求解得到各個(gè)任務(wù)的執(zhí)行節(jié)點(diǎn)序列為e=［4 3 3 1 3 2 1 1 42］，估算任務(wù)完成時(shí)間為46.9342。

4 結(jié)論

本文基于云資源調(diào)度問(wèn)題的約束目標(biāo)模型，提出了一種基于雙粒子群LDW粒子群改進(jìn)算法。首先，在慣性權(quán)重線性遞減的基礎(chǔ)上，加入了合理范圍內(nèi)的隨機(jī)數(shù)擾動(dòng)，以便于粒子群算法更多的進(jìn)行全局搜索，來(lái)抑制粒子群算法局部收斂；其次，為保護(hù)粒子群多樣性，引入了雙粒子群同時(shí)進(jìn)化并隨時(shí)交流的進(jìn)化機(jī)制，以提升算法的全局優(yōu)化性能。本文通過(guò)2種測(cè)試函數(shù)和云資源調(diào)度問(wèn)題的實(shí)際算例，采用不同的粒子群算法進(jìn)行尋優(yōu)。由尋優(yōu)結(jié)果可知，本文改進(jìn)的算法尋優(yōu)性能更佳，能夠極大程度地提升優(yōu)化求解的精度。