改进遗传算法在云资源任务调度中的应用

张 皓，赵开新，孙 冬

改进遗传算法在云资源任务调度中的应用

张 皓，赵开新，孙 冬

（河南工学院 计算机科学与技术学院，河南 新乡 453003）

为了缩短云环境中资源的调度和任务执行时间，均衡各虚拟机的负载，从影响虚拟机性能的内核、内存和带宽三个关键因素来分析研究，建立基于时间和负载的约束函数，并对遗传算法中交叉和变异两个过程进行改进，提出了基于改进遗传算法的云资源任务调度方案。在CloudSim仿真平台上的实验显示，在相同的云资源任务环境中，与基本遗传算法相比，所提方案的负载均衡率平均提高了15%，当任务数量增加到300个时，任务总完成时间节省了20多秒。

遗传算法；负载均衡；任务调度；云计算

0 引言

作为一种新技术，云计算技术具有高可靠性、按需付费、超大规模弹性服务等优点，在学术和商业界都得到了广泛的研究与应用[1]。云环境下资源调度是云计算成功与否的关键因素之一。目前国内外许多学者把蚁群算法、遗传算法、粒子群算法等智能算法[2-4]应用到云资源任务调度过程中，均取得一定的效果。

遗传算法在解决多项式复杂程度的非确定性问题（Non-deterministic Polynomial Complete ,NP）时具有突出的优越性，受到越来越多的国内外研究人员的关注。但传统的遗传算法也存在明显的不足，当云计算规模不断扩大时，云用户不断增加，其收敛性逐渐下降。本文把改进后的遗传算法应用到云资源任务调度中，并在CloudSim仿真环境下实验。实验结果表明，与基本遗传算法相比，改进后的遗传算法在任务执行时间和虚拟机负载均衡方面均具有明显优势。

1 相关工作

1.1 问题的描述

1.2 云计算环境下任务调度流程

云计算中资源调度的目的是使用户能够像使用天燃气、水、电一样方便地享用虚拟资源[5-6]。虚拟资源是物理机虚拟出来的一组虚拟机集合，通过一定的任务调度算法把任务映射到相应的虚拟机上，在各虚拟机上执行分配的任务，并且任务在各虚拟机上是并发执行的[7-8]。具体流程如图1所示。

图1 云计算环境下任务调度流程图

从图1可以看出，云资源调度的效率主要取决于任务和虚拟机两者之间高效合理的映射，这由云资源任务调度算法来决定[9]。各虚拟机所分配的任务量是否实现了负载均衡，是影响虚拟机利用率和整个云资源任务调度效率的关键因素。

2 云计算资源调度的关键因素

2.1 云资源调度的时间控制

2.2 云资源调度的负载控制

3 基于遗传算法的云任务调度及改进算法

3.1 遗传算法

遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。目前是解决组合优化问题的重要智能方法之一，遗传算法分为主从式遗传算法、细粒度遗传算法和粗粒度遗传算法。为了保持种群的多样性，本文使用粗粒度遗传算法来实现云资源中任务和虚拟机之间的映射和调度。

3.1.1 遗传算法的初始化

考虑到大规模任务处理的特性，本文采用间接编码的染色体编码方式，即任务-虚拟机映射模式。对每个子任务所占虚拟机进行编码，每条染色体基因的总长度表示子任务的总数量，染色体中每一位基因都为正整数，代表子任务编号，此位置上的值代表该子任务所占虚拟机编号，云计算环境下有个任务、个虚拟机，任务和虚拟机的映射关系如图2所示。

图2 任务和虚拟机映射关系图

其中T表示任务编号，V表示任务T执行时所占第个虚拟机编号，开始时每个任务所占有的虚拟机是随机的，通过交叉变异操作后，子任务可以分配到任一台虚拟机上。

3.1.2 遗传算法的适应度函数

3.1.3 遗传算法的交叉和变异

传统的遗传算法容易陷入局部最优，本文设计了一种新的交叉算法。根据交叉概率，在交叉操作之前，先通过适应度函数计算各个体适应度的值，并把所有个体按适应度值的大小分为群体较优组和群体较差组，然后从较优和较差组中随机各选择一个个体进行交叉，交叉操作后对新产生的子个体和父个体的适应度值进行比较，采用优胜劣汰的方法选择子个体。遗传算法的变异操作是为了增加种群的多样性，但是变异率过高，容易使算法收敛速度降低，本文根据个体的适应度值的大小选择不同的变异概率，计算各个体适应度函数值，并划分为群体较优组和群体较差组，较优组个体变异率为0.05，较差组个体变异率为0.1，这样既提高了算法收敛速度，又增加了种群的多样性。

3.2 基于改进遗传算法的云资源任务调度流程

基于改进遗传算法的云资源任务调度流程如图3所示。

图3 改进遗传算法的云资源任务调度流程图

4 实验仿真

虚拟机的负载均衡度是衡量任务调度方案优劣的重要因素之一。从图4可以看出IGA算法的虚拟机负载均衡度在0.8到0.5之间，并且随着任务数增多基本呈现减小趋势，而GA算法的虚拟机负载均衡度在0.5到0.4之间，随着任务数增多也基本呈现减小趋势。各任务下IGA算法的负载均衡度平均提高了近15%，从图4可以看出，改进的遗传算法能一定程度上平衡各虚拟机负载。

图4 负载均衡度对比图

由图5、图6、图7可以看出，在任务数相同的条件下，随着迭代次数的增加，任务总的完成时间逐渐减少，最终趋于收敛。当任务数为100时，两种算法收敛后，任务总完成时间相差大概2秒左右，随着任务数量的增加，两种算法的任务总完成时间差别越来越大，当任务数为300并且两种算法收敛时，任务总完成时间IGA比GA节省了20多秒。通过比较可以看出迭代早期两者收敛速度相差不大，但后期GA算法收敛速度较慢，且无法跳出局部最优，因此GA算法最终收敛后任务完成时间大于IGA的最终收敛后任务完成时间，而IGA算法根据个体的适应度值的大小选择不同的变异概率，提高了种群的多样性，避免了局部最优，进而提高了算法的收敛速度和效率。

图5 任务数为100时总完成时间

图6 任务数为200时总完成时间

图7 任务数为300时总完成时间

5 结束语

针对云资源任务调度所存在的效率低、负载不均衡问题，通过建立虚拟机内核、内存和带宽的约束函数作为遗传算法的适应度函数，并改进遗传算法的交叉和变异，把改进后的遗传算法应用到云资源调度过程中，在CloudSim仿真平台下进行测试，结果表明IGA算法能使云资源调度在较少的迭代次数下，实现较优的收敛，并一定程度上避免了个别虚拟机资源负载过重的情况，实现了各虚拟机的负载均衡。

[1] 高天阳,虞慧群,范贵生. 基于模拟退火遗传算法的云资源调度方法[J].华东理工大学学报(自然科学版),2019,45(3):417-477.

[2] 毛莉君,王林兵,张燕.云计算下的一种基于改进的量子遗传算法在资源分配的研究[J].科技通报,2017,33(11):141-144.

[3] 王波,张晓磊. 基于粒子群遗传算法的云计算任务调度研究[J].计算机工程与应用，2015,51(6):84-87.

[4] 李国,远王健,刘秀涵，等.改进的自适应遗传算法支持下点云与BIM模型配准[J].测绘通报,2020(2):160-162.

[5] 康艳芳,聂规划,陈冬林,等.基于遗传算法的云服务商伙伴选择问题研究[J].计算机应用研究，2015,32(1):26-29.

[6] 魏赟,陈元元.基于改进蚁群算法的云计算任务调度模型[J].计算机工程,2015,41(2):12-17.

[7] 李超,戴炳荣,旷志光，等.云计算环境下基于改进遗传算法的多维约束任务调度研究[J].小型微型计算机系统，2017,38(9):1945-1949.

[8] 张文金,许爱军.基于云计算的混合并行遗传算法求解最短路径[J].电子技术应用,2015,23(6):123-126.

[9] 徐占洋,郑克长.云计算下基于改进遗传算法的聚类融合算法[J].计算机应用研究，2018,38(2):458-463.

[10] 曾兆敏.基于改进遗传算法的云计算负载均衡研究[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

河南省高等学校重点科研项目（19A520019）；河南省科技攻关项目(202102210153)；河南省教育厅名师工作室项目（《2019》618）

张皓（1983―），男，河北保定人，实验师，硕士，主要从事智能算法及应用、数据分析处理研究。

（责任编辑吕春红）