改進遺傳算法在云計算資源優化調度中的應用

鞠成恩 趙曉俠 王明興 問尤龍

摘 要：在大量用戶請求云計算資源服務時，如何合理組織資源和任務調度是云計算的關鍵技術之一。如果分配調度方法不合理，就可能產生用戶需求得不到滿足和資源使用不均衡等問題。在傳統遺傳算法基礎上，將模擬退火算法與遺傳算法相融合，擴大遺傳算法的搜索領域，解決遺傳算法早熟收斂現象，使云資源分配更加合理，以提高云資源利用率。在CloudSim平臺上進行仿真，結果表明該方式能較好地對云計算資源進行分配，在能耗、帶寬等約束條件下達到云資源最優調度的目的。

關鍵詞：智能算法；云資源；優化調度；CloudSim仿真

DOI：10.11907/rjdk.172641

中圖分類號：TP312

文獻標識碼：A 文章編號：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 引言

云計算[1-2]由網格計算發展而來，它將計算資源、存儲資源和網絡資源進行整合，按照用戶需求進行分配資源服務，是一種新興的網絡服務和交互模式。云計算在云端部署計算機集群，運用虛擬化技術組成一個大型虛擬資源池（Virtualized Resource Pool）[3]，利用各種工具對虛擬資源池進行統一管理；在終端為用戶與運營商提供服務接口，運營商通過這些接口為用戶提供可擴展、分布式存儲與計算等服務，用戶在使用時可以對資源自行管理與配置[4]。

大多數情況下云計算的資源調度任務并發產生，且分布不均勻，當用戶群體十分龐大時，虛擬機優化調度會越來越復雜，需要云計算系統提供靈活的分配機制，這些需求使云計算調度變得困難。本文以基本遺傳算法[5-6]為基礎，引入模擬退火算法[7-8]與之相融合，以改進遺傳算法的局部搜尋能力，擴大遺傳算法搜索領域，從而有效解決了遺傳算法早熟收斂現象，使資源分配更加合理、高效。

1 基于遺傳算法的資源調度算法設計

1.1 編碼表示方法與初始種群產生

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

將N個虛擬機放置在M個主機上，得到個體基因編碼{k0，k1，…kn-1}。其中第i個虛擬機ki的取值范圍為[0，m-1]。用一個具體例子說明：當虛擬機的數量為10，主機數量為5時，編碼將產生一個長度為10的序列，假設產生的序列為{2，3，1，4，0，0，1，2，2，3}，虛擬機在編號0-9中分別按照序列{2，3，1，4，0，0，1，2，2，3}的順序創建在對應主機上。

1.2 適應度函數

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

1.3 選擇與交叉算子

使用更加合理的輪盤賭方式選擇算子。輪盤賭是累積并記錄種群中各基因的適應值，然后用一個位于[0，1]區間的隨機數D做閾值，當D大于某個基因記錄值時某個基因就被選中。例如基因數量為M種群{K1，K2，…，Km}，對應的累積值為{ΔF1，ΔF2，…，ΔFm}，ΔFi由式（2）確定。如果產生的隨機數D剛好大于ΔFi，則Ki號基因被選中：

這樣連續進行M次形成新的種群，通過新的種群進行單點交叉算子操作。在每個個體中隨機選擇一個位置作為交叉點，將一個體染色體在交叉點位置分為前后兩部分，與另一個體的部分基因進行交換。

1.4 變異方式

本文采用多點變異方式，在個體染色體內隨機選擇多個位置，每個位置進行小范圍變異，設置變異界值為0.1，若產生的隨機數小于0.1則發生變異，否則不發生變異。

2 融合模擬退火算法

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

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

3 仿真

本文采用 Cloud Sim仿真工具進行仿真試驗。 Cloud Sim 是由澳大利亞墨爾本大學的網格實驗室推出的一款具有跨平臺特點的云計算仿真軟件[11]，是一個模擬大規模云計算數據中心的開源框架，在云資源調度研究中使用非常廣泛。

初始化的參數需要對用戶數量、日期、追蹤標志等進行定義，數據中心是 Power 類型，創建數據中心代理Broker，這里代理的類型也是 Power 類型；創建虛擬機數和主機數，這里設置虛擬機數和主機數量比例為2∶1；設置調度策略配置遺傳算法；創建云任務，實驗采用Cloud Sim 自帶的云工作平臺下的任務。

設置遺傳算法所需相關參數：初始種群規模為20，變異率為0.01，起始溫度參數k為100，溫度下降參數α為0.8，溫度下降時迭代數20。傳統遺傳算法及融合退火算法對云資源分配的仿真結果比較如圖2所示。

4 結語

通過在Cloud Sim平臺上進行仿真實驗，將融入模擬退火算法改進后的遺傳算法與改進前的遺傳算法進行比較。實驗表明：融入模擬退火算法的遺傳算法比傳統遺傳算法更能體現云計算資源調度中的優勢，特別是當虛擬主機數量增加時這種優勢更加明顯，更能適應云計算大規模資源調度環境。

參考文獻：

[1] 陳康，鄭緯民.云計算：系統實例與研究現狀[J].軟件學報，2009，20（5）：1337-1348.

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

[3] 鄧維，劉方明，金海，等.云計算數據中心的新能源應用：研究現狀與趨勢[J].計算機學報，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] 張軍，詹志輝.計算智能[M].北京：國防工業出版社，1999：53-71.

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

[7] 陳華根，吳健生，王家林，等.模擬退火算法中關鍵參數的研究[J].同濟大學學報：自然科學版，2004，32（6）：802-805.

[8] 劉洪，侯向.模擬退火算法中關鍵參數的研究[J].計算機工程與科學，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.

（責任編輯：杜能鋼）