《基于改进的遗传算法的云计算资源调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
中文图书分类号：TP391密级：公开UDC：004学校代码：10005硕士学位论文MASTERALDISSERTATION论文题目：基于改进的遗传算法的云计算资源调度算法研究论文作者：仇瑞琪学科：计算机科学与技术指导教师：竹翠论文提交日期：2016年6月 UDC：004学校代码：10005中文图书分类号：TP391学号：S201307104密级：公开北京工业大学工学硕士学位论文题目：基于改进的遗传算法的云计算资源调度算法研究英文题目：STUDYOFCLOUDCOMPUTINGRESOURCEMANAGEMENTALGORITHMBASEDONIMPROVEDGENETICALGORITHM论文作者：仇瑞琪学科专业：计算机科学与技术研究方向：计算机系统结构申请学位：工学硕士指导教师：竹翠所在单位：计算机学院答辩日期：2016年6月授予学位单位：北京工业大学 独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：仇瑞琪日期：2016年6月20日关于论文使用授权的说明本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵守此规定)签名：仇瑞琪日期：2016年6月20日导师签名：竹翠日期：2016年6月20日 摘要摘要云计算是一种用户可按需分配及自主配置的新型资源池，这种技术可以为用户提供计算、网络、存储等虚拟资源。作为一种为用户提供商业服务的技术，如何合理调度系统资源是云计算中的关键问题。由于云计算具有异构性、动态性、大规模性等特性，因此应考虑如何对资源进行合理的调度，使用户在短时间内获取资源。同时，在调度中如何尽可能地提高资源利用率、降低能耗，也是一个急需解决的问题。本文实现了基于遗传算法的云计算资源调度算法。遗传算法是一种具有随机化特性的全局优化搜索算法，它借鉴自然界优胜劣汰的进化规律。由于其整体搜索策略和优化搜索方法在工作时不依赖其它辅助知识，遗传算法具有很强的通用性。同时，遗传算法在解决NP问题时有优异的表现，因此它被广泛应用在大规模集群的资源调度问题中。在满足用户需求的基础上，为了节约能耗，最大程度产生最优的经济效益，本文在适应度函数中引入经济效益约束、服务等级协议（ServiceLevelAgreement,SLA）约束和能耗约束，使得调度策略能够让虚拟机在最合适的物理机上进行创建。由于遗传算法的搜索策略，可能会过早进入局部最优从而难以走向全局最优，本文采用Tabu禁忌搜索（TabuSearch,TS）算法对这个问题进行优化。TS算法是一种逐步搜索全局最优化的算法，模拟人类智力发展的过程。在TS算法中，一个高质量的初始解可以大大提高其搜索效率，而遗传算法所获得的解恰好可以为它提供高质量的初始解，因此将遗传算法和TS算法相结合能够很大程度上提高算法性能。本文在遗传算法的计算过程中会对进入早熟阶段进行判断并引入TS算法，将遗传算法的解作为TS算法的初始输入。改进后的算法在跳出局部最优解的同时，通过TS算法产生新的邻域，保证了解的多样性，使得到的结果逐步优化，最终达到全局最优。本文实现了基于CloudSim平台的实验仿真。在CloudSim上将改进后的算法与轮询算法、随机分配算法进行实验结果对比，结果表明所采用的改进的遗传算法能更好的对云计算中的资源进行分配，在经济效益约束、SLA约束、能耗约束等多个约束条件下权衡，达到最优调度的目的。关键字：云计算；资源调度；遗传算法；Tabu禁忌算法；CloudSim-I- AbstractAbstractCloudcomputingisanewtypeofon-demandresourcepoolcanbeconfiguredtoprovideuserswithcomputing,networking,storage,andothervirtualresources.Asatechnologyprovidinguserswithcommercialservice,rationalschedulingsystemresourcesisthekeytocloudcomputing.Becauseofitsheterogeneous,dynamic,massandothercharacteristics,developersshouldconsiderhowtoreasonablyscheduletheresourcesandallowuserstoaccessresourcesinashorttime.Atthesametime,improvingresourceutilizationandreducingenergyconsumptionasmuchaspossiblearealsourgentproblemsneedtobesolved.Inthispaper,aresourceschedulingalgorithmbasedongeneticalgorithmisproposed.GeneticAlgorithm(GA)isaglobaloptimizationsearchalgorithmwitharandomizedcharacteristics,itappearsbasedonthesurvivalofthefittestlawsoftheevolution.Becauseofitsoverallsearchstrategyandoptimizationsearchmethoddoesnotdependonotherauxiliaryknowledgewhileworking,thegeneticalgorithmhasastrongversatility.Inaddition,ithasanexcellentperformanceinsolvingNPproblems,hencemanystudieshaveimplementedgeneticalgorithminsolvingtheprobleminresourceschedulingoflarge-scalecluster.Inordertosaveenergyandtomaximizetheeconomicbenefitsonthebasisofsatisfyingusers’needs,thisthesisintroduceseconomicbenefitsconstraints,SLA(ServiceLevelAgreement)constraintsandenergyconstrainsinthefitnessfunction,sothatthemostsuitableplacementstrategycouldbefoundwhencreatingthevirtualmachineinthephysicalmachine.InordertosolvetheproblemofprematureinGAcausedbyitssearchstrategy,TabuSearchAlgorithm(TS)isappliedinthisthesistoaddressthisissue.TSisagradualglobaloptimizationalgorithmthatsimulatehumanintelligencedevelopingprocess.Inthisalgorithm,agoodinitialsolutioncangreatlyimproveitssearchingefficiency.Luckily,thesolutionobtainedbyGAcanprovidesuchinitialsolution.Asaresult,thecombinationofTSwithgeneticalgorithmcandramaticallyimprovetheperformance.Inthisthesis,wewilldeterminediftheGAentersprematurestageduringthecalculationprocessandintroduceTSalgorithmusinggeneticalgorithmsolutionasitsinitialvalue.Whilejumpingoutoflocaloptimal,TSwillalsoproduceanewneighborhoodtoensuretheunderstandingofdiversity,sothatthegraduallyoptimizedresultswillbeobtained.ThecloudsimulationtoolClousSimisintroducedinthisthesis,basedonwhich-III- 北京工业大学工学硕士学位论文theproposedalgorithmissimulated.Round-Robinalgorithm(RR)andRandomAllocationalgorithm(RA)arealsotestedinthisworktomakeafaircomparisonwithproposedalgorithm.TheresultsshowthattheimprovedgeneticalgorithmcaneffectivelyallocatetheresourcesincloudcomputingandtradeoffwithinmultipleconstraintssuchasSLAconstraintandenergyconstrainttoobtainahighereconomicefficiency.Keywords:CloudComputing,ResourcesScheduling,GeneticAlgorithm,TabuSearchAlgorithm,CloudSim-IV- 目录目录摘要............................................................................................................................IAbstract.......................................................................................................................III第1章绪论................................................................................................................11.1研究背景及意义............................................................................................................11.1.1研究背景...................................................................................................................11.1.2研究意义...................................................................................................................21.2研究现状..........................................................................................................................41.3本文主要工作.................................................................................................................51.4论文组织结构.................................................................................................................7第2章云计算的发展与研究....................................................................................92.1云计算概述.....................................................................................................................92.1.1云计算体系结构.....................................................................................................92.1.2云计算的分类........................................................................................................102.1.3云计算的特点........................................................................................................112.1.4云计算中的关键技术..........................................................................................122.2云计算现有调度算法分析........................................................................................122.2.1以经济利益为目标的调度.................................................................................132.2.2以提高服务质量为目标的调度........................................................................132.2.3以系统性能为目标的调度.................................................................................132.3典型云平台OpenStack简介....................................................................................142.3.1OpenStack架构介绍............................................................................................142.3.2OpenStack中的资源调度..................................................................................152.4本章小结........................................................................................................................17第3章云环境下基于遗传算法的资源调度分析与设计......................................193.1基本遗传算法...............................................................................................................193.1.1编码..........................................................................................................................203.1.2适应度函数............................................................................................................213.1.3遗传算子.................................................................................................................213.1.4停止条件及优缺点..............................................................................................243.2基于遗传算法的资源调度算法设计......................................................................243.2.1编码映射和种群的生成.....................................................................................25-V- 北京工业大学工学硕士学位论文3.2.2适应度函数设计...................................................................................................263.2.3遗传算子设计........................................................................................................283.3算法对应在云环境中建模过程描述......................................................................283.4本章小结........................................................................................................................30第4章改进的遗传算法分析与设计......................................................................314.1Tabu禁忌搜索算法的介绍.......................................................................................314.1.1初始解与适应度函数..........................................................................................324.1.2邻域选择及候选集..............................................................................................324.1.3禁忌表及长度........................................................................................................334.1.4特赦准则.................................................................................................................344.1.5停止条件及优缺点..............................................................................................344.2基于Tabu禁忌搜索的改进遗传算法设计...........................................................344.2.1改进的算法设计方案..........................................................................................344.2.2TS算法设计..........................................................................................................364.3算法建模过程描述......................................................................................................364.4本章小结........................................................................................................................37第5章实验仿真及结果分析..................................................................................395.1仿真平台CloudSim的介绍......................................................................................395.1.1CloudSim框架介绍.............................................................................................395.1.2CloudSim的优势..................................................................................................405.2仿真流程的介绍..........................................................................................................415.3实验结果分析...............................................................................................................435.3.1基于TS算法改进的遗传算法仿真................................................................435.3.2实验结果对比分析..............................................................................................465.4本章小结........................................................................................................................48结论..........................................................................................................................49参考文献................................................................................................................51攻读硕士学位期间获得的科研成果..........................................................................55致谢..........................................................................................................................57-VI- 第1章绪论第1章绪论1.1研究背景及意义目前，云计算作为一种新型的计算资源服务在国内外都掀起了使用和研究热潮。对于云计算中所运用的多种高新技术也成为了研究热点，其中云计算资源调度一直以来都是云计算中的关键技术，如何设计一个合理的云计算资源调度策略具有着十分重要的意义。下面对于云计算资源调度的背景和本文的研究意义进行说明。1.1.1研究背景云计算，是一种以互联网为基础的计算，它为计算机或其他设备提供共享处理资源和数据，是一种按需访问的可配置的计算资源[1]。美国国家标准及技术研究所NIST（NationalInstituteofStandardsandTechnology）对云计算的定义是：云计算是一种模式，实现了无处不在的、方便的、按需的网络访问、共享可配置的计算资源池（如网络、服务器、存储、应用和服务），可快速配置和发布，以最少的管理工作获得与服务供应商的互动[2]。不同于传统的网格计算，云计算拥有着很多优点：高可靠性、通用性、高可伸缩性、按需服务、成本低廉等等，这些优势使云计算处于快速发展的阶段，根据相关研究有很多的云计算供应商年增长率超过了50%[3]。云计算相关的技术一直以来都是学术研究的热点，在市场上提供云服务的供应商也在积极投入经费进行相关研究。例如：2011年微软承诺将投入96亿美元进行云计算的相关研发[4]；IBM在收购云计算供应商方面花费了很多，超过了十亿美元；谷歌发布了数据中心全球化扩张的消息等等。除了这些商业巨头的带动，很多中小型企业也在进行相关的探索。我国的云计算也如火如荼的进行着摸索，很多企业都对云计算领域进行了积极的尝试和探索研究，代表企业主要包括：大型互联网公司如百度、阿里巴巴等；系统集成公司神州数码等；软件公司用友，金蝶等；硬件公司华为、中兴等。除此之外，电信、医疗、教育、交通等各个领域开始使用云计算，以此来提高服务质量，降低成本。云计算正在各行各业拓展相关的业务，为相关的领域带来新的活力。然而机遇和挑战是并存的，云计算这样一种全新的商业计算模式，有这么大-1- 北京工业大学工学硕士学位论文的美好前景下，同时也面临着很多问题和挑战。例如：各个云服务供应商之间尚未提供统一的标准，用户无法在一个云服务平台将应用程序等无缝迁移到另一家云服务平台上；由于硬件故障、断电断网等情况造成的服务可靠性不高；共享数据丢失或泄露等云安全问题；迅速增加的并发任务与有限的云资源之间的调度问题；全球范围内的数据中心越来越多，也越来越大型，随之而来的不容忽视的能耗问题等。其中，系统资源的调度和使用成为一个关键问题，不合理的资源调度制约着云计算的发展。由于资源调度问题而引起的：（1）并发任务较多时，由于资源之间的竞争而引起的提交的任务不能及时完成，等待时间长，用户体验差；（2）数据中心大量的资源浪费引发数据中心能耗大大增加，不节能环保；（3）创造的经济收益由于系统的性能下降而减少。由此可见，资源调度策略已经成为制约云计算发展的一个瓶颈，如何提供一个合理的资源调度策略显得尤其重要。1.1.2研究意义云计算的资源调度与传统的资源调度不同，由于云计算的特性，在云环境下的任务大多数情况下并发产生，并且分布不均匀。在用户群体十分庞大的情况下，不同的应用程序都有动态变化的资源需求，这种动态变化的需求没有可预测性，需要系统动态的满足用户的需求。此外，由于在云计算中运用了虚拟化技术，用户所使用的资源都是虚拟化资源，这种情况下，多个用户共享一台物理机的硬件资源，需要云计算系统提供灵活的分配机制。这些都造成云计算调度问题成为一个难题。在云环境下如何对异构节点上的资源进行合理的调度成为一个迫切需要解决的问题。一个合理的调度考虑的问题是多方面的，不仅要让用户在第一时间解决问题，同时应该注意减少不必要的能耗，提高系统的资源利用率。云计算的资源调度主要侧重于对虚拟资源的调度。在云计算中的虚拟资源分为两级调度：一级调度是将不同的用户任务（L个任务）在不同的约束下映射到不同的虚拟机（N个虚拟机）上；二级调度是将不同的虚拟机（N个虚拟机）映射到不同的物理机（M个物理机）上。不论是一级调度还是二级调度都已经被证实属于NP完全问题[5]。目前关于云计算任务调度问题的研究主要集中在调度策略的执行效率、任务调度的服务质量(QualityofService,QoS)控制、云服务提供商的经济利益等方面。根据调度的目标的不同，可以细分为以下三个方面：（1）基于服务质量的调度：以用户体验为目的的调度，用户提交的请求在-2- 第1章绪论很短的时间得到响应，使用户获得良好的体验，满足用户的要求。（2）基于性能的调度：是侧重于系统性能的调度，通过动态迁移等技术将云计算的任务集中起来，关闭不必要的物理机来提高整个系统的资源使用率；在系统性能中，还要求负载均衡，调度的目的是让系统中多个节点之间的资源负载大致相似，同时在一个节点中各个维度（计算、网络、存储等不同维度）的资源负载也应该是平衡的。（3）基于经济原则的调度：云计算归根到底来说是一种供应商提供给用户的服务，在保证服务质量的同时也要考虑带来的经济效益，通过降低系统能耗等手段来最大化经济利益。为了达到这些目标，专家学者提出了很多解决办法，将各种算法用于调度上以求达到调度目标。应用的简单算法有轮转调度算法、最小链接算法等传统的调度算法。还有将智能算法应用在调度上，如蚁群算法、遗传算法、神经网络等智能算法。基于这些基本的算法还提出了很多的改进算法[6]。在对现有的调度算法进行研究分析之后，发现现有的调度算法存在着很多问题，目前还没有一个完善的算法可以同时达到上述的目标，或者在上述目标中有一个很好的权衡。现有的算法在考虑问题时往往只考虑一方面的因素：例如大部分的调度算法都在研究如何提高云计算系统的资源利用率，但是在提高了系统的资源利用率后，容易导致任务过于集中在某些物理主机上，任务之间资源抢占会造成用户提交的任务响应时间长，破坏了用户的体验，服务质量下降。云计算调度算法的各个因素是相互影响的，因此从单个维度考虑问题会造成一方面的性能的提升，另一方面性能的下降。本文提出的算法期望在多方面的目标下取得一个权衡，使调度策略在各个方面都能有所兼顾，成为一个综合考虑的调度算法。另外一方面，目前在大型企业中所使用的资源调度方法还是原始简单的算法，这样并没有实现云计算资源的合理分配。主要原因是复杂的智能算法尚未应用完全，在解决这样的NP问题时，智能算法往往复杂度高，不能及时响应，而企业的云计算环境需要实时响应。然而智能算法却有很高的准确性，因此，不论是从从学术上还是从现实中，研究智能算法都有很大的意义。现在的研究热点就是如何将智能算法融入到调度算法中，使改进的调度算法更加高效，更加适合云计算环境。本文提出的基于改进的遗传算法的调度策略，在遗传算法的基础上，将经济效益，服务等级协议和能耗等因素都引入适应度函数中，从这三个方面综合考虑调度算法的性能，最大化经济利益的同时，为用户提供良好的体验，保证服务质量，节省能耗。同时还引入了TS算法对遗传算法容易早熟的缺点进行了优化。-3- 北京工业大学工学硕士学位论文1.2研究现状本文考虑的资源调度的侧重点是如何实现虚拟机与物理机的映射关系。对于这样的NP问题来说，问题规模越大，搜索最优解的空间也会急速的增大。然而在云计算中，这样的问题规模无疑来说是非常大的。面对这个难题，众多学者都将目光投向了智能算法，将智能算法融入到资源调度中，来寻求问题解决办法。其中遗传算法作为一种全局寻优能力很强的算法得到了大家的青睐。遗传算法从生物进化的角度来解决问题收敛速度很快。下面的内容是关于遗传算法在解决云计算资源调度问题中的一些研究。文献[7]提出了一种基于有偏的随机密钥遗传算法来解决云计算资源管理问题的解决方法。基于有偏的随机秘钥的遗传算法最大的改进点是改进了交叉算子。在交叉的过程中，父代的两个基因一个来自精英种群，另一个来自普通种群。为了使子代的基因更优，在交叉时精英种群的父代有更大的选择的概率。这种交叉方式是一种精英策略。在这种策略中，每次的迭代算法种群都被分成了更小的精英集合P和一个剩余的普通集合。作者通过改进的遗传算法找到一个合适的优化配置，在满足应用程序的要求的同时，解决多个决策者同时参与时提出的不同的要求（也许这些要求是有冲突的）。文献[8]提出一种改进的遗传算法，基于双适应度和负载均衡。为了达到最短时间内完成调度任务的目标，在算法中使用了两个适应度函数来对个体进行评估。在初始化种群时用贪心算法，并提出了节点之间基于方差的工作负载，为两个适应度函数赋值不同的权重来选择种群中的个体。在算法中为交叉和变异都采用动态的自适应概率。在不同的任务数量的情况下证明了提出的改进算法能很好的平衡整个系统的负载。文献[9]对比了目标不同的调度算法的性能优劣，这些算法有一大部分是基于遗传算法改进得来的。从结论中可以看出基于改进的遗传算法的效果在不同度量方式下都能取得很好的结果。在云计算环境下管理资源时，不同层次的服务都有调度的实现。云计算的体系结构将云平台分为软件即服务（Softwareasaservice,SaaS）、平台即服务（PlatformasaServic,PaaS）、基础设施即服务（InfrastructureasaService,IaaS）。云计算的调度问题也因此被分类为：（1）基于SaaS的调度：在应用程序层的调度主要是安排虚拟资源和物理资源来支持用户应用程序、任务和工作流程等，以提高服务质量和效率。（2）基于PaaS的调度：这层调度是将虚拟资源映射到物理资源上，主要解决负载均衡、节约能耗，如何在成本和效益之间取得最优等问题。（3）基于IaaS的调度：这层关注的是优化数据路由、应用迁移、服务布局-4- 第1章绪论等[10]。由于遗传算法在资源调度方面的优势，在上述的三个层次中都有基于遗传算法的研究。以上研究分别从不同的考虑角度运用了基于遗传算法的不同方法在云计算资源调度上。其中我们看到由于遗传算法的优越性，关于遗传算法在资源调度上的应用和研究得到了众多研究人员的重视。遗传算法在资源调度上有着高于其他算法的准确率，但同时作为集群中的调度需要及时对用户的需求采取相应措施，由于遗传算法的复杂性，如何提高遗传算法的效率显得尤其重要。现有的研究并没有在这一方面提供有效的解决方法。同时云计算任务调度策略在进行调度时有多重的要求，包括经济效益、服务质量、能耗等多方面的要求。这些要求很难同时满足，现有的云计算任务调度策略往往是建立在传统的分布式计算、网格计算的任务调度方法的基础上，加以改进得来的。这样的处理方式很简单，但必定不能达到理想的调度效果。现有的基于遗传算法的研究考虑问题的维度单一。例如有的在调度过程中只考虑了系统的负载均衡问题，但没有从经济效益、系统总能耗等其它方面进行对调度策略的约束，造成的结果是调度算法能很好的达到负载均衡的效果，但是其它方面的考虑欠佳。如何提供一个综合的有效的资源调度方法，目前尚无成熟的做法。本文将从二级调度的角度设计一个考虑更全面的调度算法，使资源调度在多方面的要求下能更高效的进行，实现云计算中对资源的合理调度。1.3本文主要工作一般来说，在云计算中的资源调度是指关于虚拟机资源的调度，其中虚拟机资源的调度可以分为两级：一级调度是指将用户的任务队列分配给虚拟机的过程；二级调度是指将虚拟机如何放置在物理机上的调度过程。目前大多数的研究针对一级调度[11]，在二级调度方面还有很多的不足之处和尚未分析解决的问题。因此在本文中，我们将在重点研究虚拟机的二级调度，即虚拟机与物理机的映射问题，来丰富关于二级调度的研究。图1-1是云计算资源调度中的一级调度和二级调度的示意图。-5- 北京工业大学工学硕士学位论文一级调度二级调度用户任务队列虚拟机资源物理机资源任务1任务2………………任务l图1-1虚拟机资源的两级调度示意图Figure.1-1TheTwo-levelSchedulingDiagramofVirtualMachineResources从图1-1中可以看出从用户提交的任务到最后在物理机上的运行，经过了两次调度。本文将侧重研究二级调度的过程。一个好的调度策略不仅要保证用户的服务质量，还需要系统低能耗高效率，使得云计算作为一种服务能在各方面的权衡中取得最优的经济效益。针对现有的调度算法的不足，本文提出了改进的遗传算法。通过将经济效益约束、SLA约束、能耗约束引入到适应度函数中，设计了基于遗传算法的资源调度算法；同时用Tabu禁忌搜索算法对遗传算法进行改进，解决遗传算法的早熟问题。最后在CloudSim平台上对算法进行仿真，实验中所采用的数据是CloudSim中自带的PlanetLab下来自某大型集群的真实数据。将改进后的算法与应用非常广泛的轮询算法（Round-Robin,RR）、随机分配算法（Random-Allocation,RA）进行比较，验证了算法的优越性。具体工作包括以下四个方面：（1）调研了多种现有的调度策略，对目前用户量很大的OpenStack平台的调度机制进行了分析，提出现有的调度算法的不足。（2）设计合理的适应度函数，在设计时：考虑到经济效益，通过费用条件来进行约束；通过使用SLA约束充分考虑用户的需求和服务质量；通过能耗约束将能耗也作为一个考虑因素。通过这些约束条件，调度策略能够从多个维度对资源进行分配，更加合理，这是本文的创新点一。同时根据具体问题规模设计了适合的操作算子、种群数量、迭代次数等重要参数，使本文遗传算法具有较好的稳定性与执行效率。（3）为了解决遗传算法的早熟问题，引入了Tabu禁忌搜索算法，在保证种群多样性的同时，使改进后的算法能够跳出局部最优解，从而达到全局最优解的目的，这是本文的创新点二。同时也对TS算法的参数进行了设计。（4）在CloudSim平台上对改进前后的算法都进行了仿真，并将改进后的算-6- 第1章绪论法与云计算中常用的其他调度算法进行对比分析，验证了改进后算法的合理性。1.4论文组织结构第一章，介绍云计算资源调度的研究背景和意义，分析现有调度算法的现状及其不足之处，对本文的主要工作进行了简要描述。第二章，对云计算进行较为全面系统的描述，阐述了云计算发展中的关键技术，分别介绍了不同种类的调度算法，对典型云计算平台OpenStack的调度机制进行了分析。第三章，介绍了基本遗传算法的概念和原理，针对云计算具体的资源调度问题完成了对算法的模型建立，从编码、种群生成、适应度函数设计、遗传算子的具体设计等多方面介绍了基于多因素考虑的遗传算法的调度策略。第四章，简要介绍了Tabu禁忌搜索算法，详细介绍将Tabu禁忌搜索算法引入到遗传算法中的设计方案和实现过程，阐述了两个算法的优势互补，实现了改进的遗传算法的流程。第五章，简单介绍了CloudSim云仿真平台，完成了本文提出的算法的仿真实验。通过与其他算法进行对比，得出实验结果，并对其进行分析。结论部分总结本文的主要工作，对下一步工作做出展望。-7- 北京工业大学工学硕士学位论文-8- 第2章云计算的发展与研究第2章云计算的发展与研究本文研究云计算环境下的资源调度问题，首先对云计算的结构和概念进行描述，了解云计算的特点和关键技术。对云计算中现有的调度算法进行分析概述，了解现有算法的发展状况和不足之处对提出新的调度算法有很大帮助。本章中还介绍了当下用户量很大、用户活跃度很高的云平台OpenStack，简单分析了OpenStack的架构，介绍了其中所使用的调度算法。2.1云计算概述2.1.1云计算体系结构云计算使用户能够随时获得虚拟资源，为用户省去购买硬件设施的费用，云计算利用虚拟化技术让这样的按需付费的服务得以实现，除此之外云计算还拥有高效的计算、可靠的存储、安全的访问等优点。因此云计算在当前的技术领域占有着至关重要的作用，也对未来的计算服务起着风向标的指导作用[12]。由于云计算发展的时间尚短，在整个行业内有很多不规范的地方，各企业的云计算供应商给用户提供的解决方案各有特点。在这里整理出一个通用的云计算的结构示意图，如图2-1所示。用户访问层应用层管理层企业应用服务个人应用服务安全管理服务目录服务组合平台层中间件服务数据库服务服务目录管理订阅管理服务使用计量资源层服务质量管理服务器服务网络服务存储服务部署管理服务访问物理资源服务监控图2-1云计算结构示意图Figure.2-1CloudComputingStructureDiagram从图2-1中可以看到云计算的主要结构分为下面五个层次：（1）资源层：在这层主要是物理资源，分别为网络、计算、存储等。这部-9- 北京工业大学工学硕士学位论文分的资源属于基础设备，可以将这部分的物理资源通过虚拟化技术为用户提供虚拟化资源，普通用户并不需要了解这些物理资源是如何配置等复杂的问题。（2）平台层：包括了可扩展的数据库服务，以及可扩展的中间件等服务。平台层在基础设备的基础上可以根据用户的需求来定义自己的应用，对资源层的基础设备进行封装以供用户使用。（3）应用层：包括企业应用以及个人应用，属于软件服务，这层为用户提供软件服务。（4）用户访问层：为用户提供访问接口，通过这些接口，用户可以获得服务目录、订阅管理、服务访问等服务。从服务目录中选择自定义的服务，通过订阅管理来查看已经购买的服务。（5）管理层：对用户提供云服务的管理功能，让用户能够更方便的对其中的功能进行管理。2.1.2云计算的分类云计算可以按照系统结构分为图2-2所示的三种形式。SaaS个人应用企业应用社区应用个人应用PaaS应用服务器业务能力介入业务引擎业务平台IaaS计算资源调度存储资源调度图2-2云计算体系结构分类图Figure.2-2ClassificationofCloudComputingBasedonSystemStructure（1）IaaS层：这层顾名思义为云计算提供最底层的服务。包括云计算所需的所有的硬件设施，通过虚拟技术将这些硬件设施全部虚拟化为一个抽象资源池。通过访问资源池，用户可以获取自己所需的计算、网络、存储等资源，在使用上，这些资源就像用户使用本地资源一样。IaaS的提供商主要有亚马逊的弹性云（Amazon,EC2）[13]和Google的GoogleComputeEngine（GCE）[14]，除此之外还-10- 第2章云计算的发展与研究有开源的云平台如OpenStack，CloudStack，Eucalyptus等。（2）PaaS层：这层是云计算系统的核心层，软件开发环境、存储管理、分布式文件系统等都在这层。开发人员在这层进行在线调试部署、运行在线的项目开发等，大大减少了开发周期。现有的PaaS平台各有特点，根据自己的需求开发人员可以选择不同的PaaS平台[15]。（3）SaaS层：这层是软件层，用户可以直接使用，还能根据不同需求对服务进行定制[16]。这层的应用程序用户可以通过浏览器来进行访问，而不用了解背后复杂的配置和环境。这种软件交付的模式为用户省去了复杂操作，如不用对硬件设施进行安装配置、对网络进行规划和设计等操作，只需要通过付费来获取不同的服务即可。2.1.3云计算的特点云计算与传统的信息技术有很大的差别，很多新型技术的应用使云计算具有其独特的特性，主要有以下四个方面：（1）虚拟化：云计算中给用户提供的资源都是虚拟化资源，这些资源为用户提供计算、网络、存储等服务，用户能够按需购买自己所需要的服务。（2）超大规模及弹性：云计算利用超大规模的集群，可以同时响应并发的用户任务。根据用户任务的数量大小，提供有弹性的动态的调整。这些集群的规模十分庞大，同时也是高弹性的，完全根据用户的需求而定。（3）按需付费：用户使用云计算的一大好处是用户可以随时根据需要更换服务，而不用受到硬件设施的限制，同时这种按需付费的方式也大大降低了用户的成本。（4）高可靠性：云计算为了使服务更加可靠，提供了很多针对断电断网、硬件故障、软件故障等突发情况的处理。云计算有很多数据副本，当一个节点的数据发生丢失等情况时，可以从它的备份中恢复数据；支持热迁移，当一个正在使用的节点有异常情况时提供热迁移的技术，可以在另外的节点上恢复服务。相对于本地计算机，云计算的容错机制能够使系统变得更加安全可靠。从上述的特点中我们可以看出云计算的优越性：价格低廉，用户按需付费即可，拥有更加安全可靠的服务等等。正是由于这些优点，云计算在国内外的发展迅速，同时也在改变着传统的用户使用习惯。-11- 北京工业大学工学硕士学位论文2.1.4云计算中的关键技术在云计算中，运用很多先进的技术，正是由于这些先进技术使云计算拥有众多优点，吸引越来越多用户使用。在参考了相关文献后，总结出云计算中主要的关键技术如下[17]：（1）虚拟化技术：虚拟化技术将硬件资源抽象化为资源池，使用户能够随时访问这些资源，这一技术为云计算的实现提供了最基本的支持。虚拟化技术被广泛应用在云计算中，对于管理者来说也能更高效更灵活的对资源进行管理，这种技术越来越成熟，已经获得了很好的效果[18]。（2）数据管理技术：在云计算中，由于数据量庞大，对数据读写要求较高，因此如何高速的进行数据的读取和存取也成为一个重要的问题[19]。由于云计算的分布式的特点，导致比普通的存储需要更高的速度来获取数据。除了存储数据，如何对数据进行更新、如何进行数据备份，这些都需要完整的解决方案。（3）资源管理技术：云计算中的资源都被抽象化为虚拟资源，对虚拟资源的管理是云计算中最核心的部分。由于云计算按需付费的性质，需要对虚拟资源进行实时监控和计费。由于系统庞大，需要强大的监控和计费系统。同时，资源的管理是并发的，需要系统及时处理任务，及时获取响应。这些都对虚拟资源管理有很高的要求。（4）大数据处理：在对大数据处理方面，普通的服务器已经不能满足互联网日益增大的数据处理的需求，必须有并行计算的模型来处理海量数据。目前主要使用的是Map-Reduce编程模型[20]，它可以将一个任务分为很多的子任务，将这些子任务分别发送到很多不同的节点上进行处理，然后统计返回的数据结果，对结果进行汇总。这样的方法采用并行处理的方式，大大的提高了效率，使总任务能够在更短的时间内完成。2.2云计算现有调度算法分析在1.2小节中介绍了基于遗传算法的调度策略的研究现状，除此之外在云计算中还有很多基于其他算法的调度，出于不同的调度目的，这些策略的侧重点也有所不同。研究这些不同的调度算法，对本文提出新的调度算法有很大的帮助，下面介绍了现有的基于不同目的的调度算法，分析现有的调度算法的不足，为解决问题提供更多思路，同时对云计算中的调度有更全面更透彻的理解。-12- 第2章云计算的发展与研究2.2.1以经济利益为目标的调度由于云计算按需付费的特点，在调度策略中一个重要的考虑因素就是经济效益。以经济效益为目标的调度，利用市场经济学原理的供应需求与价格的关系来反映云计算中资源的优化分配。当目前的系统中资源负载较大、供不应求的情况出现时，价格略微上调；当系统中资源负载很小、供过于求时，价格下降。这样不仅要保证云服务供应商的效益，也要保证用户在有限的支出获得最有价值的服务，然而同时满足两方面的需求是传统的资源提供方法所不能达到的。云计算系统的供应商和用户两个方面必须是互赢的前提下，才能使云计算整个行业有可持续发展的前景和未来[21]。文献[22]中Buyya等设计了基于SLA的资源分配器，提出了基于经济效益的云计算的调度方法。通过资源分配器协商云服务提供商和用户之间的关系，以获取更高的经济利益。2.2.2以提高服务质量为目标的调度为用户提供高质量的服务是云计算的目标，因此服务质量也是调度要考虑的重要问题之一。在不同的调度任务中，服务质量有不同的要求约束。例如密集计算型的任务希望云计算能够提供更强的计算处理能力，文件读取频繁的任务希望能够有更多的内存来加快速度。总之各种不同的任务都希望获得较好的QoS保障[23]。更进一步来说，服务质量[24]已经成为衡量调度算法一个非常重要的因素，有很多学者都在针对服务质量这一目标对调度算法进行优化改进，使用户获得更好的使用体验[25]。Oprescu等人[26]提出了基于任务调度器的预算约束方法，该调度器根据预算情况对调度进行约束，这种约束也是基于服务质量的，以此来完成不同任务的调度请求；Netto等[27]根据云计算中任务的截止时间提出了不同的服务质量目标，针对这些目标对任务进行调度；此外Tao等[28]在文中提到基于工作流的调度，多个工作流是有内部依赖关系的，该策略能够很好的处理这些依赖关系。2.2.3以系统性能为目标的调度在系统性能方面的调度又可以细化分为：提高系统的资源利用率，将尽可能多的任务分配给尽可能少的物理资源，以提高系统的使用率，从而达到节省能耗的目的；考虑负载均衡，分配任务时考虑各个节点的负载情况，使整体的负载达到一个相对均衡的状态。-13- 北京工业大学工学硕士学位论文文献[29]提供了一种能耗管理办法VirtualPower，该文章认为服务质量因为多个虚拟机共享服务器上的计算资源而受到影响，提出的方法整合了电源管理机制，支持独立运行的虚拟机，将虚拟机重新分配，将一些资源使用率低的闲置节点转为节能模式，从而将系统总体的能耗降低。在不同的虚拟化平台，或者在同一个虚拟化平台的不同虚拟机之间，都能合理的协调好能耗控制请求，达到整体优化的效果。当系统的负载很均衡时，云计算系统的总体性能都会很高，资源使用率也会变高；反之则系统的性能和资源使用率都会变低[30]。因此，如何使系统内的负载达到均衡的状态也成为调度策略的一个目标之一。文献[31]提出了随机WS(Work-Stealing)算法，在AmazonEC2/S3的云环境下证实了该算法的有效性。不仅能达到动态负载均衡的作用，还解决了带宽在高峰期无法调整的瓶颈问题。为了实行云计算协同性能更高效的目标，还有很多算法被应用在调度中。这些调度都以性能为中心，算法有Min-min算法、Max-Min算法等简单原始的调度算法及其相对应的改进算法；还有以遗传算法、蚁群算法等代表的智能算法。目前在云计算调度策略中整合的智能算法有很多，由于智能算法在搜索解空间的优越性，越来越多的学者将目光投入到智能算法领域中。鉴于遗传算法的优势，本文决定基于遗传算法及其优化来解决云计算虚拟资源的二级调度，提供一个合理的从虚拟机到物理机的映射方案。2.3典型云平台OpenStack简介2.3.1OpenStack架构介绍OpenStack是由Rackspace和美国国家航空航天局（NASA）共同开发的云计算平台，这是一个开源软件项目，企业和云供应商可以安装运行自己的云计算系统。与所有对云计算感兴趣的研究人员、开发人员和企业等一起建立一个开源社区，OpenStack的目标就是能够更简单的部署云计算，提供大规模可扩展具有丰富功能的平台。由于OpenStack的优异性能[32]，许多大型企业都采用它来进行云平台的搭建，如IBM、惠普等多个企业及组织。现在，OpenStack的社区已经有超过150家公司和2600人合作，这个规模还在不断增大。企业可以利用它搭建私有云，将企业内部的资源进行整合为各部门提供服务[33]。OpenStack包含5个最主要的构成部分：计算服务(Nova)，对象存储服务(Swift)，镜像管理服务(Glance)，认证服务(Keystone)以及UI服务(Horizon)。它的服务关系图如图2-3所示。-14- 第2章云计算的发展与研究Web界面(Horizon)管理界面计算服务镜像镜像服务镜像存储服务(Nova)获取(Glance)存储(Swift)身份认证认证服务(Keystone)图2-3OpenStack服务关系图Figure.2-3OpenStackServiceRelationshipDiagram其中：（1）Nova是计算组织控制器，这部分处理关于运行虚拟机、管理网络、控制访问等部分，控制着活动在生命周期的实例的所有操作。它包括六个组成部分Nova-API,消息队列（MessageQueue），Nova-Compute,Nova-Network,Nova-Volume和Nova-Scheduler.（2）Swift是OpenStack的存储基础设施，它是一个可扩展的对象存储系统。包括一个代理服务器，目标服务器，一个帐号服务器，和一个容器服务器。这是一个长期的存储系统，可以检索、利用和更新静态数据，主要功能和特点是能够安全存储大规模的对象，拥有数据冗余和容错机制。（3）Glance为虚拟机镜像进行管理。（4）Horizon提供了一个基于浏览器的用户界面，能更容易的管理云服务。（5）Keystone为一个云的身份提供了一个通用的认证和授权。2.3.2OpenStack中的资源调度在了解基本框架后，来研究它的资源调度实现。结合本文主要侧重的二级调度的具体问题，研究OpenStack中如何将虚拟机分配给主机的过程。目前OpenStack的调度功能由模块Nova实现，其中nova-scheduler具体完成由虚拟机到主机的调度任务，实现的调度算法有以下几种：（1）随机算法：随机选择目前可选择的主机；（2）可用域算法：主机的选择范围有一个指定的选择范围，虚拟机在这个范围内进行随机选择；-15- 北京工业大学工学硕士学位论文（3）简单算法：通过负载均衡器获得所有主机的负载信息，选择负载最小的主机创建虚拟机。Nova-Scheduler提供简单的调度策略供用户选择，具体的调度算法如图2-4所示。主机1主机1主机2主机2主机3主机3主机3按权值主机4筛选主机4排序主机5主机5主机5主机6主机6主机7主机7图2-4主机筛选排序过程Figure.2-4HostFilteringSortingProcess（1）启动调度器：当接到创建虚拟机的请求时，启动调度器，列出当前可选择的主机列表；（2）主机过滤：过滤一部分不符合要求的主机，具体的过滤方式由配置文件决定，还可以通过重写方法来添加自定义的过滤器（具体方法是：继承BaseHostFilter类，重写host_passes方法）；（3）按权值排序：通过对权值的排序来选择最终的主机。权值的计算由过滤的主机的调用代价函数计算得到。我们可以看出Scheduler模块所提供的调度策略很简单，但我们可以通过自定义来扩展调度策略，这对于开发人员来说有很大的好处[34]。在了解了资源调度策略之后，我们发现了资源调度存在的问题：Nova-scheduler决定部署虚拟机管理程序并没有考虑到运营商的业务需求[35]；在筛选调度的同时，这种过于简单的调度策略很容易造成硬件资源利用不均衡，这样会使集群的能耗增多；且各物理机时间段使用不平衡，简单的调度算法无法解决长时间的使用过程中如何高效调度的问题。由此OpenStack使用的资源调度方并没有实现云计算资源的合理分配。-16- 第2章云计算的发展与研究2.4本章小结本章分别对云计算的概念和体系结构、云计算的分类和特点、云计算所使用的关键技术进行了介绍。从服务质量、系统性能、经济利益三个角度来分析现有的云计算调度算法。本章还重点介绍了典型的云计算平台OpenStack，介绍了它的基本架构和服务关系，对其中所使用的调度方法进行了分析。-17- 北京工业大学工学硕士学位论文-18- 第3章云环境下基于遗传算法的资源调度分析与设计第3章云环境下基于遗传算法的资源调度分析与设计本章介绍了基本的遗传算法的相关概念和算法流程，设计了在云计算环境下基于遗传算法的资源调度算法，其中将经济效益约束、SLA约束、能耗约束三方面约束引入到适应度函数设计中，使调度算法能够更综合的考虑问题，在调度的各个要求中取得权衡，获得更加合理适用的调度方案。3.1基本遗传算法遗传算法是一种全局优化的搜索算法，1969年由美国Michigan大学的Holland教授提出[36]，后经DeJong、Goldberg等人归纳总结，形成一种新的全局优化搜索算法。它借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，并从中进行提取、简化、抽象，得出了遗传算法。遗传算法的基本思想是模拟自然界遗传机制和生物进化论，引用了随机统计理论而形成的。遗传算法的主要思想是：从最初的种群开始计算每个个体的适应度，选择优秀的基因进行遗传操作，用更优秀的基因代替上一代的种群，通过这样的过程使问题的解逐步改进。它基于进化论的原理，经过多位学者的研究，具有坚实的生物学基础[37]。在遗传算中用一个个体代表问题的一种解决方案，一个个体由若干基因组成，这样的个体叫做一条染色体，多条染色体构成一个种群。为了模拟自然界的杂交、基因突变等现象，在遗传算法中执行选择、交叉、变异等操作。接着利用适应度函数给每个个体一个数值评价，根据这样的数值进行优胜劣汰的过程，也就是将适应度高的个体留下来，将适应度低的个体淘汰掉。选择好个体之后，进行“杂交”的过程，用这些旧的个体产生新的个体，由新的个体生成新的种群。经过上述的过程，子代种群都是父代种群进行筛选之后的结果，朝着越来越好的方向进化，也就是说问题的求解也朝着最优解的方向靠拢。因此，遗传算法的求解过程就是整个种群向最优解靠拢的过程。遗传算法发展迅速，目前已经在许多领域得到了广泛的应用，如函数优化、人工智能、模式识别、图像处理、决策分析、资源调度、数据挖掘等等。将简单的遗传算法抽象为计算模型，算法的流程示意图如图3-1所示。-19- 北京工业大学工学硕士学位论文将求解问题进行编码初始化种群根据适应度函数计算每个个体的适应度是否满足终止条件是否选择输出最优解交叉变异图3-1遗传算法流程图Figure.3-1TheFlowchartofGeneticAlgorithm从图3-1中可以看到，算法流程的核心内容为：编码、适应度函数评估、终止条件、遗传算子等。下面我们对遗传算法的具体流程进行详细的介绍。3.1.1编码首先对求解问题进行编码，合适的编码可以提高算法的效率，而不合适的编码则会很大程度上影响算法的性能。常见的编码方法有如下几种：（1）二进制编码：用二进制的方式表示种群中的个体，这是最简单且最常用的办法。二进制编码的优点是易于实现。但是当应用于高精度数值问题优化时，产生的字符串过长，占用内存；还有一个缺点是二进制编码不能直接反映问题，不便于理解。（2）格雷码编码：格雷码编码是基于二进制编码的一种改进方式，在表示连续的两个整数时，只有一个基因位上的编码不同，剩下的位置完全相同。这样的设计可以解决二进制编码在表示连续函数时误差较大的缺点。假设有一个二进制编码为𝑋=𝑥𝑚𝑥𝑚−1…𝑥2𝑥1，其对应的格雷码的计算过程如公式（3-1）所示。𝑦𝑚=𝑥𝑚,𝑌={（3-1）𝑦𝑖=𝑥𝑖+1⊕𝑥𝑖𝑖=𝑚−1,𝑚−2,…,2,1表格3-1表示了针对十进制的0-9的10个整数，分别用二进制编码与格雷-20- 第3章云环境下基于遗传算法的资源调度分析与设计码编码进行编码的结果。表3-1二进制编码和格雷码编码表Table.3-1TheCodingTableofBinaryCodeandGrayCode十进制0123456789二进制编码0000000100100011010001010110011110001001格雷码编码0000000100110010011001110101010011001101格雷码跟二进制编码一样，具有易于实现的优点，而且弥补了二进制编码在连续函数方面的缺点。（3）浮点数（实数）编码：用实数表示基因，也就是用真实的数字表示基因，因此也被叫做真实值编码。这样的编码方式更有利于求解连续问题。（4）符号编码：用具有含义的非数值型符号表示个体基因。当求解的问题具有很强的专业领域性时，用非数值编码可以很好的表示对问题的求解。只要选取合适的符号集对个体进行编码，就能完成从基因到问题解映射的唯一性。若遗传算法中能够利用辅助知识进行编码时，符号编码具有很大的优势。除了上面介绍的编码方式之外，还有其他的编码方式。如何对要解决的问题进行编码是遗传算法最开始就要面对的问题，选取合适的编码方式可以很大的提高算法的效率。3.1.2适应度函数适应度函数在遗传算法中的作用是评估个体是否优秀，遗传算法最大的优势就是不需要额外的辅助信息，只需要用适应度函数对个体进行评估。就像自然法则一样，适者生存，当适应度函数越大，个体越容易进入下一轮的计算。因此要对适应度函数进行周密的设计，当适应度函数设计不合理时，算法无法对种群中的个体进行正确的评估，整个种群向全局最优解靠近的速度会非常慢，算法的收敛速度变慢，性能变差，还有可能导致最终无法获取有效解，得不到理想的结果。适应度函数还有可能导致算法最终获得的是局部最优解。适应函数的设计是否合理，直接影响到遗传算法的收敛速度，也会影响到是否能够获得最优解。因此，我们需要针对不同的问题设计最合适的适应度函数。在设计时需要注意：适应度函数的值应该是大于零的；适应度函数变化的方向应该和整个解空间向最优解靠近的方向保持一致。3.1.3遗传算子在计算出种群里全部个体的适应度值之后，基于算出的值对个体进行选择、交叉、变异三个操作。这三个操作也是遗传算法中最基本的遗传操作，遗传操作-21- 北京工业大学工学硕士学位论文的作用是模拟自然界的杂交、变异的过程。在遗传算法中，经过了遗传操作可以产生一个新的子代种群，子代种群的整体性能会比父代种群的整体性能更高，在迭代中，让种群慢慢靠近最优解，从而完成优化搜索。下面具体描述这三个遗传算子。（1）选择算子：从种群中选择优异的个体进行下一步操作的过程，选择算子保证种群往越来越好的方向发展。一般来说，不论选择算子使用哪种方法都希望适应度大的个体优先被选中。常用的选择方法有：1）适应值比例选择法：个体的适应度值与被选择的概率成正比，每个个体被选中的概率可以通过下面的公式（3-2）计算得出：𝐹𝑖𝑃𝑖=𝑀(𝑖=1,2,…,𝑀)（3-2）∑𝑖=1𝐹𝑖其中𝑃𝑖表示第i个个体被选择的概率，𝐹𝑖为第i个个体的适应度大小，种群的大小为M。这种方法简单易操作，是目前遗传算法中最常被使用的选择算法。很好的体现了适者生存的选择过程，但是误差较大，即使适应度很高的个体也有可能不被选中。被选中的个体进行下面的交叉操作。根据这种方法衍生而来的轮盘赌的方式更加合理，轮盘赌的做法是每次生成一个位于[0,1]区间的随机数e，通过计算各个个体的被选择的概率，计算累积概率。则第i个个体的累积概率由公式（3-3）计算得出：𝐴𝑃=∑𝑖𝑃(𝑖=1,2,…,𝑀)（3-3）𝑖𝑖=1𝑖如公式（3-3）所示，𝐴𝑃i表示第i个个体的累积概率的大小。此时将𝐴𝑃i与刚刚生成的随机数e进行比较，若𝐴𝑃𝑖−1<𝑒<𝐴𝑃𝑖，则选中第i个个体。这样的做法每次选中个体时都根据随机数来定，增加了选择的不确定性，更加合理，是上面介绍的简单的适应值比例选择法很好的替代优化算法。2）排序选择法：事前定义一张概率分配表，将种群中的个体按照适应度值大小进行排序，将排好序的个体按照设计好的概率分配表依次进行概率分配。这样的方法需要设计好概率分配表，概率分配表需要根据实际问题来设计。由于事前对问题并不能做出准确的估计，这样的做法存在着很大的误差。这个方法依赖于对具体问题的分析而得出的概率分配表，然而在现实中并没有完善的方法能够生成一个合理的概率分配表。3）最优复制法：我们希望每次迭代的种群中产生的最优的个体都能进入下一代的计算，但是选择、交叉、变异等操作往往会破坏掉最优个体。因此在最优复制法中将一些适应度值高的个体直接保存下来加入子代的种群中，避免其它操作破坏这些优秀的解。选择算子的方法还有很多。为了提高遗传算法的性能，还有很多其他有效的-22- 第3章云环境下基于遗传算法的资源调度分析与设计策略来进行选择操作。比如基于预测的选择策略[38]，还有基于免疫机制的选择策略[39]等等。随着对遗传算法的深入研究，选择算子的算法会越来越丰富，我们应该根据具体问题具体分析，得到最优的选择算子。（2）交叉算子：交叉算子的目的是将父代的个体进行一定规则的部分交叉来得到新的子代的个体，这样的的规则就是交叉算子。经过交叉得到的新个体有可能同时包含了父代两个个体的优点，更有利于得到最优解。对于交叉规则的选择，有很多种方法。常用的方法分为以下几种：1）单点交叉：也被称为简单交叉。在个体中选择一个位置作为交叉点，这个位置可以是固定的一个位置，也可以随机产生。交叉点将一个个体染色体分为前后两部分，交换两个个体的部分基因即可。下图为单点交叉的示意图：单点交叉的位置交叉后图3-2单点交叉示意图Figure.3-2TheSchematicDiagramSingle-pointCrossover如图3-2所示，经过单点交叉之后，一个子代个体含有两个父代个体的部分基因。2）多点交叉：当交叉点的个数大于一个时，就是多点交叉。多个交叉点将个体分为几个部分，用一定的规则交换两个个体的这些部分，生成新的个体。3）均匀交叉：新的个体通过设定好的屏蔽字来得到相应的继承规则。除此之外，还有很多别的交叉方法，如洗牌交叉、缩小代理交叉等。总体来说，交叉算子的选择使个体中的基因序列发生较大的变化，应当在实验中根据个体的长度、问题的复杂度等多个因素综合决定交叉点的多少以及交叉的长度。（3）变异算子：变异是指按照变异概率Pm随机改变父代个体中的一些基因来产生新的个体的过程，通常情况下Pm的数值是非常小的。在上面提到的选择算子、交叉算子的主要目的是完成搜索过程，而变异算子的主要目的是保证种群的多样性，在进行选择、交叉的过程时有可能造成某些基因的丢失，而变异操作是为了避免由于缺失某些基因而造成算法失效。变异概率不依赖其它因素，通常的选择范围是[0.001,0.1]。变异操作的基本过程是：在变异的过程中，对于每个个体来说都产生一个[0,1]-23- 北京工业大学工学硕士学位论文之间的随机数random，如果random小于变异概率Pm就执行变异过程，如果大于变异概率Pm就不执行变异操作。变异概率Pm的大小一般是取经验值，但是这个值是比较小的，正如自然界的基因突变的概率也是非常小的，要控制在[0.001,0.1]的范围内。通常所采用的变异操作比较简单的，随机产生一个新的基因位代替变异位的值，可以选择进行变异的基因位的个数。也有其他变异方式：如交换某些基因序列的位置；通过打乱原来的基因顺序来进行变异等操作。这些变异的形式要根据具体问题具体分析。3.1.4停止条件及优缺点算法的停止条件是：当遗传算法产生的个体状态基本稳定时或者遗传的代数超过给定的最大遗传代数时就退出运算。遗传算法最大的特点就是利用生物进化的思想，具有如下优点[40]：（1）智能性和自适应性：遗传算法在问题处理中不需要依赖辅助信息，搜索的过程只需要利用适应度函数计算个体的适应度值即可。这样的智能性和自适应性不仅适合解决各个领域的问题，而且特别适用解决复杂的非结构化问题。（2）易于并行化：遗传算法中的很多计算量都是不相关的，可以利用并行化的优点减少计算时间，提高算法的效率。（3）通用性：算法基本思想简单，通用性很强，适合很多问题的求解，且实现步骤都很清晰规范，便于具体使用。当然除了这些优点，遗传算法也有自身的缺点：（1）容易早熟：这是遗传算法最大的缺点，遗传算法的操作算子对于产生新的解空间是有限的，导致搜索的范围有局限性，容易陷入局部最优。（2）计算量大：在遗传算法的每次迭代中都需要计算所有个体的适应度值，如果问题复杂，个体的编码长，迭代次数多时，计算时间会变长。（3）稳定性差：在算法中很多过程都是基于随机类算法得到下一步的结果，结果的稳定性不能保障。3.2基于遗传算法的资源调度算法设计在了解了基本的遗传算法的相关概念和算法的使用方法之后，我们对云环境下的资源调度进行分析，设计基于遗传算法的资源调度策略，具体的设计思路如下。-24- 第3章云环境下基于遗传算法的资源调度分析与设计3.2.1编码映射和种群的生成解决资源调度问题的第一步是将虚拟机和物理机的映射关系进行编码，这里我们选择的是实数编码，而不是二进制编码。这样的编码简单有效，更有助于我们对资源调度的理解。要将n个虚拟机（用Vm表示）放置在m个主机上（用Host表示），编码可以得到这样的一个个体基因：{k0,k1,…kn-1}。其中这个个体的长度为虚拟机的个数n，k0,k1,…kn-1的取值范围是[0,m-1]。用一个更具体的例子来说明，当Vm的数量为10，Host的数量为5时，那么编码将产生一个长度为10的序列。假设产生的序列为{2,3,1,4,0,0,1,2,2,3}，代表的放置策略如3-3图所示：虚拟机虚拟机虚拟机虚拟机虚拟机虚拟机虚拟机虚拟机虚拟机虚拟机0123456789主机0主机1主机2主机3主机4图3-3虚拟机与主机映射示意图Figure.3-3TheSchematicDiagramofVirtualMachine-HostMappingVm从编号0-9分别按照序列{2,3,1,4,0,0,1,2,2,3}的顺序创建在对应的Host上，直到最后一台Vm创建完成。解决了编码问题后可以初始化生成种群，种群大小的设定要根据具体的问题规模来定。种群太小，搜索空间太小，容易造成多样性不足而陷入局部最优解；种群太大，消耗大量的计算资源。在初始化生成种群时，传统的的方式是随机生成。但是随机产生带来的问题就是在某些情况下很多虚拟机被分配到同一台物理机上，这样会造成大量的时间等待，且极容易产生创建不成功的情况。过多的虚拟机被放置在同一台主机上，会引起资源之间的抢占，整个系统的资源出现负载不均衡的现象，导致系统性能下降。在初始化种群时就避免这样的情况发生，使得生成的种群的质量没有非常差的情况出现。因此，在本文的具体实现中，对随机生成的过程进行了约束，设定了一个主机出现次数最大的阈值W。当随机生成的一条染色体其中的一个相同Host编号出现的次数超过了W，也就是说，有超过W个虚拟机都被放置在这台主机上。这种情况下是生成不成功的，会重新生成一条新的染色体，直到满足种群大小。-25- 北京工业大学工学硕士学位论文3.2.2适应度函数设计如何设计一个好的适应度函数是影响算法优劣的一个非常重要的因素。通过对现有的调度算法的充分分析之后，本文决定将三个考虑因素纳入适应度函数的计算中，分别是经济效益约束、SLA约束、能耗约束。这三个因素是衡量调度算法性能优劣的重要组成部分。但目前的调度算法都是将其中单独的一个因素进行剖析，很少从三个方面同时对调度算法进行改进。这样的设计考虑问题更加全面，从多个角度对调度算法进行衡量才能更真实的反映调度算法的好坏。这是本文的创新点之一，具体的设计方法如下：（1）经济效益约束：在现实任务中，用户为了达到不同的目的，会采用不同规格的虚拟机。为了模拟真实的云计算中虚拟机创建的过程，在实验中将虚拟机的类型分为四个类型，也就是说用户每次提交的虚拟机的大小可以选择不同规格，相对应的在云计算中对于不同规格的虚拟机的收费标准也是不同的。下面的表3-2介绍了设计的不同规格的虚拟机参数和收费标准。表3-2虚拟机类型设计表Table.3-2VirtualMachineDesignTypeVm_TypeMIPSRAMBWPRIZE1250051210000022200010241000001.53100010241000000.445005121000000.2从表3-2中，可以看到一共设计了四种规格的虚拟机，抽象出虚拟机的三方面来说明虚拟机的性能。其中每秒百万条指令（MillionInstructionsPerSecond,MIPS）是描述计算处理性能的一个指标，用它来表示虚拟机的计算处理能力；随机存取存储器（RandomAccessMemory，RAM）是虚拟机的内存，这里使用的单位是MB；带宽（BandWidth,BW）用来作为总线和内存性能的指标；最后的PRIZE是指选择不同类型的虚拟机所对应的不同的价格。在模拟的过程中获取所要创建的虚拟机的列表，根据判断虚拟机的类型得到相对应的价格标准，计算所有的虚拟机创建完成到最后销毁一共所用的时间，用时间乘以单位时间的价格得到一台虚拟机的费用，最后将所有的虚拟机的费用加起来作为总费用。计算方法如公式（3-4）所示：𝐼𝑛𝑐𝑜𝑚𝑒=∑𝑛𝑉𝑚∗𝑇𝑖𝑚𝑒（3-4）𝑡𝑜𝑡𝑎𝑙𝑖=0𝑇𝑝𝑦𝑒𝑃𝑅𝐼𝑍𝐸（2）SLA约束：云计算是供应商提供给用户的一种服务，如何能够尽快的满足用户任务的响应，提高用户体验是资源调度中必须考虑的一个重要因素。SLA是服务供应商和用户之间关于服务质量的协议。为了确保用户的服务-26- 第3章云环境下基于遗传算法的资源调度分析与设计质量，在SLA中对服务要求、责任等进行明确的说明规范。当云计算系统提供的服务不满足需求时，就进行SLA违例处理[22]。违例处理是为了保障用户的用户体验而提出的处理办法，当不满足用户的需求时，对提供服务的供应商做出一些惩罚措施以确保市场的公平合理性。本文在设计适应度函数中引入了关于SLA违例情况的处理。用𝑆𝐿𝐴𝑡𝑜𝑡𝑎𝑙𝑃𝑒𝑛𝑎𝑙来表示当调度过程中出现了违反SLA条例时的处理，以此衡量虚拟机的可用性的百分比，𝑆𝐿𝐴𝑡𝑜𝑡𝑎𝑙𝑃𝑒𝑛𝑎𝑙可以通过公式（3-5）得出。𝑀𝐼𝑃𝑆𝑡𝑜𝑡𝑎𝑙𝐴𝑙𝑙𝑜𝑐𝑎𝑡𝑒𝑑−𝑀𝐼𝑃𝑆𝑡𝑜𝑡𝑎𝑙𝑀𝑖𝑠𝑠𝑒𝑑𝑆𝐿𝐴𝑡𝑜𝑡𝑎𝑙𝑃𝑒𝑛𝑎𝑙=1−（3-5）𝑀𝐼𝑃𝑆𝑡𝑜𝑡𝑎𝑙𝐴𝑙𝑙𝑜𝑐𝑎𝑡𝑒𝑑其中的𝑀𝐼𝑃𝑆𝑡𝑜𝑡𝑎𝑙𝐴𝑙𝑙𝑜𝑐𝑎𝑡𝑒𝑑表示所有已经分配的MIPS的值，𝑀𝐼𝑃𝑆𝑡𝑜𝑡𝑎𝑙𝑀𝑖𝑠𝑠𝑒𝑑表示未及时分配给Vm的MIPS的值。𝑆𝐿𝐴𝑡𝑜𝑡𝑎𝑙𝑃𝑒𝑛𝑎𝑙是在调度中如果违反SLA约束的代价花费，在调度策略中，如果Vm随时访问所需的所有MIPS时Host都可以百分之百提供，那么就不存在违反SLA的情况；如果虚拟机所期待得到的MIPS小于给它分配的，就是违反了SLA约束。（3）能耗约束：能耗是云计算调度中另外一个必须考虑的重要因素。随着大型集群的规模越来越大，个数也越来越多，能耗问题已经逐渐成为制约云计算发展的瓶颈[41]。因此在设计适应度函数时，系统能耗也是一个必须的考虑因素。用𝐸𝑛𝑒𝑟𝑔𝑦𝑡𝑜𝑡𝑎𝑙来表示系统总共的能耗，系统总能耗计算公式如（3-6）所示。𝐸𝑛𝑒𝑟𝑔𝑦=∑𝑚−1𝐻𝑜𝑠𝑡（3-6）𝑡𝑜𝑡𝑎𝑙𝑖=0𝑖其中Hosti表示第i台主机所消耗的能耗，从创建的Host的列表里获取到所有已经创建的Host，并将它们的能耗加起来得到系统总的能耗。。综合以上三个方面的描述，将其纳入设计适应度的考虑因素，最终设计的适应度如公式（3-7）所示。𝐹𝑖𝑡𝑛𝑒𝑠𝑠=𝑤0∗𝐼𝑛𝑐𝑜𝑚𝑒𝑡𝑜𝑡𝑎𝑙−𝑤1∗𝐸𝑛𝑒𝑟𝑔𝑦𝑡𝑜𝑡𝑎𝑙−𝑤2∗𝑆𝐿𝐴𝑡𝑜𝑡𝑎𝑙𝑃𝑒𝑛𝑎𝑙（3-7）其中，Fitness是适应度函数，w0,w1,w2为各项的权重。𝐼𝑛𝑐𝑜𝑚𝑒𝑡𝑜𝑡𝑎𝑙代表着根据不同的云任务计算得到不同的收入；𝐸𝑛𝑒𝑟𝑔𝑦𝑡𝑜𝑡𝑎𝑙代表着完成调度任务所消耗的全部能耗；𝑆𝐿𝐴𝑡𝑜𝑡𝑎𝑙𝑃𝑒𝑛𝑎𝑙是在调度中如果违反SLA约束的代价花费。这样的适应度函数使得虚拟机在物理机上创建时能够找到最合适的放置策略，当一个个体的适应度值高时说明了当前的这个调度方案在经济利益、用户服务质量、能耗三个方面取得了最优的组合。使用这个适应度函数后，基于多因素考虑的遗传算法的调度不仅能够满足用户需求，提供很好的用户体验，还能节约能耗，最大程度产生最优的经济效益。-27- 北京工业大学工学硕士学位论文3.2.3遗传算子设计基于对云计算中资源调度的分析和研究，本文对遗传算子的设计如下：（1）选择算子：在选择算子方面，根据设计好的适应度函数计算种群中所有的个体的适应度值，将适应度值最高的10%的个体复制替代适应度值最低的10%的个体，然后根据轮盘赌的方法进行选择。这样的方法可以使种群中的个体都比较优异，加大了优秀的个体被选中的概率，剔除掉不好的个体，保证选择的个体不会出现很差的情况。（2）交叉算子：在交叉上选择单点交叉的方法，但每次都随机选择一个交叉点的位置。由于每次都随机选择交叉点的位置，加大了算法的随机性，种群也因此加大了多样性，有利于全局寻优。将选择的两个个体的前后两部分进行单点交叉。（3）变异算子：在变异方面，设定了变异概率，每次随机产生一个数，当随机数小于变异概率时进行变异。变异所采用的方法是单点变异，每次随机选择一个变异点，将选择的变异点变化为随机产生的主机Host编号。根据个体的长短，也就是虚拟机的个数可以选择变异点的个数。特殊情况下，若个体过长，可以多选择几个变异点进行变异。3.3算法对应在云环境中建模过程描述在设计完成编码、适应度函数、遗传算子之后，将遗传算法在云计算环境下进行建模，示意图如图3-4所示。当收到一个调度任务时，需要将n个虚拟机分配到m个主机。首先对问题进行编码，然后开始初始化种群，随机产生染色体，并对随机过程进行约束。其中主机Host的资源可包括计算、内存、网络带宽集合，可以抽象描述为公式（3-8），其中𝐻𝑜𝑠𝑡𝑟𝑒𝑠为Host的总资源，𝑀𝐼𝑃𝑆𝑟𝑒𝑠代表Host中的计算资源，𝑅𝑎𝑚𝑟𝑒𝑠代表内存资源，𝐵𝑤𝑟𝑒𝑠代表网络带宽资源。Host总的资源如公式（3-8）所示。𝐻𝑜𝑠𝑡𝑟𝑒𝑠=[𝐶𝑃𝑈𝑟𝑒𝑠,𝑅𝑎𝑚𝑟𝑒𝑠,𝐵𝑤𝑟𝑒𝑠]（3-8）一个Host所占用的资源是分配在上面的所有Vm所占用的资源的总和，𝑉𝑚𝑟𝑒𝑠表示当前虚拟机的资源，用户选择一共创建多少台虚拟机，如公式（3-9）所示。𝑗𝐻𝑜𝑠𝑡𝑟𝑒𝑠𝑓𝑜𝑟𝑛𝑜𝑤=∑𝑖=1𝑉𝑚𝑟𝑒𝑠（3-9）其中𝐻𝑜𝑠𝑡𝑟𝑒𝑠𝑓𝑜𝑟𝑛𝑜𝑤表示目前在Host上创建的[1，j]的所有Vm所占用的资-28- 第3章云环境下基于遗传算法的资源调度分析与设计源的总和。开始Vm_0···Vm_k···Vm_n-1初始化种群Host_0···Host_k···Host_m-1计算种群中个体的适应度值Vm_0···Vm_k···Vm_n-1得到分配是是否达到条件结果Host_0···Host_k···Host_m-1否选择、交叉、变异得到子代种群图3-4基于遗传算法的云计算资源调度示意图Figure.3-4TheSchematicDiagramofCloudComputingResourceSchedulingBasedonGeneticAlgorithm根据公式（3-9），我们了解到，Host的总资源在随机产生的染色体策略中，当在一个Host上即将创建Vm时，从Host总的资源中减去Vm所需的资源，当其中的任意一项小于零时，说明此染色体中当前的Host资源已被全部占用，则这条染色体一定不是最优解，我们将它从种群中剔除。这样的约束思想可以在实际操作中简化成每次出现的Host相同编号不大于一个阈值，这个阈值可以根据具体的问题规模进行修改，一般情况下根据经验值定为3。约束操作可以保障整个种群的质量，避免Vm之间的资源竞争而导致的云服务性能下降或Vm创建不成功。然后根据设计好的适应度函数计算种群中每个个体的适应度值。根据适应度函数我们可以总结出：创建的Vm的类型和个数决定着所获得的收益；服务质量越高，用户的体验越好，说明违反SLA的次数越少，适应度函数值越高；能耗越少，系统更低碳环保，资源使用率越高，适应度函数值越高。从这些角度来衡量种群中个体的质量是全面而合理的。得到种群中的个体适应度值后，根据设计好的遗传算子进行遗传操作，得到子代种群。接下来对子代种群进行终止条件的判断，如果满足终止条件就退出算法，得到对应的解，进行解码操作，将资源调度的结果反馈给云系统进行资源分-29- 北京工业大学工学硕士学位论文配；如果不满足终止条件则继续进行算法的迭代。3.4本章小结本章在分析介绍基本的遗传算法的基础上，重点介绍了本文所设计的基于遗传算法的云计算调度算法，算法包括初始化种群、设计适应度函数、设计遗传算子的过程，并描述了设计的遗传算法在云环境下的建模过程。其中的适应度函数的设计综合了三个方面的考虑因素，分别为经济效益、SLA、能耗，这样设计可以使调度算法在各种调度要求中取得权衡，得到最优的调度方案，使得虚拟机在物理机上创建时能够找到最合适的放置策略，这也是本文的创新点之一。-30- 第4章改进的遗传算法分析与设计第4章改进的遗传算法分析与设计在设计了云环境下的资源调度算法之后，由于遗传算法具有早熟的缺点，为了解决遗传算法这个缺点，决定使用Tabu禁忌搜索算法对其进行优化。Tabu禁忌搜索算法具有很强的全局搜索能力，而且能够帮助遗传算法跳出局部最优解的困境。本章将介绍基本的Tabu禁忌搜索算法，并提出如何使用它对遗传算法进行优化的方案。将改进后的算法在云计算环境中的建模过程进行描述。4.1Tabu禁忌搜索算法的介绍禁忌搜索（TabuSearch，TS），又称Tabu搜索，最早由美国科罗拉多大学系统科学家Glove教授正式提出[42]。TS算法是一种用于解决组合优化问题的启发式算法，在解决NP问题时的成功引起了学术界广泛的关注，并且在很多领域都取得了成功[43]。TS算法最大的特点是使用禁忌表。禁忌表中的信息表示着下一次搜索将不再考虑这些点，这样的设计可以避免重复搜索，在提高搜索效率的同时，有利于算法跳出局部最优点。在设定禁忌准则的同时，算法里也包含了藐视准则，藐视准则就是赦免一些被禁忌的对象，这样的对象往往能够提高整个解范围的多样性。由于TS算法这样的优越性，已经被运用到很多领域来解决问题，目前主要应用的领域有神经网络、组合优化、深度学习等多个领域。TS算法的主要流程如图4-1所示。在用TS算法时，首先要对参数进行设定，并给出问题的一个初始解。在最开始时，禁忌表是被置为空的。然后进行终止条件判断：若满足终止条件则退出；若不满足终止条件则接着进行运算。根据当前解得到当前解的邻域，这些邻域的解被称为候选解，根据适应度函数进行计算，得到候选解中的最优解。接下来对当前最优解进行判断：如果满足藐视条件就直接将其赋值为下一代的当前解并加入禁忌表中，如果已经在禁忌表中就更新其在禁忌表中的位置；如果不满足藐视条件就判断是否在禁忌表中。如果不在禁忌表中则将其加入禁忌表，并赋值给下一轮的当前解；如果已经在禁忌表中则进行新一轮的条件判断。-31- 北京工业大学工学硕士学位论文设置参数，生成初始解X，置空禁忌表判断是否满足收敛条件是否用当前解的邻域产生候选解在候选解中用适应度函数否得到最优解判断得到最优的候选解CC是否满足将C赋值为当前解是藐视准则X=C是否将C加入禁忌表中C不在禁忌表中图4-1禁忌算法流程图Figure.4-1TheFlowchartofTabuAlgorithmflowchart4.1.1初始解与适应度函数在TS算法中，一个好的初始解对其效率有至关重要的作用。当拥有一个好的初始解时，算法搜索的邻域都是质量较高的候选解，能以高效的速度完成对最优解的搜索；而一个差的初始解则会造成收敛速度的下降。由此可见，TS算法不同于其他算法，它对初始解的要求很高，依赖性很高。在一般的求解过程中，都会想办法生成一个高质量的初始解再利用TS算法来进行下面的步骤。有很多研究都对初始解的选择进行了分析。总结来说就是好的初始解可以提高TS的效率。与第三章的遗传算法类似，TS算法中也有适应度函数，也是根据适应度函数对解空间中的各个解进行评价，来决定进一步的选择。4.1.2邻域选择及候选集邻域是TS算法中的一个重要的概念。邻域基于当前解产生与当前解类似的解，产生的规则有很多不同的做法。如何选择合适的邻域对TS算法来说至关重-32- 第4章改进的遗传算法分析与设计要。邻域如何选择是基于具体问题而定的。例如在传统的旅行商问题（TravellingSalesmanProblem，TSP）中，这是一个典型的NP问题，在所有的城市中寻求最优路径。TS算法在解决这种组合优化问题中，对于邻域的选择常用的方法是互换（互换两个城市之间的位置）、逆序（选取一部分的城市顺序取逆）等操作，这与遗传算法的变异操作类似。不同的操作将影响邻域内解的质量，下一代进行搜索的解的质量对整个搜索效率来说起着关键作用，但目前的研究尚未指出其中的联系，只能对于具体问题分析得到最合适的邻域选择操作。当邻域确定之后，在当前状态的邻域中根据适应度函数的衡量，来择优选取，这时所选择的问题解构成候选集。当候选集的个数过少时，TS算法很容易早熟收敛；当候选集的个数过多时，计算量增大，算法的运行时间增长。应该根据具体数据大小和问题的特征来合理选取候选集的大小。4.1.3禁忌表及长度在TS算法中，最重要最核心的概念就是禁忌表（Tabu表）。Tabu表的数据结构是队列，也就是说最先进来Tabu表的元素最先离开。为了避免重复搜索已经搜索过的解，将当代产生的最优解放入Tabu表中，在下次搜索的时候避开这些解。这种做法能够提高算法的效率。Tabu表中的元素被称为禁忌对象。Tabu表可以使用两种记忆方式：明晰记忆，属性记忆。明晰记忆是指存入Tabu表中的是一个完整的解；而属性记忆放入Tabu表中的则是基于当前解的变化。这两个概念一个是完整存储，一个是增量储存。其中属性记忆会节省很多的时间，在进行运算时也会提高效率，但容易造成未知搜索区域的禁止，这样就减少了解空间的范围，明晰记忆则不会有这个缺点。但相比较而言，明晰记忆则有存储空间大、计算时间长的缺点。禁忌长度是指禁忌表的长度。禁忌长度与禁忌对象的生命周期有关。由于Tabu表的长度是固定不变的，每当禁忌表中多加入一个禁忌对象时，位于Tabu表队列最前端的对象就会被移出表外，为新加入的对象腾出空间。禁忌长度越长，禁忌对象生命周期越长。禁忌长度的选择也对算法有着不可忽视的影响，当禁忌长度过短代表着被禁忌的对象很快就出了禁忌范围，很容易造成搜索的循环；当禁忌长度过长又会造成搜索时间变长，搜索效率下降。因此，我们要根据具体问题确定具体的禁忌长度。-33- 北京工业大学工学硕士学位论文4.1.4特赦准则特赦准则，也称为藐视准则[44]。当Tabu表中的对象满足特赦准则时，就将它从Tabu表中释放出来。当求解过程中出现比目前已知的最优解更优的解时，可以将它作为特赦对象从禁忌表中解禁出来，这样的过程有利于获得全局化搜索，使搜索过程更优效率。4.1.5停止条件及优缺点与遗传算法相似，TS算法也有停止条件。TS算法的停止条件是：当算法产生的个体的适应度值达到要求时或者迭代次数超过了给定的最大迭代次数时就退出运算。禁忌搜索最重要的思想是Tabu表的思想，通过将已经搜索过的局部最优解放入禁忌表中，避开对这些解的搜索，跳出局部最优的陷阱，提高了算法的效率，这是TS算法最大的优点。TS算法在解决NP问题有杰出的效率。然而在设计TS算法时，需要先对使用的参数进行确定，TS算法中应用的参数很多，针对不同领域的具体问题需要设定不同的参数以提高算法的效率。目前来看，没有完善的步骤来确定这些参数[45]，我们只能针对不同情况进行具体分析。其中，禁忌算法的性能对初始解的依赖较强，因此在解决问题的开始如何获得一个有效的初始解是一个难点。参数设计的合理性对TS算法而言至关重要，TS算法最大的缺点就是对参数的依赖。4.2基于Tabu禁忌搜索的改进遗传算法设计在介绍了基础的TS算法后，我们将TS算法引入到云计算环境下。在已经实现了的遗传算法的基础上，研究如何利用TS算法的优点对第三章设计的遗传算法进行改进。4.2.1改进的算法设计方案遗传算法和TS算法各有所长，在第三章里已经介绍了遗传算法的优缺点。TS算法除了搜索高效等优点以外，还可以弥补遗传算法容易早熟这个缺陷的地方，那就是通过使用禁忌表来跳出局部极值。这样的策略可以使算法不容易陷入局部最优的状态，使最终获得的解为全局最优解。为了提高设计的基于遗传算法的云计算资源调度算法的效率，并改善算法的不足，在求解问题的时候，考虑引入TS算法。对于两个算法取长补短，通过结-34- 第4章改进的遗传算法分析与设计合两个算法各自的优点达到最好的性能。对于如何将两个算法结合起来的问题进行对相关研究的分析，普通的遗传禁忌混合算法是在遗传算法的交叉和变异操作中引入禁忌算法。通过这种方法产生新的禁忌交叉算子和新的禁忌变异算子[46]，利用改变遗传算法的这两个遗传算子来改善问题。然而这样的做法有着一个致命的缺点：调用过多时，搜索效率很低[47]。在云计算的资源调度里，调度非常频繁，当调用过多，搜索效率不高时，会为资源调度带来困难，系统无法及时的为任务分配资源，所以不采用这种做法。本文采用的优化遗传算法的做法是，判断如果当前的遗传算法进入早熟时，将得到的解作为TS算法的初始解，继续计算。由于TS算法非常依赖一个高质量的初始解，当初始解的质量高时，TS算法的效率也会很高，同时由于TS高效的全局搜索效率，能够达到快速搜索到全局最优解的目的。利用遗传算法的计算结果为TS算法提供这样一个高质量的初始解。在如何判断进入早熟阶段时，可以利用适应度的样本方差判断遗传算法是否早熟。利用方差作为判断的依据是：方差是刻画随机变量的取值对于其数学期望的离散程度的样本。方差不仅仅表示样本偏离均值的程度，更是揭示了样本内部彼此波动的程度，也可以理解为方差代表了样本彼此波动的期望[48]，样本方差越小数据的波动就越小。当遗传算法趋向早熟时，种群趋于平稳状态，此时个体之间的差异变小，因此种群的所有个体的适应度变化变小，适应度值样本方差将会变小，因此可以使用适应度方差变小的程度判断是否达到早熟。可以根据公式（4-1）对早熟情况进行判断。𝜎𝑚<<𝑛（4-1）𝜎0其中σ代表着当前种群的适应度值的方差；𝜎0为上一代种群的适应度值的方差；m,n分别是两个非常接近1的数值。我们能够得出当两代的适应度方差的比值非常接近1时，证明种群的适应度值变化越来越小，可以判定算法进入到了早熟阶段。对于m,n的取值，如果n-m的值过于大，算法还在收敛的过程中，最终的解的取值还没有达到局部或全局最优；如果n-m的值过小，那么说明算法已经进入早熟阶段，增加了迭代的次数，降低了算法的效率。经过大量的实验，发现m=0.98,n=1.02时的效果最好。同时在实验中发现，进入早熟状态的迭代次数基本都在迭代30次左右。为了算法的高效率，我们判断早熟的条件可以简化为遗传算法迭代30次。而不用每次都计算种群中个体的适应度值的方差。-35- 北京工业大学工学硕士学位论文当发生早熟状况时，通过TS算法使个体跳出所在区域的局部最优解，更容易得到全局最优解。因此，本文考虑将遗传算法和Tabu禁忌搜索算法结合在一起以解决云计算中资源调度的问题，从而获取更高的效率，为解决问题提供更有效的解决办法。对优化方案确定后，开始设计在云计算中的TS算法。4.2.2TS算法设计TS算法的难点是对其中的众多参数进行合理的设计和设定。只要参数合理，TS算法拥有非常出色的效率。但是在设置参数时，目前并没有确定参数的一般的方法[42]，都是需要根据具体问题具体分析的。在设计TS算法时，对于初始解和适应度函数要参考第三章所设计的遗传算法。将上一章中的遗传算法所得到的解作为TS算法的初始解。遗传算法所得到的解往往可能是局部最优解，对于TS来说是一个质量很高的初始解。由于TS算法和遗传算法最终要达到的目的一样，所以可以采用一致的适应度函数。这样才能使两个算法的结果朝着同一个目标进行优化趋近。对于TS算法的邻域选择：在本文选择的邻域策略是将一条当前解的一部分固定不变，另外一部分随机生成，产生一系列候选解。在候选集的大小和禁忌表的长度方面，需要根据问题规模的大小而定，在多次实验中获取结果进行分析，最终确定这些参数的具体值。这些参数目前的做法大多数也是经验值。特赦准则的阈值是多次实验后得到最优解的平均值的90%。也就是说，当前解的适应度大小达到最优解平均值的90%时就满足特赦准则。这样就设计好了TS算法中的各个参数，将设计好的TS算法按照4.2.1中的策略引入到遗传算法，得到改进的基于遗传算法的云计算资源调度算法。4.3算法建模过程描述本文在进行了大量的实验之后，提出了新的解决办法，即将遗传算法在进行一定次数的迭代之后的解作为TS算法的初始解。在迭代一定次数之后，遗传算法可能趋向早熟。这时不再进行遗传算法的计算，将所求的解作为TS算法的初始解。此时得到的解的质量是较高的，可能是局部最优解。这样可以保证TS算法初始解的优越性，极大的提高了搜索效率。改进的算法主要工作流程如图4-2所示。-36- 第4章改进的遗传算法分析与设计输出最优解编码是将其设为为初始解，初始化种群置空禁忌表根据适应度函数计算每个个体的适应度判断是否满足收敛条件是否满足终止条件是否否否用当前解的邻域产生候选解选择在候选解中用适应度函数得到最优解判断得到最优的候选解C交叉将C赋值为C是否满足藐视准则是当前解变异X=C否是将C加入禁C不在禁忌表中忌表中图4-2改进的遗传算法流程图Figure.4-2TheFlowchartofImprovedGeneticAlgorithm从图中我们可以清楚的了解到整个算法在云计算资源调度中的建模过程。当收到一个调度任务时，需要将n个虚拟机分配给m个主机。首先是进行遗传算法的计算，得到一个当前最优解，在将此临时的最优解作为TS算法的初始解，帮助遗传算法跳出局部最优解，在局部最优解的邻域进行进一步搜索，从而达到全局最优的目的。随后进行TS算法的计算，得到最终的资源调度的最优结果，利用此结果对虚拟机进行分配。4.4本章小结本章主要介绍了基于TS算法改进的遗传算法。首先介绍了基本TS算法的概念、主要参数和流程，并且分析了遗传算法和TS算法的各自的优越点，然后将TS算法引入遗传算法中。对如何将TS算法引入进行了分析，决定将遗传算法进入早熟阶段时将其得到的解作为TS算法的初始解，对于遗传算法进入早熟阶段的时机进行了分析判断。这样的做法不仅解决了遗传算法的早熟问题，并且给了TS算法一个高质量的初始解，极大的提高了算法的效率。最后结合云计算-37- 北京工业大学工学硕士学位论文资源调度的背景，对TS算法的具体设计进行分析解释，并对改进后的算法进行了建模过程的描述。其中，用TS算法对遗传算法的优化，能够提高算法效率，改善遗传算法早熟的缺点，对于寻找到的调度方案来说降低了局部最优的可能性，更容易找到全局最优解，这也是本文的创新点之一。-38- 第5章实验仿真及结果分析第5章实验仿真及结果分析5.1仿真平台CloudSim的介绍5.1.1CloudSim框架介绍CloudSim是一款云计算仿真软件，由澳大利亚墨尔本大学的网格实验室推出[49]。它是一个模拟大规模云计算数据中心的开源框架，目前在云资源调度的研究中使用非常广泛。CloudSim充分的体现了云计算虚拟化的特征，可以为用户提供虚拟化的云的建模和仿真功能。Cloudsim的层次结构图如图5-1所示。用户代码仿真规格云场景用户请求…应用配置调度策略用户或数据中心代理CloudSim用户接口任务单元云场景结构虚拟机任务单元执行云场景服务云服务虚拟机分配CPU分配内存分配虚拟空间分配带宽分配云资源事件处理传感器云协调器数据中心网络网络拓扑消息延迟计算CloudSim核心模拟引擎图5-1CloudSim层次结构图Figure.5-1CloudSimHierarchyDiagram从图5-1中可以看到CloudSim的主要结构：（1）用户代码层：这一层用户可以写自己的调度策略；还可以对云计算中的资源进行参数的设置，例如定义云计算数据中心的规模、定义虚拟机的参数、定义主机的参数等。（2）CloudSim层：这层实现了云计算数据中心的建模和仿真。在这层定义-39- 北京工业大学工学硕士学位论文了用户接口结构、虚拟机服务、云服务、云资源，同时为用户代码层提供了接口管理。这层实现了虚拟机到物理机按照定义规则进行分配的过程。（3）核心模拟引擎层：保证了CloudSim的硬件环境，确保仿真正常进行。这层是由GridSim与SimJava组成的。CloudSim的仿真流程是数据中心、云信息服务（CloudInformationService，CIS）、数据中心代理之间消息传递的过程。它们之间进行信息交互的示意图如图5-2所示。DatacenterDatacenterCISBroker注册查询可用的数据中心获取数据中心特征创建虚拟机任务调度任务完成销毁虚拟机图5-2CloudSim消息交互图Figure.5-2CloudSimMessageInteractionDiagrams从图5-2中我们可以看到：从创建数据中心到任务完成，再到销毁虚拟机的过程中，数据中心、云信息服务、数据中心代理三者之间是进行信息交互的过程。当Datacenter向CIS发送一个注册请求后，DatacenterBroker向CIS进行查询，CIS返回一个可用的数据中心。然后DatacenterBorker和Datecenter之间进行虚拟机的创建、任务调度、任务完成、销毁虚拟机等操作。5.1.2CloudSim的优势在实验阶段使用CloudSim是因为它有很多突出的功能：（1）能够模拟大型的云基础设施，而且在模拟中有很多资源调度必须具有的功能类，在定义调度算法时，可以进行对相关功能的重写和修改，完成自己的调度算法。（2）提供了虚拟引擎，本文主要研究的是二级调度，也就是从虚拟机到物理机的调度，CloudSim能够根据自定义的调度策略对虚拟机的创建主机进行选-40- 第5章实验仿真及结果分析择和创建，完成调度。（3）在进行调度时能够获取到数据中心里各个主机的能耗状态，让本文中考虑的能耗约束条件得到满足。CloudSim为云计算资源管理的研究带来了很多好处，除了上面叙述的优势之外，使用CloudSim的原因还有：在云计算模式下运行任务有复杂的配置、组成和部署要求。大规模的云计算虚拟机创建的环境不容易看出结果，真实环境难创建，时间长，可重复的方式难以实现。我们必须利用这样的平台进行仿真实验。5.2仿真流程的介绍在CloudSim中将自定义的改进后的遗传算法进行仿真，下面对主要的仿真流程进行介绍：（1）初始化：首先最开始的步骤是进行初始化，初始化的参数需要对用户数量、日期、追踪标志等进行定义，代码如下：CloudSim.init(num_user,calendar,trace_flag)；（2）创建数据中心：在仿真实验中需要获取到数据中心的能耗，对于具有能耗感知的数据中心在创建时应该选择的数据中心的类型是PowerDatacenter，因此创建的数据中心是Power类型，创建数据中心需要将所使用的调度策略和Host列表作为参数，代码如下：PowerDatacenterdatacenter=createDatacenter("Datacenter",hosts,policy);（3）创建数据中心代理：创建代理Broker，在这里代理的类型和Datacenter的类型一样，也需要是Power类型的，代码如下：DatacenterBrokerbroker=newPowerDatacenterBroker("Broker");（4）创建虚拟机：创建Vm时需要制定Vm中的各种设置，本文在实验中采用了一个帮助类Helper，在Helper中定义好Vm和Host的全部参数，创建Vm的代码如下：List
此文档下载收益归作者所有
