云计算调度算法综述

杨威

摘 要：任務调度是云计算领域所要研究的核心问题，主要研究最优的任务分配策略，以使得任务得到均衡的分配或使得每个任务的执行代价降到最低或系统的总体性能达到最优。云计算中任务调度算法的好坏直接影响云计算系统整体性能。本文对当前云计算的调度算法进行了综述；介绍和分析了在云计算调度算法领域里比较有代表性的两个基本的算法--遗传算法和粒子群优化算法。

关键词：云计算；任务调度；遗传算法；粒子群优化算法

1.引言

云计算是一种基于互联网的新的服务模式，这种模式按使用量付费，提供可用的、便捷的、按需的网络访问，它将用户需求的计算任务分布在由大量计算机构成的数据中心，数据中心采用虚拟化技术，把各种软硬件资源抽象为虚拟化资源，再通过资源调度技术使各种应用能够根据需要获取计算能力、存储空间和信息服务[1]。

云计算任务调度的目的是给需要的用户分配不同的资源，在满足用户需求的前提下，使得任务完成时间尽量小，且资源利用率尽量高。调度最终要实现时间跨度、服务质量、负载均衡、经济原则最优等目标。云计算任务调度是云计算研究中的重点和难点。任务调度算法的优劣会影响到云计算系统处理任务的能力。

本文综述了云环境下的任务调度算法，分析了近几年来典型的云计算任务调度算法的发展趋势。

1 遗传算法[2][3]

1.1 遗传算法的概念

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它利用一定的编码技术和繁殖机制来处理复杂现象，适用于处理云计算环境中大规模、多种类资源的调度；是一种较好的云计算调度算法。

1.2 遗传算法的主要求解过程

遗传算法将问题的求解过程表示成"染色体"适者生存的过程，通过"染色体"群的一代代不断进化，包括选择、交叉和变异等操作，最终收敛到"最适应环境"的个体，从而求得问题的最优解或满意解。

遗传算法的基本运算过程如下：

（1）初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P（0）。

（2）个体评价：计算群体P（t）中各个个体的适应度。

（3）选择运算：将选择算子作用于群体。目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

（4）交叉运算：所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。

（5）变异运算：即对群体中的个体串的某些基因座上的基因值作变动。群体P（t）经过选择、交叉、变异运算之后得到下一代群体P（t1）。

（6）终止条件判断：若t=T，以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

1.3 遗传算法的主要特点

（1）传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。

（2）遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。

（3）遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。

1.4 遗传操作的三个基本遗传算子

1.4.1 选择

从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种：适应度比例方法、随机遍历抽样法、局部选择法。

1.4.2 交叉

在自然界生物进化过程中起核心作用的是生物遗传基因的重组（加上变异）。遗传算法中起核心作用的是遗传操作的交叉算子。交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

1.4.3 变异

变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。

遗传算法引入变异的目的： 一是使遗传算法具有局部的随机搜索能力。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。

遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力[4]。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。

2 粒子群优化算法[5]

2.1 粒子群优化算法的概念

粒子群优化又称粒子群算法，群粒子群优化算法是一种模拟鸟群觅食行为的演化计算算法。因其结构简单、参数少、易实现，所以受到广泛重视并被应用到了许多自然科学和工程科学领域。在云环境中，用粒子群优化算法进行资源调度能得到较好的效果。

2.2 算法原理

将每个个体看作是D维搜索空间中的一个没有体积的微粒，在搜索空间中以一定的速度飞行。第i个微粒表示为Xi=（xi1，xi2，...，xiD），它经历过的最好位置记为Pi=（pi1，pi2，...，piD），也称为pbest。在群体所有微粒经历过的最好位置的索引号用符号g表示，即Pg，也称为gbest。微粒i的速度用Vi=（vi1，vi2，...，viD）表示。它的第d维（1≤d≤D）根据如下方程进行变化：

vid=w*vid+c1*rand（）*（pid-xid）+c2*Rand（）*（pgd-xid）（1）

xid=xid+vid （2）

其中w为惯性权重，c1和c2为加速常数，rand（）和Rand（）为两个在[0，1]范围里变化的随机值。

2.3 标准粒子群算法的算法流程

（1）初始化一群微粒（群体规模为m），包括随机的位置和速度；

（2）评价每个微粒的适应度；

（3）对每个微粒，将它的适应值和它经历过的最好位置pbest比较，如果较好，则将其作为当前的最好位置pbest；

（4） 对每个微粒，将它的适应值和全局所经历最好位置gbest比较，如果较好，则重新设置gbest的索引号；

（5）根据（1）变化微粒的速度和位置；

（6）如未达到结束条件回到（2）。

3 总结和展望

在云計算中面对的用户群是庞大的，而遗传算法主要通过交叉算子繁殖后代，当交叉算子所作用的两个个体相同时，不能产生有意义的新个体，因此要求初始种群具有广泛的多样性，所以遗传算法用在云计算调度中会产生较好的效果，是一种有效的云计算调度算法。但是遗传算法在群体进化到其中各个个体均非常相似时，仅靠变异算子产生新的个体，遗传迭代难以进行下去，容易发生所谓的"早熟收敛"现象，如何有效地配合使用交叉和变异操作以防止这种现象的发生，是遗传算法的一个研究重点。

粒子群优化算法是一种基于群体的自适应搜索优化算法，对于云环境中大规模、多种类的资源调度是一种有效的云计算调度算法。因其结构简单、参数少、易实现，所以受到广泛重视并被应用到了许多自然科学和工程科学领域。但对于存在较多局部极值的搜索空间，它很容易陷入局部最优，在进化后期收敛速度慢，如何避免粒子群优化算法陷入局部最优，是以后研究的一个重要方向。

参考文献

[1]张艳敏.云计算中任务调度算法的研究综述.[J].电子商务，2016.7

[2]葛继科，邱玉辉，吴春明，蒲国林. 遗传算法研究综述[ J ] . 计算机应用研究，2008.10

[3]王小平，曹立明.遗传算法[ M ].西安：西安交通大学出版社，2002.

[4]刘东山，周显春.云计算调度算法综述.[J]计算机安全，2012.10

[5]杨伟新，张晓森.甘肃科技[J].2012.5

本文是安徽财经大学科研项目：《自适应云服务组合优化算法研究》（ACKY1435）的研究成果。