基于混合优化算法的云计算资源调度策略的研究∗

阮江涛 吴海涛 钱 程 黄陈辉

（上海师范大学信息与机电工程学院 上海 200030）

1 引言

近几年来，云计算技术的发展非常迅速，与大数据，移动互联网，物联网等多种技术相互促进，俨然已经成为一种革命性的商业计算模式，也得到了广泛的应用和发展。云计算是分布式处理、并行处理和网格计算、虚拟化、效用计算、IaaS、PaaS、SaaS等技术融合的产物。云计算利用虚拟化技术，通过统一的调度和管理，将网络中庞大的、差异性大的任务，交给云服务器，经过分析，计算与处理将结果反馈给用户。Hadoop 平台作为云计算的核心，而资源调度器作为Hadoop平台［1］的核心组件，采取不同的调度算法［2～3］对用户提交的作业进行资源分配和调度，不同的调度算法会对整个集群产生不同的影响，这直接影响着提供给用户的服务质量。

目前，应用较为广泛的作业调度算法［2］包括FIFO 调度算法、Yahoo公司研发的计算能力调度算法（Capacity Scheduler）和Facebook 公司研发的公平调度算法（Fair Scheduler）。在目前发行的Ha⁃doop版本中，都包含了这三种资源调度算法构成的资源调度器，但是这些资源调度器的调度算法在实际的应用场景中仍然存在一些不足和缺陷，还是不能满足不同应用程序的服务质量要求。为了尽可能避免这些不足和缺陷，许多学者对hadoop的资源调度算法进行了改善。其中刘愉，张沫等［5～9］改进了传统的遗传算法等智能算法来优化云计算资源调度，调度性能在一定程度上得到了提升。

遗传算法和粒子群算法相似，其中遗传算法具有全局搜索能力，容易陷入局部最优，而粒子群算法局部搜索能力较强，收敛速度快，容易陷入局部极小，鉴于两者互补的优势［10～11］，本文提出了一种基于改进的遗传算法与粒子群算法结合起来的混合优化算法，对资源调度策略进行相关研究。

2 云计算资源调度

2.1 MapReduce编程模型

在Hadoop 系统中，任务调度器是一个非常重要的组件，影响到整个平台的系统资源的利用率和性能。其中Google 开发的MapReduce 模型［12］是当前应用最广泛的大数据处理编程模型，该模型工作原理概述为：用户提交作业之后，map 函数将作业分解为多个子任务，将这些子任务通过云计算资源调度算法分配到虚拟机节点上，等到子任务完成之后，然后由reduce 函数将中间结果汇总分析处理，最后输出结果数据。MapReduce 编程模型执行流程可以用图1表示。

图1 MapReduce编程模型流程图

2.2 云计算资源调度原理

在云计算作业中，任务与资源并不是一一对应的关系，而是先通过任务与资源相关联，然后将资源映射到对应的物理设备上，从而完成作业的调度。简单的来说，下面的5元组可以描述资源调度［13］的过程：

式中，S 表示一个完整的调度过程，T={t1，t2，…，tm}表示任务数量的集合，R ={r1，r2，…，rm} 表示资源数量的集合，D={d1，d2，…，dm}表示物理设备数量的集合，Mtr表示资源与任务之间的映射关系，Mrd表示资源与物理设备之间的映射关系。

其中Mtr是由计算机中心进行任务分配的，而Mrd是由资源调度器将资源调度到相应的存储设备上，因此资源调度解决的主要问题是资源到存储设备的调度。

假设现在有任务ti通过映射关系Mtr映射到资源vj上，资源vj通过调度算法调度到物理设备dk上，将任务ti通过计算机中心分配资源然后到达物理设备dk的过程，其预期执行时间记为ETD(ti，dk)，任务T对物理设备D分配矩阵记为

上面式子为一个执行时间矩阵，表示通过资源映射关系tiMtr将m 个任务分配到n 个设备上的执行时间矩阵。

任务ti通过映射关系Mtr在物理设备dk上最早完成时间记为

式中，Start(dk)表示物理设备dk上可以执行任务的最早开始时间，因此，物理设备dk上分配任务需要花费的总时间可以使用下面式子表示：

式中，cik=1 表示任务ti在物理设备dk上执行，因此，所有的任务通过资源调度器执行的总时间为

优化资源调度算法，为的就是通过资源调度器使得任务执行时间最短，即上式中的值最小，因此资源调度的目标函数为

3 遗传和粒子群算法

3.1 标准粒子群算法（PSO）

粒子群算法（PSO），又称微粒子群算法［14］，是由R.C.Eberhart 和J.Kennedy 等在1995 年提出的一种演化算法，最初的目的是为了图形化的模拟鸟群无规则的运动。该算法的使用背景是群体，通过对环境适应度的计算，将群体中的个体移动到更好的位置。PSO 算法将每个个体比作D 维空间中的一个个没有体积的粒子，在空间中按照特定的速度飞行，飞行速度会根据同伴的和自身的飞行经验动态更新。以下公式可以粒子速度和粒子位置的更新公式：

其中，d=1，2，…，D，表示搜索空间的维度，表示第k 次迭代粒子i 飞行速度矢量的第d 维分量，示第k次迭代粒子i位置矢量的第d维分量，w为惯性权重，用于调节对解空间的搜素范围，c1、c2为加速常数，调节学习最大步长，r1、r2为两个随机函数，取值范围为［0，1］，为的是增加搜索的随机性。

3.2 经典遗传算法

遗传算法［15］（Genetic Algorithm）是在1975年由美国Michigan 大学holland 教授提出来，该算法是一种模拟达尔文生物进化论的一种自适应的全局优化概率搜索算法。遗传算法类似于自然进化，通过作用在染色体上的基因来找寻更好的染色体来求解。作为一种群体智能进化算法，相比一般的优化算法具备很好的收敛性，计算精度高，计算时间少以及具备较好的鲁棒性。

4 改进的遗传算法

4.1 编码

标准的遗传算法使用的是二进制编码，该编码方式是由字符集｛0，1｝组成，所组成的个体基因为二进制编码字符串。本文研究的问题是将作业按照调度算法将

放入作业队列中，具有连续性。如果采用二进制编码的话，会使得连续的函数变成离散型函数。二进制编码显著的缺点是较大的Hamming距离，在交叉和突变变得难以跨越，而且准确度不高。实数编码使用的是Euclidean 距离，使得遗传算法更能接近问题空间，因此本文打算使用实数编码。

4.2 适应度函数

云计算中所有任务完成时间长短是衡量云计算资源调度算法的好坏的标准，适应度值越大，则表明调度算法更好，因此适应度函数［16］可以表示为

本文适应度函数中引入动态惩罚函数，对于不符合约束条件的个体，给出一个小的适应值，其惩罚函数可以表示为

式中，t表示进化的次数，通常情况下c=0.5 ，α=β=2。因此加上动态惩罚函数的适应度函数可以表示为

4.3 选择算子

本文采用比例模型方法，即轮盘赌方式，它是一种回放式的随机采样方法，基于的是适者生存的思想。假设种群大小为M，其中某个染色体个体的适应度为fi，它被选择的概率Pi可以表示为

4.4 交叉算子

在遗传算法中，在交叉计算前需要进行个体的配对，通常使用随机配对模式。假设在一个有W个个体的种群中，随机组成W/2 对，在这随机组成的两两个体之间配对。

本文采用实数编码方式，因此可以使用算数交叉方式，进行交叉的两个父代个体Xi和Xj通过算数交叉后得到两个子代个体和，交叉操作可以表示为

式中，i，j=1，2，..，W/2 ，γ取值为区间[ ]0，1 上均匀分布的随机数。

4.5 变异算子

由于本文采用的是实数编码方式，因此使用非均 匀 变 异 算 子 。 假 设 变 异 个 体 为W=[w1，w2，…，wk，…，wL]T，以概率为Pm进 行 变异，其中wk的取值范围为(wk_min，wk_max)，变异后可以用式（15）表示：

图2 云计算资源调度算法工作流程图

式中，t表示进化的代数，α表示在区间(0，1)上均匀分布的随机数，那么∆(t，x)表示在区间[0 ，x] 上非均匀分布的随机数，其表达式可以描述为

式中，b 表示的是确定非均匀度的参数，β取值为区间[0 ，1] 上的随机数，T 表示的是最大进化的代数。

5 混合优化算法

本文采用串行式混合优化算法，将遗传算法进化得出的种群作为粒子群算法进化的初始种群，结合遗传算法的全局搜索能力和粒子群算法局部搜索能力的优点，可以得出较优的云计算资源调度方案。根据改进的混合优化算法，云计算资源调度流程图如图2所示，执行步骤如下所示。

Step1：确定云计算资源调度数量，并且初始化种群，确定迭代次数，种群大小N，加速常数c1，c2等参数。

Step2：通过加入惩罚函数的适应度函数，对每个染色体进行适应度评估，得出对应的适应度值。

Step3：通过比例模型方式选择策略在当前种群中选择个体，然后通过算数交叉方式和非均匀变异算子执行。

Step4：根据是否满足终止条件，如果满足则将优化后的种群作为粒子群算法的初始化种群。如果不满足则转到Step2。

Step5：选择改进的遗传算法中最优的解作为粒子群算法的初始粒子，并且对每个粒子进行初始化。

Step6：更新群极值和个体极值。

Step6：更新每个粒子的速度和位置。

Step7：根据是否满足终止条件，如果满足则作为输出相应的粒子位置，得出最优云计算资源调度方案。如果不满足则转到Step6。

6 实验仿真及结果分析

为了验证改进的资源调度算法在云计算中的效果，本文通过CloudSim 仿真平台对本文改进的算法和其他算法进行资源调度比较。

在同样的实验条件下，选择遗传算法（GA）和改进后的混合优化算法（GA-PSO）进行实验。其中资源数量为20 个，任务数量范围为［1000，4000］，交叉概率设为0.8，变异概率设为0.2。其仿真结果如图3所示。

由图3 可知，在任务数较多的情况下，改进的混合优化调度算法比传统的遗传调度算法还有具有一点优势的。接下来的任务是在指定的大数据大量任务数为4000 的情况下，研究算法迭代次数与执行时间的关系，其仿真结果如图4所示。

图3 大数据量下算法的任务完成对比图

图4 两种算法种群收敛对比图

由上图可知，迭代初期两种算法的效果其实差别不明显，到后期随着迭代次数的增加，优化后的算法在120 代之后已经接近成熟，而传统的遗传算法具有异常的适应值，可能是种群向着错误的方向进化的结果，在优化后的改进的资源调度算法比传统的调度算法效果更好。

综上所述，改进的混合优化调度算法克服了传统调度算法缺点，得到了一种更优的云计算调度策略，既缩短了作业完成时间，又提高了系统资源利用率。

7 结语

针对云计算中资源调度问题，本文引入了遗传算法和粒子群算法，将改进后的算法进行融合，进行资源的调度，结合了遗传算法的全局搜索能力和粒子群算法的局部搜索能力，相比传统的算法在调度效果上有了明显的进步。接下来的研究任务可以从将更多智能算法和机器学习算法与云计算资源调度结合，从而优化调度效率不高或者负载不均衡的问题。