云计算环境中优化混合遗传算法的资源调度研究

王静++陈家琪

摘 要：将云计算传统的遗传算法应用到任务调度中，存在迭代次数多、资源利用率低、执行时间长等问题。因此，提出贪心算法来初始化种群，以避免随机初始化种群时基因的低表现性，并且引进精英因子到传统遗传算法中以优化收敛速度。设计出双适应度函数，兼顾考虑用户对执行时间和带宽的要求，通过采用可适应交叉和变异方法，提升算法的全局收敛能力。仿真实验结果表明，在云计算的任务调度中使用优化混合遗传算法能更加有效地解决资源调度问题。

关键词关键词：混合遗传算法；云计算；资源调度；精英因子

DOIDOI：10.11907/rjdk.162082

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2016）011005303

0 引言

云计算是一种新型计算模型，它在提供灵活、高性能、可支付、按需传达的服务上具有很大优势[1]。如果工作花费时间太长，将会降低用户满意度[2]。因此，高效率实现任务调度成为云计算中需要解决的核心问题之一。遗传算法作为启发式算法，在组合优化方面显示了特殊优势[3]。近年来，对遗传算法的应用发展迅速，尤其适用于解决科学和工程领域中的复杂问题。然而，在解决高维函数优化问题中，由于存在一些严格的限制条件，导致了传统遗传算法的低效。因此，本文提出一种优化混合遗传算法，它能在一定程度上解决传统遗传算法在资源调度上的收敛时间长、资源利用率低、平均任务花费时间长等问题[4]。

1 任务模型及其建立

1.1 任务模型

分析云计算模型是为了理清任务之间的关系（优先关系），以便于将其充分地并行化。云计算数据中心可以实现任务的并行化执行，由此提高运行效率。为了简单描述，建立以下数学模型：假设任务集用户提交的：T={t1、t2......tn}，ti是第i个子任务。因为运行是并行执行的，总运行时间由最长运行时间的资源决定。

云计算任务关系可以分为两种：依赖与冲突[5]。前者指任务在数据和控制上的相关。例如，当作函数依赖相关测试时，t1将调用t2的函数，或t2是否被执行由t1决定。后者意味着环境的冲突或任务间的并发冲突。如在性能测试中，t1应该被Apache服务器支持，但t2想要IIS服务器，或t1和t2有着一样的网络端口。因此，对于独立任务，中心将在一样的资源上被调度，否则不仅浪费了网络带宽，也会在数据传输过程中出现错误。但为了避免一些不必要的错误，对于冲突的任务，它们会被在不同的并行资源上执行。

1.2 任务模型建立

对于集合T，假设存在n*n的相关性矩阵，该矩阵是由第k个任务和第1个任务的关系所建立。它的元素值是-1、0、1。1代表tK和t1是独立的，0代表tk和t1之间无关，-1代表tk和t1之间相互冲突。根据相关性矩阵，数据中心可以创建一个新集合T′={t1′，t2′，....，ts′}，s≤n，称其为并行向量集。ts′是一个向量，它包括集合T的一个或多个元素。集合T′是任务组项目，它有着最大并行度，数据中心可以分配任务ts′到一个计算结点，以实现有效率的并行计算。例如，假设一个集合T（T={t1，t2，t3，t4，t5，t6}），相关性矩阵定义如下：

2 优化混合遗传算法资源调度

2.1 染色体编码

根据基因算法准则，首先应该编码染色体。本文使用间接编码，染色体长度是任务的量，在染色体中每一个基因值被相应任务分配资源标识。

假设有6个任务，T′={t1′={t1，t2}，t2′={t3，t4}，t3′={t5}，t4′={t6}}，所以有4个并行组等待调度。假设有3个在系统中的计算资源，染色体长度为3，每一个染色体表示1～3的排列。例如，染色体{1，2，2，3}代表t1′在第1号资源上执行，t2′和t3′在第2号资源上执行，t4′在第3号资源上执行。

编码之后，在各个资源上的任务分配则是明确的。基于此，数据中心将预测任务执行时间和创建预测执行时间矩阵ET。ET（i，j）代表第j个计算节点花费在第i个并行任务上的预测执行时间。

2.2 适应度函数

基因算法模拟自然界中最佳适应的原则进行搜索过程，在该过程中，适应度函数是群体中个体质量的准则[6]。云计算资源调度是一个多目标优化问题。本文定义了两个适应度函数，拥有较少带宽负载和时间花费的个体具有更好的适应度。采用一个权重向量来衡量用户对两个目标的重视程度不同：

2.3 交叉与变异

交叉操作指两个匹配的个体根据一定模式交换基因的一部分，从而产生两个新个体，其目的在于提升基因算法的全局搜索能力[7]。变异意味着子代中染色体编码值的改变，它可以探索出新的搜索空间和局部最优解的收敛。本文使用可适应的基因算法，交叉几率函数和变异几率函数定义如下：

2.4 优化混合基因算法实现

本文使用贪心算法进行群体初始化。假设被处理的工作是充足的，没有优先级。为了限制大量数据迁移，数据的本地性也应被考虑进去。

在初始群体被创造以后，经过一代代的适应度筛选，进化得越来越好，越来越近似于最优解。然后通过选择、交叉和变异，新一代产生，它代表一个新的解决方法。最好的解决方法将作为精英因子被选择，在若干代进化之后，不好的解决方法将会减少。优化混合遗传算法的基本步骤如下：

2.5 算法流程

算法流程如下：①根据待解问题的任务模型进行编码；②利用贪心算法初始化群体；③计算群体中每个个体的适应度值；④按照由个体适应值所决定的某个规则选择进入下一代的个体；⑤引入精英因子，将高适应度的个体直接选择出来不参与下一次迭代；⑥按交叉概率Pc进行交叉操作；⑦按变异概率Pm进行变异操作；⑧如果没有满足迭代次数要求，则转到第3步，否则进入第9步；⑨输出种群中适应度值最优的染色体作为问题的满意解或最优解。

3 仿真实验与结果分析

本文使用CloudSim作为仿真平台，实验目的是将本文的优化混合遗传算法和传统遗传算法进行对比实验。初始实验参数设置如下：最大迭代次数200，资源个数50，作业总数30，每个作业被划分为任务的数量范围是[1，90]，初始交叉概率0.8，初始变异概率0.2，设置（w1，w2）={0.4，0.6}。

由图1可以看出，随着遗传迭代次数增加，平均任务运行时间也逐渐减少，但改进后的优化混合遗传算法变化率曲线整体上要低于原始的收敛性曲线。并且可以看出，传统遗传算法最终收敛于局部最优值220，而优化混合遗传算法的收敛速度比原始收敛速度快，平均执行时间比原始平均执行时间短，与理论分析一致。

对于用户而言，适应度值大于等于0是可以接受的。由图2可以看出，随着遗传迭代次数增加，群体适应度越来越好，但改进后的优化混合遗传算法变化率曲线整体上要高于原始收敛性曲线。传统遗传算法最终收敛于0.1，而优化混合遗传算法最终收敛于0.4。也即是说，优化混合遗传算法平均适应度值要高于原始遗传算法。并且在相同的遗传迭代次数下，优化混合遗传算法的收敛速度比原始收敛速度快，与理论分析一致。

4 结语

本文提出了引入精英因子的混合遗传算法，并将其应用于云计算的资源调度中，设计了同时考虑时间和带宽的双适应度函数，并使用贪心算法初始化群体。仿真实验表明，在云环境下，将该算法应用于资源调度中具有一定优势。然而，本文的资源调度策略只考虑了当下的系统状态，没有考虑到系统变量与历史数据，这可能导致系统负载失衡，相关工作还有待下一步研究。

参考文献：

[1] 江建.精英自适应混合遗传算法及其实现[J].计算机工程与应用，2009，45（27）：3435.

[2] 冯龙华.云环境下基于贪心模型的作业调度算法研究与实现[D].重庆：重庆大学，2014.

[3] W LIN，C LIANG，J Z WANG，et al. Bandwidthaware divisible task scheduling for cloud computing[J].Software：Practice and Experience，2014（2）：163174.

[4] HU BAOFANG，SUN XIULI，LI YING，et al.An improved adaptive genetic algorithm in cloud computing[C].Parallel and Distributed Computing，Applications and Technologies （PDCAT），13th International Conference on，2012：294，297.

[5] 周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，2002.

[6] ORVOSH D，DAVIS L.Using a genetic algorithm to optimize problems with feasibility constraints[C].Proc of 1st IEEE Conf on Evolutionary Computation，1994：548553.

[7] 李敏强，寇纪淞.遗传算法的基本理论与应用[M].北京：科学出版社，2004.

（责任编辑：黄 健）