模糊云資源調(diào)度問(wèn)題的RIOPSO 算法

李成嚴(yán)，宋 月，馬金濤

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

云資源調(diào)度是云計(jì)算中的核心內(nèi)容，文獻(xiàn)[1]為了使完工時(shí)間最短，建立了相應(yīng)的云計(jì)算調(diào)度模型。文獻(xiàn)[2]在調(diào)度過(guò)程中，保證服務(wù)質(zhì)量的前提下，使云服務(wù)提供商獲取最大的利益。文獻(xiàn)[3]為了使能源消耗最小，建立了實(shí)時(shí)調(diào)度系統(tǒng)。以上這些研究中，使用的都是確定的執(zhí)行時(shí)間。但是由于任務(wù)執(zhí)行的不可預(yù)見(jiàn)性，在任務(wù)執(zhí)行完成之前，執(zhí)行時(shí)間只能是一個(gè)估計(jì)的值，這就導(dǎo)致任務(wù)的執(zhí)行時(shí)間具有不確定性，因此本文在建立云資源調(diào)度模型時(shí)，對(duì)任務(wù)執(zhí)行時(shí)間具有不確定性的情況進(jìn)行了考慮。在解決實(shí)際問(wèn)題時(shí)，數(shù)學(xué)模型可以分為三類，分別為確定性的數(shù)學(xué)模型、隨機(jī)性的數(shù)學(xué)模型和模糊性的數(shù)學(xué)模型，對(duì)于不確定的需要估計(jì)的問(wèn)題，就需要模糊數(shù)學(xué)模型進(jìn)行解決。文獻(xiàn)[4]使用模糊遺傳系統(tǒng)對(duì)疾病的診斷時(shí)間進(jìn)行了時(shí)間復(fù)雜度的分析，文獻(xiàn)[5]研究了云環(huán)境下基于模糊神經(jīng)網(wǎng)絡(luò)算法的作業(yè)調(diào)度。在本文中，使用三角模糊數(shù)對(duì)不確定的任務(wù)執(zhí)行時(shí)間進(jìn)行表示[6]，建立了模糊的云資源調(diào)度模型。

云資源調(diào)度問(wèn)題是一個(gè)NP 完全問(wèn)題[7]，沒(méi)有有效的多項(xiàng)式算法。為解決云資源調(diào)度問(wèn)題，國(guó)內(nèi)外學(xué)者常常采用智能優(yōu)化算法來(lái)實(shí)現(xiàn)上述目標(biāo)。智能優(yōu)化算法包括遺傳算法（genetic algorithm，GA）[8]，粒子群算法（particle swarm optimization，PSO）[9]和蟻群算法（ant colony optimization，ACO）[10]等。相比于GA 算法，PSO 算法在處理和實(shí)現(xiàn)上不存在重疊和突變現(xiàn)象，因此PSO 算法在求解云資源調(diào)度問(wèn)題時(shí)比GA 算法速度快。相比于ACO 算法，PSO 算法更容易獲取初始解，可以更有效地對(duì)云資源調(diào)度問(wèn)題進(jìn)行優(yōu)化。綜合考慮，由于PSO 算法在分布式環(huán)境中計(jì)算速度較快，處理時(shí)間較短，本文使用了一種基于粒子群的優(yōu)化算法對(duì)云資源調(diào)度問(wèn)題進(jìn)行求解。

在PSO 算法尋求最優(yōu)解的過(guò)程中，存在收斂精度不高，容易陷入局部最優(yōu)解，容易產(chǎn)生早熟收斂的問(wèn)題，針對(duì)以上缺點(diǎn)和不足，本文提出了一種混合粒子群優(yōu)化算法（re-randomization inertia weight orthogonal initialization particle swarm optimization，RIOPSO）。采用重新隨機(jī)化[11]的方法使粒子群能夠充分搜索解空間，避免粒子陷入早熟。采用實(shí)時(shí)更新慣性權(quán)重[12]的方法，控制粒子在搜索過(guò)程中的速度，防止陷入局部最優(yōu)。本文還采用正交矩陣對(duì)粒子種群進(jìn)行初始化[13]，使粒子群獲得有序的初始解，在粒子初始探索解空間時(shí)能夠更有效率。本文同時(shí)使用以上三種優(yōu)化方法，使PSO 算法在搜索過(guò)程中，得到的解的質(zhì)量更高，同時(shí)增強(qiáng)粒子的搜索能力，從而得到最優(yōu)解。

1 相關(guān)工作

1.1 多目標(biāo)問(wèn)題

多目標(biāo)問(wèn)題（multi-objective problem，MOP）往往由于多個(gè)目標(biāo)之間相互沖突，而無(wú)法獲得使每一個(gè)目標(biāo)都達(dá)到最優(yōu)狀態(tài)的最優(yōu)解[14]。針對(duì)這一問(wèn)題，將求解算法分為以下三種方式：

（1）基于帕累托支配的多目標(biāo)進(jìn)化算法[15]。由于目標(biāo)函數(shù)的增多，最優(yōu)解解集有時(shí)過(guò)于龐大，導(dǎo)致以該方法求解多目標(biāo)問(wèn)題時(shí)，容易產(chǎn)生消息溢出的問(wèn)題[16]。

（2）基于性能指標(biāo)的多目標(biāo)進(jìn)化算法[17]。在使用性能指標(biāo)作為算法的進(jìn)化的參考信息時(shí)，對(duì)于性能指標(biāo)的計(jì)算過(guò)于復(fù)雜，導(dǎo)致運(yùn)行時(shí)間較長(zhǎng)[18]。

（3）基于分解的多目標(biāo)進(jìn)化算法[19]。將對(duì)多目標(biāo)問(wèn)題求解轉(zhuǎn)化為對(duì)多個(gè)單目標(biāo)協(xié)同求解，引入分解的思想，將復(fù)雜的多目標(biāo)問(wèn)題簡(jiǎn)單化。該算法求解效率高，解集性能較優(yōu)。Zhang 等[20]提出的多目標(biāo)進(jìn)化算法（multi-objective evolutionary algorithm based on decomposition，MOEA/D）效果尤為顯著。

相比于其他兩種算法，基于分解的多目標(biāo)進(jìn)化算法，對(duì)于處理組合優(yōu)化問(wèn)題，有著較強(qiáng)的搜索能力。云資源調(diào)度的優(yōu)化目標(biāo)包括使總完成時(shí)間最短，使資源的消耗最少，滿足QoS 等，本文的主要研究目標(biāo)是在有限資源下，使云資源調(diào)度能夠在時(shí)間-成本約束下完成調(diào)度目標(biāo)。因此本文利用MOEA/D算法的分解思想，使用妥協(xié)模型，對(duì)時(shí)間和成本約束下的目標(biāo)評(píng)價(jià)函數(shù)進(jìn)行權(quán)重分解，根據(jù)權(quán)重占比，同步優(yōu)化時(shí)間和成本的目標(biāo)函數(shù)。

1.2 算法與性能指標(biāo)

為了驗(yàn)證本文提出的RIOPSO算法在求解多目標(biāo)云資源調(diào)度的問(wèn)題時(shí)，收斂性和多樣性都能夠得到保證，本文將使用NSGA-Ⅰ算法[21]、NSGA-Ⅱ算法[22]、NSGA-Ⅲ算法[23]和MOEA/D 算法[24]四種主流算法與本文提出的RIOPSO 算法進(jìn)行對(duì)比實(shí)驗(yàn)。

隨著多目標(biāo)優(yōu)化算法的提出，如何評(píng)價(jià)算法的優(yōu)劣也成為一個(gè)重要的研究方向，在多目標(biāo)優(yōu)化算法解決多目標(biāo)問(wèn)題時(shí)，可以使用性能指標(biāo)對(duì)算法性能進(jìn)行量化比較。常用的性能指標(biāo)可以分為：準(zhǔn)確性度量指標(biāo)、多樣性度量指標(biāo)和綜合度量指標(biāo)三類。

在上述算法求解多目標(biāo)云資源調(diào)度問(wèn)題時(shí)，使用兩個(gè)綜合度量指標(biāo)，反向世代距離（inverted generational distance，IGD）[25]和超體積（hypervolume，HV）[26]指標(biāo)，準(zhǔn)確性度量指標(biāo)覆蓋率（coverage-metric，CMetric）[27]指標(biāo)，對(duì)算法的性能進(jìn)行量化，并且通過(guò)量化后的性能對(duì)上述算法進(jìn)行對(duì)比評(píng)價(jià)。

本文使用模糊數(shù)學(xué)模型，對(duì)不確定執(zhí)行時(shí)間的多目標(biāo)云資源調(diào)度問(wèn)題進(jìn)行求解。并且對(duì)如何能夠高效地找到最佳調(diào)度方案提出了優(yōu)化算法。

2 模糊云資源調(diào)度問(wèn)題

2.1 云資源調(diào)度模型

在云資源調(diào)度中，任務(wù)需要根據(jù)可行性算法在虛擬機(jī)上執(zhí)行，并且每個(gè)任務(wù)只能在一個(gè)虛擬機(jī)上執(zhí)行，但是虛擬機(jī)可以根據(jù)需要執(zhí)行多個(gè)任務(wù)?，F(xiàn)在有m個(gè)任務(wù)TASK={Task1,Task2,…,Taskm}，有n個(gè)虛擬機(jī)VM={Vm1,Vm2,…,Vmn}，虛擬機(jī)個(gè)數(shù)n遠(yuǎn)小于任務(wù)個(gè)數(shù)m。

由于云資源調(diào)度中虛擬機(jī)和任務(wù)之間存在一對(duì)多的關(guān)系，可以將它們之間的映射關(guān)系表現(xiàn)為圖1 的形式。從圖中可以看出，每個(gè)任務(wù)只能在一個(gè)虛擬機(jī)上執(zhí)行，每個(gè)虛擬機(jī)可以執(zhí)行多個(gè)任務(wù)。如圖1 所示，代表一種調(diào)度方案Rk。

圖1是在云資源調(diào)度模型中用到的一些基本定義。

定義1timeij表示任務(wù)i在虛擬機(jī)j上執(zhí)行的時(shí)間，其計(jì)算公式如下：

其中，taskSizei表示第i個(gè)任務(wù)的大小，vmSpeedj表示第j個(gè)虛擬機(jī)的處理速度，均在給定的范圍內(nèi)隨機(jī)生成。

定義2vmTimej表示在虛擬機(jī)j上的任務(wù)執(zhí)行時(shí)間，其計(jì)算公式如下：

Fig.1 Task-VM mapping relationship圖1 任務(wù)-虛擬機(jī)的映射關(guān)系

其中，Xij表示任務(wù)i是否在虛擬機(jī)j上執(zhí)行，如果任務(wù)i在虛擬機(jī)j上執(zhí)行，那么Xij=1，否則Xij=0。

定義3vmCostj表示在虛擬機(jī)j上的任務(wù)執(zhí)行成本，其計(jì)算公式如下：

其中，costj表示單位時(shí)間內(nèi)虛擬機(jī)j的執(zhí)行成本，虛擬機(jī)執(zhí)行成本由虛擬機(jī)的處理速度經(jīng)過(guò)規(guī)則運(yùn)算得到。

定義4Time(Rk)表示調(diào)度方案Rk的總的執(zhí)行時(shí)間，由于任務(wù)的并發(fā)性，調(diào)度方案的總的執(zhí)行時(shí)間就是執(zhí)行時(shí)間最長(zhǎng)的虛擬機(jī)的執(zhí)行時(shí)間，其計(jì)算公式如下：

定義5Cost(Rk)表示調(diào)度方案Rk的總的執(zhí)行成本，調(diào)度方案總的執(zhí)行成本就是所有任務(wù)執(zhí)行消耗的成本的和，其計(jì)算公式如下：

在求解最優(yōu)調(diào)度方案時(shí)只考慮時(shí)間因素，那么時(shí)間約束函數(shù)為：

其中，Timemin、Timemax代表任務(wù)在虛擬機(jī)上執(zhí)行的最短時(shí)間和最長(zhǎng)時(shí)間。

如果只考慮成本因素時(shí)，成本約束函數(shù)為：

其中，Costmin、Costmax為任務(wù)執(zhí)行所需的最低成本和最高成本。

由于只考慮時(shí)間因素或成本因素，考慮因素過(guò)于單一，并不能得到一個(gè)使得云資源提供者和云資源消費(fèi)者都滿意的方案。文獻(xiàn)[28]提到，云資源提供者想要以較低的成本提供服務(wù)，而云資源消費(fèi)者想要以較快的時(shí)間執(zhí)行完任務(wù)。因此通過(guò)綜合考慮，為了達(dá)到能夠使云資源提供者和云資源消費(fèi)者都能滿意的目的，提出時(shí)間-成本約束條件，將時(shí)間因素（6）和成本因素（7）通過(guò)式（8）將多目標(biāo)問(wèn)題轉(zhuǎn)化為單目標(biāo)的問(wèn)題。評(píng)價(jià)函數(shù)為：

其中，t代表時(shí)間因子，c代表成本因子，本文通過(guò)改變t和c的值，來(lái)決定調(diào)度方案中時(shí)間因素和成本因素所占的比例，進(jìn)一步控制時(shí)間和成本對(duì)于評(píng)價(jià)函數(shù)的影響。

時(shí)間-成本條件約束下的云資源調(diào)度模型為：

根據(jù)調(diào)度模型P，對(duì)每一種調(diào)度方案進(jìn)行評(píng)價(jià)，得到最小的評(píng)價(jià)函數(shù)值，對(duì)應(yīng)的調(diào)度方案就是最優(yōu)調(diào)度方案。

2.2 模糊云資源調(diào)度模型

根據(jù)式（1）得到的是任務(wù)在虛擬機(jī)上執(zhí)行的確定的時(shí)間。但是由于在實(shí)際執(zhí)行過(guò)程中，任務(wù)的執(zhí)行具有不確定性，本文使用三角模糊數(shù)對(duì)任務(wù)執(zhí)行時(shí)間進(jìn)行不確定表示。

使用三角模糊數(shù)給出任務(wù)執(zhí)行時(shí)間的模糊范圍，通過(guò)式（10）和式（11）對(duì)任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間的波動(dòng)范圍進(jìn)行上下范圍的判定。

任務(wù)執(zhí)行時(shí)間的模糊下限：

任務(wù)執(zhí)行時(shí)間的模糊上限：

其中，Rand()表示在（0,1）中的隨機(jī)數(shù)，α1和α2分別表示上、下界的模糊系數(shù)。將任務(wù)的執(zhí)行時(shí)間進(jìn)行模糊之后，表示為，其中tL代表任務(wù)執(zhí)行的樂(lè)觀時(shí)間，tM代表任務(wù)執(zhí)行的最可能時(shí)間，tR代表任務(wù)執(zhí)行的悲觀時(shí)間。

根據(jù)三角模糊數(shù)的線性特征和可分解性，使用模糊后的執(zhí)行時(shí)間計(jì)算相應(yīng)的評(píng)價(jià)函數(shù)值，將式（9）轉(zhuǎn)換為式（12）：

文獻(xiàn)[29]提出了一種判別規(guī)則，通過(guò)計(jì)算三角模糊數(shù)的平均值和標(biāo)準(zhǔn)差，判定誰(shuí)的模糊性能更好。如果一個(gè)模糊數(shù)具有較高的平均值和較低的標(biāo)準(zhǔn)差，則認(rèn)為該模糊數(shù)排序更高。

根據(jù)上述方法，可將確定的云資源調(diào)度模型轉(zhuǎn)化為不確定任務(wù)執(zhí)行時(shí)間的模糊云資源調(diào)度模型。調(diào)度的目標(biāo)轉(zhuǎn)化為對(duì)評(píng)價(jià)函數(shù)的平均值和標(biāo)準(zhǔn)差的計(jì)算，然后根據(jù)三角模糊數(shù)的加法運(yùn)算和數(shù)乘運(yùn)算，利用三角模糊數(shù)的特性，得出不確定任務(wù)執(zhí)行時(shí)間下的云資源調(diào)度的問(wèn)題模型，如式（13）所示。

其中，Pη為模糊數(shù)的平均值，Pμ為標(biāo)準(zhǔn)差，?是對(duì)不確定度的加權(quán)系數(shù)。

3 RIOPSO 算法

3.1 PSO 算法分析

PSO 算法是模擬鳥(niǎo)類覓食行為的一種進(jìn)化算法，通過(guò)迭代的方式，以個(gè)體最優(yōu)尋找全局最優(yōu)，從而得到最終的結(jié)果。本文使用不確定執(zhí)行時(shí)間下的粒子群優(yōu)化算法，對(duì)云資源調(diào)度問(wèn)題進(jìn)行求解。最優(yōu)調(diào)度方案的判斷是通過(guò)評(píng)價(jià)函數(shù)的取值進(jìn)行評(píng)價(jià)的。表1 是PSO 算法中需要用到的參數(shù)的定義。

Table 1 Parameter list表1 參數(shù)列表

在PSO 算法中，粒子可以模擬鳥(niǎo)類的覓食行為，在G維空間中進(jìn)行尋優(yōu)。在粒子群中有N個(gè)粒子，其中第i個(gè)粒子的位置為：

速度為：

粒子在迭代過(guò)程中通過(guò)對(duì)表1 中的速度的更新來(lái)進(jìn)行位置的更新。

粒子群在尋優(yōu)的過(guò)程中，通過(guò)比較評(píng)價(jià)函數(shù)的值找到個(gè)體最優(yōu)和全局最優(yōu)，之后對(duì)速度和位置進(jìn)行迭代更新，其中在第k次迭代時(shí)，第i個(gè)粒子的個(gè)體最優(yōu)值為pBesti，全局最優(yōu)值為gBestk。粒子i的速度更新公式為：

粒子的位移更新公式為：

如何使用PSO 算法解決云資源調(diào)度的問(wèn)題，首先將PSO 算法中的粒子與云資源調(diào)度中的任務(wù)和虛擬機(jī)進(jìn)行對(duì)應(yīng)。粒子解空間的維數(shù)取決于云資源調(diào)度中的任務(wù)數(shù)。每一維的取值范圍就是云資源調(diào)度中被分配到的虛擬機(jī)數(shù)，即每一維的解對(duì)應(yīng)的就是虛擬機(jī)的編號(hào)。粒子每一次的迭代更新的過(guò)程，粒子的位置就會(huì)發(fā)生相應(yīng)的進(jìn)化，就會(huì)產(chǎn)生一個(gè)新的進(jìn)化粒子，產(chǎn)生一個(gè)如圖1 所示的新的任務(wù)和虛擬機(jī)之間的對(duì)應(yīng)關(guān)系，一個(gè)新的調(diào)度方案。

對(duì)一個(gè)任務(wù)數(shù)為8，虛擬機(jī)數(shù)為3 的云資源調(diào)度來(lái)說(shuō)，使用的PSO 算法中，粒子群中相應(yīng)的粒子有8維，每一維的取值可以是0、1、2。對(duì)于任務(wù)和虛擬機(jī)之間的對(duì)應(yīng)關(guān)系，表2 為粒子的一種可能表示方式。

Table 2 Expression of a particle表2 某一粒子的表示

3.2 正交初始化

在PSO 算法中，粒子的尋優(yōu)過(guò)程需要通過(guò)迭代來(lái)進(jìn)行。粒子群的初始狀態(tài)對(duì)之后的尋優(yōu)過(guò)程有著直接的影響，在粒子搜索的初始階段，初始解越有序越利于之后的粒子迭代搜索。在種群初始化時(shí)，要盡可能保證粒子均勻分布在解空間中，這就使得在初始化階段要滿足粒子具有各個(gè)方向的解。在PSO算法中，隨機(jī)初始化種群，并不能保證粒子能夠均勻分布在解空間中，有可能使粒子集中在一個(gè)區(qū)域，或者使粒子的相似程度過(guò)高，都不利于之后的尋優(yōu)過(guò)程。在本文中使用正交矩陣初始化種群的方法，使整個(gè)種群均勻分布在可行解空間中。

當(dāng)系統(tǒng)有Ele種元素，且每種元素都有Lev種水平，那么一共會(huì)有LevEle個(gè)組合數(shù)產(chǎn)生。如果在實(shí)驗(yàn)中將這LevEle個(gè)組合全部進(jìn)行實(shí)驗(yàn)，當(dāng)Lev和Ele很大時(shí)，會(huì)產(chǎn)生許多相似的組合，用這些組合做的實(shí)驗(yàn)達(dá)不到好的效果，擬合度過(guò)高。因此構(gòu)建正交矩陣G=Lrow(LevEle)，初始化種群，能夠篩選出均勻分布在解空間中的粒子，使用較少的組合進(jìn)行實(shí)驗(yàn)，從而使得粒子種群減小。這樣使用了較少的粒子，卻能夠達(dá)到更好的效果。其中，row 代表一共有多少組水平組合數(shù)，row 遠(yuǎn)小于LevEle。

對(duì)任務(wù)數(shù)為4，虛擬機(jī)數(shù)為3 的云資源調(diào)度問(wèn)題，使用正交初始化粒子種群的方式進(jìn)行舉例。如果將每一個(gè)任務(wù)在每一個(gè)虛擬機(jī)上都執(zhí)行，那么需要進(jìn)行34=81 次的實(shí)驗(yàn)。但是如果采用正交初始化的設(shè)計(jì)，只需要進(jìn)行9 次實(shí)驗(yàn)，就能夠找到代表性的解。而且隨著虛擬機(jī)數(shù)量和任務(wù)數(shù)量的增多，正交初始化就更能顯示出“均勻分散，齊整可比”的特點(diǎn)。

表3 就是使用正交矩陣，初始化虛擬機(jī)數(shù)為3，任務(wù)數(shù)為4 的云資源調(diào)度的分配方案。

Table 3 Orthogonal initial population表3 正交初始種群

從表3 可知，使用正交矩陣初始化種群，只需9個(gè)初始解就可以均勻分布在解空間中。每一行代表一種調(diào)度方案，列數(shù)代表任務(wù)數(shù)，每一個(gè)數(shù)字代表執(zhí)行任務(wù)選擇的虛擬機(jī)編號(hào)。

對(duì)于構(gòu)建正交矩陣，首先需要確定基本列，然后根據(jù)基本列構(gòu)建非基本列，基本列和非基本列的和就是需要構(gòu)建的正交矩陣的列數(shù)，也就是一共需要被執(zhí)行的任務(wù)數(shù)?；玖蠮滿足式（18），下面是創(chuàng)建正交矩陣的偽代碼。

算法1

步驟1構(gòu)建基礎(chǔ)列

步驟2構(gòu)建非基礎(chǔ)列

步驟3將ai,j進(jìn)行加1

創(chuàng)建基本列和非基本列之后，已經(jīng)將一個(gè)完整的正交矩陣構(gòu)建完成，但是最終想要得到的是適合粒子群初始化的矩陣，就要對(duì)創(chuàng)建出來(lái)的矩陣進(jìn)行列的取舍。算法2 得到最終的矩陣。

算法2

這樣就構(gòu)建了用來(lái)初始化種群的正交矩陣。

3.3 重新隨機(jī)化

根據(jù)PSO 算法容易陷入局部最優(yōu)的缺點(diǎn)，采用能夠使粒子跳出局部最優(yōu)的重新隨機(jī)化的方法對(duì)粒子尋優(yōu)能力進(jìn)行優(yōu)化，使粒子在解空間中能夠探索的范圍更大，尋優(yōu)效率更高。通過(guò)計(jì)算方差的方式對(duì)粒子進(jìn)行迭代更新，確保粒子能夠獲得更優(yōu)的解。

根據(jù)式（19）得到適用于粒子種群的方差值，然后根據(jù)得到的方差對(duì)粒子群進(jìn)行迭代更新。

在式（19）中，k代表當(dāng)前迭代次數(shù)，A表示重新隨機(jī)化的有效初始值，S代表坡度，它控制粒子的搜索范圍。在搜索過(guò)程中，第一部分稱為大范圍搜索，即廣泛搜索，此時(shí)方差曲線的坡度較大，使得粒子能夠在遠(yuǎn)離全局最優(yōu)粒子gBest的搜索空間進(jìn)行隨機(jī)搜索。第二部分稱為小范圍搜索，即精細(xì)搜索，此時(shí)方差曲線的坡度較小，粒子在靠近全局最優(yōu)粒子gBest周圍進(jìn)行隨機(jī)搜索。兩部分結(jié)合起來(lái)能夠使得最后粒子收斂到最優(yōu)解，從而使得粒子能夠在全局范圍內(nèi)進(jìn)行搜索，跳出局部最優(yōu)，搜索到最優(yōu)解。M是對(duì)應(yīng)方差曲線坡度中點(diǎn)的迭代次數(shù)，兩部分通過(guò)中間點(diǎn)M進(jìn)行分割，中間點(diǎn)M決定廣泛搜索和精細(xì)搜索的搜索時(shí)間。

3.4 更新慣性權(quán)重

粒子在解空間中尋優(yōu)時(shí)，粒子的收斂速度影響粒子在搜索過(guò)程中是否能收斂到當(dāng)前最優(yōu)狀態(tài)。粒子的慣性權(quán)重值是PSO 算法中的重要參數(shù)，通過(guò)調(diào)整粒子在每一次迭代過(guò)程中的慣性權(quán)重，來(lái)控制粒子的收斂速率。當(dāng)粒子的慣性權(quán)重較大時(shí)，粒子搜索范圍增大，收斂速率過(guò)慢，不易得到精確的解；當(dāng)慣性權(quán)重較小時(shí)，粒子的搜索范圍減小，收斂速度過(guò)快，容易陷入局部極值。根據(jù)粒子收斂過(guò)程中的這一特性，本文使用實(shí)時(shí)更新慣性權(quán)重的方式，和重新隨機(jī)化相結(jié)合，使粒子能夠探索到整個(gè)解空間的同時(shí)，控制粒子的收斂速率。

根據(jù)粒子在每一次迭代過(guò)程中評(píng)價(jià)函數(shù)的變化，對(duì)慣性權(quán)重值進(jìn)行更新。當(dāng)?shù)蟮牧Ｗ拥脑u(píng)價(jià)函數(shù)值變小，那么該粒子的慣性權(quán)重值將增加或者保持不變；如果該粒子的評(píng)價(jià)函數(shù)值變大，那么將對(duì)該粒子的慣性權(quán)重值進(jìn)行減小。對(duì)應(yīng)公式為式（20），對(duì)第i個(gè)粒子的慣性權(quán)重值進(jìn)行實(shí)時(shí)更新。

其中，ωi(k)表示當(dāng)前第i個(gè)粒子的慣性權(quán)重值，取值范圍為（0,1），S代表期望的評(píng)價(jià)函數(shù)值的范圍，ΔJi(k)代表該粒子當(dāng)前評(píng)價(jià)值與前一個(gè)狀態(tài)評(píng)價(jià)值的差值。

在重新隨機(jī)化和更新慣性權(quán)重之后速度的更新由式（16）變?yōu)槭剑?1）。

粒子的位置更新公式為：

其中，variance(k)就是重新隨機(jī)化中的方差，取值由式（19）決定。ωi(k)就是每一個(gè)粒子在每一次更新中的慣性權(quán)重值，取值由式（20）決定。

RIOPSO 算法的流程圖如圖2 所示。

Fig.2 Algorithm flowchart圖2 算法流程圖

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

4.1 數(shù)據(jù)的生成與參數(shù)的選擇

為了分析和比較本文提出的模型和算法的性能，在云計(jì)算仿真平臺(tái)Cloudsim 上進(jìn)行仿真實(shí)驗(yàn)。時(shí)間和成本對(duì)實(shí)驗(yàn)的結(jié)果都有影響，本文將式（8）中的時(shí)間因子t和成本因子c都設(shè)置為0.5。本文采用文獻(xiàn)[30]的數(shù)據(jù)生成方法產(chǎn)生數(shù)據(jù)集，使生成的任務(wù)大小和虛擬機(jī)處理速度分別在范圍[3 000,130 000]和[300,1 300]之內(nèi)。根據(jù)得到的任務(wù)的大小和虛擬機(jī)的處理速度，使用2.1 節(jié)中的計(jì)算方式，就可以得到任務(wù)在虛擬機(jī)上的執(zhí)行時(shí)間和執(zhí)行成本。

在RIOPSO 算法中，粒子群的速度、位置和慣性權(quán)重值的更新都是根據(jù)評(píng)價(jià)函數(shù)的取值是否變化，來(lái)進(jìn)行迭代更新的。在參數(shù)設(shè)置中，個(gè)體學(xué)習(xí)因子C1和群體學(xué)習(xí)因子C2的取值，對(duì)實(shí)驗(yàn)結(jié)果有所影響。當(dāng)C1=1，C2=0 時(shí)，說(shuō)明當(dāng)前的粒子只受其個(gè)體最優(yōu)值pBest影響，對(duì)當(dāng)前的全局最優(yōu)粒子的學(xué)習(xí)能力為0；而C1=0，C2=1 時(shí)，說(shuō)明當(dāng)前粒子的更新只受全局最優(yōu)gBest的影響，對(duì)該粒子個(gè)體的學(xué)習(xí)能力為0。在本文中將個(gè)體學(xué)習(xí)因子C1和群體學(xué)習(xí)因子C2均設(shè)置為0.5。

本文實(shí)驗(yàn)中各項(xiàng)參數(shù)設(shè)置如表4 所示。

Table 4 Setting of experimental parameters表4 實(shí)驗(yàn)參數(shù)的設(shè)置

在本文進(jìn)行的實(shí)驗(yàn)中，除算法改進(jìn)策略不同外，均使用相同的數(shù)據(jù)集和實(shí)驗(yàn)參數(shù)，在同一模型和同一環(huán)境下對(duì)云資源調(diào)度問(wèn)題進(jìn)行求解。

4.2 算法性能指標(biāo)評(píng)價(jià)分析

使用算法NSGA-Ⅰ、NSGA-Ⅱ、NSGA-Ⅲ和MOEA/D 與本文提出的RIOPSO 算法求解云資源調(diào)度的問(wèn)題。

（1）NSGA-Ⅰ算法。非支配排序遺傳算法，與遺傳算法相比在選擇算子執(zhí)行之前，根據(jù)個(gè)體間的支配關(guān)系進(jìn)行了分層。

（2）NSGA-Ⅱ算法。帶有精英保留策略的快速非支配多目標(biāo)優(yōu)化算法，采用了擁擠度比較的策略，是一種基于帕累托最優(yōu)解的優(yōu)化算法。

（3）NSGA-Ⅲ算法。在NSGA-Ⅱ算法的基礎(chǔ)上，提出一種參考點(diǎn)的選擇操作，代替NSGA-Ⅱ算法中的擁擠距離的選擇操作。

（4）MOEA/D 算法。一種基于分解的多目標(biāo)進(jìn)化算法。

使用上述算法解決云資源調(diào)度問(wèn)題時(shí)，分別計(jì)算此時(shí)的IGD、HV 和C-Metric，以此量化各個(gè)算法的性能。

（1）IGD 是算法的綜合性能評(píng)價(jià)指標(biāo)，對(duì)帕累托前沿上的解與算法獲得的解的最小距離進(jìn)行計(jì)算。IGD 的值越小，說(shuō)明算法得到的解分布越均勻，同時(shí)收斂性越好。

（2）HV 對(duì)非支配解覆蓋解空間的大小進(jìn)行度量，HV 的值越大，證明該算法解的質(zhì)量越高。

（3）C-Metric的計(jì)算基于帕累托解集的支配關(guān)系，該性能指標(biāo)通過(guò)兩組帕累托前沿計(jì)算收斂性能。例如C(A,B)=1 表示B中的所有個(gè)體均被A中的支配，而C(A,B)=0 則表示B中的個(gè)體沒(méi)有被A支配。

表5 所示為五種算法的性能對(duì)比結(jié)果。性能指標(biāo)結(jié)果使用均值進(jìn)行記錄。

Table 5 Performance comparison of five algorithms表5 五種算法性能對(duì)比

從表5 中可以看出，RIOPSO 算法在IGD 性能比較中，具有最小的IGD 值，說(shuō)明RIOPSO 算法獲得的解集分布均勻，能夠使種群更好地收斂到近似帕累托前沿面，綜合性能較好。通過(guò)超體積指標(biāo)HV 看出，RIOPSO 算法獲得的非支配解與參考點(diǎn)之間構(gòu)成的目標(biāo)區(qū)域空間最大，相對(duì)于其他四種算法也具有最好的求解性能。從C-Metric 覆蓋率來(lái)看，RIOPSO算法中支配關(guān)系均少于其他幾種算法，這是由于RIOPSO 算法使用正交初始化的策略，在初始階段就獲得了較高質(zhì)量的解集，從而獲得收斂性能更好的最優(yōu)解。

綜上所述，使用本文算法改進(jìn)策略在求解云資源調(diào)度問(wèn)題時(shí)能夠在提高解質(zhì)量的同時(shí)，使算法的綜合性能更好。

4.3 模型對(duì)比

由于在實(shí)際生活中，云資源調(diào)度的過(guò)程中存在任務(wù)執(zhí)行的異步性和不確定性，本文使用三角模糊的方法，對(duì)問(wèn)題模型進(jìn)行了處理，使結(jié)果更加貼近實(shí)際。下面本文將對(duì)執(zhí)行時(shí)間確定和不確定兩種情況的實(shí)驗(yàn)結(jié)果進(jìn)行比較。將每一個(gè)確定的執(zhí)行時(shí)間進(jìn)行三角模糊表示時(shí)，要對(duì)執(zhí)行時(shí)間模糊之后的數(shù)進(jìn)行左右范圍的確定，設(shè)置式（10）和式（11）中的參數(shù)α1=0.9,α2=1.2。相同的任務(wù)規(guī)模通過(guò)評(píng)價(jià)函數(shù)的平均值進(jìn)行比較。圖3 為確定模型和模糊模型的對(duì)比結(jié)果。通過(guò)圖像可以看出，使用模糊模型，評(píng)價(jià)函數(shù)的值將會(huì)比確定模型下的評(píng)價(jià)函數(shù)的值高，這意味著對(duì)于不確定因素的考慮是很有必要的。如果忽略這些不確定的因素，將會(huì)導(dǎo)致實(shí)際效果和理論估計(jì)效果產(chǎn)生偏差而降低系統(tǒng)的效率。

Fig.3 Model comparison圖3 模型對(duì)比

4.4 算法性能對(duì)比

為了分析本文提出的改進(jìn)策略的具體優(yōu)勢(shì)，將本文提出的RIOPSO 算法與其他三種算法進(jìn)行對(duì)比分析。其中SPSO（re-randomization particle swarm optimization）算法使用了重新隨機(jī)化的策略[31]，沒(méi)有對(duì)問(wèn)題的初始條件進(jìn)行改進(jìn)。SWPSO（re-randomization inertia weight particle swarm optimization）算法將重新隨機(jī)化和實(shí)時(shí)更新慣性權(quán)重進(jìn)行結(jié)合[32]，初始化種群時(shí)使用的是隨機(jī)方法。OPSO（orthogonal initialization particle swarm optimization）算法使用正交初始化種群的方式[33]對(duì)PSO 算法進(jìn)行優(yōu)化。

為了能夠更直觀地看到本文算法的效率和更好的尋優(yōu)能力，將本文提出的RIOPSO 算法，同上述提到的SPSO、SWPSO、OPSO 算法進(jìn)行對(duì)比分析，在任務(wù)規(guī)模為100、200、300，虛擬機(jī)個(gè)數(shù)為5 的情況下，對(duì)四種算法分別進(jìn)行尋優(yōu)測(cè)試，并且進(jìn)行記錄，實(shí)驗(yàn)結(jié)果如圖4～圖6 所示。其中橫縱坐標(biāo)分別代表迭代次數(shù)和算法對(duì)應(yīng)的評(píng)價(jià)函數(shù)值。

Fig.4 Comparison of algorithm optimization capabilities(100 tasks)圖4 算法尋優(yōu)能力對(duì)比（100 個(gè)任務(wù)）

Fig.6 Comparison of algorithm optimization capabilities(300 tasks)圖6 算法尋優(yōu)能力對(duì)比（300 個(gè)任務(wù)）

由圖4～圖6 可以發(fā)現(xiàn)OPSO 算法和RIOPSO 算法的初始評(píng)價(jià)函數(shù)均優(yōu)于其他兩種算法，這是因?yàn)槌跏冀獾馁|(zhì)量高，相應(yīng)的也就提高了粒子群的搜索效率，證明了正交初始化策略的有效性。但是從迭代曲線中看出，由于粒子在搜索最優(yōu)解的過(guò)程中可能會(huì)陷入局部最優(yōu)狀態(tài)，OPSO 算法并不一定能獲得優(yōu)于其他三種算法的解。相對(duì)比SPSO 算法，SWPSO算法和RIOPSO 算法在控制粒子搜索范圍的基礎(chǔ)上增加了對(duì)粒子搜索速度的控制，這使得粒子在搜索過(guò)程中能夠跳出局部最優(yōu)，更好地收斂到全局最優(yōu)解。從圖中還可以發(fā)現(xiàn)，無(wú)論是在大規(guī)模任務(wù)還是小規(guī)模任務(wù)中，綜合了以上三種策略的RIOPSO 算法，都能夠使用較少的迭代次數(shù)得出優(yōu)于其他三種算法的解，減少了算法的運(yùn)行迭代時(shí)間。因此RIOPSO 算法能夠具有尋優(yōu)速度快，尋優(yōu)能力強(qiáng)，尋優(yōu)效果好的特點(diǎn)。

為了驗(yàn)證在相同的任務(wù)數(shù)，不同的虛擬機(jī)數(shù)的情況中，RIOPSO 算法的能力，在4 個(gè)不同的數(shù)據(jù)集上進(jìn)行了多次測(cè)試，任務(wù)和虛擬機(jī)的個(gè)數(shù)分別為（100,5），（100,10），（100,15），（100,20），實(shí)驗(yàn)結(jié)果取平均值后如圖7 所示。其中橫坐標(biāo)表示任務(wù)數(shù)為100 時(shí)對(duì)應(yīng)的虛擬機(jī)的數(shù)目，縱坐標(biāo)表示評(píng)價(jià)函數(shù)值。

Fig.7 Comparison of optimization capabilities under same task scale圖7 相同任務(wù)規(guī)模下的尋優(yōu)能力對(duì)比

通過(guò)圖7 可以看出，在相同任務(wù)數(shù)，不同虛擬機(jī)數(shù)的情況下，RIOPSO 還能夠搜索到比以上三種算法更優(yōu)的解，得到更優(yōu)的調(diào)度方案。

根據(jù)圖7中各個(gè)算法的評(píng)價(jià)函數(shù)值，建立了SPSO算法、SWPSO 算法、OPSO 算法的評(píng)價(jià)函數(shù)值大于RIOPSO 算法的評(píng)價(jià)函數(shù)值的相對(duì)差值百分比圖像。如圖8 所示，橫坐標(biāo)代表虛擬機(jī)個(gè)數(shù)，縱坐標(biāo)代表相對(duì)差值百分比。從圖中可以看出，無(wú)論虛擬機(jī)規(guī)模是多是少，相比于其他三種算法，RIOPSO 算法的尋優(yōu)能力提升最高，進(jìn)一步證明RIOPSO 算法的有效性。

Fig.8 Comparison chart of algorithm optimization ability improvement圖8 算法尋優(yōu)能力提升對(duì)比圖

在時(shí)間因子t和成本因子c均為0.5 時(shí)，使用以上四種算法對(duì)不同任務(wù)規(guī)模的調(diào)度模型進(jìn)行多次實(shí)驗(yàn)，對(duì)得到的調(diào)度方案中的任務(wù)運(yùn)行總時(shí)間和任務(wù)運(yùn)行總成本，分別計(jì)算取平均值，運(yùn)行的虛擬機(jī)個(gè)數(shù)均為5。圖9 所示為四種算法運(yùn)行的任務(wù)執(zhí)行總時(shí)間，圖10 所示為任務(wù)執(zhí)行的總成本。橫坐標(biāo)均為任務(wù)規(guī)模，縱坐標(biāo)分別為得到的調(diào)度方案中的任務(wù)總的執(zhí)行時(shí)間和執(zhí)行成本。

Fig.9 Total time of task execution圖9 任務(wù)執(zhí)行總時(shí)間

從圖中可以看出，無(wú)論是任務(wù)執(zhí)行的總時(shí)間還是任務(wù)運(yùn)行的總成本，RIOPSO 算法都能夠得到最小的值。滿足關(guān)于得到最小執(zhí)行時(shí)間和最少執(zhí)行成本的雙目標(biāo)的需要。

Fig.10 Total cost of task execution圖10 任務(wù)執(zhí)行總成本

通過(guò)以上實(shí)驗(yàn)得出，本文提出的RIOPSO 算法在尋優(yōu)能力和尋優(yōu)效率方面優(yōu)于其他三種算法，并且在求解最優(yōu)的云資源調(diào)度方案方面，能夠使任務(wù)的執(zhí)行時(shí)間更短，執(zhí)行成本更低，從整體上提高了云資源調(diào)度的綜合性能。

5 結(jié)束語(yǔ)

本文將降低任務(wù)的總完成時(shí)間和總執(zhí)行成本作為主要目標(biāo)，考慮不確定因素對(duì)任務(wù)的執(zhí)行時(shí)間的影響，使用模糊的云資源調(diào)度模型，提出了一種改進(jìn)的混合PSO 算法對(duì)云資源調(diào)度問(wèn)題進(jìn)行求解。在本文提出的RIOPSO 算法中，使用到了三種切實(shí)可行的策略：粒子群的正交初始化、粒子的重新隨機(jī)化、慣性權(quán)重的更新。三種策略分別在尋找最優(yōu)解，跳出局部最優(yōu)，提高粒子的收斂能力方面得到了很好的實(shí)驗(yàn)效果。使用模糊模型使云資源調(diào)度更貼近實(shí)際應(yīng)用。使用RIOPSO 算法對(duì)模糊云資源調(diào)度方面進(jìn)行尋優(yōu)，使得任務(wù)的執(zhí)行時(shí)間更短，執(zhí)行成本更低。相比較于單一的SPSO、OPSO、SWPSO 算法，使用RIOPSO 能夠得到更優(yōu)的解，也更符合實(shí)際中的應(yīng)用。