張 皓，趙開(kāi)新，孫 冬

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

張 皓，趙開(kāi)新，孫 冬

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

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

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

0 引言

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

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

1 相關(guān)工作

1.1 問(wèn)題的描述

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

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

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

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

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

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

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

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

3.1 遺傳算法

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

3.1.1 遺傳算法的初始化

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

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

其中T表示任務(wù)編號(hào)，V表示任務(wù)T執(zhí)行時(shí)所占第個(gè)虛擬機(jī)編號(hào)，開(kāi)始時(shí)每個(gè)任務(wù)所占有的虛擬機(jī)是隨機(jī)的，通過(guò)交叉變異操作后，子任務(wù)可以分配到任一臺(tái)虛擬機(jī)上。

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

3.1.3 遺傳算法的交叉和變異

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

[10] 曾兆敏.基于改進(jìn)遺傳算法的云計(jì)算負(fù)載均衡研究[J].電子設(shè)計(jì)工程，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é)校重點(diǎn)科研項(xiàng)目（19A520019）；河南省科技攻關(guān)項(xiàng)目(202102210153)；河南省教育廳名師工作室項(xiàng)目（《2019》618）

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

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