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

0 引言

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

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

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

1 云計算資源調(diào)度問題的數(shù)學模型

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

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

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

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

式中，cost為最短的任務完成時間。

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

2 改進的粒子群算法

2.1 粒子群算法

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

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

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

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

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

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

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

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

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

2.3 粒子群算法的改進策略

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

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

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

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

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

2.4 雙種群粒子群算法

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

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

雙粒子群算法的進化流程如下所述：

Step1：隨機生成2N個粒子，分別作為初始粒子群1和初始粒子群2。

Step2：分別計算兩個粒子群的各個粒子的適應度函數(shù)值。

Step3：按照適應度函數(shù)值分別對兩個粒子群的粒子進行排序。

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

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

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

3 仿真實驗

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

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

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

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

圖中，本文提出的改進的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ù)的仿真測試結(jié)果如圖5所示。

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

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

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

3.2 基于實際算例的仿真對比

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

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

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

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

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

4 結(jié)論

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