改进遗传算法在云计算资源优化调度中的应用

鞠成恩 赵晓侠 王明兴 问尤龙

摘 要：在大量用户请求云计算资源服务时，如何合理组织资源和任务调度是云计算的关键技术之一。如果分配调度方法不合理，就可能产生用户需求得不到满足和资源使用不均衡等问题。在传统遗传算法基础上，将模拟退火算法与遗传算法相融合，扩大遗传算法的搜索领域，解决遗传算法早熟收敛现象，使云资源分配更加合理，以提高云资源利用率。在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.

（责任编辑：杜能钢）