徐 陽 陳世平,2

1(上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院 上海 200093)2(上海理工大學(xué)信息化辦公室 上海 200093)

0 引 言

近年來，隨著云計(jì)算[1-4]取得了巨大成功，大量高科技公司涌入云服務(wù)市場。隨著云計(jì)算市場規(guī)模越來越大，用戶群體變得更加復(fù)雜，相對應(yīng)的業(yè)務(wù)需求也在不斷變化。云數(shù)據(jù)中心資源調(diào)度的一個(gè)關(guān)鍵目標(biāo)，是將云數(shù)據(jù)中心的資源快速充分利用分配給用戶。目前主要用的啟發(fā)式算法有：粒子群算法(PSO)[5]、蟻群算法(ACO)[6]、遺傳算法(GA)[7-8]等。這些算法主要目的是減少成本，提高資源利用率，以至于滿足用戶各方面的要求。但是這些算法都有各自的優(yōu)缺點(diǎn)，如蟻群算法局部搜索能力較強(qiáng)，但是初始信息素匱乏、初始搜索速度慢等。

當(dāng)前云資源分配調(diào)度方案依然是云計(jì)算最關(guān)鍵的技術(shù)。為了提高云資源分配效率，減少資源分配的時(shí)間，滿足用戶的使用需求。本文引入包簇理論[9]，在包簇映射框架下，提出基于混沌擾動遺傳算法GACD(Genetic Algorithm based on Chaotic Disturbance)。該算法是在遺傳算法的基礎(chǔ)上引入混沌搜索機(jī)制、改進(jìn)種群個(gè)體選擇、交叉和變異等操作，提高算法的搜索速度和收斂效率。最后采用CloudSim進(jìn)行實(shí)驗(yàn)，以檢測算法的正確性。仿真結(jié)果表明，基于混沌擾動遺傳算法解決了傳統(tǒng)遺傳算法存在的局部收斂、收斂速度慢和資源分配效率低等缺點(diǎn)，在一定程度上加快了云計(jì)算資源分配效率，縮短了任務(wù)的完成時(shí)間。

1 包簇框架的描述

由文獻(xiàn)[9]可知，包和簇是樹形結(jié)構(gòu)。最底層的虛擬機(jī)組合成一個(gè)包，而多個(gè)包又組合成一個(gè)更高級的包。虛擬機(jī)或包所需的資源就是用戶對云資源的需求。其中用戶對資源需求包括CPU、RAM、寬帶和緩存等。同理，簇是由多個(gè)服務(wù)器或子簇組成。簇?fù)碛邪鼘Y源的需求量。

本文定義有N個(gè)子簇(或服務(wù)器)。p為子簇標(biāo)號，1≤p≤N。有M個(gè)子包(或虛擬機(jī))組成，標(biāo)號為v，1≤v≤M。本文的關(guān)鍵是將M個(gè)子包分配給N個(gè)子簇，將同一個(gè)包中包分配給同一個(gè)簇中簇，同一個(gè)算法遞歸調(diào)用把子包分配給子簇，直到虛擬機(jī)分配給服務(wù)器。

由文獻(xiàn)[10]可知資源約束：

(1)

式中：xv,p[t]是二進(jìn)制0-1變量：當(dāng)且僅當(dāng)在時(shí)間t時(shí)包v被分配給簇p，則xv,p[t]=1；否則，xv,p[t]=0。Rv,i[t]表示包v在時(shí)間t對資源i的需求總量。1≤i≤J，1≤t≤T。Ap,i[t]表示簇p在時(shí)間t時(shí)對資源i的可用總量。1≤p≤N。

由文獻(xiàn)[10]可知簇的運(yùn)營成本：

本文在基于包簇映射的框架下，以減少成本U(x,y)為目標(biāo)，通過混沌擾動遺傳算法進(jìn)行資源分配，提高分配效率，減少分配時(shí)間。

2 基于混沌擾動遺傳算法調(diào)度策略

2.1 設(shè)計(jì)思想

基于混沌擾動遺傳算法是將遺傳算法和混沌搜索機(jī)制相結(jié)合。首先求出個(gè)體之間的差異和適應(yīng)度值，利用遺傳算法進(jìn)行搜索，混沌機(jī)制來避免陷入局部最優(yōu)，通過精英保留選擇法，把優(yōu)秀的個(gè)體作為父代，然后采用改進(jìn)的交叉和變異操作。算法的主要流程如圖1所示。

圖1 算法流程圖

2.2 個(gè)體之間的差異性

種群在初始化時(shí)會有很大的機(jī)率產(chǎn)生很多相似的個(gè)體，導(dǎo)致大量迭代計(jì)算，為了解決此問題，本文引出差異性。

差異性是指特征空間中對象之間的差異，將特征空間中不同的對象進(jìn)行分類。本文用0-1編碼來對兩個(gè)個(gè)體的基因串進(jìn)行評估，其中兩個(gè)對象相同的位置編碼相同，則為0，不同則為1。0越多表示兩個(gè)對象越相同，編碼情況越相同。在算法中，限定0的個(gè)數(shù)來避免非常相似的個(gè)體。

2.3 自適應(yīng)交叉方式

設(shè)種群虛擬機(jī)的規(guī)模為M，虛擬機(jī)的任務(wù)資源需求種類為J，種群虛擬機(jī)的編碼長度為L。第i位編碼為0的個(gè)體數(shù)為Si,0，為1的個(gè)體數(shù)為Si,1，則定義第i位的相似度[12]為：

(2)

則群體的相似度定義為：

(3)

根據(jù)θ的大小來判斷種群虛擬機(jī)的收斂程度，θ越大，表示種群虛擬機(jī)越相似，虛擬機(jī)所需要的資源也就越相同。種群虛擬機(jī)的交叉概率也是依據(jù)θ的大小動態(tài)調(diào)整。算法初期，設(shè)定較大的交叉概率值，以此加快種群繁衍和收斂。當(dāng)種群虛擬機(jī)的θ比較大時(shí)，相應(yīng)地調(diào)小交叉概率。參照文獻(xiàn)[11]給出相應(yīng)的自適應(yīng)調(diào)整公式：

Pc=t1et2θ

(4)

式中：t1和t2的值由Pc和θ的取值范圍共同決定。

2.4 種群初始化和混沌擾動的確定

混沌相關(guān)的的內(nèi)容可以參考文獻(xiàn)[12-13],混沌的主要思想是利用自身的特點(diǎn)進(jìn)行搜索，防止陷入局部最優(yōu)[14-15]，本文采取Logistic映射系統(tǒng)，映射關(guān)系如下:

δn+1=uδn(1-δn)n=0,1,2，…

(5)

式中：u∈[0,4]，當(dāng)u=4時(shí)為完全混沌狀態(tài)。

首先，隨機(jī)產(chǎn)生一個(gè)L維向量δ1=[δ1,1,δ1,2,δ1,l,…,δ1,L]，δ1,l∈[0,1]，δ1作為初始向量進(jìn)行迭代。根據(jù)式(5)將得到的各混沌變量映射到優(yōu)化變量的各維取值空間，然后計(jì)算目標(biāo)函數(shù)值，對其值進(jìn)行排序，從中選取M個(gè)較好的個(gè)體作為初始種群。

為了增加解的多樣性，本文用混沌序列對虛擬機(jī)種群進(jìn)行混沌擾動，提高搜索精度，混沌擾動方程如下：

(6)

α的取值會根據(jù)搜索的范圍進(jìn)行調(diào)整，在種群初期時(shí)，搜索較大范圍，α選取較大的值。到后期時(shí)，解已經(jīng)逐步優(yōu)化，搜索的范圍變小，此時(shí)需要選取較小的α，以便在較小范圍內(nèi)變動。本文按下式確定α的值：

(7)

式中：m為參加擾動解的個(gè)數(shù)；k為擾動次數(shù)，k=1,2,…。

2.5 加速收斂變異法

生物在進(jìn)化的過程中，一些個(gè)體的某些基因位以一定的幾率發(fā)變異，由原本的1變成0，或者由0變成1，促進(jìn)了生物群體的進(jìn)化。然而當(dāng)兩個(gè)對象基因相同時(shí)，只能依靠基因變異產(chǎn)生新的基因和個(gè)體。本文提出一種加速收斂變異法，令個(gè)體的基因串前50%為高位，后50%為低位。在算法初期，首先在全局搜索出適應(yīng)度高的優(yōu)秀個(gè)體，設(shè)置其高位為高變異率，低位為低變異率。在尋找適應(yīng)度高的優(yōu)秀個(gè)體過程中，高位的變異率逐漸降低至0，低位的變異率慢慢增加，以此增加解的多樣性。

2.6 適應(yīng)度函數(shù)和解的修正

包簇資源分配問題，就是需要求出簇中資源分配到包的最低耗費(fèi)，使其成本最低。

參照文獻(xiàn)[16-17],把解的懲罰值引入適應(yīng)度函數(shù)設(shè)計(jì)中。

懲罰值：該值等于分配到包的總資源與該簇總資源之差的絕對值和二者中較大者的比值。如果被分配到包的總資源與該簇的總資源相差越大，即包需求的總資源越大于或者越小于簇中所擁有的資源，此時(shí)懲罰值越大。則構(gòu)造包簇資源分配的適應(yīng)度函數(shù)如下：

式中：U(x,y)為成本函數(shù)。

設(shè)定成本密度函數(shù)ω為簇i的總成本與總資源的比值：

解的貪心修正：首先計(jì)算出簇的成本密度值并從小到大進(jìn)行排序，然后在算出分配給簇的包所需要的總資源，如果超出該簇或服務(wù)器所擁有的資源。則需要重新匹配一個(gè)簇或服務(wù)器。如此循環(huán)直到滿足包和簇的資源約束為止，得到符合條件的解。

2.7 算法具體步驟

Step1設(shè)定種群虛擬機(jī)的編碼和各個(gè)參數(shù)。

Step2種群進(jìn)行初始化。

Step3根據(jù)相似度定義，求出每個(gè)個(gè)體的相似度值，然后按照從小到大排序。

Step4選取序列中前10%的解，把解轉(zhuǎn)換為十制數(shù)，然后除以2n-1得到小數(shù)后，進(jìn)行混沌擾動，得到10%的新個(gè)體(且盡量保證個(gè)體的適應(yīng)度值超過上一代)，若超過，則轉(zhuǎn)下一步，若未超過則進(jìn)行迭代，擾動次數(shù)加1，達(dá)到設(shè)定值轉(zhuǎn)下一步。

Step5對剩余的其他個(gè)體進(jìn)行精英保留選擇，自適應(yīng)交叉和收斂變異操作來產(chǎn)生新的個(gè)體。

Step6計(jì)算出新個(gè)體所需資源總量是否超過該簇?fù)碛械馁Y源總量，如果超過了則需要通過貪心修正。

Step7首先計(jì)算出每個(gè)包或者虛擬機(jī)的適應(yīng)度函數(shù)值，并將之與上一代中的最大適應(yīng)度個(gè)體進(jìn)行比較，若新一代適應(yīng)度函數(shù)值較大，則將該值保存、輸出轉(zhuǎn)step 3。否則直接轉(zhuǎn)step 3。

Step8循環(huán)step 3到step 7操作直至進(jìn)化代數(shù)達(dá)到設(shè)定值，輸出最優(yōu)解。

Step9在包最優(yōu)解的情況下，類似于包的求解，求出包中包的最優(yōu)資源分配解。一直遞歸求出最底層虛擬機(jī)映射到簇或者服務(wù)器的解。

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

本文設(shè)計(jì)的算法目標(biāo)有兩個(gè)，一是降低成本消耗；二是減少資源分配完成時(shí)間，提高資源分配效率。為了對算法進(jìn)行驗(yàn)證，本文在基于包簇映射的框架下設(shè)計(jì)了3組實(shí)驗(yàn)，分別是基于混沌擾動遺傳算法、簡單遺傳算法和粒子群算法進(jìn)行對比實(shí)驗(yàn)。

三種算法在CloudSim云仿真平臺上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為Sun Java SE 7。仿真參數(shù)設(shè)置：設(shè)置種群虛擬機(jī)數(shù)為I，每個(gè)虛擬機(jī)有J個(gè)任務(wù)資源需求。每q個(gè)虛擬機(jī)組合成一個(gè)一級包，每q個(gè)一級包，則生成一個(gè)二級包，依次遞歸生成，直到生成一個(gè)最高級的包。

虛擬機(jī)的任務(wù)資源需求矩陣如下：

ri,j表示虛擬機(jī)i對資源j的需求量。1≤i≤I，1≤j≤J。

最高級包的總資源需求矩陣如下：

設(shè)虛擬機(jī)的二進(jìn)制編碼為L；二進(jìn)制編碼初始化生成。

設(shè)有H個(gè)服務(wù)器，每個(gè)服務(wù)器有J個(gè)任務(wù)的種類資源。每p個(gè)服務(wù)器組合成一個(gè)一級簇，每p個(gè)一級簇，則生成一個(gè)二級簇，依次遞歸生成，直到生成一個(gè)最高級的簇。

服務(wù)器資源矩陣如下：

ah,j表示服務(wù)器h擁有資源j的量。1≤h≤H，1≤j≤J。

最高級簇總資源如下：

首先將最高級包先分配給最底層服務(wù)器，如果服務(wù)器資源不滿足包資源的需求，則依次往上分配給一級簇，如果一級簇依舊不滿足，則繼續(xù)遞歸往上一級簇分配，直到滿足包的資源需求為止。這時(shí)最高級包的下一級包，開始分配到該簇的下一級簇，依次遞歸，找到滿足需要的最少資源簇即可。類似這種分配，直到虛擬機(jī)分配到具體的某個(gè)簇或者服務(wù)器上即可停止分配。

算法主要是以簇的運(yùn)營成本U(x,y)為目標(biāo)，分別用基于混沌擾動遺傳算法、簡單遺傳算法和粒子群算法進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)具體參數(shù)如表1所示。

表1 GACD、PSO和GA算法參數(shù)設(shè)置表

小規(guī)模數(shù)據(jù)實(shí)驗(yàn)的結(jié)果如表2所示。

表2 小規(guī)模實(shí)驗(yàn)結(jié)果表

大規(guī)模數(shù)據(jù)實(shí)驗(yàn)的結(jié)果如表3所示。

表3 大規(guī)模實(shí)驗(yàn)結(jié)果表

收斂速度對比如表4所示。令虛擬機(jī)數(shù)量I=100，其他參數(shù)如表1所示。

表4 算法收斂速度實(shí)驗(yàn)對比表

為了實(shí)驗(yàn)的準(zhǔn)確性，避免偶然情況，本文實(shí)驗(yàn)的每個(gè)算法都執(zhí)行15次，然后對實(shí)驗(yàn)結(jié)果取平均值。圖2、圖3和圖4是對三種算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較。

圖2 小規(guī)模任務(wù)的完成時(shí)間比較

圖3 大規(guī)模任務(wù)完成時(shí)間比較

圖4 三種算法的收斂速度對比

從圖2可以得出，在一定任務(wù)范圍內(nèi)，GACD、PSO、GA算法完成任務(wù)的時(shí)間差別不大。但從圖3可以看出，在任務(wù)量比較多的情況下，GACD的任務(wù)完成時(shí)間最短，優(yōu)勢明顯。從圖4可以看出，本文改進(jìn)的遺傳算法收斂速度明顯比較快，算法在迭代300次后快速收斂，開始趨向穩(wěn)定。GACD算法形成的任務(wù)調(diào)度方案，對執(zhí)行包簇映射下的資源分配所需要總時(shí)間較少，基本達(dá)成了最優(yōu)化解決方案。

由實(shí)驗(yàn)可知，在包簇映射的框架下，基于混沌擾動遺傳算法引入混沌擾動機(jī)制，利用混沌的遍歷性和參數(shù)擾動策略，擴(kuò)大了虛擬機(jī)種群的多樣性，避免遺傳算法陷入局部極小值，增強(qiáng)了遺傳算法的全局搜索能力，并且在一定程度上使得該算法具有較高的搜索速度和收斂速度。

在時(shí)間上，通過圖2和圖3可知，GACD算法在資源分配的過程中，所需要時(shí)間最少，搜索速度最快，PSO算法次之。這是因?yàn)镚ACD算法采用混沌進(jìn)行種群初始化，利用參數(shù)擾動策略進(jìn)行快速搜索和資源分配。

在收斂速度上，通過圖4可知，隨著進(jìn)化代數(shù)的增加，GACD算法采用了自適應(yīng)交叉方式和加速收斂變異法，提高了算法的收斂速度，使得該算法的收斂速度快于PSO算法和GA算法。

在任務(wù)規(guī)模上，由圖2和圖3可得，GACD算法效率在小規(guī)模任務(wù)上略優(yōu)于GA算法和PSO算法，但差距不明顯，但是隨著任務(wù)規(guī)模的不斷擴(kuò)大，在一定的任務(wù)范圍之內(nèi)GACD算法明顯比PSO算法和GA算法效率更高。這是因?yàn)镻SO算法和GA算法總是盡量把滿足條件的資源分配給當(dāng)前任務(wù)，當(dāng)可用的資源較多時(shí)，完成的時(shí)間也較快。一旦任務(wù)量較大時(shí)，此時(shí)PSO算法和GA算法的缺陷也就開始顯現(xiàn)出來。

4 結(jié) 語

本文主要是在基于包簇映射的框架下，通過改進(jìn)遺傳算法對云資源分配調(diào)度進(jìn)行深入研究，引用混沌擾動機(jī)制對遺傳算法的搜索操作進(jìn)行了改進(jìn)，并且對選擇、交叉和變異操作進(jìn)一步完善，詳細(xì)地描述了算法實(shí)現(xiàn)步驟和原理。通過實(shí)驗(yàn)可以看出，該方法以耗費(fèi)成本最低為目標(biāo)，快速找到合適的云資源來進(jìn)行分配，減少了任務(wù)調(diào)度的時(shí)間，提高了效率，具有較好的效果，實(shí)現(xiàn)了較為合理的任務(wù)調(diào)度方案。