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

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

分类号TP311．13密级公开重庆邮电大学硕士学位论文论文题目基于改进遗传算法的云计算任务调度算法研究硕士研究生Computingbasedonimprovedgeneticalgorit——hm——袁永胜学科专业计算机技术论文提交日期至Ql墨玺垒目论文答辩日期2Q!墨玺互且2鱼日．论文评阅人答辩委员会主席重垄拯壑邀2013年争n27Et 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重迭鱼B电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签签字日期：20B年6月3日学位论文版权使用授权书本学位论文作者完全了解重迭由E电太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权重麽出E电盍堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：导师签名签字日期：20乃年6月多日签字日期：日 重庆邮电大学硕士论文摘要云计算自2007年提出以来，凭借其简单、廉价的特点得到了前所未有的发展，在各行各业存在着巨大的市场需求，未来必然对人的生活方式和工作方式产生影响。云计算商用以后，面向的是庞大的用户群体，他们对资源的需求是各式各样的，如何在满足所有用户需求的情况下对海量任务进行合理的调度变得十分关键。遗传算法是一种全局搜索算法，相比于传统的启发式搜索算法，它具有自组织、自适应、自学习性和并行性，尤其是在解决海量任务的时候，遗传算法的并行性具有很大的优势，可以把任务进行拆分后分配到多个处理机上同时进行处理。同时遗传算法还具有扩展性，可以方便地和其他算法进行结合，吸收其他算法的优势。目前已有学者将遗传算法应用到网格计算中进行任务调度，得出的调度方案具有更短的任务完成时间。云计算是在网格计算的基础上发展而来的，它的基本框架和网格计算的相似，因此本文将遗传算法应用到云计算的任务调度中。但是遗传算法应用到云计算中后存在一些问题：容易陷入局部最优解，算法收敛过程比较长，对非线性约束的处理不是很合理，适应度函数考虑的因素比较单一，不能得到最优的初始种群等。本文针对收敛速度慢、约束处理不合理、适应度函数考虑因素单一进行了改进。为了解决算法收敛速度慢的问题，本文对传统的串行编码方式进行了改进，采用矩阵编码方式，解决了染色体过长的问题，而且染色体交叉和变异操作更加有效，产生的新个体是潜在最优解的概率更大。为了解决算法对非线性约束处理不合理的问题，本文在原有深度值排序的基础上增加了对任务约束关系为特殊DAG图的任务分配方式，对一些特殊的任务进行优先处理，减少被依赖任务的等待时间，最终减少任务的总完成时间。为了解决适应度函数考虑因素单一的问题，本文对适应度函数进行了改进，将平均任务完成时间和任务完成所需成本加入适应度函数当中，让算法依据适应度值选出的个体既有总任务完成时间和成本较少的，也有平均任务完成时间和成本较少的。实验结果表明，改进的遗传算法在云计算环境中进行任务调度的时候，可以减少任务的完成时间，提高调度算法的收敛速度，并在完成时间．成本中寻找到了一个平衡点。因此，该算法是一种可行且有效的任务调度算法。关键词：云计算，任务调度，遗传算法，约束，成本开销，矩阵编码 重庆邮电大学硕士论文Abstractsince2007，cloudcomputinghasthehithertounknowndevelopmentbyitssimpleandcheapfeature．Therehasahugemarketdemandinallwalksoflife．Itwillinfluencethelifeandworkofpeople．Aftercloudcomputingcommercialapplication，itfacethehugeusergroups，theirdemandforresourcesarediverse，Howtoreasonableschedulingtomassivetaskinthesituationofmeetallusersdemandbecomesverycritical．Geneticalgorithmisaglobalsearchalgorithm，comparedtothetraditionalheuristicsearchalgorithm，itisself-organizing，self-adaptive，self-learningandparallel，especiallywhensolvingamassivetask，geneticalgorithmhasgreatadvantagesintheparallel，itCansplitthetaskanddistributedthemtothemultipleprocessorsprocessingsimultaneously．Inaddition，thegeneticalgorithmisscalable，itCanconvenientcombined丽thotheralgorithms，absorbsadvantageofotheralgorithms．Atpresent，geneticalgorithmhasbeenappliedtogridcomputingtaskscheduling，whichhasshortertaskcompletiontime．Thedevelopmentofcloudcomputingisbasedon鲥dcomputing，itsbasicframeworkissimilartothegridcalculation．Therefore，thesiswillputgeneticalgorithmapplytothetaskschedulingofcloudcomputing．Butthegeneticalgorithmisappliedtothecloudhassomeproblem：easytofallintolocaloptimalsolution，theconvergenceprocessisrelativelylong，processingofthenonlinearconstraintiSnotveryreasonable，consideredfactorsoffitnessfunctionrelativesingle，Can’tgettheoptimalinitialpopulation，andSOon．Thesisimprovedtheslowconvergencespeed，theunreasonableproblemofalgorithmprocessingconstraints，thefitnessfunctionconsideringfactorsingle．Inordertosolvetheproblemoftheslowconvergencespeed，thesisimprovethetraditionalserialencodingmethod，usethematrixcoding，solvetheproblemoflongchromosome，andadoptthechromosomecrossoverandmutationoperatorwithmatrixcodingscheme，itismoreefficient，thegeneratenewindividualistheoptimalsolutionhasgreaterprobability．Inordertosolvetheunreasonableproblemofalgorithmprocessingconstraints，thesisincreasethetaskassignmentmethodoftaskconstraintsspecialDAGgraphsbasedontheoriginaldepthvalueordering，giveprioritytosomespecialtask，toreducethewaitingtimeofbedependenttasks，andreducethetotalcompletiontimefinally．Inordertosolvethesingleproblemoffitnessfunctionconsideringfactor,thesisII hasmadetheimprovementtothefitnessfunction，puttheaveragecompletetimeandcostoftaskconsiderintofitnessfunction，makeindividualselectedaccordingthealgorithmthefitnessvaluesboththelesstaskcompletiontimeandlesscost．Theexperimentresultshows，whenusetheimprovedgeneticalgorithmdothetaskschedulinginthecloudenvironment，itcanreducethecompletetimeoftask，improvetheconvergencespeedofthealgorithm，andfindabalancepointbetweencompletiontimeandcostoftask．Therefore，thealgorithmisafeasibleandeffectivetaskschedulingalgorithm．Keywords：cloudcomputing，taskscheduling，geneticalgorithm，constraint，cost，matrixcodingIII 重庆邮电大学硕士论文目录摘要⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯IAbstract⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯II目录⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．IV第一章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．1云计算简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．11．2研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．31．3本文研究内容⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．41．4论文组织结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．4第二章云计算环境下的调度算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．1任务调度简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．62．1．1任务调度的定义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．62．1．2任务调度的特点⋯⋯⋯⋯⋯⋯⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．62．1．3任务调度的目标⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一72．2任务调度算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．82．3云计算环境中的任务调度⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．92．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯10第三章遗传算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．113．1遗传算法简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯113．1．1遗传算法的定义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．113．1．2遗传算法的优点与缺点⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．123．2遗传算法的实现步骤⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．133．2．1编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．133．2．2初始群体设定⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．133．2．3适应度函数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．143．2．3遗传操作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．153．2．4收敛准则⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．163．3改进遗传算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯163．3．1白适应遗传算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．16IV 重庆邮电大学硕士论文目录3．3．2混合遗传算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．173．3．3并行遗传算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．193．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯22第四章基于改进遗传算法的云计算任务调度算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．234．1数据依赖关系的处理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯234．1．1基于深度值的排序⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．244．1．2短任务优先原则⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．254．1．3含子节点优先原则⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．254．2对遗传算法的改进⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯254．2．1对数据依赖处理方式的改进⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．254．2．2编码方式的改进⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．264．2．3适应度函数的改进⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．274．3算法描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯284．3．1编码策略与初始种群的生成⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．294．3．2适应度函数的设定⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯304．3．3选择操作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．314．3．4自适应交叉操作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．314．3．5自适应变异操作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．324．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯32第五章实验仿真与结果分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．335．1实验仿真环境介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．335．1．1CloudSim简介⋯⋯．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．335．1．2CloudSim分层结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．335．1．3CloudSim的扩展⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．345．2实验结果与数据分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯355．2．1任务完成时间对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．355．2．2算法收敛速度对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．385．2．3任务完成所需成本对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．405．3本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．41第六章总结和展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．426．1论文总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯426．2展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43V 重庆邮电大学硕士论文目录弱!j射⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．44攻硕期间从事的科研工作及取得的研究成果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯45参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯46VI 重庆邮电大学硕士论文第一章绪论1．1云计算简介第一章绪论弟一早三百比随着互联网的快速发展，用户的需求也随着互联网的发展而发生改变，制造商根据用户提出的新的需要提供相应的扩展的硬件、软件和服务，这便形成了最初的云计算。事实上，云计算是网格计算，分布式计算，并行计算的扩展。它的目的是为了提供以安全，快速，便捷的数据存储和计算为中心的互联网服务llJ。云计算具有虚拟化，分布式和动态可扩展性等特征，其中虚拟化是其最主要的特征。在云计算平台下，我们可以将IT资源、软件、硬件、操作系统和存储进行虚拟化，然后对虚拟化资源进行管理，而无需考虑它们的实际物理平台。而且，对虚拟平台可以方便的进行扩展、迁移、备份等操作；分布式是指处于云计算平台中的资源节点在地理位置上是分散的，不同区域甚至不同国家的资源节点可以处于同一云计算平台下；动态可扩展性一方面表示云计算环境的规模可以动态的进行伸缩，来满足日后应用和用户数量增长的需要。另一方面表示资源的快速弹性提供，消费者可以根据自己的需求动态的申请或者释放物理和虚拟资源。这样不但提高了资源的利用率，平台的服务质量也得到了保证【2J。当前云提供者可以分为三大类【3】，即SaaS提供商、PaaS提供商和IaaS提供商。1．SaaS(SoftwareasaService)SaaS是一种全新的软件服务方式，用户不再需要对软件进行任何安装操作，而只需将电脑或者手机等终端接入网络并向软件提供商支付一定的费用，就可以向软件提供商获取各种软件服务。此时应用软件运行的环境和平台对用户是透明的，用户只能对其进行有限的设置。对于许多小型企业来说，SaaS是采用先进技术的最好途径，它消除了企业购买、构建和维护基础设施和应用程序的需要。SaaS是软件业今后的发展方向，目前，已有许多公司通过SaaS提供了各种软件应用和服务，如Salaesforce公司提供的在线客户关系管理(ClientRelationshipManagement)服务，微软提供的WindowsAzure云操作系统，Google一系列的应用平台，包括谷歌地球、Gmail、Docs等，国内外杀毒软件厂商推出的在线杀毒等云安全解决方案。2．PaaS(PlatformasaService)PaaS实际上是指将软件研发的平台作为一种服务，以SaaS的模式提交给用户，它实际上是SaaS模式的一种应用。PaaS在云架构中位于中间层，其上层是SaaS，其下层是IaaS，能够为企业或者用户提供定制化研发的中间件平台、数据库和应 重庆邮电大学硕士论文第一章绪论用服务器等，在该平台上，用户可以进行软件的开发、测试、部署和托管而不需要去购买软件和硬件来配置开发环境，如GoogleAppEngine、Facebook的开发平台等。3．IaaS((InfrastructureasaService)IaaS是指企业将具有计算、存储、网络和应用虚拟化等功能的基础资源封装成服务提供给用户，然后用户通过网络远程访问该计算资源，并从中获得应用所需的计算能力。对于这种计算资源用户不需要进行购买，而只需支付租用费用。在IaaS环境中，用户只需通过裸机和硬盘，就可以让它运行Windows或者是Linux，或者是两者同时运行，只要IaaS环境中存在资源，它就可以通过虚拟化的方式提供给用户。IaaS有公有的也有私有的。AmazonEC2针对所有用户开放，所以它在基础设施云中使用公共服务器池；而对于一些存在私有化需求的服务时，则会使用企业内部的私有服务器池；如果在企业数据中心环境中开发软件，那么这两种类型都能使用，而且EC2可以根据需求临时扩展资源，从而减少使用成本。同时，IaaS也存在安全漏洞，如果黑客可以侵入IaaS，那么用户或者企业的私密数据就有可能被窃取，因此一个强大的分区和防御策略就显得格外重要。中国云计算的发展始终围绕着创新、融合、普及三个特点，不但在云计算技术创新和商业模式上取得了突破，而且将云计算与物联网、移动互联网等新兴技术进行了融合，同时将云计算应用到了公共基础设施和公共服务等方面。1．云计算与3G云计算与用户之间需要有一条快速通道，这条通道既要保证能容纳足够多的用户，又要确保用户在使用这条通道的时候不会出现拥堵，这条通道就是3G。3G与云计算是相互依存，相互促进的关系。一方面，3G网络目前已经实现了全国的覆盖，无论用户在什么地方，只要通过具备联网功能的笔记本、手机、平板电脑等终端设备就可以接入3G网络，实现对云计算资源的访问；另一方面，云计算可以给3G用户提供无限的存储空间，强大的计算能力，丰富的软件服务，让用户通过普通的终端就可以享受到无以伦比的服务体验。2．云计算与物联网物联网通过各式各样的传感设备，将感知的信息通过互联网上传到相应的由大型计算机构成的处理中心，处理中心对汇总的信息进行处理、判断，然后再对实体世界做出反馈或发出控制信息。云计算与物联网是交相辉映的关系。一方面，物联网的发展离不开云计算的支撑。物联网采集到的信息量是巨大的，必须要有强大的数据处理中心对其进行处理，而云计算可以为物联网提供这种数据处理能力；另一方面，物联网将成为 重庆邮电大学硕士论文第一章绪论云计算最大的用户，为云计算提供更加广阔的市场，对它的发展起到积极的促进作用。3．云计算与移动互联网移动互联网融合了互联网和移动通信网的发展优势，而云计算将成为移动应用的主导运行方式。手持设备通过云计算可以实现甚至超越传统PC能达到的功能，两者的结合充分的发挥了手机的便携性和通信能力与云计算的计算能力和存储能力。1．2研究现状云计算是在网格计算的基础上发展而来t41，它在网格计算的基本框架下结合了分布式计算、并行计算等技术，注重于给用户提供虚拟的资源和服务。但两者的区别还是比较明显的，就像是TCP／IP与OSI之间的区别。作业调度是云计算的价值和目标之一。云计算通过对所有资源进行分组，来构成一个巨大的资源池。它可以将一个巨大的任务划分成许多独立的，之间没有相互关系的子任务，然后分配给资源池中的节点运行【51。如果一个节点失效或者是没有返回结果，那么该节点上的任务会重新分配到其他的节点上，而不会影响整个任务处理的过程。用户还可以从资源池中申请资源来部署应用。目前，国内外很多专家学者在云计算与网络计算的资源调度算法中做了大量的研究，将各种启发式算法用于资源调度的任务分配。在成本控制方面，Buyyat6]提了一种基于应用经济模型的优化调度模型，以尽可能少的资源来满足资源使用者的计算任务最低要求；文献【7J根据云计算环境下不同的用户对资源的需求是不一样的特点，提出一种基于成本的改进调度算法，该算法依据资源成本和计算性能给用户分配高计算比率的云资源，改善了调度效率；文献【8】通过分析云计算资源，用户计算任务的差异化QoS需求以及云服务提供商的最大收益，提出了非抢占带优先级的M／G／1队列模型和成本函数，该算法保证了用户的QoS需求和云计算服务提供商的利润最大化，但这种算法可能会增加用户的等待时间。在最优跨度方面，Ⅵncenozo【9】【10】提出了基于遗传算法的子任务资源调度，以尽可能的提高资源的使用率和吞吐量；文献[hi利用模糊聚类方法对网格异构资源进行合理划分，并且用DAG图表示任务间的依赖关系，从而缩小搜索空间，大量减少任务调度时的时间耗费；文献【12J根据甘特图生成的DAG图计算决策任务和决策路径，然后重新分配决策路径上的任务节点，以缩短整个任务的收敛时间；文献【13J提出了一种在预算和时间约束的情况下，对任务调度和资源配置进行高效管理的 重庆邮电大学硕士论文第一章绪论算法，该算法在考虑约束的情况下最大化了用户优先工作流的数量。在考虑任务间的依赖关系方面，SurajPandey[14】等将考虑了任务间的依赖关系的粒子群算法(PSO)用于云计算环境中的资源调度中；文献【l5】提出了网格工作流分类方法，并对任务间存在DAG关系的网格系统进行了研究和分析，介绍了多种DAG结构网格系统的基本原理及适应范围；文献【l6】提出了一种新的启发式算法用于异构环境下存在DAG关系任务的任务调度，该算法将任务分割成更小的子任务，然后计算节点和边的权重并评定优先级别，再根据优先级别进行任务调度，这样能较好的处理任务之间的依赖关系。1．3本文研究内容云计算环境中的资源都是动态异构的，对大规模任务进行资源调度时，在考虑资源的安全、负载均衡等问题的前提下要尽量提高系统的吞吐量和最优跨度。资源调度是个NP问题，云计算面对着十分庞大且呈曲线上升的计算任务数量，资源分配问题和任务调度问题成为了决定云计算效率的重点和难点。资源调度的准则有基于信任机制准则、服务质量QoS准则、Agent机制、最短完成时间准则、最优跨度准则、安全准则等。目前的任务调度算法可以得到最短的任务完成时间或者最高的资源利用率或者最短的资源使用者的平均等待时间。因此，在考虑任务间有依赖关系的前提下，如何对云计算中的资源进行合理的分配，对任务进行高效的调度成为任务调度的一个重要研究方向。针对上述调度算法考虑因素单一的问题，对遗传算法进行研究，考虑到遗传算法的全局搜索能力和最优解的良好收敛性，本文提出了一种新的改进遗产算法用于云计算环境中的资源调度，该算法在海量任务的编码上和适应度函数上均做了改进，不仅保证了种群初始时的多样性同时也保证了种群最后得到的最优解较为理想。最后在云仿真器ClousSim上仿真，实现结果表明改进型的遗传算法资源调度算法能很好地适用于云计算环境中大规模的任务资源调度。1．3论文组织结构本论文分为六章，结构如下：第一章对云计算及其发展做了介绍，分析了云计算与网格计算的区别和联系，概述了论文的研究内容和论文结构；第二章对任务调度的定义、特点、目标做了阐述，介绍了一些常用的任务调4 重庆邮电大学硕士论文第一章绪论度算法以下云计算环境下的任务调度算法；第三章分析了遗传算法的优缺点，以及遗传算法的操作过程：第四章对遗传算法存在的一些缺点进行了改进，并对算法进行了设计；第五章介绍了CloudSim平台，并在该平台下对算法进行了仿真，从任务完成时间、算法收敛速度、任务完成所需成本三方面验证了算法的有效性；第六章，总结与展望，总结了本文所做工作和不足之处，并提出了未来的发展和研究方向。 重庆邮电大学硕士论文第二章云计算环境下的调度算法2．1任务调度简介云计算涉及多种关键技术，包含数据中心节能技术、节点互联技术、可用性技术、容错性技术、数据存储技术、数据管理技术、数据切分技术、任务调度技术、编程模型、负载均衡技术、并行计算技术、虚拟机技术、系统监控技术等。云计算环境中的资源是异构的和动态变化的，同时云计算环境中的应用程序和任务数量也是巨大的，不同的应用和任务所需求的资源也是不同的，这些原因导致了任务调度复杂性高。优良的任务调度策略不但可以减少任务的执行时间，还可以提高整个系统的效率。所以在云计算环境中，任务调度技术成为了重中之重。2．1．1任务调度的定义在云计算环境下，一个应用程序可以划分成多个子任务，这些子任务构成了程序的任务集合，集合中的任务可以按照线性的方式串行执行，也可以分配到多台处理机上同时执行。但是在一些子任务之间由于存在数据依赖的关系，即被依赖的任务必须在依赖的任务完成后才能执行，所以任务调度的目的就是在满足这种依赖关系的前提下，寻找到一种合理的调度策略，将任务合理地分配到不同的处理机上执行，以减少任务的执行时间【r71。为了得出调度算法的优劣，必须根据一定的性能指标来对其进行评价。本文根据调度算法的特点，选择调度算法的最优解性能和搜索效率作为评价的标准。调度算法的性能体现的是调度策略下的任务完成时问，调度算法的效率体现的是算法的收敛速度。显然一个优良的调度算法得出的最优解可以保证最短的任务完成时间，同时搜索到最优解的过程也比较短。2．1．2任务调度的特点在云计算环境下，应用程序和任务数量也是巨大的，且任务之间可能存在数据依赖的关系，导致任务的分配和调度存在一定的复杂性。因此在云计算环境下进行任务调度时必须考虑以下几个特点：1．任务调度是大规模的、存在约束条件的。云计算系统可能包含互联网上的 重庆邮电大学硕士论文第二章云计算环境下的调度算法任何一台服务器或PC，所以不可能对所有的任务进行集中式的调度和管理。因此，针对任务的特点可以在前提条件下对任务进行分区域的、并行的方式进行任务调度。2．任务调度的环境是异构的。云计算环境的显著特点就是异构性，所以调度算法必须充分考虑这个特点，对不同的资源节点进行区别化的管理。3．任务调度是可以扩展的。云计算系统的规模会随着越来越多的资源节点的加入而变得越来越庞大，在这种情况下，云计算系统的任务调度必须进行相应的扩展，以提高云计算系统的性能。4．任务调度与云计算资源节点内部的调度策略必须相互独立。资源节点之间具有自己的调度策略，该策略不受云计算任务调度系统的影响。5．任务调度具有动态自适应性，可以根据变化的环境动态的进行自适应调整。云环境中的资源规模和结构无时无刻不在发生变化。云计算环境对资源没有严格的限制，任务节点都可以随时加入到云计算环境中，这样就可能存在某些资源会出现故障，在故障修复后又可以从新加入到云计算环境中等。所以，任务调度应该适应这种动态的环境，动态的调整任务的分配，给用户提供更加可靠的服务。2．1．3任务调度的目标云计算作业调度的基本要求是使用户的任务完成时间最短、任务所需的单位成本最少。其主要目标包括几个方面：最优跨度、服务质量、负载均衡、经济原则【18】：1．最优跨度实现最优的跨度是用户与云计算系统的共同目标。跨度表示的是任务执行所占用的资源长度，是从任务获得资源运行到所有的任务运行完毕释放资源所占用的资源时间。2．服务质量QoS云服务的QoS主要表现在经济费用，响应时间(包括处理时间和传输时f日-j)，可靠性即云服务正常运行的概率，可用性即云服务可被成功访问的概率，安全性即用户的数据不能被第三方获取。3．负载均衡根据各资源节点上任务队列的情况来设置相应的调度策略，可以使任务在各资源节点上的分布均衡一些。常用的负载均衡策略有轮询策略、加权轮询策略、负荷最轻策略、粘连策略等。如果在任务调度中不考虑负载均衡可能导致部分资源使用率过高而部分资源空闲的状况，因此在开发并行计算与分布式计算应用时， 重庆邮电大学硕士论文第二章云计算环境下的调度算法负载均衡是一个重要的衡量指标。4．经济原则云环境中的资源既有高性能的服务器，也有普通的PC机，它们的运行速度和稳定性都有很大的差别。在实际的使用环境中，云计算服务提供商会根据设备的不同性能制定不同的价格。如何使用户获得较好的资源同时又要使云计算服务提供商的利润最大化也是任务调度的追求的目标。2．2任务调度算法云计算和网格计算有很多的相似性，尤其在任务调度方面。而网格计算中对任务调度的研究已经十分成熟，存在很多高效的任务调度算法，所以可以将网格计算中的任务调度算法应用到云计算的任务调度中。1．传统的作业调度算法传统的调度算法包含轮循调度、加权轮循调度、最小连接调度及其改进算法、目标地址散列调度、源地址散列调度等，这些算法的时间复杂度较低，比较简单，但是性能比较差。2．启发式智能调度算法启发式智能算法是研究比较深入，应用比较广泛的寻优算法。目前，很多启发式智能算法相继的被学者提了出来，如神经网络、模拟退火【191、禁忌搜索、遗传算法1201、蚂蚁算法121】等，并将这些算法运用于网格计算的任务调度中，有效的提高了系统的吞吐量，减少了任务的完成时间。3．基于Agent的作业调度算法基于Agent的任务调度[221[231其基本设计思想是：把网格计算的资源节点通过特定的技术封装成一个Agent，然后网格计算的任务分配对象就由资源节点变成了Agent，而Agent具有一定的自学习和局部感知能力，在Agent之间进行任务分配具有较高的求解效率。而且在网格计算环境中，Agent的层次结构可以更加方便的进行扩展。4．基于经济学模型的调度算法网格计算中的资源相当于商品经济模型中的商品，而用户就是商品的最终购买者，对不同的资源需要支付的费用也不同，基于经济学模型的作业调度【241的基本思想是通过区别定价来协调资源和用户之间的关系，以达到系统的优化和效率的提高。5．其他改进的调度算法以上提到的都是比较基础的算法，目前已有很多学者在上述调度算法上进行 重庆邮电大学硕士论文第二章云计算环境下的调度算法了改进和综合，尤其是考虑到算法的实际使用环境而加入了相应的条件约束，如任务优先级约束、成本约束、负载均衡约束、QoS约束等。2．3云计算环境中的任务调度目前，云计算环境中的任务调度算法的研究已经有一定的进展，google、IBM、微软、亚马逊等大型公司都已经开发出了自己云计算平台，由于缺乏统一的标准，不同厂商的任务调度方式也存在一定的差异。分布式数据处理MapReducel25JMapReduce是一种软件架构，依靠并行计算的方式处理大规模海量数据。它分为Map和Reduce两个过程。Map过程是把一个任务分解成多个子任务，并将一个子任务对应一个MapO醒l数，实现映射过程。Reduce过程则把MapOi函数对子任务的处理结果进行汇总，以得到最后的结果。两个主要的函数如下：Map：(in_key,in_value)一{(keyj，valuej)Ij=l⋯k)Reduce：(key,[valuel,---,valuem】)--"(key,final_value)Map与Map之间，Reduce与Reduce之间都是相互独立的，因此可以并行操作。一个大型任务进过分割和并行计算都可以明显减少任务完成时间。MapReduce不仅可以并行计算，还能进行容错处理和负载均衡。由于一个任务是被分割成多个子任务分发给一个主节点管理下的各个分节点进行处理的，因此可以根据资源节点负载的情况来进行子任务的分配和管理。在节点处理任务的时候，主节点会对分节点的工作情况进行监控，一旦分节点失效或者未得到处理结果，该节点上的所有任务就会重新分配到其他的节点上运行。MapReduce的运行模型如图2．1所示。原始数据l原始数据2原始数据M结果1结果R图2．1MapReduce的运行模型 重庆邮电大学硕士论文第二章云计算环境下的调度算法MapReduce操作的执行流程图如图【2612．2所示。MapReduceh函数按每块16MB～64MB的大小对输入的文件进行分块，然后通过主控程序Master把分块后的Map任务和Reduce任务分派到空闲的Worker机上执行；分配了Map任务的Worker处理读取到的输入块数据，产生中间结果并定时将缓冲到内存的中间结果写入到本地硬盘；执行Reduce的Worker读取到MapWorker硬盘上存储的中间值，然后对中间值进行排序和简化，并输出最终结果。输入文件Map阶段占氅蔻嚣Reduce阶段输出文件集2．4本章小结图2．2MapReduce的执行流程图本章对任务调度的定义、特点、目标做了详细阐述，同时分类介绍了现在流行的一些启发式任务调度算法，以及目前云计算环境中常用的云计算任务调度模型。上述算法在对异构环境下的海量任务进行调度的时候存在不足，不能满足最优跨度的需求，而遗传算法恰好在群体寻优方面存在优势，非常适合于云计算环境下任务调度。10 重庆邮电大学硕士论文第三章遗传算法'帚二早逐传异法遗传算法(GeneticAlgorithm)是由美国Michigan大学J．Holland教授于1975年首先提出来的，它是模拟达尔文生物进化论的一种搜索启发式算法，是进化算法的一种，可以通过计算机来模拟它的遗传、选择、交叉、变异操作。由于其具有较好的全局寻优能力和潜在的并行性，遗传算法已广泛地应用于人工智能、机器学习等领域。3．1遗传算法简介遗传算法【27】(GeneticAlgorithm)是进化算法中产生最早，应用比较广泛的一个研究方向。它模拟自然界的进化方式，将求解问题抽象成染色体，一条染色体表示一种问题的解决方案。通过对染色体进行交叉变异操作产生不同的问题解决方案，并从中选择最优的方案。遗传算法的本质是一种高效、并行、全局寻优的进化算法，它能在搜索过程时智能地进行调整搜索方向，按照适应度值的大小挑选优秀个体，组成新的群体，新的群体既继承了上一代的信息，又优于上一代，这样逐代进化就能产生越来越好的近似解。3．1．1遗传算法的定义遗传算法【28】的求解过程是从一个初始种群开始的，种群中包含多条染色体，染色体通过基因编码的方式获得的，基因反应的是问题特征，所以说一条染色体表示的就是多个问题特征的集合。因此，首先要做的工作就是问题特征转换成相应的基因，并将基因值组成一条染色体，这就是编码过程，为了简化编码过程，常用二进制的编码方式。初始种群生成以后，需计算染色体的适应度值，并根据适应度值的大小来选择个体，优秀个体的适应度值更大，被保留的概率也就越大。为了确保种群的多样性，防止出现局部最优解，需对种群进行交叉和变异操作以产生新的染色体。这就好比自然进化，后代种群中的个体会更加的接近最优解。只要对上述过程进行无限次的迭代，算法就有可能求出问题的最优解。遗传算法流程图如图3．1[291所示。 重庆邮电大学硕士论文第三章遗传算法@题的初始⑩上I编码和初始化种群上适应度检测卜J个体选择上交叉与变异土新种群◇解码士＼题的解空间)N图3．1遗传算法流程图3．1．2遗传算法的优点与缺点遗传算法作为一种全局搜索算法较传统启发式优化搜索算法存在很大的优势：具有自组织、自适应、和自学习性，只要确定好了初始种群、适应度函数、交叉变异算子，算法就可以对解空间自行组织搜索，根据交叉和变异算子调整搜索方向，中途不需人为的进行干涉，适用于解决复杂的非结构化问题；具有本质并行性，可以将种群中的个体分配到数百台甚至数千台计算机上并行计算而无需考虑并行系统的结构，也可以将种群分为多个区域，不同区域可以并行的进行解空间的搜索；具有可扩展性，容易与其他算法结合。但是，遗传算法也在最优解搜索的时候也存在不足【30】：(1)容易陷入局部最优，发生“早熟"收敛；(2)存在“欺骗”问题。在遗传算法的搜索过程中有可能搜索到最优解但又将其舍弃，使最后搜索到的并不是全局最优解；(3)难于处理非线性约束。对非线性约束的处理，大部分算法都是添加惩罚因子，这是一笔不小的开支；(4)初始种群的优劣一定程度上决定了算法的性能和效率，遗传算法在初始种群的设置方面没有优势，可以用其他的启发算法来确定初始种群；(5)遗传算法具 重庆邮电大学硕士论文第三章遗传算法有的内在并行性和内含并行性没有得到真正的发挥。3．2遗传算法的实现步骤3．2．1编码遗传算法求解问题时，需要将目标的问题特征转换成遗传算法的染色体的基因值，该转换过程就是遗传算法的编码过程，它实现了问题空间到遗传算法解空间的映射，后续的所有操作都是在该解空间上进行的。遗传算法的计算过程具有鲁棒性，因而它对编码方式没有严格的要求。但是编码方式会影响后续交叉和变异的方式，所以采用合适的编码方式有利于问题的求解。目前很多学者对编码方式进行了研究，提出了许多的编码方式，这些编码方式都具有以下几个特点【3l】：完备性，解空间中包含了所有问题空间的映射；健全性，遗传算法解空间中的所有染色体中必须包含问题空间的潜在最优解；非冗余性，染色体和潜在解必须一一对应。遗传算法常用的编码方式有：(1)--进制编码，它将问题特征表示成0和1两种状态，所以问题的状态值就构成了染色体的基因值，这种编码方式符合编码原则，但存在一定的误差；(2)格雷码编码(Graycoding)，格雷码编码是在上种编码的基础上进行改进得到的，相邻格雷码编码的染色体之间只有一位基因值不同，便于连续函数的局部空间搜索【32】；(3)实数编码，实数编码是指用决策变量的真实值来表示个体的基因值，染色体的长度由变量个数决定；(4)符号编码，符号编码也称为大字符集编码，是指个体染色体编码串中的基因值除了取字符集{0，1)之外．还选取无数值含义而只有代码含义的符号集；(5)其他编码，除了上述编码方式外，还存在排列编码、二倍体编码、DNA编码、混合编码、二维染色体编码或矩阵编码等。3．2．2初始群体设定遗传算法中初始群体的设定是通过随机的方式产生的，一般可以采取两种策略：在设定初始群体之前，先找出最优解在解空间的大概位置，然后将该位置周边的染色体作为初始群体；先通过随机方式产生包含一定数目个体群体，然后通过其它的启发式算法从该群体中挑选最好的个体加到初始群体中。对上述步骤进行多次迭代，直到挑出的个体数量达到了预先设定的初始种群规模大小。群体规模的大小会影响到遗传操作的结果。如果群体规模很大，个体的多样 重庆邮电大学硕士论文第三章遗传算法性就越丰富，算法就可能得出最优解。相反，如果群体的规模较少，群体中就有可能缺乏比较好的基因，从而是搜索停留在未成熟的阶段，出现未成熟收敛现象，所以群体规模不能太小。但是，群体规模并不是越大越好。如果群体规模越大，将增加适应度的计算次数，从而增加计算量，影响算法效率。3．2．3适应度函数遗传算法是根据适应度值来对个体进行选择的，适应度值决定了个体在解空间的生存能力，优良的个体对应的适应度值更大，在选择操作中被保留的概率也就更大。由于适应度值是算法进行选择操作的唯一依据，所以适应度函数直接决定了种群的进化方向。而适应度函数是将目标函数通过一定的变换规则而得来的，这种变换称为尺度变换。常用的尺度变换方式有如下三种：(1)将目标函数直接转化为适应度函数Fit(f(x)】：j，厂@)目标函数为最大问题(3．1)卜吖t-／(x)目标函数为最小问题、7从3．1式中可以看出该适应度函数的计算方式比较简单，但是常用的轮盘赌选择中的概率不能出现负数，而该适应度函数显然不能满足这点。如果目标函数的函数值分布具有不均匀性，由此计算出来的平均适应度值必然不能真正反映个体的优劣，得到的最优解也不一定是真正意思上的最优解。(2)界限构造法目标函数为最小问题时：Fit(删=n_ml舞‰似(3．2)式中cmax为f(x)的最大估计值。目标函数为最大问题时：眦(f(X))=R‰西掰‰m(3．3)式中cm汛为厂@)的最小估计值。这是对3．1方法的改进，解决了3．1算法存在的问题，但在某些情况下却不能准确的估计界限值。(3)倒数法目标函数为最小问题时：14 重庆邮电大学硕士论文第三章遗传算法Fit(f(X))=高目标函数为最大问题时：m(f(X))=志c为目标函数界限的保守估计值。3．2．3遗传操作c≥0，c+厂(x)≥0(3．4)c≥0，c一厂(x)≥0(3．5)标准遗传算法的操作算子一般都包括选择(selection，也可以称作复制)、交叉(crossover，或称作重组)和变异(mutation)--"个基本形式。选择操作就是按照群体中个体适应度值的大小选择优良个体，淘汰劣质个体的过程。个体被选择的概率同个体的适应度值是成正比的。目前的选择算子主要有适应度比例选择、Boltzmann选择、排序选择、联赛选择、精英选择【33】等。适应度比例选择作为最基本的选择算子，通常用轮盘赌的方式实现。在该选择算子中，个体被选择的概率是个体的适应度值与种群中所有个体适应度值总和的比值。假设一个种群的规模为刀，种群丁=阢乃，一列，弓∈啪适应度值为厂(Tj)，则该个体被选择的概率可以表示为：B(飞)=丽Ittj)，J|『∈㈨)(3-6)交叉操作的方式是从选择操作中得到的母体中随机选择两个个体搭配成对，然后按照一定的规则交换他们的部分基因值。交叉操作主要包含单点交叉、多点交叉、均匀交叉、洗牌交叉等等。举一个单点交叉的例子，假设有如下八位长的二个体：父个体1101110父个体2101101通过随机数发生器产生一个在1到7之间的随机数a，假如现在产生的是3，选择染色体从右往左的第3个与第4个基因值之间作为交叉点，交换交叉点后的基因值，其交换后的两个子个体为：子个体11010子个体21101110变异是对个体的某一个或者一些基因上的基因值按某一较小的概率进行改变，且变异概率不能取的太大，必须小于0。5。变异操作的方法很多，常见的变异算子是以一定的概率随机改变串结构数据中某一个串的值或某几个基因位原有基因值， 重庆邮电大学硕士论文第三章遗传算法或将某一基因段上的基因倒序口4】【35】。变异操作体现了遗传算法的局部搜索能力，可以避免早熟的现象发生。变异的主要方式有基本位变异、边界变异、均匀变异、非均匀变异、高斯近似变异等等。比如有如下二进制编码表示：l0lO1l0其码长为8，随机产生一个1至8之间的数S，假如现在s=5，则对从右往左的第5位基因进行变异操作，改变该位置的基因值，变异后的个体基因值如下：101010二进制编码表示时的简单变异操作是对于染色体上的基因位，若等位基因为0，则变为1，等位基因为1，则变为0，从而形成新的位串。3．2．4收敛准则遗传算法是一种通过多次迭代以求得最优解的搜索算法，但是不能让算法无限次的迭代下去，所以需要设置一定条件，当结果满足需求时结束算法。可以预先设定一个能反映问题解质量的值，当搜索到的解等于或者超过该值的时候就终止算法；或者设定最大的进化代数，当判断到遗传算法进化次数超过该值时，就认为算法收敛，结束进化。3．3改进遗传算法遗传算法自提出以来至今在各个领域都有它的具体应用。但是，在使用遗传算法的过程中也发现了一些不足，容易陷入局部收敛、存在“欺骗”问题、难于处理非线性约束、初始种群选择困难等。这是因为算法是按一定的概率进行交叉、变异操作的，这样可以更快的产生新个体，也保证了种群的多样性，但是也有可能使种群出现退化的情况。此外，固定的遗传操作虽然适合大多数问题的求解，但却忽略了对问题特性的考虑，从而使得对问题的求解缺乏灵活性。鉴于上述问题，众多学者对遗传算法进行了深入的研究，并对遗传算法的编码方式、群种初始化方法、适应度函数、交叉和变异算子提出了改进的办法。为了改进遗传算法的性能，学者们对现有的遗传算法进行变形，提出了自适应方式和动态策略。3．3．1自适应遗传算法遗传算法中选择算子就是将父代种群中优良个体保留下来传给子代种群；交叉算子则是为了得到更多的潜在最优个体；变异算子是为了保持种群中个体的多 重庆邮电大学硕士论文第三章遗传算法样性。所以交叉算子和变异算子的选择对遗传算法的性能和效率有着至关重要的作用，决定了算法的收敛速度。交叉概率越大，就可以更快的生成新个体，但也容易对遗传模式造成破坏，使得潜在最优解的基因结构发生改变。当交叉概率过小，则会降低搜索速度，甚至停滞不前；过小的变异概率，种群的个体结构就会显得比较单一，但如果变异概率太大，遗传算法就和随机搜索算法相差无几。为了找到合适的交叉概率和变异概率，Srinvivas等提出了一种自适应遗传算法(AGA)【36J，该算法在进化的过程中可以对交叉变异概率动态的进行调整。当种群中各个个体适应度值比较接近或者出现“早熟”时，提高交叉概率，让种群快速生成新个体；当种群个体适应度值差别较大时，为了保护潜在的最优个体，应减少适应度值较高的个体的交叉概率，而对适应度值较低的个体，应增加其的交叉概率，保持个体的进化。在自适应算法中，交叉变异概率按如下公式进行自适应调整【28】：r尼1嘛似一厂’)足={扁默一尼叼L良2(k3嘛似一厂)Pm={厂m簖一厶叼Lk4。l≥‰g。}<‰g。f2‰gIf<‰g(3．7)(3．8)厶默表示群体中最大的适应度值，五增为每代群体的平均适应度值，厂’为要交叉的两个个体中较大的适应度值，厂为要变异个体的适应度值。这里k1，k2，k3，k4可以根据调度的特征取(0，1)区间的值。上述的自适应调整方法对于进化后期是非常合适的，可以保留最优解，但是在进化初期，较优的个体由于有较高的适应度值，所以它对应的交叉概率会很小，从而不能产生更优的个体，使搜索陷入局部收敛。因此，对上述公式做进一步的改进，保证群体中的最大适应度值的个体的交叉率和变异率不为零，这就相当于把较优个体的交叉率和变异率提高了，使它们也参与算法的进化。为了保证每一代的优良个体不被破坏，采用精英选择策略，将它们直接复制到下一代中。改进后的交叉选择概率如下：足：卜≮掣∥‰(3．9)LPcl，厂7<尼妒口Pm：卜等掣驼钿(3-10)LPml，厂<尼叼3．3．2混合遗传算法有些优化算法有很强的局部搜索能力，而一些启发式算法在运行效率方面有 重庆邮电大学硕士论文第三章遗传算法较强的优势。如果将一种局部寻优算法和遗传算法加以混合，就可以得出一种混合遗传算法，它集合了两类算法的优势，在求解速度和求解质量方面都有较大的提升。目前混合遗传算法可以通过引入局部搜索过程或者增加编码变换操作来实现。混合遗传算法的基本构成框架如图3．2：图3．2混合遗传算法构成示意图(1)遗传算法和蚁群算法相结合的混合遗传算法蚁群算法(antcolonyoptimization，ACO)是一种用来在图中寻找优化路径的机率型算法。主要是通过一种正反馈机制原理使蚂蚁群体之间的信息素得到传递和更新，从而得到最短路径，但在算法开始的时候由于信息素较少，导致算法搜索速度较慢。遗传算法和蚁群算法的结合可以把两者的优势结合起来，初期利用遗传算法的全局快速搜索能力来生成信息素分布，后期根据遗传算法的正反馈机制求解最优解，从而提高了求解速度，增加了求解精度。(2)遗传算法和粒子群算法相结合的混合遗传算"法(GAPSO)t37】在算法运行初期用遗传算法对种群进行全局搜索，待种群的规模缩小后，再利用粒子群算法来加快算法后期的收敛速度。这样可以加快收敛速度并且经过多次迭代产生的末代种群中的个体将更接近全局最优解。该算法需要对遗传算法的适应度函数、交叉算子、变异算子、混合算法切换点进行改进。算法流程如下： 重庆邮电大学硕士论文第三章遗传算法N开始初始化种群确定参数三[选择交叉变异黾否满赶日换条件＼／Y选择M个最优个体作为粒子群算法的初始粒子并初始化速度更新粒子个体极值以及领域极值更新粒子速度和位置《黔弋苎兰吵‘丙Y土选择最优个体作为调I度问题的最优解———厂一厂萧f结束)图3．3算法流程图(3)遗传算法与模拟退火算法想结合的混合遗传算法在遗传算法后期，不同个体的适应度值区别不大，子代的优势不明显，群种可能陷入局部收敛。此时对遗传算法的适应度进行适当的拉伸(scalingorstretching)，遗传算法后期，拉伸作用就凸显出来，使适应度相近的个体适应度差异放大，从而就可以更加容易的选择更优的个体。适应度的拉伸方法：0℃|1^=殛i而(3．1i)厶J￡=】VT=To(0．99a_1)式中，^为第i个个体的适应度，M为种群大小，g为遗传代数，丁为温度，％为初始温度。3．3．3并行遗传算法遗传算法具有天生的并行性，根据算法复杂度，算法的结构可以有很多种并行设计方法。在当前多核处理器已经成为主流配置的大环境中，并行设计可以充分利用处理器资源，提高算法效率。同时并行遗传算法还可以有效地降低过早收敛的风险，因为在并行遗传算法中有多个群体，各种求解最优解，然后再汇合在一起寻找整体最优解。目前有三类实现方案： 重庆邮电大学硕士论文第三章遗传算法(1)主从式并行遗传算法，又称为全局并行化方法。该方法包含一个主服务器和多个从服务器，主服务器监控整个染色体的种群，执行选择、交叉、变异等操作，并给从服务器指派染色体适应度值的计算工作；从服务器接收主服务器指派的染色体适应度值得计算任务，并把计算结果返回给主服务器。主从式并行遗传算法在执行的过程中，主服务器要给从服务器传递染色体代码和接收从服务器返回的个体适应度值。所以主服务器必须等待接收到所有的个体适应度值后，才能进行后续的演化计算。这就导致了通信时间会影响算法执行的效率，并且这种方法使得主服务器的负载比较大，引起负载不平衡，效率不高。Wo图3．4主从式并行遗传算法示意图(2)粗粒度并行遗传算法【38】，又称分布式遗传算法。该方法把整个种群分成多个子种群，并分配给各自对应的服务器，每个子种群在各自的服务器上孤立的进行选择、交叉和变异操作，并定期的与周边的服务器进行最优个体交换，从而可以加快算法收敛的速度。该算法是目前比较流行的一种并行遗传算法，粗粒度模型对并行系统平台要求不是很高，可以松散耦合并行系统，且很好的开发了群体之间的并行性。图3．5粗粒度并行遗传算法示意图(3)细粒度并行遗传算法【39】，也称领域模型。该方法把种群中的每一个个体均分配给一个处理器，每个处理器单独的进行适应度值的计算，同时与相邻的处理器传递个体来进行选择、交叉和变异的操作。20 重庆邮电大学硕士论文第三章遗传算法●▲●▲●▲●1，1，1，'，1，一▲●▲●▲●▲●▲1，1，1，1，1，●l●▲●▲1，1，1，1，1，●▲●▲●▲●▲●▲1，1，'IV'，1，●▲●▲●▲●▲●▲1，1，1，1，1，图3．6细粒度并行遗传算法示意图(4)多层并行遗传算,澍40j，该模型如同一棵树，在最底层，多个子节点并行运行基本的遗传算法，每个子节点的染色体、遗传算法的结构参数随机确定。上层节点同样运行基本的遗传算法，但染色体和遗传算法参数均来自前一层节点的较优染色体和算法参数，上述就是一个递归的过程，直到到达最高层，从而获得问题的最终解。图3．7多层并行遗传算法(子节点是主从式模型)图3．8多层并行遗传算法(子节点是细粒度模型) 重庆邮电大学硕士论文第三章遗传算法3．4本章小结图3．9多层并行遗传算法(子节点是粗粒度模型)本章对遗传算法做了介绍，描述了遗传算法详细的操作流程，分析了目前遗传算法在求解问题的优势以及存在的一些不足，最后对现在的遗传算法的改进策略进行了阐述。下一章在改进遗传算法的基础上，进行了再次改进，并加入了算法对一些特殊情况的考虑，让算法更加适合于现实的使用环境。 重庆邮电大学硕士论文第四章基于改进遗传算法的云计算任务调度算法在云计算环境中，一个大型的任务可以分解为多个子任务，然后分配到不同的处理机上并行运行，以减少任务的运行时间，同时提高处理机的执行效率。但是当子任务的数量规模较大的时候，找出最短的任务完成时间已被证明属于NP问题。对于规模较小的任务的并行多机任务调度可以用启发式算法，但是要处理大规模任务的时候，启发式算法仍然不够有效。遗传算法具有近优、快速、并行性、易实现等特点，在解决大型任务调度方面具有很大的优势。目前有很多学者在研究遗传算法的任务调度问题，并对该算法进行了改进，解决了遗传算法早熟、难于处理非线性约束、稳定性差等问题，并把遗传算法应用到网格计算、云计算的任务调度中。但是有些子任务之间是存在不同程度的数据依赖关系的，因此，如何合理的调度和部署这些存在数据依赖关系的任务成为了提高系统的服务质量的一个关键因素。4．1数据依赖关系的处理任务之间的数据依赖关系可以描述为：如果存在任务乃、乃，乃依赖于乃，则表示任务乃需要获得乃运行完后得到的结果作为自己的数据输入，如果在任务的执行序列中乃先于乃执行，则会出现死锁现象，乃会一直处于等待数据获取状态。所以必须采取一定的方法来避免这种现象。对于任务调度对象是存在数据依赖的任务时，可以绘制DAG图来进行任务调度，如图4．1。图4．1只有一个根节点和一个叶子节点的DAG图 重庆邮电大学硕士论文第四章基于改进遗传算法的云计算任务调度算法图4．2一个树形的DAG图图中的节点表示的是任务，节点之间的有向边表示的是任务的前驱和后继关系，被指向的节点以上一节点为数据依赖，只有等上一节点任务完成之后才能开始任务。因此，死一乃表示任务乃完成之后才能启动任务乃。对于一个DAG图G，设G=仃E驯，其中，T为子任务集，产阢乃，一死，，乃为第f个子任务，表示DAG图中的一个节点；E表示DAG图中的有向边集，(瓦，乃)∈E，表示的是乃一乃的关系，乃为乃的一个前继，乃为乃的一个后继；局为估计运行时间矩阵，可表示为矩阵历，瑕川，西以矽为子任务Ti在处理机乃上的估计运行时间；处理机的集合P=PD，PJ，．．．，厶，，Pi表示第f个处理机；处理机之间的数据传输延时可以用一个mxn的矩阵C[m，，，2，表示，处理机Pf与处理机P，间的传输延时表示为Cff，．71，。任务调度的目的就是，在各个任务满足依赖关系的约束下，把所有的任务合理的分配到有限的处理机上，并使整个大任务的完成时间最短。假定某个DAG图的一个分配与调度策略为S，则在调度策略S下，处理机尸，完成所有分配的任务所需要的时间为瓦俨∥。所有分配和调度S完成所需要的总时间设为聊，则有T(S)=max(Ts俐，ltime(ail，)i∈[1，m】(4。4)J‘-一t，=1由于不同的处理机是同时进行任务处理的，故总的任务完成时间是处理机集合P中最后完成任务者所花的时间，所以总任务完成时间的计算方法如下：7’@)=m锻罂z(瓦(Pf))=maxmt艺cfme(口协)(4-s)完成所有任务所需要的成本为所有处理机完成任务的时间乘以单位时间运行成本RCU(i)之和：cost(S)=>[rAPi)×RCU(i)】(4．6)J‘_Ji=1子任务‰v完成所需要的时间设共Jfinishtime(auv)，实际包含了等待处理机上处理排在％妒之前的其他子任务的时间：finishtime(auv)=>time(atl妒)u∈【1，m](4．7)J‘·一妒=1在调度策略S下，平均任务完成时间为所有子任务的完成时间总和除以任务个数：=型m三三圣naveragetime(S)!=三兰塑垫立(4-8)=丝些鼍半型型(4．8)4．3算法描述算法的目的是为了得到一个合法的调度，使得各个子任务在不破坏DAG图的约束关系的前提下执行，得到的总任务完成时间．成本或平均任务完成时间-成本最短。算法流程图如图4．3所示。 重庆邮电大学硕士论文第四章基于改进遗传算法的云计算任务调度算法图4．3算法流程图Step1．通过深度遍历，读取DAG图中任务节点的深度信息，并创建初始种群(初始种群中任务的排序满足深度值的从小到大排列、满足短任务优先原则、满足含子节点的任务优先原则、满足含直接后续的节点优先原则)：Step2．计算出种群中个体的适应度值大小，并通过精英策略【43】，把最优解直接复制到下一代中；Step3．如果算法不满足终止条件，则继续执行下一步，否则执行第七步；Step4．通过轮盘赌的方式进行选择操作，形成下一代种群；Step5．以概率尸尉染色体矩阵的任意两行进行交叉操作：Step6．以概率鼢寸染色体矩阵的某一个基因元素进行变异操作。转第二步；Step7．输出算法找到的最优解，算法终止。在这个算法执行中，DAG图、节点与节点之间的依赖关系和子任务的估计运行时间都是通过随机的方式产生。4．3．1编码策略与初始种群的生成本算法采用4．2．2节的矩阵编码方式，把任务集产阢乃，一列分配到处理机集P=驴D，尸2，．．．，P∥上的方式为：先计算DAG图中所有子任务的高度值H；然后把相同高度值的子任务划分到一个集合中，总共可以划分成h+1个子集 重庆邮电大学硕士论文第四章基于改进遗传算法的云计算任务调度算法DAG(i)，1≤f≤h，h是DAG图的最大高度值；随机的将DAG(i)中的所有子任务分配到m个处理机上；最后将各个处理机上的子任务按高度值日做升序排列，再按短任务优先原则、含子节点的节点优先原则、含直接后续的节点优先原则进行再次排列。如将DAG图4．1的任务随机分配到两台处理机疡、尸J上，得到的随机染色体矩阵41=【爱薏凳7一"67一"7】(4．9)然后根据深度值约束、短任务优先原则、含子节点的节点优先原则、含直接后续的节点优先原则对染色体矩阵的每行基因进行排序，排序后得到的4，如下：4。=【爱凳爰7一"62】(4．10)通过染色体矩阵可以直接得到处理机乃、尸，上的任务执行队列Po=(to，n，丁4，死，驯，P1=仍，瓦，驯，不需要进行解码，减少了系统处理时间。上述的过程其实就是种群中染色体的生成过程，要达到种群的规模，只需重复上述染色体的生成过程即可。重复一次就可以生成一条染色体，要使种群规模为&则只需重复S次染色体的生成过程即可。生成的种群GJ=口^A2，⋯，彳∥。4．3．2适应度函数的设定适应度函数是用来从种群中选择问题最优解的一个依据，问题的最优解可能是问题空间的一个最大值或者最小值。4．2．3节中对适应度函数进行了改进，使得任务调度的目标变为缩短总任务和平均任务的完成时间，在该节中得出了总任务和平均任务完成时间的计算公式。定义两个适应度函数分别为总任务完成时间和平均任务完成时间的倒数。在调度策略S下，总任务完成时间的适应度函数：1^(S)=而i(4．11)丁@)表示在调度策略S下的总任务完成时间。在调度策略S下，平均任务完成时间的适应度函数：1nh(s)=—average—time(S)=琢疆磊丽瓦丽(4．12)averagetime(S)为在调度策略S下的平均任务完成时间。在调度策略S下，任务完成所需成本的适应度函数：艿(s)=忑1丽(4．13)考虑总任务完成时间．成本的适应度函数为：30 重庆邮电大学硕士论文第四章基于改进遗传算法的云计算任务调度算法R(S)=口^(S)+flf3(s)(4．14)考虑平均任务完成时间．成本的适应度函数为：巴(S)=口厶(S)+p艿(S)(4．15)其中倪￡【0，1]，f140，1】，口+卢=1。通过适应度函数可以看出，成本较低且总任务完成时间或者平均任务完成时间越短的个体，适应度函数值越大，在选择操作中更容易被保留。4．3．3选择操作本文采用轮盘赌选择(roulettewheelselection)作为选择操作算子，它类似于博彩游戏中的轮盘赌。为了防止最优个体由于遗传算子的偶然性而被破坏掉，选择算子同时采用最优个体保护策略，即把父代群体中的最优个体直接复制到子代群体中。根据两个适应度函数可以分别计算出第i个个体被选择的概率为：啪)=毫‰(4．16)哺)=毫‰(4-17)选择下一代个体前，先以弘和妒(其中肛E[0，1】，190E[o，1】，肛+妒=U的概率来分别选择P1(1)和P2(f)。在这个选择的情况下，种群中将存在两个类型的个体，即总时间．成本较低的个体和平均时间．成本较少的个体，好处是保存了种群的多样性，避免了一些优良基因的丢失。4．3．4自适应交叉操作由于在任务调度的过程中考虑了任务间的数据依赖关系，交叉的过程中也必须保持这种依赖关系不被破坏。为了简化交叉操作，降低工作量，保证交叉后生成的新解都是合法解，本文在上节中提出了在染色体矩阵内部进行交叉操作。其交叉算法如下：1．从父代种群中以交叉概率R选择一个染色体矩阵，在染色体矩阵中随机的选出矩阵的两行三，和幻。2．随机生成一个任意数n(O≤n≤R)，R为矩阵的列数。3．根据随机数n确定三J和幻的交叉点。4．将染色体矩阵的两行三，和幻中交叉点以后的任务序列互换。上节中通过实例说明了该交叉过程。B的大小决定了产生新个体的快慢，本文使用Srinvivas提出的自适应遗传算法，通过适应度来动态的调整交叉概率巴。如果个体的适应度值较高，则减少交叉概率R，以保护潜在的最优个体不被破坏， 重塞壑曳盔堂硬±论文第四章基于改进遗传算法的云计算任务调度算法如果个体的适应度值较低，则增加交叉概率R，把该个体淘汰掉。R：卜与掣∥≥钿(4．18)LPcl，厂7<厶叼式中，Pcl=0．9，Pc2=o．6，扁盯表示群体中最大的适应度值，厶vg为每代群体的平均适应度值，厂’为要交叉的两个个体中较大的适应度值，厂为要变异个体的适应度值。4．3．5自适应变异操作变异操作可以保证种群～定的多样性，在种群局部收敛时，通过变异算子的突变作用，可以使局部收敛被破坏。在任务调度中，对染色体矩阵的变异操作是把一个处理机上的任一任务插入到另一个处理机上执行。变异操作的过程如下：1．随机生成一个任意数h(0≤h≤H)，H为DAG图的深度值。2．从父代种群G尸即J，A2,⋯，以)中，以交叉概率Pm选择其中的一个染色体矩阵。3．计算染色体矩阵彳中每行中的子任务个数Ⅳ：『(0≤i≤m)，该行中需包含深度值为h的子任务。4．从最大的帐O≤i≤m)所在行中选出高度值为h的子任务，将该子任务迁移到最小的似0≤i≤m)所在行中。插入位置为高度值为h的子任务之后。当然，f，m并不是越大越好，fIm太大会使遗传算法变成随机搜索算法，而Pm太小则不易产生新的个体、算法也有可能得到局部最优解。Pm对个体的影响和Pc一样。P胁的计算公式如下：％：卜等掣，f‰(4-19)LPml，厂<厶p口式中，尸Iml=o．1，尸‰2=0．001，厂m口x表示群体中最大的适应度值，厶vg为每代群体的平均适应度值，厂7为要交叉的两个个体中较大的适应度值，厂为要变异个体的适应度值。4．4本章小结在本章中，首先介绍了三种对数据依赖处理的方式。然后针对现有的遗传算法存在的问题，对数据依赖处理方式、编码方式、适应度函数进行了改进。增加了一种对存在数据依赖关系的任务处理方法，编码方式由串行编码改为矩阵编码，在适应度函数中增加了平均任务完成时间和成本因素。最后对改进遗传算法的操作过程进行了描述。 重庆邮电大学硕士论文第五章实验仿真与结果分析CloudSiml44]是一个能够对云计算基础设施和应用进行模拟和仿真的可扩展的工具。通过CloudSim仿真工具可以很容易地构建云计算环境来测试和分析新算法的性能；也可以很方便地通过扩展CloudSim的核心组件建立特定的云组件和云体系结构，并在其上实现相关策略及算法测试其性能。为了加快本课题的研究进展，本文扩展了CloudSim核心功能，并对本文提出的基于改进遗传算法的任务调度算法进行了实现。5．1实验仿真环境介绍5．1．1CloudSim简介CloudSim是网格计算模拟器GridSim的升级，其提供了云计算的仿真环境并支持云计算环境中的资源调度管理和模拟。云仿真器CloudSim与网格仿真器GridSim最大的区别是CloudSim提供了虚拟化技术，将数据中心的资源进行虚拟化，并整合和组织起来对云计算环境中的其他服务提供虚拟资源【45】。CloudSim在GridSim基础上扩展和提供了一系列接口，用于云计算数据中心资源虚拟化、模型和仿真环境的虚拟化，同时还提供了资源监控和映射功能。5．1．2CloudSim分层结构CloudSim的层次结构如图5．1所示，共包括三层，最底层为CloudSim核心模拟引擎、中间层为CloudSim仿真层、上层为用户代码层。CloudSim核心模拟引擎是对之前体系结构中的GridSim层和SimJava层进行改进得来的，主要实现对离散事件管理，包含的相关类如图5．2所示。CloudSim仿真层主要为云数据中心环境的建模和仿真提供支持。其网络层通过延时矩阵来模拟真实网络拓扑及模型中的一个消息从一个CloudSim实体传递到另一个实体过程中产生的时延；云资源层模拟与云相关的核心硬件基础设施，并对云协调器实体进行建模，让其负责和其它数据中心及终端用户的通信，监控和管理数据中心实体的内部状态；云服务层主要进行资源的分配，包括对虚拟机的分配，CPU、内存、带宽、存储空间等资源的分配等；虚拟机服务层提供了对虚拟机生命周期的管理；用户接口结构层提供了任务单元和虚拟机实体的创建接口。 重庆邮电大学硕士论文第五章实验仿真与结果分析用户代码层，该层提供主机、应用、虚拟机、用户数量和应用类型，以及代理调度策略等实体。开发人员还可以对上述实体进行扩展。．一一—__—————————————————————●———————●——————————●———————————————————●—●—————·——'———、、(CloudSiIll核心模拟引擎)图5．1分层的CloudSim体系结构5．1．3CloudSim的扩展图5．2CloudSim核心模拟引擎类图PredicateNotTypeCloudSim是开源的，它提供了很好的云计算调度算法仿真平台，可以为用户提供一系列可扩展的实体和方法，用户可以根据自身的要求对上述接口进行扩展，以实现自定义的调度策略，完成对调度算法的模拟，以及进行相关测试和实验。 重庆邮电大学硕士论文第五章实验仿真与结果分析5．2实验结果与数据分析本节通过使用CloudSim仿真工具对本文提出的基于改进遗传算法的任务调度算法进行了实现，并把实验过程中产生的数据与标准遗传算法和考虑数据依赖的遗传算法进行了对比。5．2．1任务完成时间对比第四章中对传统数据依赖的处理进行了改进，并从理论上证明了改进后的数据依赖处理方式可以明显的缩短整体的任务执行时间。但是这只是针对较少的任务和处理机的任务调度，不具有代表性，故这节中通过仿真工具模拟在相同的参数和初始条件下，不同的子任务数量或不同的处理机数量的情况下，标准遗传算法(SGA)mJ和考虑数据依赖的遗传算法(DGA)H7】以及本文改进数据依赖处理方式的遗传算法(IDGA)进行任务调度，并记录任务完成时间。为了保证实验的可对比性，此组任务只考虑任务完成时间而不考虑成本因素，故在IDGA算法进行选择操作的时候取口=1，p=0，而u和妒的取值依据文献【48】得出，取¨=0．7，妒=0．3，同时通过实验来验证“和妒取值的合理性。表5．1参数取值实验处理机个数m子任务个数nu取值(p取值IDGA任务完成时间0．10．9681O．20．8667O．3O．76320．4O．66445】000．5O．56280．6O．4619O．70．36160．80．26220．9O．1635DAG图是任意生成的，每个节点可以包含O~4个后继节点，估计运行时间矩阵地玎的值通过随机方式产生，其范围是1～50，算法的最大进化代数为1000。 重庆邮电大学硕士论文第五章实验仿真与结果分析表5．2算法的主要参数：算法参数取值算法参数取值算法参数取值种群规模10种群规模10种群规模lO吃1．0Pcl0．9Pcl0．9SGAPmO．05DGAPc2O．6IDGAPaO．6Pml0．1PmlO．1Pm20．oolPm2O．0011．少量任务的情况下，将任务分配到5个处理机上，改变子任务的数量从lO到100，记录任务的完成时间。结果如表5．3和图5．3所示表5．3仿真结果对比处理机个子任务个总任务完成时间IDGA较DGA性能数m数nSGADGAIDGA提高百分比％201121081043．7402362272231．765603673443313．78804904614424．121006796436164．2800700600暑500亡：饕伽窭300‘斗20010004060801∞任务数量SGADGAIDGA图5．3任务数量变化的完成时间对比从图5．3可以看出，在较少任务的情况下，三种算法的任务完成时间区别不大，IDGA算法的优势没有表现出来。2．大量任务的情况下，将任务分配到20个处理机上，任务数量的变化区域改为从1000到4000，记录任务的完成时间。结果如表5．4和图5．4所示。 重庆邮电大学硕士论文第五章实验仿真与结果分析表5．4仿真结果对比处理机个子任务个总任务完成时间×103IDGA较DGA性能数m数nSGADGAIDGA提高百分比％10002．3091．9641．8764．4815003．5732．7622．5487．7520005．0453．8413．457102025007．2395．545．1257．4930008．7936．7346．1878．12350011．1728．2467．7585．92400013．60110．3118．90913．6noX厘富镫根球出14121086任务数量图5．4任务数量变化的完成时间对比从图5．4可以看出，在大量任务情况下，IDGA的任务完成最短，与DGA相比具有一定的优势，而SGA由于对依赖关系的处理不当，导致某些子任务被阻塞，长时间等待前继节点的处理结果，进而造成了总任务完成较长。3．把任务数量设为常量4000，处理机数量可变，变化范围为10到40。记录在不同的处理机数量的情况下，任务的完成时间。结果如表5．5和图5．5所示。表5．5仿真结果对比子任务个处理机个总任务完成时间×103IDGA较DGA性能数n数mSGADGAlDGA提高百分比％1056．1239．23331．28720．2540001537．56226．26821．68317．45—4J】1，]咖一0一∞J8～3一一∞一5—2—0一∞J8—1orIl+r．．●●●，llllllL，-t，j4』．0彻 重庆邮电大学硕士论文第五章实验仿真与结果分析2022．51816．42514．1513．852515．82412．1511．3466．623011．36710．6879．29813．17358．8737．8427．1588．72407．4496．7276．2017．82noX厘茁镊由黑昧出：厂——i40j处理机个数图5．5处理机变化的任务完成时间对比从图5．5可以看出，在处理机个数较少的情况下，由于平均分配到不同处理机的任务数量较大，任务执行队列的排序就变得很关键。IDGA较DGA、SGA存在处理数据依赖关系的优势，可以把任务执行序列变的很合理，减少了有前继节点的子节点的等待时间，且IDGA使用了双适应度函数，保留了种群的多样性，避免了优良基因的丢失，所以在处理机个数较少的情况下，IDGA任务完成时间比DGA和SGA缩短了很多。但是，当处理机个数越来越多的时候，IDGA的优势变得越来越不明显。5．2．2算法收敛速度对比IDGA不仅在搜索任务的最优解方面有优势，而且收敛速度也是比较快的。这是因为经过数据依赖关系的处理后的调度策略有效的防止了死锁的产生，且初始种群和交叉变异后的种群的调度策略都是有效的调度策略，相应的搜索范围就变得更小，收敛速度也就更快。下面通过两组实验记录在不同初始条件下，任务完成时间随进化代数增加时的变化情况，参数设置与5．2．1相同。图5．6的初始条件 重庆邮电大学硕士论文第五章实验仿真与结果分析为处理机数量为5，子任务数为100。图5．7的初始条件为处理机数量为20，子任务数量为4000。厘留锓根昧垲noX星莒餐士R昧堪1520406080100120140160180200进化代数图5．6算法收敛速度对比卜4～。一SGA卜～—＼。一卜DGA‘、、IDGA一。、～～＼一‘～～一——k一1r、L————L———————l————一—————l—————————————L—一———————』————一———————L————————————j—————一————二一———————L——————————J一20406080100120140160180200进化代数图5．7算法收敛速度对比在图5．6中，标准遗传算法(SGA)收敛趋势明显，但是在进化到第200代的时候，算法仍然没有完全收敛。而DGA大概在180代时完成收敛，IDGA大概在100代时就完成收敛。说明在任务数量较少的情况下，IDGA较DGA和SGA在收敛速度上有明显的提升，前者的收敛速度明显快于后两者。而在图5．7中，由于任务数量比较多，SGA的收敛速度变得非常缓慢，甚至停滞不前，DGA在200代时出现了收敛的趋势，但未完成收敛，而IDGA约在190代的时候完成了收敛。说明在任务数量较多的情况下，IDGA的收敛速度仍然优于DGA和SGA。IDGA收敛速度更快的原因是因为采用了二维编码的编码方式，染色体的交叉和变异变的更加有效，能使染色体朝最优的方向发展，并且算法采用了自适应的交叉算子和变异算子，使得算法在收敛速度变慢的时候，通过改变交叉和变异概率，让群体产生新的染色体，从而得到更好的最优解，如图5．7中的IDGA曲线在140～160代之间收敛趋势不明显，而在160代之后又出现更好的个体。39O0∞阳∞ 重庆邮电大学硕士论文第五章实验仿真与结果分析5．2．3任务完成所需成本对比为了保证实验的可对比性，本节在相同条件下把IDGA算法与SGA算法和CGA算法(在IDGA算法的基础上进行更改，使其适应度函数只与成本有关)进行对比。DAG图是任意生成的，每个节点可以包含o~4个后继节点；估计运行时间矩阵日阢习的值通过随机方式产生，其范围是1～50；Rcuo')的值同样通过随机的方式产生，其范围值是1～10：种群规模为10，算法的最大进化代数为1000。表5．6算法的主要参数：黛CGA．IDGASGA主要参数＼0【00．6B10．4无“0．7O．7妒O_30．3Pcl0．9忍1．O砭2O．6PmlO．1％O．05Pm20．0011．在只有5个处理机的前提下，改变子任务的数量从10到100,记录任务完成时共消耗的成本。结果如表5．7和图5．8所示。通过表5．6和图5．8可以看出，在任务数量较少的情况下，三个算法的成本开销相差不是很大，但随着任务数量的增长，差别变得越来越明显，此时SGA的成本开销比CGA和IDGA大了许多。这是因为SGA只考虑到了任务的完成时间，忽略了成本约束，导致任务过多分配到成本较高成本的处理机上。CGA的成本开销略小于IDGA的成本开销，这是由于CGA只以成本约束作为选择个体的依据，从而将任务过多的分配给成本较低的处理机，导致任务完成的成本较低但总任务的完成时间较长。而IDGA同时把任务完成时间和成本约束作为个体选择的依据，所以IDGA的任务完成时间是最短的，虽然在成本开销方面略高于CGA，但总体上讲，IDGA仍是一种较优的搜索算法，它不但能从种群中搜索的最优解，同时还有较快的收敛速度，同时成本的开销也比较小。 重庆邮电大学硕士论文第五章实验仿真与结果分析表5．7仿真结果对比处理机个子任务个总任务完成所需成本×103数m数nCGAIDGASGA202．1982．4173．274404．6715．8266．8455607．1797．86910．166809．43310．13714．14610013．22414．39019．57225誉20r一×基15幄藿10根壹505．3本章小结20406080100任务数量图5．8任务完成所需成本对比SGACGAIDGA本章通过使用cloudsim仿真平台，对本文提出的改进遗传算法模型进行了验证，并在任务完成时间、算法收敛速度、任务完成所需成本方面与其他算法进行对比，结果表明IDGA算法比传统算法和其他改进算法具有更强的最优解搜索能力，更快的收敛速度，更低的成本开销。 重庆邮电大学硕士论文第六章总结和展望6．1论文总结第六章总结和展望云计算是一种正处于蓬勃发展的超级计算方式，可以是以数据为中心的数据密集型方式，也可以是以数据处理为中心的计算密集型方式。其在资源管理、数据的存储与管理、任务管理等方面具有自己独特的技术，而在任务管理中的任务调度技术仍是目前研究的热点。目前的任务调度算法有很多，而且调度的目的也是各异的，有的是为了尽量减少任务的完成时间，有的是为了使负载能够均衡，有的是为了使任务运行的成本能够降低。而云计算环境的一个显著特点就是资源是动态异构的，且任务规模是比较庞大的。考虑到这些因素，有学者将具有全局寻优能力的遗传算法引入到云计算环境中进行任务调度，且得到了比较满意的结果。但是遗传算法也存在一些缺陷，容易发生“早熟”收敛且存在“欺骗”问题，对一些约束条件处理的不够恰当等。针对这些问题，本文对任务之间的数据依赖处理、遗传算法的编码方式、适应度函数、交叉和变异算子进行了改进，并在仿真平台上把改进的算法和其它算法进行了比较。具体的工作包含以下几个方面的内容：(1)云计算现有技术的学习，通过广泛阅读书籍和文献资料，了解目前云计算环境中所使用的各种技术，并分析技术的优缺点。(2)对云计算环境下的任务调度技术进行研究，研究云计算和网格计算中的任务调度算法的区别与联系，分析把网格计算中的优秀任务调度算法移植到云计算中的可行性。(3)对云计算环境中的任务调度算法进行改进，研究遗传算法的原理，操作流程，验证遗传算法应用到云计算环境中进行任务调度的可行性，分析遗传算法的优点和缺点，并根据云计算环境的特点，将遗传算法进行改进，是之能对云计算环境下的大量任务进行更加有效的调度。(4)通过仿真平台验证算法的性能，改进后的遗传算法调度的目的是为了得到更短的任务完成时间、更快的任务收敛速度、更低廉的成本开销，通过实验仿真来验证在改进算法和标准算法以及其他改进算法在任务完成时间、任务收敛速度、任务消耗的成本进行比较，最终根据改进算法在效率和成本控制上的优势，得出改进遗传算法是一种有效的任务调度算法。42 重庆邮电大学硕士论文第六章总结和展望6．2展望目前，云计算环境中的任务调度研究还处于起步阶段，未来还有很大的发展空间。虽然本文提出的改进遗传算法综合考虑了任务的完成时间和成本开销两个因素，而且在收敛速度上也有一定的优势，但是实验仿真平台和现实环境还是有一定的差别的。为了简化仿真过程，算法忽略了对一些因素的考虑，且对任务完成估计时间矩阵和处理机的单位时间成本都是通过随机的方式产生的，不能完全模拟实际环境。在未来的工作中，希望能在以下几点进行研究：(1)本文设计的算法目前只考虑了任务完成时间和成本开销的约束，但在实际的使用环境中，任务在迁移的时候受网络延迟的影响也是比较大的，同时任务在调度的时候也必须考虑到负载均衡方面。(2)在云环境下的任务调度中，可能存在任务执行不成功或者处理节点失效的情况。在这种情况下，如何对任务进行再次分配，动态的进行任务的分配与调度是下一步研究的重点。43 重庆邮电大学硕士论文致谢时光荏苒，白驹过隙，转眼间三年的研究生生活即将画上句号。回想起陪伴我走过三年时光的导师、同学和学校的食堂、宿舍、图书馆、教室以及一草一木，不禁让人有一种莫名的悲伤。想着要离开一起生活了三年的人和物，心中总有种种的不舍，也许这三年已经让我养成了许多的习惯。我习惯了学习上有葛君伟教授的事无巨细，每必躬亲的悉心教导。他满腹经纶，学富五车，对我在学习上碰到的问题常常是言之谆谆、教之切切进行解答，让我学会了怎样去发现问题、分析问题、解决问题。葛老师也时刻关心我们的论文写作，常常在百忙之中挤出时间来帮我们审查论文，并提出修改意见。我习惯了生活上有曾跃书记、刘浩然书记、夏淑芳、曾立梅等老师的关心照顾，是她们不分工作和休息时间的为我们解答生活和学习中碰到的各种疑惑，让我的校园生活不在迷茫，让我在研究生生涯中有了清晰的奋斗目标，并向着这个目标一步步靠近。我习惯了日常生活中有实验室同门和师弟师妹们和宿舍兄弟们的陪伴。邓金鑫、杨锋、王燕峰、郑海明、郑剑、苗爱华、赵明等同学不仅经常和我讨论学术问题，而且在业余生活中给我带来了无尽的欢乐，让我研究生三年从未感到过孤独。也正是由于他们，帮我解决了我实验仿真中碰到的各种问题，保证了论文工作能顺利的进行。我习惯了去图书馆去查阅最新的专业书籍。是图书馆工作人员孜孜不倦、处处为学生着想的态度，造就了图书馆现在丰富的存书量，安静温馨的阅读环境。对上述让我养成各种习惯的老师、书记、同学、室友、图书馆工作人员，我要表示最衷心的感谢，感谢你们为我和其他同学们所做的一切，是你们给予了我们人生最美好的回忆，它将是我们今后人生中最宝贵的财富。袁束同生 重庆邮电大学硕士论文攻硕期间从事的科研工作及取得的研究成果◆发表的论文、著作和专利：【1】GEJunwei，YUANYongsheng．Researchofcloudcomputingtaskschedulingalgorithmbasedonimprovedgeneticalgorithm[C]．CSETIS201345 重庆邮电大学硕士论文参考文献[1】刘鹏著．云计算(第二版)【M】．北京：电子工业出版社，2011．[2】姜进磊，孙瑞志，向勇，史美林．云计算[M】．北京：机械工业出版社，2009【3】维基百科[EB／OL]．http：／／zh．wikipedia．org／wiki／％E9％9B％B2％E7％AB％AF％E9％81％8B％E7％AE％97[4】申丽君，杨兰娟，赵华云．计算与网格计算的比较研究[J／OL]．http：／／www．qikan．tom．cn／Article／dnjl／dnjl201117／dnjl20111711．html，2011．07．09．[5】杨小博，欧阳超．云计算与网格计算的特点分析【J】．现代经济信息，2009，24(191)：17-19．[6】BuyyaR，AbramsonD，GiddyJ．Aneconomydrivenresourcemanagementarchitectureforglobalcomputationalpowergrids[C]／／Proceedingsofthe2000InternationalConferenceonParallelandDistributedProcessingTechniquesandApplications(PDPTA2000)．2000：26—29．[7】SelvaraniS，SadhasivamGS．Improvedcost-basedalgorithmfortaskschedulingincloudcomputing[C]／／ComputationalIntelligenceandComputingResearch(ICCIC)，2010IEEEInternationalConferenceon．IEEE，2010：1—5．【8】“L．Anoptimisticdifferentiatedservicejobschedulingsystemforcloudcomputingserviceusersandproviders[C]／／MultimediaandUbiquitousEngineering，2009．MUE’09．ThirdInternationalConferenceon．IEEE，2009：295．299．[9】DiMartinoV，MililottiM．Suboptimalschedulinginagridusinggeneticalgorithms[J]．Parallelcomputing，2004，30(5)：553-565．[10】DiMartinoV，MililottiM．Schedulingina鲥dcomputingenvironmentusinggeneticalgorithms[C]／／Proceedingsofthe16thInternationalParallelandDistributedProcessingSymposium．2002：297．[1l】杜晓丽，蒋昌俊，徐国荣，等．一种基于模糊聚类的网格DAG任务图调度算法川．软件学报，2006，17(11)：2277-2288．[12】林剑柠，吴慧中．一种基于动态决策路径的网格任务调度算法[J】．计算机研究与发展，2008，45(5)，841．847． 重庆邮电大学硕士论文参考文献【13]【14】【15】[16】【17】[18】[19】[20】[21】【22】[23】【24】【25】Mflawsl【iM，JuveG，DeelmanE，eta1．Cost-anddeadline-constrainedprovisioningforscientificworkflowensemblesiniaasclouds[C]／／ProceedingsoftheInternationalConferenceonHighPerformanceComputing，Networking，StorageandAnalysis．IEEEComputerSocietyPress，2012：22．PandeyS，WuL，GuruSM，eta1．Aparticleswamioptimization-basedheuristicforschedulingworkflowapplicationsincloudcomputingenvironments[C]／／AdvancedInformationNetworkingandApplications(AINA)，201024thIEEEIntemationalConferenceon．IEEE,2010：400—407。YuJ，BuyyaR．Ataxonomyofworkflowmanagementsystemsforgridcomputing[J]．JournalofGridComputing，2005，3(3-4)：171—200．Sakellariou＆ZhaoH．AhybridheuristicforDAGschedulingonheterogeneoussystems[C]／／ParallelandDistributedProcessingSymposium，2004．Proceedings．18thInternational．IEEE，2004：111．BermanF，WolskiR，CasanovaH，eta1．AdaptivecomputingOnthegridusingAppLeS[J]．ParallelandDistributedSystems，IEEETransactionson，2003，14(4)：369．382．罗红，慕德俊，邓智群，等．网格计算中任务调度研究综述【J】．计算机应用研究，2005，22(5)：16—19．康立山，谢云，尤矢勇．非数值并行算法：模拟退火算法【M】．北京：科学出版社，1994．刘勇，康立山．非数值并行算法一遗传算法：第2册【M】．北京：科学出版社，1995丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合【J]．计算机研究与发展，2003，40(9)：1351-1356．秦宇强，冯秀芳，余雪丽．网格计算中保证QoS的Agent技术[J】．全国ISNBM学术交流会暨电脑开发与应用创刊20周年庆祝大会论文集，2005，1(18)：13—15．翟东升，李莉。Multi--Agent系统基于优先级的负载均衡任务调度模型术【J】．2007，1(8)：35-39．张涛．基于网格计算经济模型的资源调度算法研究【D】．江南大学，2006．JollIlDarlington，Yi—keGuo，HingWingTo．Structuredparallelprogramming：theorymeetspractice[M】．Computingtomorrow：futureresearchdirectionsincomputersciencebookcontentsPages：49-6547 重鏖塑皇盔堂堡主迨塞．．参考文献【26】DeanJ，GhemawatS．MapReduce：simplifieddataprocessingonlargeclusters[J]．CommunicationsoftheACM，2008，51(1)：107—113．[27】李晓强，寇纪淞，林丹，李书全．遗传算法的基本理论与应用口咽．北京：科学出版社，2002【28】王小平，曹立明．遗传算法．理论、应用与软件实现【M】．西安：西安交通大学出版社，2002[29】陈国良，王煦法，庄镇泉，王东生．遗传算法及其应用【M】．北京：人民邮电出版社，1998[30】玄光男，程润伟．遗传算法与工程优化【M】_匕京：清华大学出版社．2004：25．35【31】Goldberg，D．E．Geneticalgorithmsinsearch，optimizationandmachineleaming[M]．MA：Addison-WesleyPublishingCompany，1998【32】周明，．孙树栋．遗传算法原理及应用[M】北京：国防工业出版社，1999[33】DeJong，K．A．Ananalysisofthebehaviorofaclassofgeneticadaptivesystems(Ph．DDissertation)[J]．UniversityofMichigan，No．76-9381，1973【34】VoseMD．Modelingsimplegeneticalgorithms[J]．EvolutionaryComputation，1995，3(4)：453-472．【35】MichalewiczZ，JanikowCZ，KrawczykJB．Amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computers&Mathematics、ⅣimApplications，1992，23(12)：83—94．[36】WuM，SunXH．Ageneralself-adaptivetaskschedulingsystemfornon-dedicatedheterogeneouscomputing[C】／／ClusterComputing，2003．Proceedings．2003IEEEInternationalConferenceon．IEEE，2003：354—361．【37】张敏，余青松，黄俊，等．基于GAPSO混合算法的网格工作流调度研究[J]．计算机应用与软件，2011，28(4)：236．238．[38】GrossoPB．Computersimulationsofgeneticadaptation：Parallelsubcomponentinteractioninamultilocusmodel[J]．DissertationAbstractsIntemationalPartB：ScienceandEngineering[DISS．ABST．INT．PT．B—SCI．&ENG．】，，1986，46(7)。【39]GordonVS．DataflowParallelisminGeneticAlgorithminParallelProblemSolvingfromNature[J]．ElsevietScience，1992：553—562[40】WangG，GoodmanED，PunchWF．Simultaneousmulti—levelevolution[J]．SubmittedtoEvolutionaryComputation，1996．[41】钟求喜，谢涛，陈火旺．基于遗传算法的任务分配与调度[J】．计算机研究与发展，2000，37(10)：1197—1203 重瘗壑皇盔堂堡主迨塞参考文献—————————————————————————————————————————一=：==：=：[42]李匙韬，王惠南，钱志余．遗传算法的一种新颖编码研究[J】．信息与控制，2006，35(5)：624-629．[43】ZhongQiuxi，XieTao，ChenHuowang．SurvivalstrategyofsolutioninGA[J]．ComputerEngineering&Science，2000，22(1)：14．17[44】BwyaR，manjanR，CalheirosRN．ModelingandsimulationofscalableCloudcomputingenvironmentsandtheCloudSimtoolkit：Challengesandopportunities[C]／／HighPerformanceComputing&Simulation，2009．HPCS’09．InternationalConferenceon．IEEE，2009：1—11．[45】R．N．Callheiro，R．Ranjan，C．A．F．D．Rose，R．Buyya．Cloudsim：Anovelframeworkformodelingandsimulationofcloudcomputinginfrastructuresandservices．ComputingResearchRepository，2009(1)：1-9．[46】HouESH，AnsariN，RenH．Ageneticalgorithmformultiprocessorscheduling[J]．ParallelandDislributedSystems，IEEETransactionson，1994，5(2)：113．120．[47】汪自云，李艳生．基于自适应遗传算法的并行任务分配与调度叨．控制工程，2010，17(005)：636-639．[48】李建锋，彭舰．云计算环境下基于改进遗传算法的任务调度算法阴．计算机应用，2011，31(1)：184—186．49