基于遗传算法的云计算任务分配

王 倩，周书臣

（1.周口师范学院 计算机科学与技术学院，河南 周口 466001;2.黄淮学院 国际学院，河南 驻马店 463000）

目前，云计算成为信息技术领域所讨论的热点[1-2].关于云计算，文献3里这样描述：基础设施（用来构造应用程序，相当于微型计算机的OS）和云计算应用（建立在基础设施之上）.与网格计算相比，网格程序是把大的任务分解成许多个小的任务并行运行在不同的集群以及服务器上，看重的是科学地进行计算应用程序的运行.对于云计算而言，它是一个具有更广泛定义的计算平台，不仅能够支持网格的应用，还支持非网格的应用，比如，支持网络服务程序中的前台网络服务器、数据库服务器和应用服务器这三层应用程序架构模式等.云计算是能够提供虚拟化、动态资源池和高可用性的下一代计算平台[3].当前，云计算服务可分基础设施即服务（如Amazon的弹性计算云等）、平台即服务（如Google的Google AppEngine等）和软件即服务（如Salesforce公司的客户关系管理服务等）为这3个层次[4].

云计算的核心思想是将大量计算资源（用网络连接的）进行统一的管理和调度，形成一个计算资源池，以便按照用户的需要进行服务.云的含义是提供资源的网络.在用户看来，“云”中的资源是能够无限扩展的，还能随时获取，按使用付费.总的来说，云计算是并行计算和网格计算的进一步的发展.企业数据中心的运行将与互联网更相似，使计算分布在大量的分布式计算机上.这样能够使企业将资源切换到所需的应用上，按照需求去访问计算机和存储系统.它意味着计算能力也能作为一种商品进行流通，像煤气、水电一样，取用方便，费用低廉.与煤气、水电相比，最大的不同之处是通过互联网传输.

对于云计算服务提供商来说，其核心技术是如何对用户申请的计算资源进行分配和管理，其效率直接影响整个云计算环境的工作性能以及企业效益.因此，为云计算环境找到一个合理的任务分配方法迫在眉睫.本文提出了一种基于遗传算法的任务调度算法，实验证明了该算法有效地提高了资源的分配和管理.

1 遗传算法

近些年仿生学迅猛发展，仿生技术也备受各界学者的关注，已经用于解决复杂的问题（如：任务分配、路径等）.遗传算法（简称GA）研究历史比较短，它是模拟生物界中的遗传和进化的一种最优化的方法.1975年，John Holland等人出版了《自然与人工系统中的自适应》专著，标志着GA正式诞生.现今，GA已成功应用于生物、计算机科学、图像处理等领域.由于其并行性、全局搜索以及高求解精度且易于和其他方法相结合的特点，能在庞大的解空间中最大限度地寻找全局最优，在解决组合优化问题方面显示出了较大优势.其核心思想是：通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群，通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群.再对这个新种群进行下一轮进化.

精英个体是指具有较高适应度值的个体.在群体里，文献[5]指出：全局最优解和精英个体的亲和度要大于全局最优解和非精英个体的亲和度，并与精英个体有较大亲和度的个体也应该具有较高的适应度值.所以，在种群的进化过程中精英个体起着非常重要的推动作用.

协同进化与传统遗传算法相比，它具有强搜索能力和渐进学习能力，能够克服传统遗传算法的早熟收敛现象.能够有效地解决遗传算法中进化模式单一性的问题，从而较好地保持种群个体的多样性，避免了未成熟收敛和收敛速度慢等问题.

近年来，GA的研究仍然被众多学者所关注，并取得了显著的成果.文献[7]结合遗传算法与线性鉴别分析提出了一种玉米品种的快速鉴别方法，与常用的PCA等方法相比，运算时间更短，正确率更高.文献[8]针对噪声环境下多模函数的优化，本文理论上分析了噪声对多模函数优化的收敛精度和全局收敛性的影响，并对全局区域收敛精度和全局区域搜索率进行分析噪声对算法的影响程度.噪声的强度和加多模函数寻优的难度，遗传算法的全局区域搜索率都在下降，全局区域收敛精度总体变差；重采样的方法能够有效提高算法的全局区域搜索率，总体改善算法的全局区域收敛精度.遗传算法被应用各个领域.文献[9]提出了一种混合竞争协同进化遗传算法(htCGA)，其基本思想是，将局部搜索方法引入到协同进化遗传算法中，提高了算法局部搜索的能力.但上述两种算法都采用了对解空间进行分割的策略.因此较容易陷入局部极小值的问题.文献[1]提出了一种蜜蜂进化型遗传算法，该算法充分利用了精英个体的信息.但该算法中随机种群的比例参数需要通过人为经验来确定，一定程度上增加了算法的随机性.遗传算法容易陷入局部最优解，而且收敛速度和寻优精度有待提高.为此，本文提出了的算法对云计算中的任务调度策略进行改进，通过对任务的优化调度来最大限度地提高云计算环境的效率.

2 基于遗传算法的云任务分配

2.1 云计算中的模型

目前，云计算的环境大多数采用Map/Reduce模型[10].本文采用基于Map/Reduce的思想开发的编程工具，这模型适用于产生和处理大规模的数据集.

图1 Map/Reduce的执行过程

图1看出，Map/Reduce主要分两个阶段：

第一个阶段（Map阶段）：通过Map/Reduce函数将一个大的任务划分多个小的任务，然后并行执行（执行Map操作的worker），输出处理后的中间文件.

第二个阶段（Reduce阶段）：将第一个阶段处理后的结果汇总分析并处理，输出最后结果.

目前一些任务调度的算法过多地关注总任务的完成时间(造成潜在优良基因丢失).既要关注总任务的完成时间，又要关注平均完成时间，所以，本文提出了一种对云计算中任务调度的改进算法，最大限度地提高云计算环境的效率.

2.2 算法流程

2.2.1 个体评价策略

本文对群体中的个体进行适应度评价采用以下策略.定义：

其中，P={a1,a2,…,an}是群体所包含的个体集合，n是表示群的规模分别表示i和j个体第l位的值.这个策略引入了差异度作为其权系数，能够有效地保持种群的多样性，从而避免因有效模式缺失而导致的早熟收敛问题.

2.2.2 交叉操作

传统的遗传算法采用统一的交叉、变异策略，很大程度上增加了算法的随机性，降低了算法的收敛速度.本文受MECA算法[11]的启发，采用两种交叉算子：单点交叉算子和两点算子（两点交叉是设置两个交叉点，为选定父代基因链上的两个位置进行交叉）.当个体i,j的差异度时，产生新个体采用单点交叉算子x=(x1,x2,…,xn)和y=(y1,y2,…,yn).当个体i,j相似时，使用两点交叉算子(如表1所示)产生新个体.

表1 两点交叉

2.2.3 精英进化

对于种群的进化，精英个体起着非常重要的作用.遗传算法采用精英策略能够较快地收敛到全局最优解.DECGA算法采用双精英进化策略.这一算法的核心操作是以精英个体作为进化的，在进化过程中充分地发挥了精英个体的推动作用，使个体有方向地朝好的方向进化.

初始种群生成时，首先组成精英库种群（随着种群的进化而不断更新），精英种群是从种群中前M个适应度值最高的不同个体中选择出来的，每一代中的两个精英个体都是也是这样选择的，用EliteA（提高算法收敛速度，能够有效避免因种群个体过于相似而导致的无效交叉，从而提高算法的进化效率）和EliteB（避免出现算法由于选择压力而造成的过早收敛现象）来表示两个精英个体，这两个精英个体协同进化，最终完成算法的整个进化操作.

算法的流程描述如下：

（1）随机产生初始种群，计算每个个体的适应度函数并排序.

（2）选择前M个适应度值相异的优秀个体作为精英库Best(0)成员，并令 t=0；

（3）选择Best(t)中的最优个体作为EliteA，并利用种群分割策略得到分割种群P0Pe和P0Pc.

（4）按比例选择法选择与EliteA相异的个体EliteA，种群个体评价函数.

（5）将 A(t+1)和 B(t+1)种群合并，得到种群 Temp(t+1)，并计算Temp(t+1)的适应度值；

（6）精英库Best(t)与temp(t+1)中的个体竞争，并计算Temp(t+1)中不存在此精英个体，则用此精英个体替代Temp(t+1)中的最差个体；否则不进行任何操作.得到下一代种群P(t+1)，并将种群按适应度降序排列；

（7）若P(t+1)中的最优个体 bestlndividual大于Best(t)中的最优个体，则用最优个体bestlndividual替代Best(t)中的最差个体.得到更新后的精英库Best(t+1)；

（8）是否满足终止条件：若是，则结束；否则，转到Step3.

3 仿真实验结果与分析

本文制作仿真实验并对结果进行分析，目的是在云计算任务分配上改进遗传算法和遗传算法有更好的对比以及预测时间与实际执行时间的比较.

3.1 实验模型

为了验证上述遗传算法在云计算任务分配上的可行性以及较好的稳定性，本文需要选择一个有意义的测试环境.本文选用2.40GHz的CPU和2GB的RAM作为硬件环境，Windows XP的操作系统，JDK7.0的基础环境及Ant1.8.2的编译工具.

首先设置参数：worker为50，task为50；每个task划分为子任务数范围为[20,80].

终止条件：达到最大迭代数或如果连续50代总任务完成时间与任务平均完成时间都没有变化时，终止算法.

3.2 实验结果

在增加流量负载和暂时饱和的情况下，本文算法的平均完成时间与GA算法进行比较（如图2所示）.横坐标为任务的申请数量.纵坐标为两种算法分别进行处理申请作业所消耗的时间.

图2 云计算环境下的算法比较

通过实验，可以看出：本文算法（蓝线）的平均完成时间在任务较少时优势较小而任务较多时远远小于GA算法（红线），主要原因是：采用了双精英策略思想，随着任务数量的增多预测时间逐渐接近实际时间.

4 结束语

本文提出了一种基于遗传算法的任务调度算法，减少了处理请求任务的平均完成时间，保证云服务的质量.通过本算法可以对云计算环境下这种模型实现较为理想的任务调度，它是一种有效的任务调度算法.

〔1〕FOSTER I,YONG ZHAO,RAICU I,et al.Cloud computing and grid computing 360-degree compared[C]//Proceedings of the 2008 Grid Computing Environments Workshop.Washington, DC:IEEE Computer Society,2008:1-10.

〔2〕ARMBRUST M,Fox A,GRIFFITH R,et al.Above the clouds:A Berkeley view of cloud computing[EB/OL].[2010-01-25].http://www.eecs.berleley.edu/Pubs/Techrpts/2009/EECS-2009-28.pdf.

〔3〕陈康.云计算：系统实例与研究现状[D].软件学报,2009.

〔4〕冯登国，等.云计算安全研究[D].软件学报,2011.

〔5〕Meng W,Han XD,Hong BR.Bee evolutionary genetic algorithm.Acta Electronica Sinica,2006,34(7):1294-1300(in Chinese with English abstract).

〔6〕Eglover,Tabu search:Part I.ORSA Journal on Computing.1989,1(3):1 90-206.

〔7〕王徽蓉，等.基于遗传算法与线性鉴别的近红外光谱玉米品种鉴别研究[D].光谱学与光谱分析,2011（3）.

〔8〕李军华，等.噪声环境下多模态函数优化的遗传算法[D].电子学报,2012（2）.

〔9〕Danoy G.Bouvry P,Martins T.Hlcga:A hybrid com-petitive coevolutionary genetic algorithm.In:Hoes L,ed.Proc.of the 6th Int,I Conf.on Hybrid Intelligent Systems.Com-puter Society Press,2006.48-51.[doi:10.1109/HIS.2006.264931].

〔10〕DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Symposium on Operating System Design and Implementation.New York:ACM,2004:137-150.

〔11〕Mu CH.Jiao LC,Liu Y.M-Elite coevolutionary algorithm for numerical optimization.Journal of Softwar-e,2009,20(11):2925-2938(in Chinese with English abstrac-t).http://www.jos.org.cn/1000-9825/3496.htm[doi-:10.3724/SP.J.1001.2009.03496].