基于改进遗传算法的云计算任务调度算法研究

《基于改进遗传算法的云计算任务调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号TP311．13密级公开重庆邮电大学硕士学位论文论文题目基于改进遗传算法的云计算任务调度算法研究硕士研究生Computingbasedonimprovedgeneticalgorit——hm——袁永胜学科专业计算机技术论文提交日期至Ql墨玺垒目论文答辩日期2Q!墨玺互且2鱼日．论文评阅人答辩委员会主席重垄拯壑邀2013年争n27Et独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重迭鱼B电太堂或其他教育机构的学位或证书而使用过

2、的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签签字日期：20B年6月3日学位论文版权使用授权书本学位论文作者完全了解重迭由E电太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权重麽出E电盍堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：导师签名签字日期：20乃年6月多日签字日期：日重庆邮电大学硕士论文摘要云计算自2007年提出以来，凭借

3、其简单、廉价的特点得到了前所未有的发展，在各行各业存在着巨大的市场需求，未来必然对人的生活方式和工作方式产生影响。云计算商用以后，面向的是庞大的用户群体，他们对资源的需求是各式各样的，如何在满足所有用户需求的情况下对海量任务进行合理的调度变得十分关键。遗传算法是一种全局搜索算法，相比于传统的启发式搜索算法，它具有自组织、自适应、自学习性和并行性，尤其是在解决海量任务的时候，遗传算法的并行性具有很大的优势，可以把任务进行拆分后分配到多个处理机上同时进行处理。同时遗传算法还具有扩展性，可以方便地和其他算法进行结合，吸收其他算法的优势。目前已有学者将遗传算法应用到网格计算中进行

4、任务调度，得出的调度方案具有更短的任务完成时间。云计算是在网格计算的基础上发展而来的，它的基本框架和网格计算的相似，因此本文将遗传算法应用到云计算的任务调度中。但是遗传算法应用到云计算中后存在一些问题：容易陷入局部最优解，算法收敛过程比较长，对非线性约束的处理不是很合理，适应度函数考虑的因素比较单一，不能得到最优的初始种群等。本文针对收敛速度慢、约束处理不合理、适应度函数考虑因素单一进行了改进。为了解决算法收敛速度慢的问题，本文对传统的串行编码方式进行了改进，采用矩阵编码方式，解决了染色体过长的问题，而且染色体交叉和变异操作更加有效，产生的新个体是潜在最优解的概率更大。为

5、了解决算法对非线性约束处理不合理的问题，本文在原有深度值排序的基础上增加了对任务约束关系为特殊DAG图的任务分配方式，对一些特殊的任务进行优先处理，减少被依赖任务的等待时间，最终减少任务的总完成时间。为了解决适应度函数考虑因素单一的问题，本文对适应度函数进行了改进，将平均任务完成时间和任务完成所需成本加入适应度函数当中，让算法依据适应度值选出的个体既有总任务完成时间和成本较少的，也有平均任务完成时间和成本较少的。实验结果表明，改进的遗传算法在云计算环境中进行任务调度的时候，可以减少任务的完成时间，提高调度算法的收敛速度，并在完成时间．成本中寻找到了一个平衡点。因此，该算法

6、是一种可行且有效的任务调度算法。关键词：云计算，任务调度，遗传算法，约束，成本开销，矩阵编码重庆邮电大学硕士论文Abstractsince2007，cloudcomputinghasthehithertounknowndevelopmentbyitssimpleandcheapfeature．Therehasahugemarketdemandinallwalksoflife．Itwillinfluencethelifeandworkofpeople．Aftercloudcomputingcommercialapplication，itfacethehugeusergrou

7、ps，theirdemandforresourcesarediverse，Howtoreasonableschedulingtomassivetaskinthesituationofmeetallusersdemandbecomesverycritical．Geneticalgorithmisaglobalsearchalgorithm，comparedtothetraditionalheuristicsearchalgorithm，itisself-organizing，self-adaptive，self-learning