改進(jìn)遺傳算法在云計(jì)算資源優(yōu)化調(diào)度中的應(yīng)用

鞠成恩 趙曉俠 王明興 問(wèn)尤龍

摘 要：在大量用戶請(qǐng)求云計(jì)算資源服務(wù)時(shí)，如何合理組織資源和任務(wù)調(diào)度是云計(jì)算的關(guān)鍵技術(shù)之一。如果分配調(diào)度方法不合理，就可能產(chǎn)生用戶需求得不到滿足和資源使用不均衡等問(wèn)題。在傳統(tǒng)遺傳算法基礎(chǔ)上，將模擬退火算法與遺傳算法相融合，擴(kuò)大遺傳算法的搜索領(lǐng)域，解決遺傳算法早熟收斂現(xiàn)象，使云資源分配更加合理，以提高云資源利用率。在CloudSim平臺(tái)上進(jìn)行仿真，結(jié)果表明該方式能較好地對(duì)云計(jì)算資源進(jìn)行分配，在能耗、帶寬等約束條件下達(dá)到云資源最優(yōu)調(diào)度的目的。

關(guān)鍵詞：智能算法；云資源；優(yōu)化調(diào)度；CloudSim仿真

DOI：10.11907/rjdk.172641

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）004-0045-02

Abstract：With the development of Internet， cloud computing has become a hot research topic in academic and commercial fields. When a large number of users request cloud computing resource services， how to do reasonable resource sister scheduling and task scheduling becomes one of the key technologies of cloud computing. If the allocation method is not reasonable， the user demand can not be met and the use of resources is not balanced. The traditional genetic algorithm combines with simulated annealing algorithm to expand the search field and solve the premature convergence phenomenon and makes the use of cloud resource allocation more reasonable to improve the utilization of cloud resources. Simulation experiments on CloudSim platform show that this method can better allocate the cloud computing resources， and achieve the purpose of optimal scheduling of cloud resources.

Key Words：intelligence algorithm； cloud resource； optimal scheduling； CloudSim simulation

0 引言

云計(jì)算[1-2]由網(wǎng)格計(jì)算發(fā)展而來(lái)，它將計(jì)算資源、存儲(chǔ)資源和網(wǎng)絡(luò)資源進(jìn)行整合，按照用戶需求進(jìn)行分配資源服務(wù)，是一種新興的網(wǎng)絡(luò)服務(wù)和交互模式。云計(jì)算在云端部署計(jì)算機(jī)集群，運(yùn)用虛擬化技術(shù)組成一個(gè)大型虛擬資源池（Virtualized Resource Pool）[3]，利用各種工具對(duì)虛擬資源池進(jìn)行統(tǒng)一管理；在終端為用戶與運(yùn)營(yíng)商提供服務(wù)接口，運(yùn)營(yíng)商通過(guò)這些接口為用戶提供可擴(kuò)展、分布式存儲(chǔ)與計(jì)算等服務(wù)，用戶在使用時(shí)可以對(duì)資源自行管理與配置[4]。

大多數(shù)情況下云計(jì)算的資源調(diào)度任務(wù)并發(fā)產(chǎn)生，且分布不均勻，當(dāng)用戶群體十分龐大時(shí)，虛擬機(jī)優(yōu)化調(diào)度會(huì)越來(lái)越復(fù)雜，需要云計(jì)算系統(tǒng)提供靈活的分配機(jī)制，這些需求使云計(jì)算調(diào)度變得困難。本文以基本遺傳算法[5-6]為基礎(chǔ)，引入模擬退火算法[7-8]與之相融合，以改進(jìn)遺傳算法的局部搜尋能力，擴(kuò)大遺傳算法搜索領(lǐng)域，從而有效解決了遺傳算法早熟收斂現(xiàn)象，使資源分配更加合理、高效。

1 基于遺傳算法的資源調(diào)度算法設(shè)計(jì)

1.1 編碼表示方法與初始種群產(chǎn)生

遺傳算法產(chǎn)生種群一般采用隨機(jī)方式，這種方法產(chǎn)生的種群有很多非連通路徑，這些非連通路徑雖然在以后的迭代運(yùn)算中可能轉(zhuǎn)化為連通路徑，但轉(zhuǎn)化效果一般，使得過(guò)程解在有限的進(jìn)化代數(shù)內(nèi)可能過(guò)早收斂，從而影響最終解的質(zhì)量。所以，在確保初始種群的多樣性前提下，要盡可能保證所產(chǎn)生的路徑是連通的，這對(duì)于改善算法的求解速度和全局收斂性幫助很大。

將N個(gè)虛擬機(jī)放置在M個(gè)主機(jī)上，得到個(gè)體基因編碼{k0，k1，…kn-1}。其中第i個(gè)虛擬機(jī)ki的取值范圍為[0，m-1]。用一個(gè)具體例子說(shuō)明：當(dāng)虛擬機(jī)的數(shù)量為10，主機(jī)數(shù)量為5時(shí)，編碼將產(chǎn)生一個(gè)長(zhǎng)度為10的序列，假設(shè)產(chǎn)生的序列為{2，3，1，4，0，0，1，2，2，3}，虛擬機(jī)在編號(hào)0-9中分別按照序列{2，3，1，4，0，0，1，2，2，3}的順序創(chuàng)建在對(duì)應(yīng)主機(jī)上。

1.2 適應(yīng)度函數(shù)

云環(huán)境下的能耗模型主要考慮計(jì)算能耗和數(shù)據(jù)傳輸能耗。有研究表明，云計(jì)算環(huán)境下主機(jī)的功耗與其CPU利用率之間存在一種近似線性關(guān)系[9]，所以使用CPU利用率作為主機(jī)的能耗，用E表示；而直接影響服務(wù)質(zhì)量和用戶使用感受的另一個(gè)主要因素是帶寬[10]，具有較少帶寬負(fù)載和時(shí)間花費(fèi)的個(gè)體有更好的適應(yīng)度，用B表示。因此，消耗程度低的認(rèn)為適應(yīng)度較好，其函數(shù)F為：

1.3 選擇與交叉算子

使用更加合理的輪盤賭方式選擇算子。輪盤賭是累積并記錄種群中各基因的適應(yīng)值，然后用一個(gè)位于[0，1]區(qū)間的隨機(jī)數(shù)D做閾值，當(dāng)D大于某個(gè)基因記錄值時(shí)某個(gè)基因就被選中。例如基因數(shù)量為M種群{K1，K2，…，Km}，對(duì)應(yīng)的累積值為{ΔF1，ΔF2，…，ΔFm}，ΔFi由式（2）確定。如果產(chǎn)生的隨機(jī)數(shù)D剛好大于ΔFi，則Ki號(hào)基因被選中：

這樣連續(xù)進(jìn)行M次形成新的種群，通過(guò)新的種群進(jìn)行單點(diǎn)交叉算子操作。在每個(gè)個(gè)體中隨機(jī)選擇一個(gè)位置作為交叉點(diǎn)，將一個(gè)體染色體在交叉點(diǎn)位置分為前后兩部分，與另一個(gè)體的部分基因進(jìn)行交換。

1.4 變異方式

本文采用多點(diǎn)變異方式，在個(gè)體染色體內(nèi)隨機(jī)選擇多個(gè)位置，每個(gè)位置進(jìn)行小范圍變異，設(shè)置變異界值為0.1，若產(chǎn)生的隨機(jī)數(shù)小于0.1則發(fā)生變異，否則不發(fā)生變異。

2 融合模擬退火算法

模擬退火算法（Wimulated Annealing， SA）的思想最早由Metropolis[8-9]提出，其原理來(lái)源于物理中高溫固體物質(zhì)的物理退火，用于求解組合優(yōu)化問(wèn)題。云環(huán)境下遺傳算法中融合模擬退火算法具體實(shí)現(xiàn)如下：①初始化參數(shù)。設(shè)定足夠大的初始溫度T=T0，溫度衰減參數(shù)α，隨機(jī)選擇群體中的基因作為初始解進(jìn)行適應(yīng)值計(jì)算，確定每個(gè)溫度T下的迭代次數(shù)L；②通過(guò)交差算子和變異等生成新種群，計(jì)算新種群每個(gè)基因個(gè)體的適應(yīng)度值；③分別與父代個(gè)體進(jìn)行比較，按照Metropolis準(zhǔn)則：若新適應(yīng)度值大于原適應(yīng)度值，則接受新個(gè)體，并以新個(gè)體代替原來(lái)種群中對(duì)應(yīng)的舊個(gè)體；若新適應(yīng)度值小于原適應(yīng)度值，則以概率expfk-newfkT接受新個(gè)體代替舊個(gè)體；④gen=gen+1，若達(dá)到最大迭代次數(shù)L則向下進(jìn)行，若沒有則返回到第②步；⑤若達(dá)到終止條件則輸出最優(yōu)解，若沒有達(dá)到則令T=αT，重置迭代數(shù)并返回到第②步。

遺傳算法中融合模擬退火算法流程見圖1。

3 仿真

本文采用 Cloud Sim仿真工具進(jìn)行仿真試驗(yàn)。 Cloud Sim 是由澳大利亞墨爾本大學(xué)的網(wǎng)格實(shí)驗(yàn)室推出的一款具有跨平臺(tái)特點(diǎn)的云計(jì)算仿真軟件[11]，是一個(gè)模擬大規(guī)模云計(jì)算數(shù)據(jù)中心的開源框架，在云資源調(diào)度研究中使用非常廣泛。

初始化的參數(shù)需要對(duì)用戶數(shù)量、日期、追蹤標(biāo)志等進(jìn)行定義，數(shù)據(jù)中心是 Power 類型，創(chuàng)建數(shù)據(jù)中心代理Broker，這里代理的類型也是 Power 類型；創(chuàng)建虛擬機(jī)數(shù)和主機(jī)數(shù)，這里設(shè)置虛擬機(jī)數(shù)和主機(jī)數(shù)量比例為2∶1；設(shè)置調(diào)度策略配置遺傳算法；創(chuàng)建云任務(wù)，實(shí)驗(yàn)采用Cloud Sim 自帶的云工作平臺(tái)下的任務(wù)。

設(shè)置遺傳算法所需相關(guān)參數(shù)：初始種群規(guī)模為20，變異率為0.01，起始溫度參數(shù)k為100，溫度下降參數(shù)α為0.8，溫度下降時(shí)迭代數(shù)20。傳統(tǒng)遺傳算法及融合退火算法對(duì)云資源分配的仿真結(jié)果比較如圖2所示。

4 結(jié)語(yǔ)

通過(guò)在Cloud Sim平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)，將融入模擬退火算法改進(jìn)后的遺傳算法與改進(jìn)前的遺傳算法進(jìn)行比較。實(shí)驗(yàn)表明：融入模擬退火算法的遺傳算法比傳統(tǒng)遺傳算法更能體現(xiàn)云計(jì)算資源調(diào)度中的優(yōu)勢(shì)，特別是當(dāng)虛擬主機(jī)數(shù)量增加時(shí)這種優(yōu)勢(shì)更加明顯，更能適應(yīng)云計(jì)算大規(guī)模資源調(diào)度環(huán)境。

參考文獻(xiàn)：

[1] 陳康，鄭緯民.云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào)，2009，20（5）：1337-1348.

[2] 劉鵬.云計(jì)算[M].第2版.北京：電子工業(yè)出版社，2011：1-14.

[3] 鄧維，劉方明，金海，等.云計(jì)算數(shù)據(jù)中心的新能源應(yīng)用：研究現(xiàn)狀與趨勢(shì)[J].計(jì)算機(jī)學(xué)報(bào)，2013，36（3）：582-598.

[4] FOPING F S， DOKAS I M， FEEHAN J， et al. A new hybrid schema-sharing technique for multitenant applications[C]. Fourth IEEE International Conference on Digital Information Management， ICDIM 2009， November 1-4，2009， University of Michigan， Ann Arbor， Michigan，USA.2009：1-6.

[5] 張軍，詹志輝.計(jì)算智能[M].北京：國(guó)防工業(yè)出版社，1999：53-71.

[6] 周明，孫樹棟.計(jì)算智能[M].北京：清華大學(xué)出版社，2009.

[7] 陳華根，吳健生，王家林，等.模擬退火算法中關(guān)鍵參數(shù)的研究[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，32（6）：802-805.

[8] 劉洪，侯向.模擬退火算法中關(guān)鍵參數(shù)的研究[J].計(jì)算機(jī)工程與科學(xué)，2008，30（10）：55-57.

[9] BELOGLAZOV A， BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in Cloud data centers[J]. Concurrency & Computation Practice & Experience，2012，24（13）：1397-1420.

[10] HIRAI T， MASUYAMA H， KASAHARA S， et al. Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing[J].Journal of Industrial & Management Optimization，2014，10（1）：113-129.

[11] CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al.Cloud Simulation： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software Practice & Experience，2011，41（1）：23-50.

（責(zé)任編輯：杜能鋼）