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

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

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

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

DOI：10.15938/j.jhust.2022.01.005

中圖分類號： TP399? ? 文獻標(biāo)志碼： A? ? 文章編號： 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引言

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

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

現(xiàn)階段，對于智能算法的研究是解決云計算資源調(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)點，而且PSO算法在搜索過程中，會將當(dāng)前的全局最優(yōu)和局部最優(yōu)都進行“記憶”，這有益于粒子群在之后的尋優(yōu)搜索。但是粒子群算法使用的是隨機初始化的方式，這就可能導(dǎo)致粒子在解空間中可能存在分布不均勻或者粒子的擬合度過高的問題，不利于粒子種群的尋優(yōu)。

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

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

問題的模型進行描述，第二部分對CMAPSO算法進行描述，第三部分在仿真平臺上進行實驗，第四部分對實驗結(jié)果進行總結(jié)分析并給出結(jié)論。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)三角模糊數(shù)的隸屬函數(shù)將式（1）轉(zhuǎn)換為模糊模型進行求解。根據(jù)可分解性，在式（9）中，模糊之后的評價函數(shù)的3個端點PL，PM，PR與模糊執(zhí)行時間的3個端點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）是對模糊數(shù)取平均值，公式（11）是對模糊數(shù)取標(biāo)準(zhǔn)差，二者都是對模糊數(shù)進行去模糊化處理。使用文[13]中提到的對模糊數(shù)進行排序的方法，對評價函數(shù)進行均值和方差的計算，如果該評價函數(shù)的模糊數(shù)的平均值較高，方差較低，那么認(rèn)為該評價函數(shù)對應(yīng)的調(diào)度方案越好。

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

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

min{Pη+Pμ}（12）

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

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

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

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

2CMAPSO算法

2.1算法思想

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

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

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

2.2種群初始化

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

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

使用協(xié)方差自適應(yīng)進化策略求解云資源調(diào)度問題，主要需要對協(xié)方差矩陣C進行初始化，初始矩陣C=I∈RN×N，然后根據(jù)該初始協(xié)方差矩陣更新逐步對搜索種群進行更新，得到搜索種群rgrgx，根據(jù)該搜索種群獲取任務(wù)對應(yīng)的虛擬機編號。然后根據(jù)該搜索種群可以對協(xié)方差矩陣C進行迭代更新，重復(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個個體;m代表群體均值，m=∑μi=1ωirgrgxi：λ（其中∑μi=1ωi=1）;B矩陣的列向量是協(xié)方差矩陣C的特征向量正交基;D的對角元素是由特征向量C的特征值的平方根構(gòu)成的對角陣。

通過式（15）計算進化路徑pathσ。利用進化路徑對進化步長進行累積控制。

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

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

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

全局步長的更新公式為

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

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

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

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

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

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

對于協(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）中對應(yīng)參數(shù)，對協(xié)方差矩陣C進行更新，根據(jù)更新后的矩陣重新獲取搜索種群rgrgx，得到相應(yīng)的調(diào)度方案。

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

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

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

2.3尋優(yōu)迭代

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

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

粒子的速度更新公式為

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

c2rand（）（gBest-rgrgxg）（19）

粒子的位移更新公式為

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

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

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

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

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

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

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

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

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

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

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

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

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

O（g×3N3）（21）

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

3仿真實驗

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

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

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

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

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

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

3.2數(shù)值實例

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

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

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

3.3算法性能分析

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

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

3.4模型對比

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

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

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

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

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

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

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

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

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

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

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

4結(jié)語

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

參 考 文 獻：

[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]張雨， 李芳， 周濤. 云計算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[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]陳興國，徐修穎，陳康揚，等. 基于CMAES集成學(xué)習(xí)方法的地表水質(zhì)分類[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]. 計算機應(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]. 計算機應(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]王恩重， 陶傳奇. 基于改進蟻群優(yōu)化算法的云計算調(diào)度方法[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]朱亞會， 陳丹， 莊毅. 云數(shù)據(jù)中心資源利用率均衡的虛擬機調(diào)度算法[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í)行時間的云計算資源調(diào)度[J]. 哈爾濱理工大學(xué)學(xué)報， 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]鄧志誠，孫輝，趙嘉，等.具有動態(tài)子空間的隨機單維變異粒子群算法[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.

（編輯：溫澤宇）