模糊云資源調(diào)度的CMAPSO算法

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

摘要：針對(duì)多目標(biāo)云資源調(diào)度問題，以優(yōu)化任務(wù)的總完成時(shí)間和總執(zhí)行成本為目標(biāo)，采用模糊數(shù)學(xué)的方法，建立了模糊云資源調(diào)度模型。利用協(xié)方差矩陣能夠解決非凸性問題的優(yōu)勢(shì)，采取協(xié)方差進(jìn)化策略對(duì)種群進(jìn)行初始化，并提出了一種混合智能優(yōu)化算法CMAPSO算法（covariance matrix adaptation evolution strategy particle swarm optimization，CMAPSO ），并使用該算法對(duì)模糊云資源調(diào)度模型進(jìn)行求解。使用Cloudsim仿真平臺(tái)隨機(jī)生成云計(jì)算資源調(diào)度的數(shù)據(jù)，對(duì)CMAPSO算法進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果證明了CMAPSO算法對(duì)比PSO算法（particle wwarm optimization），在尋優(yōu)能力方面提升28%，迭代次數(shù)相比提升20%，并且具有良好的負(fù)載均衡性能。

關(guān)鍵詞：云計(jì)算;任務(wù)調(diào)度;粒子群算法; 協(xié)方差矩陣進(jìn)化策略

DOI：10.15938/j.jhust.2022.01.005

中圖分類號(hào)： TP399? ? 文獻(xiàn)標(biāo)志碼： A? ? 文章編號(hào)： 1007-2683（2022）01-0031-09

CMAPSO Algorithm for Fuzzy Cloud Resource Scheduling

LI Chengyan，SONG Yue，MA Jintao

（School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080，China）

Abstract：Aiming at the multiobjective cloud resource scheduling problem， with the goal of optimizing the total completion time and total execution cost of the task， a fuzzy cloud resource scheduling model is established using the method of fuzzy mathematics. Utilizing the advantage of the covariance matrix that can solve the nonconvexity problem， adopting the covariance evolution strategy to initialize the population， a hybrid intelligent optimization algorithm CMAPSO algorithm （covariance matrix adaptation evolution strategy particle swarm optimization，CMAPSO） is proposed to solve the fuzzy cloud resource scheduling model. The Cloudsim simulation platform was used to randomly generate cloud computing resource scheduling data， and the CMAPSO algorithm was tested. The experimental results showed that compared with the PSO algorithm （particle swarm optimization）， the optimization capability of CMAPSO algorithm is increased by 28%， the number of iterations of CMAPSO algorithm is increased by 20%， and it has good load balancing performance.

Keywords：cloud computing; task scheduling; particle swarm algorithm; covariance matrix adaptation evolution strategy

0引言

云計(jì)算是一種商業(yè)計(jì)算的模型和服務(wù)模式[1]，而云計(jì)算資源調(diào)度的主要目的是將網(wǎng)絡(luò)上的資源進(jìn)行統(tǒng)一的管理和調(diào)式，再給予用戶服務(wù)調(diào)用。如何將計(jì)算資源和數(shù)據(jù)進(jìn)行有效的管理和使用，就是云計(jì)算資源調(diào)度的主要研究目標(biāo)。

云資源調(diào)度問題是一個(gè)NP難問題，有效的資源調(diào)度可以降低任務(wù)的執(zhí)行時(shí)間，減少執(zhí)行成本和能源消耗等，并能對(duì)可靠性，安全性，可用性和可伸縮性等QoS需求進(jìn)行考慮。如果使用現(xiàn)有的調(diào)度方法，比如說時(shí)間片輪轉(zhuǎn)，先進(jìn)先出算法，哈希法，貪心算法等，很難達(dá)到使云計(jì)算資源調(diào)度的各個(gè)方面都滿意的地步，會(huì)產(chǎn)生服務(wù)性能失衡，或者其他的一些問題[2]。

現(xiàn)階段，對(duì)于智能算法的研究是解決云計(jì)算資源調(diào)度問題的主要研究方向。諸如粒子群算法（particle swarm optimization， PSO）[3]，蟻群算法（ant colony optimization， ACO）[4]，遺傳算法（genetic algorithm， GA）[5]，模擬退火算法（simulated annealing， SA）[6]等。PSO算法具有可調(diào)參數(shù)少，收斂速度快的優(yōu)點(diǎn)，而且PSO算法在搜索過程中，會(huì)將當(dāng)前的全局最優(yōu)和局部最優(yōu)都進(jìn)行“記憶”，這有益于粒子群在之后的尋優(yōu)搜索。但是粒子群算法使用的是隨機(jī)初始化的方式，這就可能導(dǎo)致粒子在解空間中可能存在分布不均勻或者粒子的擬合度過高的問題，不利于粒子種群的尋優(yōu)。

協(xié)方差矩陣自適應(yīng)進(jìn)化策略[7]（covariance matrix adaptation evolution strategy， CAMES ）是一種以進(jìn)化策略為基礎(chǔ)發(fā)展起來的，對(duì)于解決非線性問題具有良好適應(yīng)性的算法。本文利用CMAES的協(xié)方差矩陣具有的高引導(dǎo)性的性能[8]，提升PSO算法在初始化階段存在的不足。通過協(xié)方差矩陣進(jìn)化生成高質(zhì)量的解集[9]，使用該解集對(duì)PSO算法進(jìn)行初始化，改變?cè)械某跏蓟绞剑沽Ｗ釉诔跏茧A段就具有分布均勻且離最優(yōu)解較近的優(yōu)勢(shì)。所以本文提出一種基于協(xié)方差矩陣的粒子群優(yōu)化算法，CMAPSO算法（covariance matrix adaptation evolution strategy particle swarm optimization， CMAPSO ）對(duì)模糊云計(jì)算資源調(diào)度問題進(jìn)行求解。

本文的結(jié)構(gòu)如下，第一部分對(duì)模糊云計(jì)算資源

問題的模型進(jìn)行描述，第二部分對(duì)CMAPSO算法進(jìn)行描述，第三部分在仿真平臺(tái)上進(jìn)行實(shí)驗(yàn)，第四部分對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行總結(jié)分析并給出結(jié)論。

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

在云計(jì)算資源調(diào)度中，任務(wù)依照可行性算法在虛擬機(jī)（virtual machine， VM）上運(yùn)行。一個(gè)任務(wù)只能在一個(gè)虛擬機(jī)上執(zhí)行，但是一個(gè)虛擬機(jī)可以執(zhí)行不同的任務(wù)[10-11]。圖1表示任務(wù)和虛擬機(jī)之間的對(duì)應(yīng)關(guān)系，其中Ti代表任務(wù)編號(hào)為i，Vj代表虛擬機(jī)編號(hào)為j。

由于任務(wù)執(zhí)行的不可預(yù)見性，使任務(wù)執(zhí)行的具體完成時(shí)間無法進(jìn)行準(zhǔn)確的估計(jì)，這就使得任務(wù)的完成具有不確定性。針對(duì)這種不確定性，根據(jù)文[12]提到的使用三角模糊數(shù)的方法對(duì)云計(jì)算資源調(diào)度進(jìn)行建模。

通過圖1中的調(diào)度算法部分得到不同的調(diào)度方案，對(duì)不同的調(diào)度方案進(jìn)行不確定環(huán)境下的評(píng)價(jià)函數(shù)的計(jì)算。式（1）為確定條件下的評(píng)價(jià)函數(shù)。

Res（Pi）=trTime（Pi）+crCost（Pi）（1）

式中：Pi代表一種調(diào)度方案;Res（Pi）代表該調(diào)度方案的評(píng)價(jià)函數(shù);t和c分別代表時(shí)間因子和成本因子，表示時(shí)間和成本分別對(duì)于評(píng)價(jià)函數(shù)的影響占比。式（1）用于評(píng)價(jià)粒子的搜索性能，對(duì)粒子的迭代尋優(yōu)具有指導(dǎo)能力，當(dāng)算法停止迭代時(shí)，具有最優(yōu)的評(píng)價(jià)函數(shù)值的粒子代表當(dāng)前最優(yōu)解。

在式（1）中，時(shí)間評(píng)價(jià)函數(shù)rTime（Pi）和成本評(píng)價(jià)函數(shù)rCost（Pi）分別表示為

rTime（Pi）=Time（Pi）-TimeMINTimeMAX-TimeMIN（2）

rCost（Pi）=Cost（Pi）-CostMINCostMAX-CostMIN（3）

式中：TimeMAX和TimeMIN分別代表任務(wù)在虛擬機(jī)上執(zhí)行的最長(zhǎng)時(shí)間和最短時(shí)間; CostMAX和CostMIN分別代表任務(wù)執(zhí)行所需的最大成本和最小成本。

調(diào)度方案P總的執(zhí)行時(shí)間計(jì)算公式為

Time（Pi）=maxmj=1vmTime（4）

vmTimej表示第j個(gè)虛擬機(jī)的執(zhí)行時(shí)間。

調(diào)度方案P總的執(zhí)行成本計(jì)算公式為

Cost（Pi）=∑mj=1vmTimej×cstj（5）

式中：cstj表示第j個(gè)虛擬機(jī)單位時(shí)間內(nèi)的執(zhí)行成本。

根據(jù)三角模糊數(shù)的特性，通過隸屬函數(shù)對(duì)任務(wù)的執(zhí)行時(shí)間進(jìn)行表示。

μT（x）=x-tLtM-tL，x∈[tL，tM]

tR-xtR-tM，x∈[tM，tR]（6）

當(dāng)x≤tL，x≥tR時(shí)μT（x）=0。其中tL，tR分別表示任務(wù)可能的最短執(zhí)行時(shí)間和最長(zhǎng)執(zhí)行時(shí)間;tM表示任務(wù)最可能的執(zhí)行時(shí)間。tL，tR根據(jù)式（7）和式（8）進(jìn)行計(jì)算：

tL=tM×（l+（1-l）×Rand（））（7）

tR=tM×（1+（u-1）×Rand（））（8）

式中l(wèi)和u代表模糊下界和模糊上界的系數(shù)，Rand（）代表隨機(jī)生成數(shù)，范圍在[0，1]之間。根據(jù)三角模糊數(shù)的線性特性和可分解性，不確定的云計(jì)算資源調(diào)度模型中的評(píng)價(jià)函數(shù)表示為

min{res（Pi）}=min{P～}=min{PL，PM，PR}（9）

根據(jù)三角模糊數(shù)的隸屬函數(shù)將式（1）轉(zhuǎn)換為模糊模型進(jìn)行求解。根據(jù)可分解性，在式（9）中，模糊之后的評(píng)價(jià)函數(shù)的3個(gè)端點(diǎn)PL，PM，PR與模糊執(zhí)行時(shí)間的3個(gè)端點(diǎn)tL，tM，tR有關(guān)。

x-p（X～）=14（XL+2XM+XR）（10）

σp（X～）=180[3（XL）2+4（XM）2+3（XR）2-

4XLXM-2XLXR-4XMXR]12（11）

式（10）是對(duì)模糊數(shù)取平均值，公式（11）是對(duì)模糊數(shù)取標(biāo)準(zhǔn)差，二者都是對(duì)模糊數(shù)進(jìn)行去模糊化處理。使用文[13]中提到的對(duì)模糊數(shù)進(jìn)行排序的方法，對(duì)評(píng)價(jià)函數(shù)進(jìn)行均值和方差的計(jì)算，如果該評(píng)價(jià)函數(shù)的模糊數(shù)的平均值較高，方差較低，那么認(rèn)為該評(píng)價(jià)函數(shù)對(duì)應(yīng)的調(diào)度方案越好。

根據(jù)該排序方式，將式（9）去模糊化之后轉(zhuǎn)變?yōu)槭剑?2）：

min{res（Pi）}=min{P～}=min{PL，PM，PR}=

min{Pη+Pμ}（12）

其中表示對(duì)不確定度的加權(quán)系數(shù)。

負(fù)載均衡的計(jì)算公式為

Load=min1≤i≤mvmTimeimax1≤i≤mvmTimei（13）

其中：min1≤i≤mvmTimei代表虛擬機(jī)執(zhí)行最短時(shí)間;max1≤i≤mvmTimei代表虛擬機(jī)最長(zhǎng)執(zhí)行時(shí)間。對(duì)于負(fù)載均衡度來說，負(fù)載越接近于1，說明負(fù)載越均衡，當(dāng)負(fù)載均衡度為0時(shí)，說明有的虛擬機(jī)沒有被分配到任務(wù)，這時(shí)負(fù)載均衡性較差。負(fù)載均衡也是本文衡量算法是否具有穩(wěn)定性的一個(gè)指標(biāo)。

2CMAPSO算法

2.1算法思想

PSO算法在尋優(yōu)過程中，由于問題的非凸性的本質(zhì)，可能會(huì)陷入局部最優(yōu)狀態(tài)，如果使用隨機(jī)初始化的方式，可能會(huì)因?yàn)槌跏冀獾姆植疾痪瑪M合度過高等問題，導(dǎo)致算法搜索不到最優(yōu)解。而CMAPSO算法利用協(xié)方差矩陣的健壯性，對(duì)搜索空間映射的不變性等特點(diǎn)，能夠有效的解決具有非凸性的目標(biāo)函數(shù)的問題[14]。

利用這種優(yōu)勢(shì)，本文提出的CMAPSO算法利用協(xié)方差矩陣進(jìn)化過程中，產(chǎn)生的采樣個(gè)體逐漸靠近最優(yōu)解的特點(diǎn)，對(duì)采樣個(gè)體進(jìn)行存儲(chǔ)，產(chǎn)生種群的初始矩陣A。使得CMAPSO算法在初始階段就具有離最優(yōu)解較近的初始值，且均勻分布在最優(yōu)解的周圍。這就使得CMAPSO算法在初始搜索階段，就能夠?qū)ψ顑?yōu)解所在區(qū)域進(jìn)行精細(xì)搜索，提升搜索精度[15，16]。

下面對(duì)CMAPSO算法求解模糊云計(jì)算資源調(diào)度問題的步驟進(jìn)行詳細(xì)描述。

2.2種群初始化

協(xié)方差矩陣自適應(yīng)進(jìn)化策略是依靠多維協(xié)方差矩陣自適應(yīng)調(diào)整，使其逐步逼近Hessian矩陣，從而收斂得到最優(yōu)解。根據(jù)這一特性，本文通過協(xié)方差矩陣得到CMAPSO算法的初始矩陣，并對(duì)粒子種群進(jìn)行初始化。

協(xié)方差矩陣C服從多維正態(tài)分布N（m，C），并且C表示種群的突變方向和突變尺度，通過當(dāng)前的最優(yōu)解rgrgx與前一代的平均值m的關(guān)系更新協(xié)方差矩陣C，使整個(gè)種群向著最優(yōu)解的方向進(jìn)行突變。協(xié)方差矩陣C的規(guī)模為N×N，其中N=TaskNum+VmNum，TaskNum為云計(jì)算資源調(diào)度中任務(wù)的規(guī)模，VmNum為虛擬機(jī)的規(guī)模，VmNum小于TaskNum。

使用協(xié)方差自適應(yīng)進(jìn)化策略求解云資源調(diào)度問題，主要需要對(duì)協(xié)方差矩陣C進(jìn)行初始化，初始矩陣C=I∈RN×N，然后根據(jù)該初始協(xié)方差矩陣更新逐步對(duì)搜索種群進(jìn)行更新，得到搜索種群rgrgx，根據(jù)該搜索種群獲取任務(wù)對(duì)應(yīng)的虛擬機(jī)編號(hào)。然后根據(jù)該搜索種群可以對(duì)協(xié)方差矩陣C進(jìn)行迭代更新，重復(fù)上述步驟，找到最優(yōu)的調(diào)度方案。

在CMAPSO算法中，設(shè)置子代大小為λ，父代大小為μ（λ<μ），g代表當(dāng)前迭代次數(shù)，pathgσ∈RN，pathgc∈RN，σg∈R+，其中path0σ=path0c=0。

根據(jù)公式（14）生成CMAPSO算法的搜索種群rgrgx。

rgrgxg+1k=m+σgBgDgN（0，I）～N（m，σ2C）（14）

其中：rgrgxg+1k代表第g+1次迭代的第k個(gè)個(gè)體;m代表群體均值，m=∑μi=1ωirgrgxi：λ（其中∑μi=1ωi=1）;B矩陣的列向量是協(xié)方差矩陣C的特征向量正交基;D的對(duì)角元素是由特征向量C的特征值的平方根構(gòu)成的對(duì)角陣。

通過式（15）計(jì)算進(jìn)化路徑pathσ。利用進(jìn)化路徑對(duì)進(jìn)化步長(zhǎng)進(jìn)行累積控制。

pathσ=（1-cσ）pathσ+cσ（2-cσ）μeffC-12×

∑μi=1[ωi（rgrgxi-m）/σ]（15）

其中：μeff=1/∑μi=1ω2i表示協(xié)方差矩陣的有效選擇質(zhì)量;cσ表示對(duì)前一代的pathσ的學(xué)習(xí)率。

全局步長(zhǎng)的更新公式為

σ=σexpcσdσ||pathσ||E||N（0，I）||-1（16）

其中：dσ代表阻尼系數(shù)且dσ≈1，E||N（0，I）||代表多維正態(tài)分布范數(shù)的期望值。

式（17）對(duì)協(xié)方差矩陣進(jìn)化路徑pathc進(jìn)行計(jì)算。根據(jù)pathc對(duì)協(xié)方差矩陣進(jìn)行調(diào)整。

pathc=（1-cc）pathc+hccc（2-cc）μeff×

∑μi=1[ωi（rgrgxi-m）/σ]（17）

其中：hσ代表Heaviside函數(shù);控制協(xié)方差矩陣在線性環(huán)境中的增長(zhǎng)速度;cc表示對(duì)前一代的pathc的學(xué)習(xí)率。

對(duì)于協(xié)方差矩陣的更新公式為

C=（1-c1-cμ）C+c1（pathcpathTc+δ（hσ）C）+

cμ∑μi=1[ωi（（rgrgxi-m）/σ）（（rgrgxi-m）/σ）T]（18）

其中δ（hσ）=（1-hσ）cc（2-cc）;c1，cμ表示秩為1和秩為μ的協(xié)方差矩陣C的學(xué)習(xí)更新率。

根據(jù)式（14）獲得搜索種群rgrgx，根據(jù)式（14），（15），（16），（17）獲得式（18）中對(duì)應(yīng)參數(shù)，對(duì)協(xié)方差矩陣C進(jìn)行更新，根據(jù)更新后的矩陣重新獲取搜索種群rgrgx，得到相應(yīng)的調(diào)度方案。

根據(jù)協(xié)方差矩陣生成初始矩陣的算法描述，設(shè)置采樣個(gè)體的維數(shù)設(shè)置為N，計(jì)算采樣種群rgrgx的數(shù)值，然后進(jìn)行排序比較，在父代μ中截取子代λ大小，對(duì)此時(shí)數(shù)值較小的rgrgx的行進(jìn)行記錄，即為虛擬機(jī)的編號(hào)，列代表的就是任務(wù)號(hào)。

例如，如果有編號(hào)0到9共10個(gè)任務(wù)，編號(hào)0到3共4個(gè)虛擬機(jī)，min（xij），其中j∈（0，3），i∈（0，9），代表第j個(gè)任務(wù)在第i號(hào)虛擬機(jī)上執(zhí)行。

將每一次迭代產(chǎn)生采樣個(gè)體表示的任務(wù)和虛擬機(jī)的對(duì)應(yīng)關(guān)系依次存儲(chǔ)在矩陣A中，就得到了CMAPSO算法的初始種群。

2.3尋優(yōu)迭代

根據(jù)2.2節(jié)產(chǎn)生的初始矩陣A對(duì)CMAPSO算法進(jìn)行初始化，能夠得到在解空間中離最優(yōu)解較近且分布均勻的解集，然后通過這個(gè)解集對(duì)CMAPSO算法進(jìn)行之后的迭代尋優(yōu)操作，使CMAPSO算法能夠較快收斂到質(zhì)量更高的解。

CMAPSO算法通過粒子群的速度和位移的變換，經(jīng)過多次的迭代搜索，使“粒子”向著個(gè)體最優(yōu)pBest（自身經(jīng)歷）和全局最優(yōu)gBest（社會(huì)經(jīng)歷）的方向進(jìn)行移動(dòng)。

粒子的速度更新公式為

Vg+1=ωVg+c1rand（）（pBest-rgrgxg）+

c2rand（）（gBest-rgrgxg）（19）

粒子的位移更新公式為

rgrgxg+1=rgrgxg+Vg+1（20）

在速度更新公式中，ω為慣性因子，當(dāng)它的值較大時(shí)，全局搜索能力強(qiáng)，當(dāng)它的值較小時(shí)，局部搜索能力強(qiáng)。c1為個(gè)體學(xué)習(xí)因子，表示對(duì)自身最優(yōu)解的學(xué)習(xí)能力，c2為群體學(xué)習(xí)因子，表示對(duì)當(dāng)前全局最優(yōu)解的學(xué)習(xí)能力。rand（）表示（0，1）之間的隨機(jī)數(shù)。

在CMAPSO算法求解模糊云計(jì)算資源調(diào)度問題時(shí)，式（20）中每一個(gè)粒子的位移代表一種調(diào)度方案，通過比較相應(yīng)的評(píng)價(jià)函數(shù)值，對(duì)粒子的速度和位移進(jìn)行更新。其中粒子的維度代表任務(wù)集的大小，每一維代表一個(gè)任務(wù)，每一維的取值代表該任務(wù)在哪一個(gè)虛擬機(jī)上執(zhí)行。

圖2對(duì)粒子與任務(wù)和虛擬機(jī)的關(guān)系進(jìn)行了舉例。

其中，0，1，2，3…，n代表n個(gè)任務(wù)，下面的3，1，m，0，…，2，代表每個(gè)任務(wù)在那一臺(tái)虛擬機(jī)上執(zhí)行。比如0號(hào)任務(wù)在3號(hào)虛擬機(jī)上執(zhí)行，1號(hào)任務(wù)在1號(hào)虛擬機(jī)上執(zhí)行，以此類推，得到一個(gè)粒子表示的任務(wù)和虛擬機(jī)的映射關(guān)系，即為一個(gè)調(diào)度方案。

CMAPSO算法求解模糊云計(jì)算調(diào)度模型時(shí)，使用評(píng)價(jià)函數(shù)對(duì)得到的調(diào)度方案進(jìn)行比較，然后進(jìn)行下一步的迭代搜索，直到找到最優(yōu)的解。

2.4CMAPSO算法流程與時(shí)間復(fù)雜度

在CMAPSO算法中，主要包括使用協(xié)方差矩陣生成矩陣A對(duì)粒子種群進(jìn)行初始化，CMAPSO算法的迭代尋優(yōu)操作等。

使用矩陣A對(duì)粒子種群進(jìn)行初始化，要考慮生成初始矩陣A時(shí)的時(shí)間復(fù)雜度。在生成初始矩陣A時(shí)，需要進(jìn)行三種函數(shù)的計(jì)算，分別為更新采樣種群，更新搜索步長(zhǎng)，更新協(xié)方差矩陣，而每一種函數(shù)的計(jì)算最壞的時(shí)間復(fù)雜度均為O（N3），所以生成CMAPSO算法的初始矩陣A的最壞時(shí)間復(fù)雜度為O（g×3N3），其中g(shù)為迭代次數(shù)，N為協(xié)方差矩陣C的行數(shù)。

CMAPSO算法在求解云計(jì)算資源調(diào)度問題時(shí)，迭代過程的最壞時(shí)間復(fù)雜度為O（taskNum×popsize×g），其中popsize代表粒子種群的大小。

算法中的其他操作，比如評(píng)價(jià)函數(shù)值的比較等操作，時(shí)間復(fù)雜度較小，與上述過程相比較，可以忽略不計(jì)。

綜上所述，本文提出的CMAPSO算法的時(shí)間復(fù)雜度為

T（n）=O（g×3N3）+O（taskNum×popsize×g）=

O（g×3N3）（21）

CMAPSO算法的流程圖如圖3所示。

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

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

為了驗(yàn)證本文提出的CMAPSO算法在求解模糊云計(jì)算資源調(diào)度方面的準(zhǔn)確性，使用云計(jì)算仿真平臺(tái)Cloudsim進(jìn)行仿真實(shí)驗(yàn)。使用文[17]的方法，生成任務(wù)集，每個(gè)任務(wù)的大小范圍為[3000，130000]，生成虛擬機(jī)集，虛擬機(jī)的執(zhí)行速度范圍為[300，1300]。根據(jù)任務(wù)的大小和虛擬機(jī)的執(zhí)行速度計(jì)算任務(wù)在不同虛擬機(jī)上的執(zhí)行時(shí)間。根據(jù)虛擬機(jī)的處理調(diào)度根據(jù)規(guī)則計(jì)算得出單位時(shí)間內(nèi)虛擬機(jī)的執(zhí)行成本。

經(jīng)過大量的反復(fù)實(shí)驗(yàn)，在過程中發(fā)現(xiàn)CMAPSO算法在迭代100左右時(shí)，能夠過得比較穩(wěn)定的解，所以將算法的迭代次數(shù)設(shè)置為100任務(wù)的規(guī)模分別為50，100，150。虛擬機(jī)的個(gè)數(shù)設(shè)置為5。

表1為實(shí)驗(yàn)過程中的參數(shù)設(shè)置。表2為實(shí)驗(yàn)過程中算法的參數(shù)設(shè)置。

在表2中個(gè)體學(xué)習(xí)因子和全體學(xué)習(xí)因子都設(shè)置為0.5，表示對(duì)當(dāng)前代的個(gè)體最優(yōu)和群體最優(yōu)的學(xué)習(xí)能力相同，時(shí)間因子t和成本因子c都設(shè)置為0.5，表示在求解評(píng)價(jià)函數(shù)時(shí)，對(duì)于時(shí)間和成本的考慮相同。

在實(shí)驗(yàn)過程中，除了解決云計(jì)算資源調(diào)度問題的算法不同之外，實(shí)驗(yàn)參數(shù)和實(shí)驗(yàn)環(huán)境均相同。

3.2數(shù)值實(shí)例

在本文中，為了驗(yàn)證本文使用CMAPSO算法在初始階段就具有距離最優(yōu)解較近的優(yōu)勢(shì)，使用下述實(shí)例進(jìn)行驗(yàn)證。

例如，在云計(jì)算資源調(diào)度中有任務(wù)數(shù)為10，虛擬機(jī)數(shù)為3時(shí)，使用隨機(jī)和初始矩陣A對(duì)粒子t和h分別進(jìn)行初始化，對(duì)得到的調(diào)度方案使用式（9）進(jìn)行評(píng)價(jià)。在實(shí)驗(yàn)中，隨機(jī)初始化粒子t，得到粒子的位置為rgrgxt{0，0，1，2，2，0，0，0，0，1}，此時(shí)它的評(píng)價(jià)函數(shù)為Res（P（t））=0.4112119。使用式（19）和式（20）對(duì)粒子t的速度和位置進(jìn)行迭代更新，繼續(xù)對(duì)解空間進(jìn)行搜索，得到的粒子的位置為rgrgxt{1，0，0，2，1，0，2，0，1，0}，此時(shí)的評(píng)價(jià)函數(shù)為Res（P（t））=0.3786563。通過2.1節(jié)種群初始化獲得的初始矩陣A對(duì)粒子h進(jìn)行初始化，得到其一個(gè)粒子h的位置為rgrgxh{2，2，1，0，1，0，0，2，0，1}，此時(shí)它的評(píng)價(jià)函數(shù)為Res（P（h））=0.2942045。根據(jù)式（19）和式（20）對(duì)粒子h的速度和位置進(jìn)行迭代更新，繼續(xù)對(duì)解空間進(jìn)行搜索，得到最終解為rgrgxh{1，2，0，1，1，2，0，0，2，1}，此時(shí)的評(píng)價(jià)函數(shù)為Res（P（h））=0.2763707。通過上述實(shí)例可以看出，使用CMAPSO算法得到的調(diào)度方案的評(píng)價(jià)函數(shù)值較小，而使用隨機(jī)初始化得到調(diào)度方案的評(píng)價(jià)函數(shù)值較大，粒子h相比于粒子t最終得到調(diào)度方案優(yōu)越性提升了約28%，并且在實(shí)驗(yàn)過程中發(fā)現(xiàn)CMAPSO算法的迭代次數(shù)相比提升了約20%。

通過該數(shù)值實(shí)例，可以了解本文提出的CMAPSO算法，并且對(duì)于該算法提出的必要性進(jìn)行了論證。

3.3算法性能分析

在本文中，為了驗(yàn)證本文算法的性能，使用反向世代距離[18]（inverted generational distance， IGD），超體積[19]（hypervolume， HV），準(zhǔn)確性度量指標(biāo)覆蓋率[20]（converage metric， CMetric）對(duì)CMAPSO算法，與NSGA算法[21]，NSGAⅡ算法[22]，NSGAⅢ算法[23]和MOEA/D算法[24]的性能進(jìn)行量化。表3所示為5種算法的性能對(duì)比結(jié)果。結(jié)果均使用平均值表示。

從表中的IGD值來看，算法CMAPSO具有最小的IGD值，說明CMAPSO得到的解的分布更加均勻。算法CMAPSO有最高的HV值，這也說明它得到的解的質(zhì)量更高。由于初始就獲得了高質(zhì)量的集合，從CMetric值可以看出，CMAPSO算法求得的解的收斂性也較優(yōu)。綜上，本文提出的CMAPSO算法能夠獲得較好的調(diào)度方案。

3.4模型對(duì)比

為了驗(yàn)證本文提出的針對(duì)不確定云資源調(diào)度模型的準(zhǔn)確性和實(shí)際性能，使用不同的任務(wù)規(guī)模，相同虛擬機(jī)規(guī)模對(duì)確定云計(jì)算資源調(diào)度模型和不確定云

計(jì)算資源調(diào)度模型進(jìn)行實(shí)驗(yàn)對(duì)比分析。圖4為兩種模型的評(píng)價(jià)函數(shù)對(duì)比。橫坐標(biāo)為任務(wù)數(shù)，縱坐標(biāo)為評(píng)價(jià)函數(shù)值。虛擬機(jī)數(shù)量均為5。

從圖4可以看出，不論任務(wù)規(guī)模多大，不確定云計(jì)算資源調(diào)度的評(píng)價(jià)函數(shù)值都比確定云計(jì)算資源調(diào)度的評(píng)價(jià)函數(shù)值高，這正是因?yàn)槿蝿?wù)執(zhí)行的不確定性導(dǎo)致的，所以在實(shí)驗(yàn)過程中需要考慮這種不確定性的存在。

3.5算法尋優(yōu)能力對(duì)比

為了驗(yàn)證本文提出的CMAPSO算法具有良好的尋優(yōu)性能，本文采用相同數(shù)據(jù)集，相同環(huán)境下的協(xié)方差矩陣自適應(yīng)進(jìn)化策略算法和PSO算法與它進(jìn)行對(duì)比分析。根據(jù)評(píng)價(jià)函數(shù)的取值來判定尋優(yōu)性能的好壞，算法的評(píng)價(jià)函數(shù)值越低，認(rèn)為該算法的尋優(yōu)性能越好。

圖5～7表示在任務(wù)數(shù)和虛擬機(jī)數(shù)分別為（50，5），（100，5），（150，5）時(shí)PSO算法，協(xié)方差矩陣自適應(yīng)進(jìn)化策略和CMAPSO算法的尋優(yōu)能力對(duì)比圖。橫坐標(biāo)代表算法的迭代次數(shù)，縱坐標(biāo)代表對(duì)應(yīng)的評(píng)價(jià)函數(shù)值。

從圖中可以看出，無論任務(wù)規(guī)模的大小，CMAPSO算法在解決云計(jì)算資源調(diào)度問題時(shí)，相比于其他兩種算法都有較好的尋優(yōu)性能。在圖中還可以看出，CMAPSO算法由于在初始搜索階段就具有質(zhì)量較高的解，所以初始搜索性能就高于其他兩種算法。而且由于這種優(yōu)勢(shì)，使得CMAPSO算法收斂到最優(yōu)解的迭代次數(shù)最少，收斂速度較快。

本文使用權(quán)重占比的方式對(duì)評(píng)價(jià)函數(shù)中時(shí)間和成本進(jìn)行比重控制，當(dāng)時(shí)間因子和成本因子均為0.5時(shí)，分別對(duì)PSO算法，CMAES算法，CMAPSO算法任務(wù)執(zhí)行總時(shí)間和總成本進(jìn)行記錄，執(zhí)行任務(wù)的虛擬機(jī)個(gè)數(shù)均為5，實(shí)驗(yàn)結(jié)果如圖8，圖9所示。圖中橫坐標(biāo)均表示任務(wù)數(shù)量，圖8中縱坐標(biāo)代表執(zhí)行總時(shí)間，圖9中縱坐標(biāo)代表執(zhí)行總成本。

從圖8和圖9中可以看出，使用3種算法對(duì)同一個(gè)數(shù)據(jù)集的任務(wù)執(zhí)行總時(shí)間和總成本進(jìn)行記錄，可以看出本文提出的CMAPSO算法求解雙目標(biāo)下的資源調(diào)度方案能夠使任務(wù)總的執(zhí)行時(shí)間最短，總執(zhí)行成本最低。

圖10表示3種算法間的負(fù)載均衡對(duì)比圖，橫坐標(biāo)表示算法在求解云計(jì)算資源調(diào)度時(shí)的任務(wù)規(guī)模與虛擬機(jī)規(guī)模，縱坐標(biāo)表示算法的負(fù)載均衡能力。

通過上述實(shí)驗(yàn)對(duì)比可知，CMAPSO算法在解決模糊云計(jì)算資源調(diào)度時(shí)，不僅具有較好的尋優(yōu)性能，而且算法的收斂速度也是較快的，在負(fù)載均衡方面，也能夠減輕虛擬機(jī)的工作壓力。可以看出，CMAPSO算法在整體上具有良好的性能。

4結(jié)語

本文的主要目標(biāo)是降低任務(wù)總的完成時(shí)間和執(zhí)行成本，對(duì)模糊云計(jì)算資源調(diào)度模型進(jìn)行求解。本文使用了一種混合優(yōu)化算法CMAPSO算法，結(jié)合協(xié)方差矩陣自適應(yīng)進(jìn)化策略和PSO算法的優(yōu)勢(shì)，使該算法的尋優(yōu)能力較好，并且尋優(yōu)速度較快，該算法還能夠提高負(fù)載均衡性能，使對(duì)資源的利用率提高。實(shí)驗(yàn)證明了CMAPSO算法能夠提高云計(jì)算資源調(diào)度的整體性能。

參 考 文 獻(xiàn)：

[1]SINGH S， CHANA I. A Survey on Resource Scheduling in Cloud Computing： Issues and Challenges[J]. Journal of Grid Computing， 2016， 14（2）：217.

[2]張雨， 李芳， 周濤. 云計(jì)算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2014， 50（6）：51.

ZHANG Yu， LI Fang， ZHOU Tao. Task Scheduling Algorithm Based on Genetic Ant Colony Algorithm in Cloud Computing Environment[J]. Computer Engineering and Applications， 2014， 50（6）：51.

[3]SADHASIVAM N， THANGARAJ P. Design of an Improved PSO Algorithm for Workflow Scheduling in Cloud Computing Environment[J]. Intelligent Automation & Soft Computing， 2016，31（8）：493.

[4]HU X X， ZHOU X W. Improved Ant Colony Algorithm on Scheduling Optimization of Cloud Computing Resources[J]. Applied Mechanics & Materials， 2014， 678：75.

[5]HASSAN M A， KACEM I， MARTIN S， et al. Genetic Algorithms for Job Scheduling in Cloud Computing[J]. Studies in Informatics & Control， 2015， 24（4）：387.

[6]CUNHA M， MARQUES J. A New Multiobjective Simulated Annealing Algorithm—MOSAGR： Application to the Optimal Design of Water Distribution Networks[J]. Water Resources Research， 2020， 56（3）：e2019WR025852.

[7]陳興國(guó)，徐修穎，陳康揚(yáng)，等. 基于CMAES集成學(xué)習(xí)方法的地表水質(zhì)分類[J]. 計(jì)算機(jī)科學(xué)與探索，2020（3）： 426.

CHEN Xingguo， XU Xiuying， CHEN Kangyang，et al. SurfaceWater Quality Classification via CMAES Ensemble Method[J]. Journal of Frontiers of Computer Science and Technology， 2020（3）： 426.

[8]黃亞飛， 梁昔明， 陳義雄. 求解全局優(yōu)化問題的正交協(xié)方差矩陣自適應(yīng)進(jìn)化策略算法[J]. 計(jì)算機(jī)應(yīng)用， 2012（4）：95.

HUANG Yafei， LIANG Ximing， CHEN Yixiong. Hybrid Orthogonal CMAES for Solving Global Optimization Problems[J]. journal of Computer Applications， 2012（4）：95.

[9]饒華， 王忠， 李欣. 基于CMAESSVR的WLAN室內(nèi)定位算法研究[J]. 計(jì)算機(jī)應(yīng)用研究， 2019， 36（8）：2514.

RAO Hua， WANG Zhong， LI Xin. Research on WLAN Indoor Positioning Algorithm Based on CMAESSVR[J]. Application Research of Computers， 2019， 36（8）：2514.

[10]王恩重， 陶傳奇. 基于改進(jìn)蟻群優(yōu)化算法的云計(jì)算調(diào)度方法[J]. 計(jì)算機(jī)與數(shù)字工程， 2019， 47（4）.

WANG Enzhong， TAO Chuanqi. Cloud Computing Scheduling Method Based on Improved Ant Colony Optimization Algorithm[J]. Computer & Digital Engineering， 2019， 47（4）.

[11]朱亞會(huì)， 陳丹， 莊毅. 云數(shù)據(jù)中心資源利用率均衡的虛擬機(jī)調(diào)度算法[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2017（2）：232.

ZHU Yahui， CHEN Dan， ZHUANG Yi. Virtual Machine Scheduling Algorithm for Resource Utilization Balanced in Cloud Data Center[J]. Minimicro Systems， 2017（2）：232.

[12]李成嚴(yán)， 曹克翰， 馮世祥，等. 不確定執(zhí)行時(shí)間的云計(jì)算資源調(diào)度[J]. 哈爾濱理工大學(xué)學(xué)報(bào)， 2019， 24（1）：89.

LI Chengyan， CAO Kehan， FENG Shixiang， et al. Resource Scheduling with Uncertain Execution Time in Cloud Computing[J]. Journal of Harbin University of Science and Technology， 2019， 24（1）：89.

[13]BALIN， SAVAS. Nonidentical Parallel Machine Scheduling with Fuzzy Processing Times Using Genetic Algorithm and Simulation[J]. International Journal of Advanced Manufacturing Technology， 2012， 61（9/12）： 1115.

[14]NIKOLAUS Hansen. The CMA Evolution Strategy： A Comparing Review[M]. Berlin：Springer， Towards a New Evolutionary Computation， 2006.

[15]鄧志誠(chéng)，孫輝，趙嘉，等.具有動(dòng)態(tài)子空間的隨機(jī)單維變異粒子群算法[J].計(jì)算機(jī)科學(xué)與探索， 2020，14（8）：1409.

DENG Zhicheng， SUN Hui， ZHAO Jia，et al. Stochastic SingleDimensional Mutated Particle Swarm Optimization with Dynamic Subspace[J]. Journal of Frontiers of Computer Science and Technology，2020，14（8）：1409.

[16]HANSEN N， OSTERMEIER A. Completely Derandomized SelfAdaptation in Evolution Strategies[J].Evolutionary Computation， 2001，9（2）：159.

[17]CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al. CloudSim： a Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[J]. Software Practice & Experience， 2010， 41（1）：23.

[18]MARGARITA Reyes Sierra， CARLOS Coello A. Coello. Improving PSOBased Multiobjective Optimization Using Crowding， Mutation and∈Dominance[C]// International Conference on Evolutionary MultiCriterion Optimization. Springer， Berlin， Heidelberg， 2005： 505.

[19]SCHTZE， Oliver， Hernández， Víctor Adrián Sosa， Trautmann H， et al. The Hypervolume Based Directed Search Method for Multiobjective Optimization Problems[J]. Journal of Heurs， 2016， 22（3）：1.

[20]LIU R C， LI J X， LIU J， et al. A Survey on Dynamic MultiObjective Optimization[J]. Chinese Journal of Computers， 2020，43（7）：1246.

[21]ZHENG J H， SHI Z Z， XIE Y. A Fast Multiobjective Genetic Algorithm Based on Clustering[J]. Journal of Computer Research and Development， 2004（7）：44.

[22]SAHMOUD S， TOPCUOGLU H R. Sensorbased Changedetection Schemes for Dynamic Multiobjective Optimization Problems[C]// 2016 IEEE Symposium Series on Computational Intelligence （SSCI）， 2016：1.

[23]MIRIAM A J， SAMINATHAN R， CHAKARAVARTHI S. Nondominated Sorting Genetic Algorithm （NSGAIII） for Effective Resource Allocation in Cloud[J]. Evolutionary Intelligence， 2020（2）：436.

[24]LI H， ZHANG Q F. MOEA/D： a Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Trans on Evolutionary Computation， 2007， 11（6）： 712.

（編輯：溫澤宇）