張 皓，趙開新，孫 冬

改進遺傳算法在云資源任務(wù)調(diào)度中的應(yīng)用

張 皓，趙開新，孫 冬

（河南工學(xué)院 計算機科學(xué)與技術(shù)學(xué)院，河南 新鄉(xiāng) 453003）

為了縮短云環(huán)境中資源的調(diào)度和任務(wù)執(zhí)行時間，均衡各虛擬機的負(fù)載，從影響虛擬機性能的內(nèi)核、內(nèi)存和帶寬三個關(guān)鍵因素來分析研究，建立基于時間和負(fù)載的約束函數(shù)，并對遺傳算法中交叉和變異兩個過程進行改進，提出了基于改進遺傳算法的云資源任務(wù)調(diào)度方案。在CloudSim仿真平臺上的實驗顯示，在相同的云資源任務(wù)環(huán)境中，與基本遺傳算法相比，所提方案的負(fù)載均衡率平均提高了15%，當(dāng)任務(wù)數(shù)量增加到300個時，任務(wù)總完成時間節(jié)省了20多秒。

遺傳算法；負(fù)載均衡；任務(wù)調(diào)度；云計算

0 引言

作為一種新技術(shù)，云計算技術(shù)具有高可靠性、按需付費、超大規(guī)模彈性服務(wù)等優(yōu)點，在學(xué)術(shù)和商業(yè)界都得到了廣泛的研究與應(yīng)用[1]。云環(huán)境下資源調(diào)度是云計算成功與否的關(guān)鍵因素之一。目前國內(nèi)外許多學(xué)者把蟻群算法、遺傳算法、粒子群算法等智能算法[2-4]應(yīng)用到云資源任務(wù)調(diào)度過程中，均取得一定的效果。

遺傳算法在解決多項式復(fù)雜程度的非確定性問題（Non-deterministic Polynomial Complete ,NP）時具有突出的優(yōu)越性，受到越來越多的國內(nèi)外研究人員的關(guān)注。但傳統(tǒng)的遺傳算法也存在明顯的不足，當(dāng)云計算規(guī)模不斷擴大時，云用戶不斷增加，其收斂性逐漸下降。本文把改進后的遺傳算法應(yīng)用到云資源任務(wù)調(diào)度中，并在CloudSim仿真環(huán)境下實驗。實驗結(jié)果表明，與基本遺傳算法相比，改進后的遺傳算法在任務(wù)執(zhí)行時間和虛擬機負(fù)載均衡方面均具有明顯優(yōu)勢。

1 相關(guān)工作

1.1 問題的描述

1.2 云計算環(huán)境下任務(wù)調(diào)度流程

云計算中資源調(diào)度的目的是使用戶能夠像使用天燃?xì)狻⑺?、電一樣方便地享用虛擬資源[5-6]。虛擬資源是物理機虛擬出來的一組虛擬機集合，通過一定的任務(wù)調(diào)度算法把任務(wù)映射到相應(yīng)的虛擬機上，在各虛擬機上執(zhí)行分配的任務(wù)，并且任務(wù)在各虛擬機上是并發(fā)執(zhí)行的[7-8]。具體流程如圖1所示。

圖1 云計算環(huán)境下任務(wù)調(diào)度流程圖

從圖1可以看出，云資源調(diào)度的效率主要取決于任務(wù)和虛擬機兩者之間高效合理的映射，這由云資源任務(wù)調(diào)度算法來決定[9]。各虛擬機所分配的任務(wù)量是否實現(xiàn)了負(fù)載均衡，是影響虛擬機利用率和整個云資源任務(wù)調(diào)度效率的關(guān)鍵因素。

2 云計算資源調(diào)度的關(guān)鍵因素

2.1 云資源調(diào)度的時間控制

2.2 云資源調(diào)度的負(fù)載控制

3 基于遺傳算法的云任務(wù)調(diào)度及改進算法

3.1 遺傳算法

遺傳算法（Genetic Algorithm, GA）是模擬達(dá)爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。目前是解決組合優(yōu)化問題的重要智能方法之一，遺傳算法分為主從式遺傳算法、細(xì)粒度遺傳算法和粗粒度遺傳算法。為了保持種群的多樣性，本文使用粗粒度遺傳算法來實現(xiàn)云資源中任務(wù)和虛擬機之間的映射和調(diào)度。

3.1.1 遺傳算法的初始化

考慮到大規(guī)模任務(wù)處理的特性，本文采用間接編碼的染色體編碼方式，即任務(wù)-虛擬機映射模式。對每個子任務(wù)所占虛擬機進行編碼，每條染色體基因的總長度表示子任務(wù)的總數(shù)量，染色體中每一位基因都為正整數(shù)，代表子任務(wù)編號，此位置上的值代表該子任務(wù)所占虛擬機編號，云計算環(huán)境下有個任務(wù)、個虛擬機，任務(wù)和虛擬機的映射關(guān)系如圖2所示。

圖2 任務(wù)和虛擬機映射關(guān)系圖

其中T表示任務(wù)編號，V表示任務(wù)T執(zhí)行時所占第個虛擬機編號，開始時每個任務(wù)所占有的虛擬機是隨機的，通過交叉變異操作后，子任務(wù)可以分配到任一臺虛擬機上。

3.1.2 遺傳算法的適應(yīng)度函數(shù)

3.1.3 遺傳算法的交叉和變異

傳統(tǒng)的遺傳算法容易陷入局部最優(yōu)，本文設(shè)計了一種新的交叉算法。根據(jù)交叉概率，在交叉操作之前，先通過適應(yīng)度函數(shù)計算各個體適應(yīng)度的值，并把所有個體按適應(yīng)度值的大小分為群體較優(yōu)組和群體較差組，然后從較優(yōu)和較差組中隨機各選擇一個個體進行交叉，交叉操作后對新產(chǎn)生的子個體和父個體的適應(yīng)度值進行比較，采用優(yōu)勝劣汰的方法選擇子個體。遺傳算法的變異操作是為了增加種群的多樣性，但是變異率過高，容易使算法收斂速度降低，本文根據(jù)個體的適應(yīng)度值的大小選擇不同的變異概率，計算各個體適應(yīng)度函數(shù)值，并劃分為群體較優(yōu)組和群體較差組，較優(yōu)組個體變異率為0.05，較差組個體變異率為0.1，這樣既提高了算法收斂速度，又增加了種群的多樣性。

3.2 基于改進遺傳算法的云資源任務(wù)調(diào)度流程

基于改進遺傳算法的云資源任務(wù)調(diào)度流程如圖3所示。

圖3 改進遺傳算法的云資源任務(wù)調(diào)度流程圖

4 實驗仿真

虛擬機的負(fù)載均衡度是衡量任務(wù)調(diào)度方案優(yōu)劣的重要因素之一。從圖4可以看出IGA算法的虛擬機負(fù)載均衡度在0.8到0.5之間，并且隨著任務(wù)數(shù)增多基本呈現(xiàn)減小趨勢，而GA算法的虛擬機負(fù)載均衡度在0.5到0.4之間，隨著任務(wù)數(shù)增多也基本呈現(xiàn)減小趨勢。各任務(wù)下IGA算法的負(fù)載均衡度平均提高了近15%，從圖4可以看出，改進的遺傳算法能一定程度上平衡各虛擬機負(fù)載。

圖4 負(fù)載均衡度對比圖

由圖5、圖6、圖7可以看出，在任務(wù)數(shù)相同的條件下，隨著迭代次數(shù)的增加，任務(wù)總的完成時間逐漸減少，最終趨于收斂。當(dāng)任務(wù)數(shù)為100時，兩種算法收斂后，任務(wù)總完成時間相差大概2秒左右，隨著任務(wù)數(shù)量的增加，兩種算法的任務(wù)總完成時間差別越來越大，當(dāng)任務(wù)數(shù)為300并且兩種算法收斂時，任務(wù)總完成時間IGA比GA節(jié)省了20多秒。通過比較可以看出迭代早期兩者收斂速度相差不大，但后期GA算法收斂速度較慢，且無法跳出局部最優(yōu)，因此GA算法最終收斂后任務(wù)完成時間大于IGA的最終收斂后任務(wù)完成時間，而IGA算法根據(jù)個體的適應(yīng)度值的大小選擇不同的變異概率，提高了種群的多樣性，避免了局部最優(yōu)，進而提高了算法的收斂速度和效率。

圖5 任務(wù)數(shù)為100時總完成時間

圖6 任務(wù)數(shù)為200時總完成時間

圖7 任務(wù)數(shù)為300時總完成時間

5 結(jié)束語

針對云資源任務(wù)調(diào)度所存在的效率低、負(fù)載不均衡問題，通過建立虛擬機內(nèi)核、內(nèi)存和帶寬的約束函數(shù)作為遺傳算法的適應(yīng)度函數(shù)，并改進遺傳算法的交叉和變異，把改進后的遺傳算法應(yīng)用到云資源調(diào)度過程中，在CloudSim仿真平臺下進行測試，結(jié)果表明IGA算法能使云資源調(diào)度在較少的迭代次數(shù)下，實現(xiàn)較優(yōu)的收斂，并一定程度上避免了個別虛擬機資源負(fù)載過重的情況，實現(xiàn)了各虛擬機的負(fù)載均衡。

[1] 高天陽,虞慧群,范貴生. 基于模擬退火遺傳算法的云資源調(diào)度方法[J].華東理工大學(xué)學(xué)報(自然科學(xué)版),2019,45(3):417-477.

[2] 毛莉君,王林兵,張燕.云計算下的一種基于改進的量子遺傳算法在資源分配的研究[J].科技通報,2017,33(11):141-144.

[3] 王波,張曉磊. 基于粒子群遺傳算法的云計算任務(wù)調(diào)度研究[J].計算機工程與應(yīng)用，2015,51(6):84-87.

[4] 李國,遠(yuǎn)王健,劉秀涵，等.改進的自適應(yīng)遺傳算法支持下點云與BIM模型配準(zhǔn)[J].測繪通報,2020(2):160-162.

[5] 康艷芳,聶規(guī)劃,陳冬林,等.基于遺傳算法的云服務(wù)商伙伴選擇問題研究[J].計算機應(yīng)用研究，2015,32(1):26-29.

[6] 魏赟,陳元元.基于改進蟻群算法的云計算任務(wù)調(diào)度模型[J].計算機工程,2015,41(2):12-17.

[7] 李超,戴炳榮,曠志光，等.云計算環(huán)境下基于改進遺傳算法的多維約束任務(wù)調(diào)度研究[J].小型微型計算機系統(tǒng)，2017,38(9):1945-1949.

[8] 張文金,許愛軍.基于云計算的混合并行遺傳算法求解最短路徑[J].電子技術(shù)應(yīng)用,2015,23(6):123-126.

[9] 徐占洋,鄭克長.云計算下基于改進遺傳算法的聚類融合算法[J].計算機應(yīng)用研究，2018,38(2):458-463.

[10] 曾兆敏.基于改進遺傳算法的云計算負(fù)載均衡研究[J].電子設(shè)計工程，2018,38(2):42-45.

Application of Improved Genetic Algorithm in Cloud Resource Task Scheduling

ZHANG Hao, ZHAO Kai-xin, SUN Dong

(School of Computer Science and Technology, Henan Institute of Technology, Xinxiang 453003, China)

In order to shorten the time of resource scheduling and task execution in cloud environment, balance the load of each virtual machine, analysis and research on three key factors which affect the performance of virtual machine, such as kernel, memory and bandwidth, designs load constraint function based on time, two processes of crossover and mutation in genetic algorithm are improved, and the task scheduling algorithm based on improved genetic algorithm is proposed. In CloudSim environment simulation results show that the load balancing rate of the proposed scheme is improved by 15%. when the number of tasks increased to 300 and the algorithm convergence, the total task completion time of the proposed scheme saves more than 20 seconds, verify effectiveness and feasibility of the proposed scheme.

genetic algorithm; load balancing；task scheduling; cloud computing

TP399

A

2096–7772(2020)03–0024–06

2020-03-19

河南省高等學(xué)校重點科研項目（19A520019）；河南省科技攻關(guān)項目(202102210153)；河南省教育廳名師工作室項目（《2019》618）

張皓（1983―），男，河北保定人，實驗師，碩士，主要從事智能算法及應(yīng)用、數(shù)據(jù)分析處理研究。

（責(zé)任編輯呂春紅）