陳俊仁 郭一晶

(廈門大學(xué)嘉庚學(xué)院信息科學(xué)與技術(shù)學(xué)院 福建 漳州 363105)

0 引 言

云計(jì)算作為一種新型的計(jì)算模式,已被互聯(lián)網(wǎng)用戶廣泛使用。它是按需為用戶動(dòng)態(tài)整合不同計(jì)算機(jī)虛擬資源以提供數(shù)據(jù)處理的計(jì)算服務(wù)系統(tǒng)。對(duì)用戶而言,其關(guān)注的是云計(jì)算的服務(wù)質(zhì)量。調(diào)查發(fā)現(xiàn),云計(jì)算的服務(wù)質(zhì)量最大程度取決于計(jì)算服務(wù)系統(tǒng)完成用戶所提交的任務(wù)的耗費(fèi)時(shí)間。所以,提高任務(wù)的處理速度是用戶最關(guān)心的問(wèn)題。此問(wèn)題的關(guān)鍵就是尋找一種高效的調(diào)度方案使得用戶提交的任務(wù)處理時(shí)間盡量短,實(shí)質(zhì)為云計(jì)算的任務(wù)調(diào)度,屬于一種組合優(yōu)化問(wèn)題。文獻(xiàn)[1]已證明云計(jì)算任務(wù)調(diào)度問(wèn)題是一個(gè)非確定性多項(xiàng)式(Non-deterministic Polynomial,NP)難題。近年來(lái)一些學(xué)者已采用群體智能算法對(duì)該問(wèn)題進(jìn)行求解。文獻(xiàn)[2]采用遺傳算法并結(jié)合啟發(fā)式規(guī)則求解多優(yōu)先隊(duì)列分布式計(jì)算系統(tǒng)的任務(wù)調(diào)度問(wèn)題,實(shí)驗(yàn)證明該方法可以有效獲得可行解,但算法過(guò)于復(fù)雜,實(shí)現(xiàn)難度較大。文獻(xiàn)[3]針對(duì)基本蟻群算法自身存在的缺陷,設(shè)計(jì)一種改進(jìn)蟻群算法,該算法可以減少云計(jì)算中任務(wù)執(zhí)行的總完成時(shí)間,但算法的迭代過(guò)程過(guò)于繁雜,其空間復(fù)雜度增加。文獻(xiàn)[4]提出了一種改進(jìn)螢火蟲(chóng)算法的云計(jì)算作業(yè)調(diào)度機(jī)制,實(shí)驗(yàn)證明該方法可以有效減少作業(yè)的執(zhí)行時(shí)間,但其目標(biāo)僅僅針對(duì)作業(yè)的完成時(shí)間,并未考慮資源的使用情況。然而,隨著云計(jì)算的需求量日益增多,調(diào)度方案不僅要考慮如何快速完成多用戶提交的云任務(wù),而且還應(yīng)該關(guān)注計(jì)算資源的利用率。文獻(xiàn)[5]設(shè)計(jì)一種改進(jìn)的負(fù)載均衡蜜蜂算法,仿真實(shí)驗(yàn)說(shuō)明該算法可以有效減少任務(wù)的執(zhí)行時(shí)間并提升資源的負(fù)載均衡,但蜜蜂算法自身存在進(jìn)化后期收斂速度慢、共享機(jī)制低效等缺點(diǎn)。文獻(xiàn)[6]結(jié)合資源的負(fù)載均衡和任務(wù)的執(zhí)行時(shí)間,設(shè)計(jì)出一種改進(jìn)的禁忌搜索啟發(fā)式調(diào)度策略,但算法的整體啟發(fā)規(guī)則較為復(fù)雜,操作相對(duì)煩瑣。文獻(xiàn)[7]提出了一種以任務(wù)總完成時(shí)間、任務(wù)平均完成時(shí)間和資源負(fù)載均衡為目標(biāo)的遺傳算法,實(shí)驗(yàn)結(jié)果證明算法有效,但因?yàn)榫幋a問(wèn)題,算法進(jìn)化過(guò)程的操作過(guò)于繁雜,且可能陷入局部最優(yōu)。與此同時(shí),粒子群算法(PSO)在多個(gè)領(lǐng)域已被證明具有記憶能力、參數(shù)少、收斂速度快、實(shí)現(xiàn)簡(jiǎn)單等特點(diǎn)[8-10],并且在云計(jì)算任務(wù)調(diào)度問(wèn)題上也得到了應(yīng)用。文獻(xiàn)[11]設(shè)計(jì)了一種針對(duì)云任務(wù)調(diào)度問(wèn)題的小生境粒子群算法,實(shí)驗(yàn)結(jié)果表明該算法可縮短任務(wù)執(zhí)行時(shí)間并使資源負(fù)載均衡。

基于以上考慮,本文根據(jù)云計(jì)算任務(wù)資源分配問(wèn)題的特點(diǎn),對(duì)基本的交換粒子群算法進(jìn)行改進(jìn)。引入進(jìn)制編碼,在其基礎(chǔ)上重新定義運(yùn)算法則,加入自適應(yīng)概率調(diào)整,改進(jìn)其適應(yīng)度函數(shù),綜合考慮任務(wù)完成時(shí)間和資源負(fù)載均衡等指標(biāo),提出了一種新的云計(jì)算任務(wù)調(diào)度算法。

1 云計(jì)算任務(wù)調(diào)度描述

1.1 問(wèn)題定義

現(xiàn)今,主流的云計(jì)算平臺(tái)大部分采用Map/Reduce的工作方式。該方式適用于處理大規(guī)模的數(shù)據(jù),可將用戶請(qǐng)求的大任務(wù)拆分成若干個(gè)子任務(wù),再根據(jù)指定的策略去調(diào)度合適的資源來(lái)處理計(jì)算這些子任務(wù)。換言之,云計(jì)算任務(wù)調(diào)度問(wèn)題可理解為調(diào)度中心調(diào)度p個(gè)虛擬資源來(lái)處理計(jì)算q個(gè)子任務(wù),即建立虛擬資源與任務(wù)之間的映射,使其完成后達(dá)到任務(wù)總處理時(shí)間最少,資源利用率最高。

為簡(jiǎn)化調(diào)度處理流程,現(xiàn)對(duì)云計(jì)算平臺(tái)中用戶提交的任務(wù)及其提供的資源作如下假設(shè):

1) 拆分后的子任務(wù)之間無(wú)前后執(zhí)行依賴關(guān)系,并且各子任務(wù)是相互獨(dú)立;

2) 一個(gè)子任務(wù)只由一個(gè)虛擬資源連續(xù)處理,不考慮中斷;

3) 拆分后的子任務(wù)數(shù)量遠(yuǎn)遠(yuǎn)多于平臺(tái)所提供的資源數(shù)量,并且資源處理任務(wù)的成本可知。

云計(jì)算任務(wù)調(diào)度的過(guò)程如圖1所示。

圖1 云計(jì)算任務(wù)調(diào)度過(guò)程

1.2 任務(wù)調(diào)度模型

云計(jì)算任務(wù)調(diào)度是由子任務(wù)集合、虛擬資源集合以及子任務(wù)與虛擬資源之間分配關(guān)系的集合構(gòu)成?？杀硎緸?

D=(ST,VR,MAP)

式中:D表示一個(gè)云計(jì)算任務(wù)調(diào)度方案,ST為調(diào)度方案D中子任務(wù)的集合,VR是調(diào)度方案D中虛擬資源的集合,MAP是調(diào)度方案D中子任務(wù)與虛擬資源之間分配關(guān)系的集合。

子任務(wù)集合ST表示為ST={st1,st2,…,stq},其中第i個(gè)任務(wù)表示為sti(1≤i≤q,i∈Z)。虛擬資源集合VR表示為VR={vr1,vr2,…,vrp},vrj(1≤j≤p,j∈Z)表示第j個(gè)虛擬資源。子任務(wù)與虛擬資源之間分配關(guān)系的集合MAP表示為MAP={…,, …},其中,(1≤i≤q,1≤j≤p,i∈Z,j∈Z)表示第i個(gè)子任務(wù)分配到第j個(gè)虛擬資源處理。

另外,任務(wù)的衡量指標(biāo)一般采用MI(百萬(wàn)條指令數(shù)),本文令Numberi表示子任務(wù)sti的待執(zhí)行機(jī)器指令條數(shù),即子任務(wù)的大小。資源的指令執(zhí)行速度采用MIPS(每秒執(zhí)行的百萬(wàn)條指令數(shù))衡量,Speedj代表虛擬資源vrj的計(jì)算性能。ti,j代表子任務(wù)sti在虛擬資源vrj上的執(zhí)行時(shí)間。

ti,j=Numberi/Speedj

1≤i≤q,1≤j≤p,i∈Z,j∈Z

(1)

再者,p個(gè)虛擬資源處理計(jì)算q個(gè)子任務(wù)的期望計(jì)算時(shí)間ETC(Expeeted Time to Compute)[12-13]可用矩陣T表示,該矩陣是一個(gè)q×p的矩陣,如下:

虛擬資源vrj的執(zhí)行時(shí)間ExeTime為該資源處理計(jì)算其分配的所有任務(wù)的執(zhí)行時(shí)間之和。

(2)

式中:sti→vrj,sti∈ST表示虛擬資源vrj處理的所有任務(wù),k代表在該資源上執(zhí)行的任務(wù)總數(shù)。根據(jù)上文的假設(shè),以及各虛擬資源并行計(jì)算的特點(diǎn),可得任務(wù)調(diào)度方案D的完成時(shí)間為最晚完成任務(wù)的虛擬機(jī)的執(zhí)行時(shí)間[13],表示方式如下:

Makespan=max{ExeTime(j)|j∈Z,1≤j≤p}

(3)

云計(jì)算任務(wù)調(diào)度追求的目標(biāo)應(yīng)是尋找一種使總完成時(shí)間Makespan最小的調(diào)度方案。

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

2.1 離散粒子群算法

粒子群算法(PSO)是由Eberhart和Kennedy在1995年模擬鳥(niǎo)類群體覓食設(shè)計(jì)出的一種自適應(yīng)全局優(yōu)化搜索算法?；玖Ｗ尤核惴ㄝ^適合于求解連續(xù)空間優(yōu)化問(wèn)題,但對(duì)于離散空間優(yōu)化問(wèn)題,該算法并不適用。2000年Clerc[14]提出了一種以交換離散值向量為基礎(chǔ)的粒子群算法,用于求解離散空間優(yōu)化問(wèn)題,已被證明成功求解旅行商問(wèn)題(TSP)。對(duì)于本文研究的云計(jì)算任務(wù)調(diào)度問(wèn)題來(lái)說(shuō),其結(jié)果亦分散在解空間,本質(zhì)上也屬于離散空間組合優(yōu)化問(wèn)題,性質(zhì)與TSP問(wèn)題相似,但又有區(qū)別。TSP問(wèn)題的解為所有城市訪問(wèn)順序的排列組合,而云計(jì)算任務(wù)調(diào)度問(wèn)題的解則為子任務(wù)與虛擬資源的映射組合。另外,云計(jì)算任務(wù)調(diào)度求解過(guò)程需要考慮資源的負(fù)載均衡指標(biāo)。因此,本文將結(jié)合所研究的調(diào)度問(wèn)題特點(diǎn)在基本的交換粒子群算法上做了相應(yīng)的改進(jìn)。

2.2 粒子編碼

在基本的交換粒子群算法中,粒子是采用整數(shù)編碼方式,用不同的整數(shù)代表不同的城市,并且每個(gè)城市只被訪問(wèn)一次,即訪問(wèn)次序與城市是一一對(duì)應(yīng)。然而,在本文研究的問(wèn)題中,同一個(gè)虛擬資源可以執(zhí)行多個(gè)不同的子任務(wù),為一對(duì)多的關(guān)系。由此可見(jiàn),整數(shù)編碼并不適合本文的問(wèn)題,因此本文結(jié)合云計(jì)算任務(wù)調(diào)度的特點(diǎn),采用“進(jìn)制編碼”對(duì)粒子的編碼方式進(jìn)行改進(jìn)。

對(duì)于任何包含q個(gè)待處理子任務(wù)的云環(huán)境來(lái)說(shuō),本文按1～q的順序?qū)@q個(gè)子任務(wù)進(jìn)行編號(hào)?，F(xiàn)假設(shè)數(shù)據(jù)中心代理有p個(gè)虛擬資源,且有q個(gè)子任務(wù)待計(jì)算處理,則本文按表1所示的方式進(jìn)行p進(jìn)制編碼。

表1 粒子的進(jìn)制編碼

其中,虛擬資源的編號(hào)為1至p的整數(shù)。一組1至p的組合序列代表該問(wèn)題解空間里的一個(gè)解,即表示一種云計(jì)算任務(wù)調(diào)度方案。

2.3 基于交換的運(yùn)算法則

傳統(tǒng)粒子群算法中的粒子速度和位移更新公式并不適合求解離散空間組合優(yōu)化問(wèn)題,故本文采用基于交換的運(yùn)算。然而,運(yùn)用原始的交換操作求解本文的問(wèn)題會(huì)存在一定缺陷。因?yàn)?不同編號(hào)的子任務(wù)可能被分配到同一個(gè)虛擬資源上執(zhí)行,此時(shí)編碼序列中兩個(gè)任務(wù)對(duì)應(yīng)位置上的進(jìn)制數(shù)相同,所以互換位置后編碼序列未發(fā)生任何改變,即粒子保持不動(dòng),從而降低算法的收斂速度。為解決此問(wèn)題,本文提出的改進(jìn)算法將重新定義交換子和交換序,并用其來(lái)表示粒子的飛行速度。其中,交換子表示在一種調(diào)度方案中互換兩個(gè)子任務(wù)的處理虛擬資源,且要求虛擬資源不為同一個(gè),即交換子對(duì)應(yīng)的兩個(gè)虛擬資源編號(hào)不能相等;交換序則由一個(gè)或多個(gè)交換子組成。為了實(shí)現(xiàn)離散值向量間的交換且同時(shí)保留粒子群算法思想,本文采用如式(4)所示的粒子速度更新公式,式(5)為粒子的位置更新公式。

(Pi-Xi)⊕β×(Gb-Xi)

(4)

(5)

2.4 適應(yīng)度函數(shù)

在粒子群算法中,適應(yīng)度函數(shù)是衡量粒子離目標(biāo)遠(yuǎn)近的標(biāo)準(zhǔn),一般稱之為粒子的適應(yīng)值。種群中第i個(gè)粒子的適應(yīng)值記為f(Xi)。

由于實(shí)際的云計(jì)算環(huán)境中,不同虛擬資源的計(jì)算能力存在一定差異,經(jīng)常出現(xiàn)算力高的虛擬資源負(fù)載過(guò)高,其任務(wù)隊(duì)列中等待任務(wù)數(shù)量過(guò)多,而其他虛擬資源則處于空閑狀態(tài),因此造成資源使用率不高且負(fù)載不均衡,甚至任務(wù)的總完成時(shí)間較長(zhǎng)。為了避免該現(xiàn)象發(fā)生,本文對(duì)適應(yīng)度函數(shù)做了相應(yīng)改進(jìn),在評(píng)價(jià)粒子適應(yīng)值時(shí)引進(jìn)負(fù)載均衡指標(biāo),即給虛擬資源分配任務(wù)時(shí)既要追求完成時(shí)間短,同時(shí)要考慮各虛擬資源的負(fù)載情況。

虛擬資源vrj的負(fù)載Loadj此處定義為預(yù)分配到其上所有子任務(wù)的預(yù)期執(zhí)行時(shí)間,Loadj越大,表明虛擬資源vrj的負(fù)載越高,結(jié)合式(2)可得:

Loadj=ExeTime(j)

(6)

定義所有虛擬資源的預(yù)期執(zhí)行時(shí)間均值為L(zhǎng)oadavg,公式如下所示:

(7)

式中:p為虛擬資源的個(gè)數(shù)。

對(duì)任意云計(jì)算任務(wù)調(diào)度方案的負(fù)載均衡評(píng)價(jià)指標(biāo)LB定義為所有虛擬資源的預(yù)期執(zhí)行時(shí)間的標(biāo)準(zhǔn)差,公式如下:

(8)

其中,調(diào)度方案的負(fù)載均衡評(píng)價(jià)指標(biāo)LB越大,表明該調(diào)度方案的負(fù)載均衡情況越差。

結(jié)合式(3)和式(8),本文定義的適應(yīng)度函數(shù)為:

f(X)=ω1Makespan+ω2BL

(9)

式中:ω1和ω2為權(quán)重值,ω1+ω2=1。適應(yīng)度函數(shù)f(X)越小,說(shuō)明粒子X(jué)對(duì)應(yīng)的調(diào)度方案越好。

4.1.1 餐飲服務(wù)單位的食品安全管理制度齊全，確保食品原料新鮮、加工過(guò)程生熟分開(kāi)，食品燒熟煮透，其加工時(shí)食品中心溫度應(yīng)不低于70℃。主要食品安全管理制度應(yīng)包括但不僅限于以下各項(xiàng)：食品安全崗位責(zé)任制；從業(yè)人員健康管理制度；從業(yè)人員培訓(xùn)管理制度；加工經(jīng)營(yíng)場(chǎng)所清潔制度；設(shè)施設(shè)備清潔、消毒和維修保養(yǎng)制度；食品采購(gòu)索證索票制度；食品進(jìn)貨查驗(yàn)和臺(tái)賬記錄制度；餐廚廢棄物處置管理制度；食品安全突發(fā)事件應(yīng)急處置方案；投訴受理制度等相關(guān)制度。

2.5 自適應(yīng)概率調(diào)整

云計(jì)算任務(wù)調(diào)度的求解比TSP問(wèn)題復(fù)雜很多。首先,要求各個(gè)虛擬資源保持負(fù)載均衡;其次,子任務(wù)在不同算力的虛擬資源中執(zhí)行時(shí)間差別較大,執(zhí)行子任務(wù)的虛擬資源更換后,可能引起任務(wù)的總完成時(shí)間發(fā)生變化,導(dǎo)致尋找負(fù)載均衡且時(shí)間短的調(diào)度方案難度加大。與此同時(shí),基本交換粒子群算法容易出現(xiàn)粒子聚集現(xiàn)象,導(dǎo)致算法在進(jìn)化后期陷入局部最優(yōu)的可能性增加。為此本文引進(jìn)一種自適應(yīng)的調(diào)整概率對(duì)粒子群算法做了改進(jìn)。算法根據(jù)此概率值決定是否對(duì)粒子當(dāng)前所處的位置序列做調(diào)整操作。調(diào)整過(guò)程如下:在粒子的位置序列中隨機(jī)挑選兩個(gè)不在同一臺(tái)虛擬機(jī)上計(jì)算的子任務(wù),然后互換這兩個(gè)子任務(wù)的處理虛擬機(jī)。若互換后該粒子的適應(yīng)值低于當(dāng)前種群最優(yōu)值,則認(rèn)為此次調(diào)整操作有效并把該位置標(biāo)記成種群當(dāng)前最優(yōu)位置。此外,該概率值是根據(jù)算法迭代次數(shù)、前一代調(diào)整概率以及前一代調(diào)整的成功次數(shù)動(dòng)態(tài)變化,公式如下:

λ=b·[1-nsuc/(apt·m)]

(10)

apt+1=r^(1-t/G)λ

(11)

式中:ap表示調(diào)整概率;m表示種群大小;nsuc表示前一代調(diào)整的成功次數(shù);b是常數(shù),本文取值為3;λ為調(diào)整權(quán)重;t為當(dāng)前的迭代數(shù);G為總迭代次數(shù)(進(jìn)化代數(shù));r∈[0.2,0.5]。從式(10)和式(11)可以看出,迭代初期ap值較小以保持算法的收斂速度;迭代后期ap值增大,交換操作的次數(shù)將逐步增多,以此保持粒子的多樣性,從而降低陷入局部最優(yōu)的概率。

2.6 算法流程

本文提出的基于交換的改進(jìn)粒子群算法,主要包括初始化種群、粒子移動(dòng)、選擇和自適應(yīng)調(diào)整四個(gè)過(guò)程。具體操作步驟如下。

Step1初始化:輸入算法參數(shù),并在問(wèn)題解空間里隨機(jī)產(chǎn)生m個(gè)粒子的位置序列和速度交換序。

Step2評(píng)價(jià)粒子:通過(guò)適應(yīng)度函數(shù)評(píng)價(jià)每一個(gè)粒子的適應(yīng)值。

Step3更新極值:1) 比較粒子的適應(yīng)值和個(gè)體本身歷史最優(yōu)值,若前者優(yōu)于后者,則將個(gè)體自身歷史最優(yōu)位置替換成粒子當(dāng)前的位置序列;2) 比較粒子的適應(yīng)值和種群當(dāng)前最優(yōu)值,如果前者好于后者,則將群體最優(yōu)位置替換成粒子當(dāng)前的位置序列。

Step5調(diào)整:根據(jù)調(diào)整概率調(diào)整粒子的位置序列,如果新的適應(yīng)值比種群當(dāng)前最優(yōu)值更優(yōu),則把種群最優(yōu)位置設(shè)為粒子調(diào)整后的位置序列。

Step6終止:重復(fù)Step2～Step5,直至滿足算法終止條件。

Step7輸出:輸出種群最優(yōu)位置對(duì)應(yīng)的調(diào)度方案。

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

為了驗(yàn)證基于交換的改進(jìn)粒子群算法(Improved Discrete PSO,IDPSO)對(duì)云計(jì)算任務(wù)調(diào)度的有效性和可行性,本文使用開(kāi)源的CloudSim云仿真平臺(tái)進(jìn)行實(shí)驗(yàn),并在同等實(shí)驗(yàn)條件下與Min-Min調(diào)度算法、基本的離散粒子群算法(PSO)和基于交換運(yùn)算法則的粒子群算法(Discrete PSO,DPSO)進(jìn)行對(duì)比實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)環(huán)境

仿真實(shí)驗(yàn)環(huán)境具體信息如下:處理器為Inter(R) Core(TM) i5-6267U CPU @ 2.90 GHz,內(nèi)存為8 GB,操作系統(tǒng)為Windows 10,軟件平臺(tái)為Eclipse、CloudSim,編程語(yǔ)言為Java。

CloudSim是一款由Java編寫的基于事件的仿真框架,可在一臺(tái)主機(jī)上模擬大規(guī)模的集群及任務(wù)調(diào)度,只需在框架中實(shí)現(xiàn)其調(diào)度算法并重寫相關(guān)類,即可完成仿真工作。另外,IDPSO本身具有粒子群算法參數(shù)少、迭代流程簡(jiǎn)便的特點(diǎn),并且本文采用的進(jìn)制編碼、交換子、交換序及交換操作均可使用基本類型數(shù)組存儲(chǔ)與運(yùn)算,總體上實(shí)現(xiàn)相對(duì)簡(jiǎn)便。

3.2 參數(shù)設(shè)置

在云仿真平臺(tái)中設(shè)置虛擬資源的個(gè)數(shù)為10,其計(jì)算能力參數(shù)范圍為1 024～2 048。子任務(wù)數(shù)量范圍為[100,400],子任務(wù)的待執(zhí)行機(jī)器指令條數(shù)范圍為1 000～10 000。

上述算法中設(shè)置的主要參數(shù)有,種群大小m為50,慣性權(quán)重ω為0.85,學(xué)習(xí)因子c1和c2均為2,ω1和ω2分別為0.6和0.4。

3.3 結(jié)果分析

實(shí)驗(yàn)分為4種不同子任務(wù)數(shù),任務(wù)數(shù)分別為100、200、300和400,與之對(duì)應(yīng)的迭代數(shù)分別為500、700、1 000和1 500。每組各做50次獨(dú)立重復(fù)實(shí)驗(yàn),取其平均值。實(shí)驗(yàn)結(jié)果如圖2和圖3所示。

圖2 不同任務(wù)數(shù)的適應(yīng)度函數(shù)值對(duì)比

圖3 不同任務(wù)數(shù)在不同迭代次數(shù)下取得的適應(yīng)值對(duì)比

圖2為Min-Min算法、PSO、DPSO和IDPSO在相同仿真環(huán)境和參數(shù)下的適應(yīng)度函數(shù)值對(duì)比圖。由圖可知,在任務(wù)數(shù)為100和200的情況下,IDPSO取得的結(jié)果最好,但其優(yōu)勢(shì)仍不夠明顯。在任務(wù)數(shù)為300和400時(shí),IDPSO體現(xiàn)出更好的性能,其得到的適應(yīng)度函數(shù)值比DPSO低更多,且都好于Min-Min算法和PSO。特別在400個(gè)任務(wù)時(shí),其優(yōu)勢(shì)更加突出。因此可得,IDPSO總體上取得的結(jié)果都優(yōu)于其他算法,隨著任務(wù)數(shù)增加,其效果越明顯,即更適合任務(wù)數(shù)較多的場(chǎng)景。換句話說(shuō),IDPSO在任務(wù)數(shù)較多時(shí)更能找到任務(wù)總完成時(shí)間短、資源負(fù)載均衡的調(diào)度方案。

圖3中的實(shí)驗(yàn)是針對(duì)基于交換運(yùn)算法則的粒子群算法改進(jìn)前后的收斂對(duì)比?？梢钥闯?不同任務(wù)數(shù)的求解過(guò)程中,IDPSO的收斂速度均比DPSO快,在任務(wù)數(shù)較少時(shí)效果較為明顯。由此可見(jiàn),本文采用的進(jìn)制編碼和重新定義的粒子更新運(yùn)算法則具有一定的優(yōu)勢(shì)。同時(shí)可得,算法在迭代初期自適應(yīng)調(diào)整概率較小時(shí),不會(huì)導(dǎo)致收斂速度變慢。還有,從算法取得的結(jié)果來(lái)看,DPSO尋優(yōu)過(guò)程較易陷入局部最優(yōu),加入自適應(yīng)概率調(diào)整后,IDPSO收斂速度在任務(wù)數(shù)多的情況下與DPSO相當(dāng),但其得到的適應(yīng)度函數(shù)更優(yōu),可見(jiàn)自適應(yīng)概率調(diào)整可有效促使IDPSO跳出局部最優(yōu)。另外,從圖3亦可發(fā)現(xiàn)IDPSO在不同任務(wù)數(shù)下的收斂適應(yīng)值均更小,可見(jiàn)具有魯棒性。由此可得,IDPSO在云計(jì)算任務(wù)調(diào)度中表現(xiàn)出更快的收斂速度,以及更強(qiáng)的全局搜索能力。

4 結(jié) 語(yǔ)

本文在交換的粒子群算法基礎(chǔ)上,通過(guò)重新定義交換子及粒子的運(yùn)算法則,引入自適應(yīng)概率調(diào)整,并且以任務(wù)調(diào)度的總完成時(shí)間和資源的負(fù)載情況為適應(yīng)度函數(shù)來(lái)衡量調(diào)度方案的優(yōu)劣,以此進(jìn)行云計(jì)算任務(wù)調(diào)度方案優(yōu)化。仿真實(shí)驗(yàn)采用開(kāi)源的CloudSim平臺(tái),并在此平臺(tái)上進(jìn)行實(shí)例分析。實(shí)驗(yàn)結(jié)果表明本文提出的算法能夠有效地找出云計(jì)算任務(wù)調(diào)度結(jié)果,以完成較好的任務(wù)調(diào)度。通過(guò)多組實(shí)驗(yàn)對(duì)比,可以得出改進(jìn)后的算法具有收斂速度快和魯棒性強(qiáng)等特點(diǎn)。然而,本文提出的算法并未對(duì)速度更新公式中的幾個(gè)參數(shù)做動(dòng)態(tài)調(diào)整,后續(xù)的工作中可以對(duì)這些參數(shù)進(jìn)行自適應(yīng)改進(jìn),以期更好地提升算法性能,尋找到更優(yōu)的調(diào)度方案。另外,在實(shí)際云計(jì)算應(yīng)用中,不僅要考慮任務(wù)的總完成時(shí)間,還應(yīng)綜合考慮計(jì)算成本、帶寬、能耗等因素,這將是今后研究的重點(diǎn)。