基于MGA-PSO的云計(jì)算多目標(biāo)任務(wù)調(diào)度

孫長(zhǎng)亞 王向文

1(上海電力大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 200090)2(上海電力大學(xué)電子與信息工程學(xué)院 上海 200090)

0 引 言

云計(jì)算的基礎(chǔ)設(shè)施規(guī)模比單一的物理設(shè)備大很多，但是其提供的虛擬資源仍然有限，面對(duì)龐大的云任務(wù)，如何高效地將子任務(wù)分配給虛擬資源，進(jìn)行合理的任務(wù)調(diào)度已成為一項(xiàng)必不可缺的研究課題[1-4]。先前解決云計(jì)算任務(wù)調(diào)度問題的各種努力主要針對(duì)完工時(shí)間[5-6]。隨著按需付費(fèi)模式的普及，用戶也會(huì)重點(diǎn)關(guān)注執(zhí)行成本，對(duì)云服務(wù)提供商而言，還需要考慮虛擬機(jī)的負(fù)載均衡。幾種經(jīng)典的調(diào)度算法雖然實(shí)現(xiàn)簡(jiǎn)單，但是缺點(diǎn)很明顯，如Min-Min算法[7]、Max-Min算法[8]和先進(jìn)先出(First In First Out，F(xiàn)IFO)算法[9]。前兩個(gè)算法未能有效利用資源，從而容易導(dǎo)致負(fù)載不均衡的問題；FIFO算法按任務(wù)提交順序安排資源，如果較早提交的任務(wù)占用大量計(jì)算資源，則后面較小的任務(wù)必須等待很長(zhǎng)時(shí)間。許多研究者使用啟發(fā)式算法解決云計(jì)算任務(wù)調(diào)度的問題。例如:文獻(xiàn)[10]提出了一種基于粒子群算法(PSO)的云任務(wù)調(diào)度方案，用于減少總執(zhí)行時(shí)間和任務(wù)傳輸時(shí)間，并且證明了PSO比遺傳算法運(yùn)行的更快，有效減少了任務(wù)的執(zhí)行時(shí)間，但是PSO可能會(huì)陷入局部最優(yōu)解，容易導(dǎo)致求解精度下降，進(jìn)而增加任務(wù)的完工時(shí)間和執(zhí)行成本；文獻(xiàn)[11]使用改進(jìn)的蟻群算法進(jìn)行云計(jì)算資源調(diào)度，通過信息素的累積和更新尋找較精確的解決方案，但是由于求解初期信息素匱乏，導(dǎo)致求解速率較慢，這樣可能會(huì)占用用戶大量時(shí)間，不能很好地滿足用戶的服務(wù)質(zhì)量需求；文獻(xiàn)[12]提出了一種基于最早完成時(shí)間和PSO的自適應(yīng)參數(shù)遺傳算法，交叉概率的參數(shù)根據(jù)當(dāng)前的演化狀態(tài)進(jìn)行自適應(yīng)，以促進(jìn)進(jìn)化并找到更好的解決方案，缺點(diǎn)是只考慮了最小化完工時(shí)間，優(yōu)化的目標(biāo)過于單一；文獻(xiàn)[13]將遺傳算法和蟻群算法融合用于云計(jì)算任務(wù)調(diào)度，提高了云計(jì)算資源調(diào)度的效率，但是參數(shù)較多，編程實(shí)現(xiàn)較為復(fù)雜，且沒有考慮云系統(tǒng)的負(fù)載均衡，任務(wù)過大或過多時(shí)，容易導(dǎo)致云系統(tǒng)運(yùn)行異常。

為了彌補(bǔ)傳統(tǒng)算法用于與計(jì)算任務(wù)調(diào)度的不足，本文綜合考慮任務(wù)完工時(shí)間、執(zhí)行成本、云系統(tǒng)負(fù)載均衡三個(gè)目標(biāo)，提出了一種混合微生物遺傳粒子群算法(MGA-PSO)用于云計(jì)算任務(wù)調(diào)度。該算法結(jié)合微生物遺傳算法(MGA)和PSO的長(zhǎng)處，在任務(wù)調(diào)度前期使用MGA縮小求解空間以提升尋優(yōu)速度；在任務(wù)調(diào)度后期使用動(dòng)態(tài)慣性權(quán)重的PSO進(jìn)一步尋找并快速收斂到最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，MGA-PSO算法可有效減少完工時(shí)間、降低執(zhí)行成本并平衡云數(shù)據(jù)中心虛擬機(jī)的負(fù)載。

1 云計(jì)算多目標(biāo)任務(wù)調(diào)度

云計(jì)算利用并行化技術(shù)處理大量任務(wù)，在數(shù)據(jù)中心利用虛擬化技術(shù)建立一定數(shù)量的虛擬機(jī)，根據(jù)用戶需求，將子任務(wù)分配到合適的虛擬機(jī)上執(zhí)行。通常采用Map/Reduce編程模型，通過Map(映射)和 Reduce(化簡(jiǎn))兩個(gè)階段， 將一個(gè)較大的任務(wù)分割成為很多較小的子任務(wù)，然后分配給若干個(gè)虛擬機(jī)并行執(zhí)行，最后返回運(yùn)行結(jié)果。該模型具有良好的擴(kuò)展性和容錯(cuò)性，一臺(tái)機(jī)器宕機(jī)時(shí)，可以迅速將任務(wù)轉(zhuǎn)移到另外一個(gè)節(jié)點(diǎn)運(yùn)行。本文只考慮子任務(wù)相互獨(dú)立的情況，整個(gè)任務(wù)調(diào)度框架可簡(jiǎn)化為圖1。

假設(shè)有t個(gè)相互獨(dú)立的任務(wù)，如：A={α1,α2,…,αt},其中αi(0≤i≤t)表示第i個(gè)任務(wù), 每個(gè)任務(wù)的大小為SIZEi；另假設(shè)云系統(tǒng)由p個(gè)高速互聯(lián)的虛擬機(jī)組成，如：B={β1,β2,…,βp}，其中βj(0≤j≤p)代表第j個(gè)虛擬機(jī)，每個(gè)虛擬機(jī)具備一定的處理能力MIPSj，使用MGA-PSO算法將個(gè)任務(wù)調(diào)度到p個(gè)虛擬機(jī)上以非搶占方式執(zhí)行(t>p)。

任務(wù)i在虛擬機(jī)j上執(zhí)行時(shí)間的計(jì)算公式如下：

Tij=SIZEi/MIPSj

(1)

虛擬機(jī)j的釋放時(shí)間RTj初始化為0，當(dāng)有任務(wù)執(zhí)行時(shí)其更新公式如下：

RTj=RTj+Tij

(2)

任務(wù)i是虛擬機(jī)j上的第一個(gè)任務(wù)時(shí)，其開始執(zhí)行時(shí)間定義為0，否則定義為虛擬機(jī)j的釋放時(shí)間RTj。

STij=RTj

(3)

任務(wù)i的完成時(shí)間為任務(wù)i在虛擬機(jī)j上的開始執(zhí)行時(shí)間與執(zhí)行時(shí)間之和，其公式如下：

FTij=STij+Tij

(4)

任務(wù)的最大完工時(shí)間為所有虛擬機(jī)釋放時(shí)間的最大值，其更新公式如下：

Makespan=max{RTj|?βj∈B}

(5)

云環(huán)境的負(fù)載均衡定義為所有虛擬機(jī)釋放時(shí)間的標(biāo)準(zhǔn)差，其公式表示如下：

(6)

給云數(shù)據(jù)中心的內(nèi)存、帶寬、處理器和存儲(chǔ)空間設(shè)置一定的單位價(jià)格，通過統(tǒng)計(jì)任務(wù)調(diào)度過程中各資源的使用量計(jì)算執(zhí)行成本Cost。

云任務(wù)的調(diào)度過程是多目標(biāo)優(yōu)化問題，所以本文定義適應(yīng)度函數(shù)為任務(wù)完工時(shí)間、執(zhí)行成本及云環(huán)境負(fù)載均衡的加權(quán)和，用于衡量云計(jì)算任務(wù)調(diào)度的性能，其公式表示如下：

fitness=λ1×Makespan+λ2×LB+λ3×Cost

(7)

式中：λ1+λ2+λ3=1，可以根據(jù)任務(wù)需求靈活地調(diào)整各權(quán)重的值。任務(wù)調(diào)度的最終目標(biāo)是最小化適應(yīng)度函數(shù)的值。

2 混合微生物遺傳粒子群算法

2.1 微生物遺傳算法

John Holland教授于1975年提出了基于種群進(jìn)化機(jī)制的遺傳算法(GA)，該算法提出了一個(gè)自然選擇的過程，隨著時(shí)間的推移會(huì)產(chǎn)生更好的解決方案，具有并行搜索、群體尋優(yōu)的特點(diǎn)，適用于大型空間的求解問題。

GA存在無法保留“好父母”的缺點(diǎn)：無論父母染色體多么優(yōu)秀，都不會(huì)保留，只能進(jìn)行交叉變異操作生成新的個(gè)體，但是新個(gè)體并不一定優(yōu)于父母，容易導(dǎo)致解的精度不夠。為克服此缺點(diǎn)，借鑒微生物遺傳算法(MGA)[14]的思想，在種群每次迭代過程中，隨機(jī)抽取兩個(gè)染色體作為父染色體并比較其適應(yīng)度，適應(yīng)度好的父染色體不做任何處理，只對(duì)適應(yīng)度差的父染色體進(jìn)行改進(jìn)的交叉操作和變異操作。如果變異后的子染色體適應(yīng)度優(yōu)于其父染色體，則將其與適應(yīng)度好的父染色體作為下一代置于新種群上，否則，保留原種群。這樣，可以有效保留種群中適應(yīng)度好的父代染色體，大大提高了求解的精度。

MGA流程如圖2所示。首先，通過隨機(jī)創(chuàng)建染色體對(duì)種群進(jìn)行初始化；其次，根據(jù)適應(yīng)度值進(jìn)行選擇操作，選擇一些染色體以創(chuàng)建新的種群；接著，隨機(jī)選擇兩個(gè)父代染色體進(jìn)行改進(jìn)的交叉操作，在適應(yīng)度好的父染色體上隨機(jī)截取一個(gè)基因交叉點(diǎn)i，將第1到i個(gè)基因片段替代適應(yīng)度差的父染色體對(duì)應(yīng)位置；然后，對(duì)改進(jìn)的交叉操作產(chǎn)生的子染色體進(jìn)行基本位變異操作，即隨機(jī)選擇一個(gè)新基因去替換原有基因；最后，計(jì)算染色體的適應(yīng)度，如果變異后的子染色體適應(yīng)度更好，則將其取代適應(yīng)度差的父染色體置于新種群上，否則，兩個(gè)父代染色體仍置于新種群上。整個(gè)過程持續(xù)進(jìn)行，直到滿足終止條件，選擇適應(yīng)度最好的染色體作為最優(yōu)解。

圖2 MGA流程

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

2.2.1標(biāo)準(zhǔn)粒子群算法

粒子群算法(PSO)[15]是一種基于群體智能的優(yōu)化算法，算法中的粒子類似于搜尋食物過程中飛行的鳥群，各個(gè)鳥群信息共享，它們總是搜索目前離食物最近鳥的周圍區(qū)域，根據(jù)飛行經(jīng)驗(yàn)去尋找食物。PSO的設(shè)計(jì)思想就是基于這種信息共享機(jī)制，任意時(shí)刻每個(gè)粒子位置都受個(gè)體最佳位置和問題空間中全局最佳位置的影響。PSO中粒子的性能可通過適應(yīng)度函數(shù)來測(cè)量，根據(jù)適應(yīng)度值判斷粒子的好壞在每一次迭代中對(duì)粒子進(jìn)行優(yōu)化。為描述粒子群算法，相關(guān)參數(shù)定義見表1，算法中粒子速度和位置的更新公式如下：

表1 粒子群算法相關(guān)參數(shù)定義

(8)

(9)

式(8)右側(cè)可以拆分為三部分：1) “慣性”，即粒子前一次迭代時(shí)速度的經(jīng)驗(yàn)；2) “自我認(rèn)知”，表示粒子當(dāng)前位置與自身最佳位置的距離；3) “群體經(jīng)驗(yàn)”，表示粒子當(dāng)前位置與種群整體最佳位置的距離。PSO沒有MGA的交叉、變異操作，需要設(shè)置的參數(shù)較少，編程實(shí)現(xiàn)簡(jiǎn)單且收斂速度快，可以用來加快求解速度。

2.2.2動(dòng)態(tài)慣性權(quán)重的粒子群算法

慣性權(quán)重ω的取值影響PSO的性能。ω的值較大，有利于全局搜索，可以加快求解速度；ω的值較小，有利于局部搜索，能夠提高解的精度。標(biāo)準(zhǔn)PSO中慣性權(quán)重ω的取值固定，不利于在算法運(yùn)行過程中實(shí)現(xiàn)全局搜索和局部搜索的平衡。

在PSO運(yùn)行的早期，粒子相對(duì)分散，具有較好的多樣性，這時(shí)應(yīng)該保持較大的慣性權(quán)重值，以增強(qiáng)算法的全局搜索能力；在算法運(yùn)行的后期，粒子越來越聚集，這時(shí)應(yīng)該保持較小的慣性權(quán)重值，以改善算法的局部搜索能力。很多算法將慣性權(quán)重設(shè)置為隨迭代次數(shù)的增加線性遞減，在一定程度上提高了算法的性能，但是線性遞減策略對(duì)于動(dòng)態(tài)系統(tǒng)的效果并不理想。因此，提出一種隨迭代次數(shù)非線性遞減的動(dòng)態(tài)慣性權(quán)重策略，其數(shù)學(xué)公式描述為：

(10)

式中：ωmax表示慣性權(quán)重的最大值；ωmin表示慣性權(quán)重的最小值；n為當(dāng)前迭代次數(shù)；N為最大迭代次數(shù)；α1、α2、α3為控制因子，對(duì)慣性權(quán)重進(jìn)行調(diào)節(jié)，保證算法運(yùn)行前期具有較大的權(quán)重值，加強(qiáng)全局搜索，從而加快求解速度，在算法運(yùn)行后期，使權(quán)重值快速減小，加強(qiáng)局部搜索，從而提高解的精度。

2.3 混合微生物遺傳粒子群算法

本文將MGA和改進(jìn)的PSO融合，形成混合微生物遺傳粒子群算法(MGA-PSO)用于云計(jì)算任務(wù)調(diào)度。在任務(wù)調(diào)度前期，使用MGA處理初始種群，因?yàn)镸GA找到較精確的解需要訓(xùn)練很長(zhǎng)的時(shí)間，所以本文提出：只迭代較少的次數(shù)以縮小求解范圍，無須找到較精確的解決方案。在任務(wù)調(diào)度后期，利用PSO快速收斂到最優(yōu)解的優(yōu)點(diǎn)，使用改進(jìn)的PSO對(duì)上一階段產(chǎn)生的解決方案進(jìn)一步優(yōu)化，找到最優(yōu)的解決方案，這一階段可以迭代多次，從而提高解的精度。MGA全局搜索能力強(qiáng)的優(yōu)點(diǎn)，可大大縮小求解范圍，提高解的精度，避免PSO在進(jìn)一步優(yōu)化解決方案時(shí)陷入局部最優(yōu)解。而PSO快速收斂到最優(yōu)解的優(yōu)點(diǎn)，減少了云計(jì)算任務(wù)調(diào)度的時(shí)間，彌補(bǔ)了MGA需要較長(zhǎng)時(shí)間找到精確解的缺點(diǎn)。

MGA-PSO算法用于云計(jì)算任務(wù)調(diào)度之前，需要建立云計(jì)算任務(wù)調(diào)度的解決方案與算法中染色體和粒子的對(duì)應(yīng)關(guān)系。假設(shè)云系統(tǒng)有8個(gè)任務(wù)和3個(gè)虛擬機(jī)，在使用MGA階段，每個(gè)染色體由代表虛擬機(jī)的一些基因組成，染色體的長(zhǎng)度等于云任務(wù)的數(shù)量，該階段可以定義染色體的長(zhǎng)度為8，基因的種類為3。在使用改進(jìn)的PSO階段，粒子是要分配的任務(wù)，粒子的維度是要分配的任務(wù)數(shù)，分配給粒子的每個(gè)維度的值是虛擬機(jī)編號(hào)，該階段可以定義粒子的維度為8，每個(gè)維度的值只能取0、1或2。

圖3展示了這種對(duì)應(yīng)關(guān)系，它既可以表示一條染色體，又可以表示一個(gè)粒子。當(dāng)表示一條染色體時(shí)，第0個(gè)基因的值為1，代表任務(wù)0被分配給虛擬機(jī)1；第3個(gè)基因的值為2，代表任務(wù)3被分配給虛擬機(jī)2。當(dāng)表示為一個(gè)粒子時(shí)，第1維取值為0，代表任務(wù)1被分配給虛擬機(jī)0；第7維取值為2，代表任務(wù)7被分配給虛擬機(jī)2。

圖3 一條染色體或一個(gè)粒子

MGA-PSO算法用于云計(jì)算任務(wù)調(diào)度的流程如圖4所示，其執(zhí)行步驟總結(jié)如下。

圖4 MGA-PSO算法流程

1) 生成隨機(jī)種群并指定迭代次數(shù)，種群表示任務(wù)調(diào)度的一系列解決方案，每個(gè)解決方案是云任務(wù)在可用虛擬機(jī)上的分布。

2) 使用MGA縮小求解范圍，云計(jì)算任務(wù)調(diào)度的解決方案在這里被稱為染色體，通過MGA算子(即選擇、交叉、變異)在每次迭代中保留適應(yīng)度較好的染色體，將得到的染色體傳遞給改進(jìn)的PSO。

3) 使用改進(jìn)的PSO進(jìn)一步優(yōu)化解決方案，來自MGA的染色體被稱為粒子，在每次迭代中通過式(8)-式(10)逐漸增強(qiáng)粒子。

4) 根據(jù)式(7)選擇具有最佳適應(yīng)度的粒子作為云計(jì)算任務(wù)調(diào)度的解決方案。

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

3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

為了評(píng)估MGA-PSO算法的性能，使用墨爾本大學(xué)開發(fā)的CloudSim[16]云仿真平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，其運(yùn)行的硬件環(huán)境為Intel i7處理器，16 GB DDR4內(nèi)存，1 TB硬盤空間，Windows 10系統(tǒng)。CloudSim支持云計(jì)算的研究與開發(fā)，用戶編寫的算法可以在此平臺(tái)上測(cè)試運(yùn)行，減少了搭建云平臺(tái)的時(shí)間和成本。本文的仿真實(shí)驗(yàn)將MGA-PSO算法用于云計(jì)算任務(wù)調(diào)度并與現(xiàn)有的云任務(wù)調(diào)度算法作比較，它們是GA和PSO。另外編寫一個(gè)和本文算法原理相同的GA-PSO算法，驗(yàn)證對(duì)GA和PSO改進(jìn)的必要性。

實(shí)驗(yàn)中四個(gè)算法各自運(yùn)行22次，去除實(shí)驗(yàn)結(jié)果的最大值和最小值，取剩下20次實(shí)驗(yàn)結(jié)果的平均值作為有效比較數(shù)據(jù)。算法中的相關(guān)參數(shù)設(shè)置見表2。

表2 算法的相關(guān)參數(shù)

續(xù)表2

3.2 性能分析

圖5顯示了四種算法用于云計(jì)算任務(wù)調(diào)度時(shí)的尋優(yōu)效果，任務(wù)數(shù)設(shè)置為500。可以看出，GA和PSO用于云計(jì)算任務(wù)調(diào)度的尋優(yōu)效果一般，過早的陷入了局部最優(yōu)。GA-PSO算法和MGA-PSO算法的適應(yīng)度有一段時(shí)間沒有變化，可能陷入了局部最優(yōu)，但是隨著迭代次數(shù)的增加，都能迅速跳出局部最優(yōu)，并且能夠快速找到最優(yōu)解。本文MGA-PSO算法最終的適應(yīng)度最低，尋優(yōu)效果最好，具有較強(qiáng)的全局搜索能力。

圖5 四種算法用于云計(jì)算任務(wù)調(diào)度的尋優(yōu)曲線

圖6和圖7顯示了小規(guī)模任務(wù)下四種算法完工時(shí)間和執(zhí)行成本的對(duì)比效果，任務(wù)數(shù)設(shè)置為20、40、60、80、100。從圖6可以看出，GA和PSO用于云計(jì)算任務(wù)調(diào)度會(huì)花費(fèi)較多的時(shí)間，當(dāng)任務(wù)數(shù)增加時(shí)，GA的完工時(shí)間增幅最快。整體上MGA-PSO算法的完工時(shí)間低于GA-PSO算法，該結(jié)果是因?yàn)樗岢鯩GA在迭代過程中保留了適應(yīng)度好的父代染色體，提高了解的精度，能以更好的方式收斂到解決方案。從圖7可以看出，GA的執(zhí)行成本最高，可能原因是發(fā)生了“早熟”收斂；MGA-PSO算法和GA-PSO算法及PSO用于小規(guī)模任務(wù)調(diào)度的執(zhí)行成本相差不大，這種微小的差異是由于所提出的混合算法主要依賴于PSO將解決方案收斂到最優(yōu)解，任務(wù)規(guī)模越小差異越小。

圖6 小規(guī)模任務(wù)四種算法的完工時(shí)間

圖7 小規(guī)模任務(wù)四種算法的執(zhí)行成本

圖8和圖9顯示了大規(guī)模云任務(wù)下四種算法完工時(shí)間和執(zhí)行成本的對(duì)比效果，任務(wù)數(shù)設(shè)置為200、400、600、800、1 000。從圖8可以看出，進(jìn)行大規(guī)模云任務(wù)調(diào)度時(shí)， MGA-PSO算法和GA-PSO算法在完工時(shí)間方面具有較大優(yōu)勢(shì)，隨著任務(wù)規(guī)模的增加，MGA-PSO算法的完工時(shí)間明顯低于GA-PSO算法。這是由于任務(wù)規(guī)模變大，生成的初始種群更加隨機(jī)，在MGA-PSO算法前期能保留較多優(yōu)秀的父代染色體，大大提高了解的精度。從圖9可以看出，在執(zhí)行成本方面，當(dāng)任務(wù)調(diào)度時(shí)，任務(wù)規(guī)模越大，MGA-PSO算法優(yōu)勢(shì)越明顯。這是因?yàn)閯?dòng)態(tài)慣性權(quán)重的PSO的改進(jìn)有效平衡了算法的全局搜索能力和局部搜索能力，能夠找到更為合適的解決方案。

圖8 大規(guī)模任務(wù)四種算法的完工時(shí)間

圖9 大規(guī)模任務(wù)四種算法的執(zhí)行成本

圖10為四種算法用于云計(jì)算任務(wù)調(diào)度時(shí)的虛擬機(jī)負(fù)載均衡對(duì)比效果，任務(wù)數(shù)設(shè)置為20、80、200、1 000。可以看出MGA-PSO算法的負(fù)載均衡效果比GA和PSO好很多，這是因?yàn)镸GA-PSO算法將任務(wù)完工時(shí)間、執(zhí)行成本、云系統(tǒng)負(fù)載均衡三個(gè)目標(biāo)作為任務(wù)執(zhí)行時(shí)虛擬機(jī)選擇的依據(jù)，總是選擇最合適的虛擬機(jī)來執(zhí)行任務(wù)，而不僅僅關(guān)注虛擬機(jī)的處理能力，這可能會(huì)選擇處理能力稍弱的虛擬機(jī)處理云任務(wù)，并減慢云任務(wù)的整體執(zhí)行速度(即增加完工時(shí)間)，但是在其他方面會(huì)有改善，例如虛擬機(jī)負(fù)載更加均衡，執(zhí)行成本更低。靈活地調(diào)整適應(yīng)度函數(shù)中各權(quán)重的值可以滿足不同方面的需求。

圖10 虛擬機(jī)負(fù)載均衡效果對(duì)比

無論是在完工時(shí)間、執(zhí)行成本還是虛擬機(jī)負(fù)載均衡效果方面，MGA-PSO算法的調(diào)度性能都優(yōu)于同種思想的GA-PSO算法，可見對(duì)GA和PSO的改進(jìn)提升了云計(jì)算任務(wù)調(diào)度的性能。

4 結(jié) 語

針對(duì)GA和PSO各自的優(yōu)缺點(diǎn)，本文將MGA(“升級(jí)版”GA)與改進(jìn)的PSO組合成MGA-PSO算法用于云計(jì)算任務(wù)調(diào)度。該算法充分考慮了體現(xiàn)用戶服務(wù)質(zhì)量的完工時(shí)間、執(zhí)行成本和云系統(tǒng)負(fù)載均衡三個(gè)目標(biāo)，并根據(jù)這些目標(biāo)建立適應(yīng)度函數(shù)作為算法運(yùn)行時(shí)虛擬機(jī)選擇的依據(jù)。仿真結(jié)果表明，MGA-PSO算法在完工時(shí)間、執(zhí)行成本和負(fù)載均衡方面都優(yōu)于GA、PSO和GA-PSO算法，能夠滿足用戶的服務(wù)質(zhì)量需求，有效提高云計(jì)算任務(wù)調(diào)度的效率。