遗传算法在云任务调度中的应用

２０１３年５月　第３２卷第５期　洛阳师范学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｌｕｏｙａｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ　Ｍａｙ．，２０１３　Ｖｏ１．３２　Ｎｏ．５　

遗传算法在云任务调度中的应用　

李　英，黄国范　

（南阳师范学院软件学院，河南南阳４７３０６１）　

摘要：云任务调度的目的是快速找到全局最优解．将多个云任务合理的分配给有限的资源上，使得整个任务　的完成时间较短．文中主要介绍了遗传算法在云任务调度中的应用．通过仿真实验分析了采用精英策略的遗　传算法和没有采用精英策略的遗传算法在云任务调度中的不同．　关键词：任务调度；云计算；任务调度；遗传算法　中图分类号：ＴＰ３９３　文献标识码：Ａ　文章编号：１ｏ０９—４９７０（２０１３）０５—００５７—０３　

０　引言　

云计算是在并行计算、分布式计算、集群计　算、网格计算的基础上发展起来的一种新兴计算模　式…，其基本思想是通过构建数据中心，并采用成　

熟的虚拟化技术给用户提供服务Ｌ２　Ｊ．然而，不同的　

用户对服务的需求是不同的，这就要求云计算平台　能够通过任务调度为不同的用户提供不同类型的服　

务，并保证用户能够获得较好的服务质量．　任务调度是云计算的关键技术之一．云任务调　

度的目的就是按照某种策略，将任务合理地分配到　

处理单元，以达到完成时间最短，成本最小以及提　高系统利用率等目的　．　

本文着重介绍遗传算法在云任务调度中的应　用，分析了基本遗传算法和采用精英策略的遗传算　

法的特点，并使用云计算仿真器Ｃｌｏｕｄｓｉｍ工具中对　这两种算法进行了比较．　

１　问题描述　

云计算是在网格计算的基础之上发展起来的，　两者有很多相似之处，但是也有很多不同之处，在　

任务调度方面两者就有着根本性的不同．网格的原　理就是利用网络上的各种资源协同完成单个资源或　

多个闲散资源无法完成的超级计算任务，在这个过　程中，非常重要的一步就是利用特定的网格软件，　

将用户提交的超级计算任务分割成粒度相对均匀、　相互独立的子任务，然后通过一定的任务调度策略　将这些相对小的子任务分别交给网格系统中的计算　

节点去完成．所以，在执行任务的过程中，即便某　个计算节点失效，不能正常返回计算结果，对整个　

任务的正确运行也不会产生影响，因为失效节点所　承担的计算任务可以利用任务调度将其迁移到正常　

的其它计算节点上重新执行．而云计算不再将用户　提交的任务分配给具体的物理节点去执行，而是采　

用成熟的虚拟化技术将一台主机资源映射为多台虚　拟机，构成云计算的各类虚拟资源池，从而使用户　

所需请求使用的资源以一台台虚拟机的形式呈现．　

因此，对于云任务调度而言，可以以多台虚拟机组　织形式组建用户所需的资源。执行用户所提交的任　

务，这样对用户来讲更方便、直观．　

２遗传算法分析　

２．１遗传算法　

遗传算法操作对象是一群染色体（即种群），每　个染色体都对应问题的一个解，从初始种群开始，　

采用基于适应值比例的选择策略在当前种群中选择　个体，使用交叉和变异来产生下一代种群，一代一　代演化下去，直到满足期望的终止条件　］．因此，　

遗传算法应用在各种实际问题求解．　

２．１．１　染色体组编码与解码　染色体组编码与解码方式采用的是任务一资源　

间接编码方式，将任务分解成若干个子任务，对子　

收稿日期：２０１３—０３—０４　基金项目：南阳师范学院科研基金资助课题（ＱＮ２０１２０４８）　作者简介：李英（１９８２一），女，硕士，助教．研究方向：分布式计算、网格计算．

　・５８・　洛阳师范学院学报２０１３年第５期　

任务和其所占用的资源进行编码．染色体组由两条　

染色体组成，第一条为子任务的序列；第二条为资　

源（虚拟机）序列，该序列为子任务所对应的虚拟机　的编号．染色体的长度为子任务的个数．例如，有　

６个子任务，２个虚拟机，编码如图１所示．　

子任务序列臣二臣［［！［　【　圈　

资源序列　—　—厂　丁　Ｔ　—ｒ　

图１任务一资源编码示例　

对图１中的染色体组进行解码，可知，分配给　０号虚拟机的任务编号为０、１和５；分配给１号虚　

拟机的任务编号为２、３和４．　

２．１．２种群的初始化　种群的初始化采用随机方式产生．初始种群规　

模为ＰＯＳＩＺＥ，子任务个数为ＣＨＲＯＭＬＥＮＧＴＨ，资　

源个数为ＲＳ，遗传基因（即每个子任务占用的资源　编号）在资源个数ＲＳ的范围内进行选取．　

２．１．３适度函数　在遗传算法中，群体中各个个体的优劣程度是　通过适应函数来度量的．文中适应函数表示为　

１　Ｆｉｔｎｅｓｓ（　）　（　）　

其中，Ｆｉｔｎｅｓｓ（Ｆｉ）表示种群中第ｉ个染色体　的适应度．Ｆｒ（Ｆｉ）为ｎ任务完成时间．　

＝　Ｆｒ（Ｆｉ）＝　似∑Ｍｊ　（２）　

其中，Ｍｊ表示子任务在资源上所花费的时间．　２．１．４选择　

根据适应度的大小，文中采用轮赌盘选择后代．　

２．１．５　交叉　遗传算法中，交叉操作起着核心的作用，交叉　操作可以改变两个父代的部分基因，并将它们组成　

新的个体．文中采用的是染色体组编码方式，因　此，交叉操作分为两个部分，第一部分为对任务序　

列进行交叉；第二部分为对资源序列进行交叉．交　

叉操作的具体描述如下．　

（１）任务序列交叉．首先，生成一个Ｅｏ，１］之间　的随机数，用该数值与交叉概率进行比较．若该数值　

大于交叉概率，将当前的任务序列归人参加交叉集　

合中；若该数值小于交叉概率，则将任务序列归入不　

参加交叉集合中．其次，随机生成两个在［０，　

ＣＨＲＯＭＬＥＮＧＴＨ一１］之间的整数（ＣＨＲＯＭＬＥＮＧＴＨ　为子任务个数），将两个父代任务序列中处于这两个　

整数之间的基因序列进行交换．最后，将交叉后的个　体集合与不参加交叉个体的集合一起组成新的集合．　

（２）资源序列交叉．首先，随机将资源序列分　

成３部分．其次，随机生成［０，２］之间的整数，若随　机数为０，则将两个父代资源序列中第一部分进行　

交换；若随机数为１，则将第二部分进行交换；若随　

机数为２，则将第三部分进行交换．　２．１．６变异　

通过变异操作，可以保障群体的多样性，提高　遗传算法局部搜索的效率．遗传算法中变异率的取　

值一般受种群的大小，子任务的多少等因素影响．　由于变异概率较低，一般取值范围在０．００１—０．１　

之间　Ｊ．文中变异概率为０．１．文中的变异操作：　

随机生成两个在［０，ｃＨＲＯＭＬＥＮＧＴＨ一１］之间的　整数ａ，ｂ（ＣＨＲＯＭＬＥＮＧＴＨ为子任务个数），将任务　

序列中ａ位置基因与ｂ位置的基因进行交换．　

２．２精英策略　由于选择操作具有随机性，适应度好的个体也　

有可能产生不了后代，而适应度差的个体可能被选　

择进行繁衍．为了避免这种情况的发生，需要对遗　

传算法进行改进，通常采用精英选择法，即将种群　中最优秀的个体直接复制到下一代，将最差的个体　淘汰．这样可以避免优秀的个体经过选择、交叉、　

变异等操作，失去较好的基因．　

３仿真实验　

本文使用云计算仿真平台Ｃｌｏｕｄｓｉｍ＿４－６］来分析　

遗传算法以及采用精英策略的遗传算法在云任务调　度中的应用．算法所用到的参数如下：种群的大小　

为２００，迭代次数为２００，交叉概率为０．６，变异概　

率为０．１．当资源数为５，任务数为２００时，进化代　数和适应度之间的关系如图２所示．　

０　２ｏ　４０　６０　８ｏ　ｌ００　１２ｏ　ｌ４ｏ　ｌ６ｏ　ｌ８ｏ　２ｏｏ　进化世代数　图２进化代数和适应度关系　

通过仿真实验，可以看出没有采用精英策略的　

遗传算法虽然随着进化代数的增加，适应度总体呈　

现上升趋势，但是，从图２中可以看出适应度可能会　！

∞洛阳师范学院学报２０１３年第５期　・５９・　

出现下降，这是因为没有采用精英策略的遗传算法　会使得适应度好的个体有可能产生不了后代，而适　

应度差的个体可能被选择进行繁衍．采用精英策略的　遗传算法比没有采用精英策略的遗传算法能够选择出　

适应度更强的个体，从而得到调度问题的最优解．　

４　结论　

任务调度是云计算的关键技术之一．本文主要介绍　了遗传算法在云任务调度中的应用，通过仿真实验分析　了采用精英策略遗传算法能够得到问题的更优解．　

参考文献　

［１］吴煜祺，曾国荪，曾嫒．云计算环境下调度算法的趋势　分析［Ｊ］．微电子学与计算机，２０１２，２９（９）：１０３—１０８．　［２］杨丽，武小年，商可曼．一种基于聚类的云计算任务调　度算法［Ｊ］．大众科技，２０１２，１５３（１４）：３７—３９．　［３］徐娟，王景华，等．基于小生境遗传算法的网格任务调　度［Ｊ］．计算机工程，２０１０，３６（２１）：２２—２４．　［４］丁阳，颜惠琴．基于改进粒子群算法的云计算任务调度策　略［Ｊ］．无锡职业技术学院学报，２０１２，ｉ１（３）：加页码．　［５］李坤．云环境下的任务调度算法研究与实现［Ｄ］．吉　林：吉林大学，２０１２：１２—１４．　［６］申丽君，刘丽，等．基于改进免疫进化算法的云计算　任务调度［Ｊ］．计算机工程，２０１２，３８（９）：２０８—２１０．　

［责任编辑徐刚］　

Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　ｉｎ　Ｃｌｏｕｄ　Ｔａｓｋ　Ｓｃｈｅｄｕｌｉｎｇ　

ＬＩ　Ｙｉｎｇ，ＨＵＡＮＧ　Ｇｕｏ—ｆａｎ　（Ｓｃｈｏｏｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，Ｎａｎｙａｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｙａｎｇ　４７３０６１，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｐｕｒｐｏｓｅ　ｏｆ　ｃｌｏｕｄ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ　ｉｓ　ｔｏ　ｑｕｉｃｋｌｙ　ｆｉｎｄ　ｔｈｅ　ｇｌｏｂａｌ　ｏｐｔｉｍｕｍ．Ｒｅａｓｏｎａｂｌｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ　

ｏｆ　ｍｕｌｔｉｐｌｅ　ｔａｓｋｓ　ｔｏ　ｌｉｍｉｔｅｄ　ｒｅｓｏｕｒｃｅｓ　ｉｓ　ｔｏ　ｓｈｏｒｔｅｎ　ｔｈｅ　ｅｎｔｉｒｅ　ｔａｓｋ　ｃｏｍｐｌｅｔｉｏｎ　ｔｉｍｅ．Ｔｈｉｓ　ｐａｐｅｒ　ｄｅｓｃｒｉｂｅｓ　ｇｅｎｅｔｉｃ　ａｌ—　ｇｏｒｉｔｈｍ　ｉｎ　ｃｌｏｕｄ　ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ．Ｔｈｒｏｕｇｈ　ｓｉｍｕｌａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔｓ，ｔｈｅ　ｄｉｆｆｅｒｅｎｃｅｓ　ｏｆ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｃｌｏｕｄ　

ｓｃｈｅｄｕｌｉｎｇ　ａｒｅ　ａｎａｌｙｚｅｄ，ｗｉｔｈ　ａｎｄ　ｗｉｔｈｏｕｔ　ｔｈｅ　ｅｌｉｔｉｓｔ　ｓｔｒａｔｅｇｙ．　

Ｋｅｙ　ｗｏｒｄｓ：ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ；ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ；ｔａｓｋ　ｓｃｈｅｄｕｌｉｎｇ；ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　

（上接第５２页）　参考文献　

３　结语　

把成本控制的观念融于无机化学实验室的管理　

和执行之中，让学生了解绿色化学、低碳化学；通过　微量实验的操作，提高了学生的环境意识，进一步强　

化节约资源和能源、改善环境、促进可持续发展观　念；促进同事之间的交流，提高大家的主人公意识．　［１］白林，李生英，徐飞．小量一半微量实验技术在无机化学　试验中的应用［Ｊ］．甘肃高等学报，２００１，６（２）：８４—８６．　［２］郝志峰，吴茂英，肖楚民，等．探索基础无机化学实验教　学的新策略［Ｊ］．实验室研究与探索，２０１１，（８）：３１９—　３２１．　［责任编辑胡灵敏］　

Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｃｏｓｔ　Ｃｏｎｔｒｏｌ　ｉｎ　ｔｈｅ　Ｅｘｐｅｒｉｍｅｎｔ　ｏｆ　Ｉｎｏｒｇａｎｉｃ　Ｃｈｅｍｉｓｔｒｙ