一種用于云計(jì)算資源調(diào)度的改進(jìn)遺傳算法

劉　峰，畢　利，楊　軍

（1.寧夏大學(xué)數(shù)學(xué)計(jì)算機(jī)學(xué)院，銀川　750021；2.寧夏大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)管理中心，銀川　750021）

一種用于云計(jì)算資源調(diào)度的改進(jìn)遺傳算法

劉峰1，畢利1，楊軍2

（1.寧夏大學(xué)數(shù)學(xué)計(jì)算機(jī)學(xué)院，銀川750021；2.寧夏大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)管理中心，銀川750021）

針對(duì)輪詢調(diào)度算法、遺傳算法和模擬退火算法在云計(jì)算資源調(diào)度中存在收斂速度慢、易早熟和資源負(fù)載不均衡等問題，提出了一種基于模擬退火思想的改進(jìn)遺傳算法（simulated annealing improved genetic algorithm：SAIGA）；改進(jìn)算法設(shè)計(jì)了基于任務(wù)平均完成時(shí)間和負(fù)載均衡的雙適應(yīng)度函數(shù)和自適應(yīng)的交叉變異概率函數(shù)，允許算法在退火過程中以一定概率接受劣質(zhì)解從而避免早熟現(xiàn)象的發(fā)生，將虛擬資源上任務(wù)分配數(shù)的標(biāo)準(zhǔn)差作為選擇個(gè)體的依據(jù)來實(shí)現(xiàn)節(jié)點(diǎn)的負(fù)載均衡；仿真結(jié)果表明，改進(jìn)算法與上述算法相比，在任務(wù)平均完成時(shí)間、資源利用率以及收斂速度上表現(xiàn)得更優(yōu)越，能夠較快地找到資源最優(yōu)調(diào)度方案，具有較好的可行性和實(shí)用性。

云計(jì)算；輪詢調(diào)度；模擬退火思想；改進(jìn)遺傳算法；負(fù)載均衡

0　引言

云計(jì)算作為繼網(wǎng)格計(jì)算、并行計(jì)算和分布式計(jì)算之后的新興計(jì)算模式，被高校、科研機(jī)構(gòu)以及商業(yè)組織進(jìn)行了大量的研究。中國(guó)網(wǎng)格計(jì)算、云計(jì)算專家劉鵬給出如下定義：“云計(jì)算將計(jì)算任務(wù)分布在大量計(jì)算機(jī)構(gòu)成的資源池上，使各種應(yīng)用系統(tǒng)能夠根據(jù)需要獲取計(jì)算力、存儲(chǔ)空間和各種軟件服務(wù)［1］”。然而，云計(jì)算服務(wù)的核心問題是資源的調(diào)度，其服務(wù)質(zhì)量的好壞取決于調(diào)度效率的高低，因此資源調(diào)度一直是云計(jì)算研究領(lǐng)域重點(diǎn)和難點(diǎn)［2］。

傳統(tǒng)資源調(diào)度算法大都是一些靜態(tài)算法，如貪心算法、輪詢調(diào)度算法等，這類方法對(duì)于少量任務(wù)的調(diào)度可以獲得較好的調(diào)度方案。隨著任務(wù)數(shù)的不斷增加，云計(jì)算系統(tǒng)的復(fù)雜性增大，傳統(tǒng)方法存在任務(wù)完成時(shí)間過長(zhǎng)、節(jié)點(diǎn)間負(fù)載不均衡和資源利用率低等缺點(diǎn)［3-4］。目前，人工智能技術(shù)的日趨成熟，智能算法越來越多地被用于資源調(diào)度中，成為當(dāng)前研究的熱點(diǎn)。

劉瑜等［5］提出了基于最優(yōu)跨度和負(fù)載均衡改進(jìn)遺傳算法的資源調(diào)度策略，考慮到云計(jì)算任務(wù)的數(shù)量大和復(fù)雜性，設(shè)計(jì)了基于資源數(shù)的編碼方式，在算法接近收斂階段自適應(yīng)調(diào)節(jié)最優(yōu)跨度適應(yīng)度函數(shù)來提高算法的收斂速度。袁浩等［6］提出了一種基于社會(huì)力群的智能優(yōu)化算法，通過模擬人群的擁擠退讓行為尋找使任務(wù)總時(shí)間最小的調(diào)度方案。徐文忠［7］等提出了一種新的基于遺傳算法的關(guān)于虛擬機(jī)負(fù)載均衡的調(diào)度策略，但沒有考慮到任務(wù)平均完成時(shí)間指標(biāo)，不能滿足用戶對(duì)任務(wù)響應(yīng)時(shí)間的需求。李建鋒等［8］設(shè)計(jì)了雙適應(yīng)度函數(shù)去優(yōu)化資源調(diào)度過程，尋求使總?cè)蝿?wù)完成時(shí)間和任務(wù)平均完成時(shí)間都較小的調(diào)度方案，并取得了不錯(cuò)的效果。薛玉［9］提出一種基于混沌粒子群算法的云資源調(diào)度模型，把資源的負(fù)載均衡度作為要優(yōu)化的目標(biāo)函數(shù)，在尋優(yōu)過程中人工引入混沌機(jī)制對(duì)粒子進(jìn)行擾動(dòng)，通過粒子間的信息交流與共享，尋求調(diào)度最優(yōu)解。鄔海艷［10］提出了基于元胞自動(dòng)機(jī)模型改進(jìn)遺傳算法用于云資源調(diào)度，其主要作用于遺傳算法的選擇和交叉操作中，根據(jù)演化規(guī)則自適應(yīng)調(diào)節(jié)元胞與鄰居元胞的狀態(tài)，獲取最大適應(yīng)度值個(gè)體。Gao等［11］提出一種以任務(wù)完成時(shí)間、系統(tǒng)吞吐量為優(yōu)化目標(biāo)的蟻群算法構(gòu)建云計(jì)算資源調(diào)度模型，在任務(wù)總完成時(shí)間上取得不錯(cuò)的效果，但資源的利用率不高。Zhan Zhi-Hui等［12］提出了基于Min-min和上Max-min方法的負(fù)載均衡感知遺傳算法（LAGA），通過在適應(yīng)度函數(shù)中引入時(shí)間負(fù)載均衡模型（TLB）選擇優(yōu)勢(shì)個(gè)體，生成資源節(jié)點(diǎn)負(fù)載更均衡的調(diào)度方案，僅考慮了資源的負(fù)載情況，卻對(duì)犧牲了算法的收斂速度。

針對(duì)以上問題，本文結(jié)合模擬退火的思想來改進(jìn)遺傳算法在云計(jì)算資源中的調(diào)度，提出了基于任務(wù)平均完成時(shí)間和負(fù)載均衡的雙適應(yīng)度函數(shù)，設(shè)計(jì)自適應(yīng)的交叉和變異概率函數(shù)，使算法在尋優(yōu)時(shí)以一定概率接受劣質(zhì)解，減小改進(jìn)算法收斂到局部最優(yōu)解的可能性，同時(shí)采用基于資源節(jié)點(diǎn)數(shù)作為染色體的總長(zhǎng)度，每個(gè)資源所映射的任務(wù)總數(shù)和任務(wù)編號(hào)作為基因值的編碼方式，加快了算法的收斂速度，提高了算法的尋優(yōu)能力。

1　云計(jì)算資源調(diào)度問題描述

在云計(jì)算平臺(tái)上，管理者利用虛擬化技術(shù)把計(jì)算機(jī)的物理資源抽象為統(tǒng)一的虛擬資源，統(tǒng)一的虛擬資源又被分配到相互獨(dú)立的虛擬機(jī)上，而云計(jì)算中的資源調(diào)度問題就是利用一種調(diào)度策略把大量的計(jì)算任務(wù)分配到虛擬機(jī)上，實(shí)現(xiàn)虛擬資源的最大化利用。具體的講，就是如何把云計(jì)算中大量的計(jì)算任務(wù)根據(jù)一定的調(diào)度策略分配到最佳虛擬資源上，保證最少的任務(wù)完成時(shí)間和最大的資源利用率，云計(jì)算資源調(diào)度管理模型如圖1。

圖1　云計(jì)算資源調(diào)度管理模型

云計(jì)算資源調(diào)度包括數(shù)據(jù)中心D=｛d1，d2，…，dm｝

虛擬資源V=｛vm1，vm2，…，vmm｝、計(jì)算任務(wù)T=｛t1，t2，…，tn｝以及它們之間的映射關(guān)系。云計(jì)算資源調(diào)度模型可描述為：S=｛T，V，D，Mtv，Mvd｝（1）式中，Mtv為任務(wù)與虛擬資源之間的映射關(guān)系，Mvd為虛擬機(jī)與數(shù)據(jù)中心的之間的映射關(guān)系。根據(jù)上述用戶任務(wù)-虛擬資源之間的映射關(guān)系，本文用二維數(shù)組統(tǒng)計(jì)每個(gè)任務(wù)在每個(gè)虛擬資源上的預(yù)計(jì)完成執(zhí)行時(shí)間ETC（Excepted Time To Completion）。

其中：ETCij=cloudlet［i］.length/vm［j］.mips，表示第i個(gè)任務(wù)在第j個(gè)資源上的預(yù)計(jì)執(zhí)行時(shí)間。設(shè)Start（i，j）為任務(wù)ti在vmj上的開始執(zhí)行時(shí)間。則ti在vmj上的完成時(shí)間見式（3）。Finish（i，j）=Start（i，j）+ETCij（3）那么vmj上全部任務(wù)的完成時(shí)間見式 （4）（5）。

式（5）中，cij=1表示任務(wù)ti在vmj上執(zhí)行，cij=0表示ti不在vmj上執(zhí)行。

對(duì)于用戶全部計(jì)算任務(wù)T= ｛t1，t2，…，tn｝的任務(wù)平均完成時(shí)間見式（6）。

對(duì)于云計(jì)算資源的調(diào)度問題，即求使式（6）值最小的解，因此本文的目標(biāo)函數(shù)見式（7）。

2　遺傳算法與模擬退火思想的融合設(shè)計(jì)

2.1模擬退火思想

2.2基于模擬退火思想的改進(jìn)遺傳算法設(shè)計(jì)

2.2.1染色體編碼與種群初始化

在任務(wù)調(diào)度的問題中，傳統(tǒng)遺傳算法通常將任務(wù)總數(shù)作為染色體基因串的長(zhǎng)度，每個(gè)任務(wù)對(duì)應(yīng)的資源ID作為染色體的基因值。但是云計(jì)算環(huán)境中任務(wù)的總數(shù)遠(yuǎn)遠(yuǎn)大于資源節(jié)點(diǎn)的個(gè)數(shù)，如果把任務(wù)總數(shù)作為染色體基因串的長(zhǎng)度，會(huì)導(dǎo)致算法收斂速度慢，找到最優(yōu)解的時(shí)間過長(zhǎng)。因此本文對(duì)染色體的編碼方式進(jìn)行了改進(jìn)，將資源節(jié)點(diǎn)的數(shù)量作為染色體基因串的長(zhǎng)度，每個(gè)資源所映射的任務(wù)總數(shù)和任務(wù)編號(hào)作為染色體基因值，這種編碼方式可以加快算法的收斂速度。本文采用資源——任務(wù)的間接編碼方式，先對(duì)染色體進(jìn)行預(yù)編碼，設(shè)有n個(gè)任務(wù)，M個(gè)資源節(jié)點(diǎn)，如下產(chǎn)生一條染色體。

｛3，1，1，2，3，…，m-1，m，m-1｝

表示第1、5個(gè)任務(wù)分配到第3個(gè)資源上，第2、3個(gè)任務(wù)分配到第1個(gè)資源上，第n-2，n-1個(gè)任務(wù)分配到第m-1資源上，第n個(gè)任務(wù)分配到第m個(gè)資源上。接著對(duì)該染色體進(jìn)行二次編碼，則染色體基因串的長(zhǎng)度為資源總數(shù)m，染色體基因值為每個(gè)資源節(jié)點(diǎn)分配任務(wù)的總數(shù)和任務(wù)ID，二次處理后的染色體見表1。

表1　二次處理后染色體的編碼方式

在對(duì)染色體進(jìn)行編碼后，接著對(duì)種群進(jìn)行初始化，本文采用隨機(jī)方式產(chǎn)生N個(gè)染色體。

2.2.2基于任務(wù)平均完成時(shí)間和負(fù)載均衡的雙適應(yīng)度函數(shù)設(shè)計(jì)

基于任務(wù)平均完成時(shí)間的適應(yīng)度函數(shù)見式（9）。

式（9）表示第k個(gè)染色體上所有任務(wù)在節(jié)點(diǎn)j上平均執(zhí)行時(shí)間。在任務(wù)調(diào)度的過程中，我們還需要考慮資源負(fù)載均衡問題，節(jié)點(diǎn)負(fù)載較均衡使得資源利用率較高，避免計(jì)算能力高的節(jié)點(diǎn)出現(xiàn)負(fù)荷同時(shí)能力低的節(jié)點(diǎn)被閑置。采用資源節(jié)點(diǎn)上任務(wù)分配數(shù)的標(biāo)準(zhǔn)差來衡量節(jié)點(diǎn)的負(fù)載均衡問題，設(shè)任務(wù)數(shù)為n，資源節(jié)點(diǎn)數(shù)為M，則每個(gè)資源節(jié)點(diǎn)上平均分配的任務(wù)數(shù)為資源節(jié)點(diǎn)任務(wù)分配數(shù)標(biāo)準(zhǔn)差的適應(yīng)度函數(shù)見式（10）。

其中：Assign_tasksk，i表示第k個(gè)染色體上的第i個(gè)資源節(jié)點(diǎn)所分配到的任務(wù)數(shù)。

所以，本文設(shè)計(jì)基于任務(wù)平均完成時(shí)間和負(fù)載均衡的雙適應(yīng)度函數(shù)見式（11）。

ω1和ω2分別是基于最小完成時(shí)間和任務(wù)分配數(shù)標(biāo)準(zhǔn)差適應(yīng)度函數(shù)的權(quán)重。用戶根據(jù)自己的偏好決定每個(gè)適應(yīng)度函數(shù)的權(quán)重，且滿足ω1+ω2=1。

2.2.3選擇算子設(shè)計(jì)

在選擇算子的設(shè)計(jì)采用改進(jìn)的輪盤賭方法。首先根據(jù)式（9）計(jì)算每個(gè)染色體的適應(yīng)度值，然后計(jì)算該適應(yīng)度值相對(duì)于整個(gè)種群適應(yīng)度值總和中所占的比例，即該個(gè)體被復(fù)制到下一代中的概率。則個(gè)體k被選中的概率見式（12）。

2.2.4交叉和變異算子設(shè)計(jì)

本文采用模擬退火的思想對(duì)個(gè)體進(jìn)行交叉操作，種群中較優(yōu)個(gè)體以較低概率進(jìn)行交叉，增加種群中“弱勢(shì)”個(gè)體的交叉可能性，提高種群的多樣性，使算法陷入局部最優(yōu)解的可能性減小。交叉概率函數(shù)見式（13）。

其中：favg表示每代群體的平均適應(yīng)度值，f2，f1分別表示隨機(jī)選擇的兩個(gè)個(gè)體中適應(yīng)度值的較大者與較小者。α為退火系數(shù)，T為算法當(dāng)前迭代的溫度。當(dāng)適應(yīng)度函數(shù)值較大時(shí) （f2＞f 1＞favg），這時(shí)讓交叉概率Pc變小，防止較優(yōu)的個(gè)體被破壞，同時(shí)較小的交叉概率能加快種群向最優(yōu)解收斂。當(dāng)適應(yīng)度函數(shù)值較小時(shí)（f1＜f2＜favg），使交叉概率變大，期望重組出新的個(gè)體。交叉算子有利于在全局范圍內(nèi)找到較好的個(gè)體，容易出現(xiàn)在最優(yōu)解附近徘徊的現(xiàn)象，對(duì)局部解空間的尋優(yōu)能力較差，使用變異算子可以微調(diào)個(gè)體的基因值，提高全局的收斂精度，個(gè)體的變異概率函數(shù)見式（14）。

其中，f′表示隨機(jī)選擇的個(gè)體適應(yīng)度函數(shù)值，favg表示種群適應(yīng)度的平均值。當(dāng)隨機(jī)選擇個(gè)體的適應(yīng)度值大于平均適應(yīng)度值時(shí)（即f′＞favg），根據(jù)上面的公式，f′越大，種群中個(gè)體的變異概率則越小。這樣可以在很大程度上避免較優(yōu)個(gè)體的結(jié)構(gòu)被破壞。

2.2.5算法終止條件

當(dāng)連續(xù)60代適應(yīng)度函數(shù)值無變化或者進(jìn)化代數(shù)達(dá)到200次時(shí)，終止算法的執(zhí)行。

本文使用均勻交叉、多點(diǎn)交叉相結(jié)合的實(shí)現(xiàn)方式，變異方式使用基因值變異。最后基于模擬退火的改進(jìn)遺傳算法（SAIGA）流程圖如圖2所示。

圖2　改進(jìn)算法的流程圖

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

3.1仿真環(huán)境

在Intel.Core2四核2.83 GHz CPU，4 G RAM，操作系統(tǒng)為Windows7 32 bit，采用CloudSim3.0軟件對(duì)算法進(jìn)行仿真，其核心是中心代理人和虛擬機(jī)調(diào)度策略，改進(jìn)算法通過擴(kuò)展Datacenter Broker和VMAllocationPolicy類實(shí)現(xiàn)云資源調(diào)度的模擬。

3.2對(duì)比算法

本文選擇輪詢調(diào)度算法（RR）、遺傳算法（GA）和模擬退火算法（SA）做對(duì)比實(shí)驗(yàn)，分析比較4種算法在任務(wù)總完成時(shí)間、任務(wù)平均完成時(shí)間、負(fù)載均衡以及收斂速度方面的優(yōu)劣性。GA、SA和SAIGA算法的參數(shù)設(shè)置見表2。

表2　GA、SA及SAIGA算法參數(shù)設(shè)置表

3.3結(jié)果與分析

實(shí)驗(yàn)中模擬任務(wù)的長(zhǎng)度MI取1 000～20 000之間，資源的運(yùn)算能力MIPS取500～5 000之間，分析任務(wù)數(shù)和虛擬資源數(shù)的變化對(duì)任務(wù)總完成時(shí)間、平均完成時(shí)間以及資源負(fù)載均衡的影響。

1）將任務(wù)分配到10個(gè)資源節(jié)點(diǎn)，改變?nèi)蝿?wù)的數(shù)量從10到200，記錄任務(wù)的總完成時(shí)間（ms），結(jié)果見表3，圖3。

表3　資源數(shù)一定，不同任務(wù)數(shù)下的完成時(shí)間

圖3　資源數(shù)一定，不同任務(wù)數(shù)下的總完成時(shí)間

從圖3可以看出，在任務(wù)數(shù)不多時(shí)，4種算法下任務(wù)的完成時(shí)間差別不大，這是由于初期資源節(jié)點(diǎn)的數(shù)量和任務(wù)的數(shù)量差別不大，節(jié)點(diǎn)有足夠的能力去處理這些任務(wù)。隨著任務(wù)數(shù)的增多，特別地當(dāng)任務(wù)數(shù)大于150時(shí)，SAIGA算法調(diào)度下的任務(wù)總完成時(shí)間明顯優(yōu)于其他3種算法。

2）當(dāng)任務(wù)數(shù)量固定為1 000時(shí)，改變虛擬資源的數(shù)量，從10到50，記錄任務(wù)的平均完成時(shí)間如圖4。

從圖4可以看出，在虛擬資源數(shù)較少時(shí)，SAIGA的任務(wù)完成時(shí)間遠(yuǎn)遠(yuǎn)小于RR、GA和SA。隨著虛擬資源數(shù)量的增加，4種算法下任務(wù)的完成時(shí)間都在不斷減少，最后SAIGA、GA和SA算法的任務(wù)平均完成時(shí)間大致接近，這是由于隨著資源節(jié)點(diǎn)數(shù)量的增加，其處理能力能夠逐漸滿足任務(wù)的執(zhí)行需求，任務(wù)搶占資源的情況減少。

3）任務(wù)數(shù)為1 000時(shí)，將任務(wù)分配到5個(gè)資源節(jié)點(diǎn)（R1，R2，R3，R4，R5）上，設(shè)置其處理能力分別為：（1 200， 900，600，1800，800）MIPS，記錄5個(gè)資源節(jié)點(diǎn)上的負(fù)載情況如圖5。

圖4　不同資源數(shù)下任務(wù)的平均完成時(shí)間

圖5　大量任務(wù)下資源節(jié)點(diǎn)的負(fù)載情況

從圖5可以看出，在資源計(jì)算能力有較大差異的情況下，SAIGA算法的分配的任務(wù)數(shù)更加均衡，而RR沒有考慮到節(jié)點(diǎn)能力的差異性，采取了均分任務(wù)的方式，GA、SA中則出現(xiàn)計(jì)算能力高的節(jié)點(diǎn)分配到任務(wù)數(shù)較多，計(jì)算能力低的節(jié)點(diǎn)分配到的任務(wù)數(shù)較少的現(xiàn)象?？傊?，SAIGA算法在資源節(jié)點(diǎn)的負(fù)載均衡方面表現(xiàn)出較好的優(yōu)越性。

4）任務(wù)數(shù)為1 000時(shí)，資源節(jié)點(diǎn)為40時(shí)，GA和SAIGA算法的迭代收斂情況如圖6。

圖6　SAIGA和GA算法收斂結(jié)果比較

從圖6可以看出，在算法迭代初期GA和SAIGA性能差不多，但由于SAIGA采用任務(wù)總數(shù)加編號(hào)的方式作為染色體的基因值，使它后期的收斂速度加快。SAIGA算法在迭代120次后開始收斂，而GA算法在接近160代時(shí)才出現(xiàn)收斂的趨勢(shì)，在收斂精度上改進(jìn)算法提高了近130秒。另外，GA算法迭代大約至60代時(shí)出現(xiàn)一些適應(yīng)度值超常的個(gè)體誤導(dǎo)了種群進(jìn)化的方向，但這些個(gè)體并不是算法最優(yōu)解。由于SAIGA采用自學(xué)習(xí)的交叉概率函數(shù)，在算法接近收斂的階段對(duì)超常適應(yīng)度值的個(gè)體進(jìn)行了一定概率的調(diào)整，避免誤導(dǎo)了種群的進(jìn)化方向，使得改進(jìn)算法更快地收斂到最優(yōu)解。

4　結(jié)束語

針對(duì)云資源調(diào)度的動(dòng)態(tài)性、實(shí)時(shí)性等特點(diǎn)，提出了一種基于模擬退火思想的改進(jìn)遺傳算法SAIGA。該算法比GA、SA和RR在任務(wù)平均完成時(shí)間上分別縮短了11%，25%和56%，在算法的收斂精度和速度上都有顯著的提高，收斂速度上提高了40代左右，能夠有效避免超常個(gè)體誤導(dǎo)種群的進(jìn)化方向和算法陷入局部最優(yōu)，同時(shí)改進(jìn)算法能夠較均衡地分配任務(wù)到各個(gè)節(jié)點(diǎn)上，提高了資源的利用率。因此，改進(jìn)算法更加適合云環(huán)境下的資源調(diào)度，具有較好的實(shí)用性。

［1］劉鵬.云計(jì)算［M］.北京：電子工業(yè)出版社，2011.

［2］Armbrust M，F(xiàn)ox A，Griffith R，et al.A View of Cloud Computing［J］.Communications of the ACM，2010，53（4）：50-58.

［3］Caballer M，Blanquer I，MoltóG，et al.Dynamic Management of Virtual Infrastructures［J］.Journal of Grid Computing，2015，13（1）：53-70.

［4］林偉偉，齊德昱.云計(jì)算資源調(diào)度研究綜述［J］.計(jì)算機(jī)科學(xué)，2012，39（10）：1-6.

［5］劉愉，趙志文，李小蘭，等.云計(jì)算環(huán)境中優(yōu)化遺傳算法的資源調(diào)度策略［J］.北京師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，48（4）：378-384.

［6］袁浩，李昌兵.基于社會(huì)力群智能優(yōu)化算法的云計(jì)算資源調(diào)度［J］.計(jì)算機(jī)科學(xué)，2015，42（04）：206-208.

［7］徐文忠，彭志平，左敬龍.基于遺傳算法的云計(jì)算資源調(diào)度策略研究［J］.計(jì)算機(jī)測(cè)量與控制，2015，23（5）：1653-1656.

［8］李建鋒，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法［J］.計(jì)算機(jī)應(yīng)用，2011，31（1）：184-186.

［9］薛玉.云計(jì)算環(huán)境下的資源調(diào)度優(yōu)化模型研究［J］.計(jì)算機(jī)仿真，2013，30（5）：362-365.

［10］鄔海艷.基于云計(jì)算環(huán)境下資源調(diào)度算法研究 ［D］：贛州：江西理工大學(xué)，2012.

［11］Gao Y，Guan H，Qi Z，et al.A multi-objective ant colony system algorithm for virtual machine placement in cloud computing［J］.Journal of Computer and System Sciences，2013，79（8）：1230-1242.

［12］Zhan Z H，Zhang G Y，Ying L，et al.Load Balance Aware Genetic Algorithm for Task Scheduling in Cloud Computing［A］.In：Dick G，Browne W，Whigham P，Zhang M，Bui L，Ishibuchi H，Jin Y，Li X，Shi Y，Singh P，Tan K，Tang K，editors.Simulated Evolution and Learning［C］.Springer International Publishing，2014：644-655.

［13］Gall J，Rosenhahn B，Seidel H P.An Introduction to Interacting Simulated Annealing［A］.In：Rosenhahn B，Klette R，Metaxas D，editors.Human Motion［C］.Springer Netherlands，2008：319-345.

［14］S K，P VM.Optimization by simmulated annealing［J］.science，1983，220（4598）.

An Improved Genetic Algorithm for Cloud Computing Resource Scheduling

Liu Feng1，Bi Li1，Yang Jun2
（1.School of Mathematics and Computer Science，Ningxia University，Yinchuan750021，China；2.Network Administration Center，Ningxia University，Yinchuan750021，China）

For Round-Robin scheduling algorithm and genetic algorithm and simulated annealing algorithm in cloud resource scheduling having shortcomings，such as slow convergence speed，easy to premature and the imbalance of the resource load，the paper proposed the improved genetic algorithm combined with simulated annealing thought（Simulated Annealing Improved Genetic Algorithm：SAIGA）.The improved algorithm gave a dual fitness function based on task average completion time and load balance and adaptive crossover mutation probability function.It allowed the algorithm in the annealing process to accept inferior solution with a certain probability to avoid prematurity phenomenon occurs.We regarded the virtual machine task allotment standard deviation as the basis of individual choice to realize the resource node load balancing.Simulation experiments showed that the improved algorithm is more superior on average task completion time，resource load balancing，and the convergence rate.It can rapidly find the optimal scheduling scheme and has good feasibility and practicability.

cloud computing；round robin scheduling；simulated annealing thought；improved genetic algorithm；load balancing

1671-4598（2016）05-0202-05

10.16526/j.cnki.11-4762/tp.2016.05.057

TP393

A

2015-11-09；

2015-12-11。

國(guó)家自然科學(xué)基金項(xiàng)目（61261001）；教育部科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目（212189）。

劉峰（1989-），男，山東菏澤人，碩士研究生，主要從事智能調(diào)度算法方向的研究。

畢利（1968-），女，寧夏銀川人，教授，碩士生導(dǎo)師，主要從事數(shù)據(jù)挖掘及組合優(yōu)化控制方向的研究。

楊軍（1972-），男，寧夏吳忠人，教授，碩士生導(dǎo)師，主要從事云計(jì)算資源調(diào)度及無線傳感器網(wǎng)絡(luò)方向的研究。