毕业论文-基于改进蚁群算法的云计算任务调度研究

PAGE学科分类号110黑龙江科技大学本科学生毕业论文学号院（系）指导教师***20PAGEVI摘要随着网络时代的到来，摩尔定律早已被打破，云计算日益渗入人们的生活，如何合理解决云计算资源调度是我们首要的问题，考虑如何将资源的利用变成最大化，是负载均衡的程度最高。本文通过对蚁群算法的原理进行分析，得知蚁群算法在旅行商问题、调度问题等方面取得一系列较好的实验结果，由于蚁群算法在解决实际问题中出险不足，结合实际情况对蚁群算法进行改进，采用蚁群和粒子群算法的融合算法，首先随机生成大量的可行解，对信息素初始化，然后利用粒子群算法进行交叉、变异操作，从而得到最优解。通过蚁群算法、遗传算法、蚁群改进算法实验相比较，在相同的环境下，基于蚁群算法的粒子群改进算法融合算法的资源调度策略比单一算法的调度策略所用时间短，效果更显著。 最后通过测试环境平台实验，我们发现在生产环境下，蚁群改进算法的调度策略优于单一算法，为探索新的云计算资源调度策略提供了可能性。关键词蚁群算法粒子群算法融合算法最优解AbstractWiththenadventoftheeraofnetwork,Moorelawhasbeenbroken,cloudcomputingisbecomingmoreandmoreintopeoplelife,howtoreasonablysolvetheproblemofcloudcomputingresourcesschedulingisourprimary,considerhowtomaximizetheutilizationofresourcesinto,isthehighestdegreeofloadbalancing.Inthisarticle,throughanalysisoftheprincipleofantcolonyalgorithm,learnedthatantcolonyalgorithminthetravelingsalesmanproblem,suchasschedulingproblemhasmadeaseriesofgoodresults,becauseoftheantcolonyalgorithminsolvingthepracticalproblemsinthecompensationofshortage,combinedwiththeactualsituationtoimprovetheantcolonyalgorthm,theantcolonyandparticleswarmoptinizationalgorithm,thefirstrandomlygeneraedalotoffeasiblesolution,thepheromoneinitialization,thenuseparticleswarmoptimizationalgorithmforcrossoverandmutationoperation,andtheoptimalsolutionisobtained.Throughtheantcolonyalgorithm,geneticalgorithmandantcolonyalgorithm,incomparisonwiththeexperimentinthesameenvironment,theparticleswarmalgorithmbasedonantcolonyalgortjm-fusionalgorthmofschedulingstartegyusedtime,theeffectismoreprominent.Finallythroughthetestenviromentplatformexperiment,wefoundthatinaproductionenvironment,theschedulingstrategyofantcolonyalgorithmisbetterthanofsinglealgorithm,andtoexplorethenewcloudcomputingresourceschedulingstrategyprovidesapossibility.KeywordsantcolonyalgorithmparticleswarmalgorithmfusionalgorithmoptimalsolutionPAGEIII目录18008摘要 I27007Abstract II13572第1章绪论 1157371.1论文背景和意义 113441.1.1引言 1255721.1.2背景和意义 1229721.2国内外研究状况 2265841.3本文的主要工作 316333第2章云计算介绍和任务调度现状 4321332.1云计算的现状 4200382.1.1国内主流的云计算平台 4282092.1.2云计算任务调度算法的研究现状 520702.2云计算架构和任务调度基本问题 5319752.2.1云计算技术体系结构 622122.2.2云计算编程模式之——hadoop 6209472.2.2云计算任务调度基本问题 928739第3章改进的蚁群算法--算法融合 11106023.1经典蚁群算法 11310433.1.1经典蚁群算法简介 11117133.1.2经典蚁群算法原理介绍 1187923.1.3经典蚁群算法数学模型 12214533.1.4经典蚁群算法优点 143723.1.5经典蚁群算法缺点 1490493.2粒子群算法 15108303.2.1粒子群算法的介绍 15184203.2.2粒子群算法的数学模型 15118083.2.2粒子群算法的优缺点 17312833.3算法改进--两种算法的融合 1798323.3.1改进算法的思想 1730493.3.2改进算法的融合 1827423.3.2改进算法在求解TSP问题中的有效性验证 1930540第4章利用改进算法解决云计算任务调度问题 22209324.1任务调度的实现和参数设置 2241304.1.1基于改进算法任务调度的实现 2282974.1.2改进算法的参数设置 23121324.2改进算法在任务调度中的应用 2574734.2.1云计算平台环境介绍 25135704.2.2调度算法的生效 25301054.2.3用于测试的应用程序介绍 26226924.2.4测试实验 2619008结论 3018849致谢 318590参考文献 3224452附录 34Contents26864摘要 I23207Abstract II10493第1章Introduction 152421.1Thethesisbackgroundandsignificance 1193861.1.1Introduction 13221.1.2backgroundandsignificance 1136921.2researchstatusathomeandabroad 298011.3Thisarticlemainwork 318343第2章computingisintroducedandthestatusquoofthetaskscheduling 4296152.1presentsituationofcloudcomputing 4155802.1.1Themainstreamofcloudcomputingplatform 4165042.1.2Cloudcomputingtaskscheduling 58812.2Cloudcomputingarchitectureandthetaskschedulingproblem 5203672.2.1Cloudcomputingarchitecture 6288712.2.2Cloudcomputingprogrammingmode——hadoop 6282432.2.2Cloudcomputingtaskschedulingproblems 915425第3章Antcolonyalgorithm--Fusionalgorithm 11503.1Classicalantcolonyalgorithm 11263333.1.1Introductiontotheclassicalantcolonyalgorithm 11103213.1.2Theprincipleofclassicalantcolonyalgorithm 1173683.1.3Mathematicalmodelofclassicalantcolonyalgorithm 1223973.1.4Classicalantcolonyalgorithm 14185303.1.5classicalantcolonyalgorithmshortcoming 1453653.2pso 1526993.2.1Psoalgorithmisintroduced 15284913.2.2particleswarmoptimizationmathematicalmodel 15108033.2.2Theadvantagesanddisadvantagesofparticleswarmoptimization 17207223.3Algorithmtoimprove--Fusionalgorithm 17239343.3.1Theimprovedalgorithmofthought 17245613.3.2Theimprovedalgorithmfusion 1884473.3.2ValidationoftheimprovedalgorithminsolvingTSPproblem 19658第4章Thesueofimprovedalgorithminsolvingcloudcomputingscheduling 22137814.1Therealizationofthetaskschedulingandparameters 223914.1.1Therealizationoftheimprovedalgorithmoftaskscheduling 22260354.1.2Theimprovedalgorithmofparametersettings 23154484.2Theimprovedalgorithmintheapplicationoftaskscheduling 25256234.2.1Cloudcomputingplatformenvironmentisintroduced 2526274.2.2Theeffectofschedulingalgorithm 2577344.2.3Applicationtestexperiment 26294134.2.4testexperiment 266004Conclusion 301384Thanks 317767Reference 322584Appendix 34PAGEPAGE39第1章绪论1.1论文背景和意义1.1.1引言云计算作为一种新的商业模式，作为云计算核心部分任务调度成为一个重要的问题，任务调度的性能优劣直接影响到云服务的质量，从而关系到用户的需求是否能得到满足以及资源是否合理利用。本章首先介绍云计算的国内外发展情况，任务调度现状，概述本文要研究的问题，最后给出全文的组织结构。1.1.2背景和意义计算机产生后相当长的一段时间内，计算机网络都处在一个黑暗的时代。但是90年代以后，网络出现爆炸式的发展，随即进入网络泡沫时代，在21世纪初，正当互联网泡沫破碎之际，web2.0的兴起，让网络迎来新的发展高潮期。Flickr、Mysqace、YouTub等一些主流网站的访问量已经远远超出了传统门户网站，应对如此庞大的用户群体已经成为21纪网络时代的一大问题。Google文件系统搭建起谷歌服务器集群，为谷歌提供了强大的搜索引擎能力，正因为需求的出现，云计算因此出现了。近年来，IT界的新贵--云计算开始被人们广泛关注，中国云计算从无到有，迅速发展至今，云计算的发展离不开商业的推动，一切技术的革新都离不开商业的需求，从社会层面讲数字一代的崛起，消费行为的改变也是云计算的发展方向，国外的谷歌、微软、亚马逊等IT企业作为该产业的领头羊，一直推动云计算的高速向前发展。云计算是将若干台计算机组成一个超大的集群，将所有机器的资源虚拟化成一个超大型的虚拟资源池，该集群的虚拟资源对外是透明的，用户不需要关心任务的分发和管理，用户所担心的是任务的处理时间和支付的费用，随着移动终端的迅猛增加，使得网络资源请求成为一大压力，大量的任务和海量的数据需要处理，所以如何合理的分配资源虚拟资源，对用户任务进行高效科学的调度，使处理用户任务的时间缩短、系统调度执行开销和用户执行费用较小。目前的云计算提供者注重服务的响应速度，忽略了经济效益和资源利用率，往往会造成系统的负载不均衡，资源池中性能好的计算机资源利用较高，云计算的优势没有很好的发挥出来。1.2国内外研究状况云计算的发展推动着云产品的完善，云计算开始进入更多的领域，如航空航天技术、气象预报、生物工程等许多领域，在各国政府的全力推动下，多云计算已经走上了快速发展的轨道，美国政府带头采用云服务，在2011年9月发布的《联邦政府云战略》，规定所有联邦政府信息化项目中优先使用云技术，力求解决美国联邦政府电子政务技术设施使用率底、资源需求分散、系统重复建设严重、工程建设难于管理以及建设周期过长等问题，以达到明确度量云计算生产的效益、注意事项和选择条件，推动云计算的部署目的。2010年7月，欧盟第七框架计划（FP7）发布了《2011—2012年工作计划》，为云计算的研究方向制定了框架，包括可扩展的云计算资源的智能与自动管理、基础设施虚拟化与跨平台执行技术、不同云计算环境的糊操作性、对移动情景感知应用的无缝支持、云计算软件与服务的能效与可持续性、支持计算与网络环境集成的构架与技术、云计算软件栈的开源执行等。亚太地区云计算应用广泛，且正在持续加速。根据2011年3月SpringboardResearch发布的《云计算及IT的角色转变的白皮书》中对亚太地区的六千多家企业和公共事业部门云计算应用情况的调查结果，在新加坡、澳大利亚、马来西亚、日本等国家中，认为所在企业或公共部门云计算使用的比例均超出80%。中国的IT企业也开始启动云计算工作，除了阿里巴巴外，瑞星、盛大网络等一批企业相继宣布了自己的“云计划”，同时，针对云计算的研发和应用，本土企业取得了新的进展，世纪互联网推出了ClocdEX产品线，包括完整的互联网主机服务，联想公司不仅将云计算构架用在自身的研发平台中，还通过软件研发，将云计算与客服联系系统结合起来，优化用户体验。上海电信开展云存储业务，与EMC公司合作，将分布在异构存储系统与平台中的数据进行虚拟化云存储，推出面向家庭和个人用户的云信息服务“e云”。继推出e云计划后，上海电信正在筹划“云手机”业务，利用3G高宽带的优势，将大量手机上的应用转移到运营的云端，降低消费者支出成本。Google是一家最先开始研究云计算的公司，是云技术概念的提出者也是云计算的推动者，超大型的分布式文件系统具有很好的可伸缩性，而且对硬件的要求不高，集群可以运行在廉价的机器上，从而降低了服务提供者的成本，Google的云计算从最开始的hadoop1.X到如今的hadoop2.X，在计算模型上发生了改变，系统得到完善，增加了其稳定性。IBM公司在传统的计算机领域出于决定的优势，但在如今的大环境下，IBM也推出了自己的云产品，其主要优势是无可匹敌的企业级服务交付，动态安排成规模服务；每种云技术都内置了安全性和弹性；客户通过自助和开放的企业管理工具实施控制；针对工作负载进行优化的部署模型，实现混合型服务交付。云计算的发展促使云产品的完善，云计算主要体现在如下几个方面：云计算系统向外提供的是服务。云计算以对用户透明的方式提供给使用者各种各样的服务，用户不需要知道云服务是如何管理和控制的。经济性。云计算平台的搭建相比高配置的服务器来说是划算的，大家都知道计算机的配置之间是相互作用才能达到最大的性能利用，所以瓶颈是无可避免的，云计算克服了这个缺点，云计算的集群所需的是一般的PC机器，这个可以大大节约成本。高可用性。高性能的处理计算能力、高质量的服务、海量存储体现出计算的高可用性，云计算视失效的节点为常态，不影响整个集群的正常工作。高层次编程模型。用户通过对计算框架的改写可以满足自己的业务需求，云计算的一般编程是采用MR的计算模型。采用冗余机制保证系统的可靠性。云计算系统一般由许多商用计算机集群组成，集群对外提供服务，在计算机硬件无法保证可靠性的情况下，分布式存储和数据冗余来保证数据的可靠性。1.3本文的主要工作阐述云计算的定义、架构、任务调度现状，以及云计算的编程模式。讲诉云计算的任务调度概念、调度特点。研究蚁群算法、粒子群算法，通过蚁群算法和粒子群算法进行融合。根据虚拟资源的调度特点，结合蚁群算法和粒子群算法的融合算法，设计一种新的算法，融合算法用于解决云计算任务调度问题，通过合理使用虚拟资源，使云服务负载均衡，降低投入成本，同时也满足客户的需求。第2章云计算介绍和任务调度现状2.1云计算的现在2.1.1国内主流的云计算平台当今IT界备受关注的云计算在人们的争论中逐渐发展起来，从经济学的方面说：有需求才有市场！云计算的不断发展也是信息的必然改革，对于数据量的不断增加，摩尔定律已经被打破的情况下，云计算应运而生，对于云计算的平台和服务的系统构架的谈论没有统一的结论，大家对云计算的理解大多只是停留在数据量大的表面层，所有使得云计算出现了这种主流所谓的认同。一种说法是，云计算是分布式技术的一种，主要功能是对海量数据的存储，通过底层高效的HDFS分布式文件系统能实现高效的存储速度，使得日志的存储速度大大提高，高稳定性的文件系统也为数据存储的安全性提供了保障，云计算技术最基本的概念是，通过网络宽带，将普通的PC机组合在一起，形成一个庞大的超巨型计算机，当云计算平台接受到任务时，任务会被切块分成若干的子任务，然后将任务发送到各个主机，由主机在本机执行任务，由于云计算的分布式系统是共享目录对所有主机开放的，主机之间可以进行数据的交换，提高了数据的计算能力，当各个主机处理完子任务之后会将子任务的结果返回给客户端，也就是任务的请求者，这种技术的实现可以在数秒内处理千万级别的数据，达到了超级计算机的强大效果，能解决硬件和软件之间的瓶颈问题，所以对用户来说只关心两个事情，一个是任务的请求和结构的返回。另一种说法是，云计算是用来做某种平台或某种应用的术语，云计算是按需分配的原则，资源是动态管理的，所有的资源都放在虚拟的资源池中，有云计算自己管理和对任务的分发处理，平台的搭建可以是真是的物理机也可也是虚拟机，因为云计算是拿到所有机器的资源后，将所有的资源放在一起，最终还是形成虚拟的资源作为服务的响应资源使用，这些云计算同样描述了一些可以通过互联网被访问到的可扩展的应用程序，这样云计算应用程序为应用提供了强大的服务支撑web和web服务，如下是云服务在未来的几年内的服务方向，如下图2-1图2-1云计算在未来互联网中的发展方向2.1.2云计算任务调度算法的研究现状云计算作为新型的产业备受计算机行业的关注，经典的神经网络、人工智能和分布式算法等都被应用到云计算的资源调度问题中，用于解决服务提供商的成本问题，解决资源的投入成本的同时也满足用户的需求。传统的单机计算通过提高硬件配置已经不能满足如今的用户需求，分布式计算模型越来越受到人们的关注，通过集群的计算能力来解决实际问题，大大提高了计算效率，降低硬件的要求，然而，分布式集群计算的关键在于如何将集群的资源利用最大化，也就是今年大数据平台的热点问题资源调度。由于资源调度的选择会决定用户需求的执行效率、资源数以及整体的性能。所以云计算的资源调度目的是为了找到最优的调度，应用于云计算资源调度的常见算法有以下：粒子群算法。是一种仿生算法，通过观察鸟群寻找食物的过程，个体在时刻调整自己的速度和位置，不断的迭代来加快群体的极值最优，基于粒子群算法的缺点，提出一种改进算法，该算法主要是结合蚁群算法来解决云计算服务提供商在资源利用和负载均衡的优化问题。蚁群算法。蚁群算法被广泛的应用于云计算任务调度中，在下文中将会使用该算法应用于Google公司的云计算框架使用基于蚁群改进算法的任务调度策略中。2.2云计算架构和任务调度基本问题2.2.1云计算技术体系结构云计算在各大提供云服务的厂商和业界之间还没形成一个统一的规范和标准，各个厂商之间云计算技术系统结构也都不相同，深入对比研究了各个企业提供的云计算解决方案，为广大读者简单的介绍一下。云计算的技术体系结构是分层的结构，具体由四层组层，下面对这四层提供的功能进行简单的描述。SOA构建层可以看到最上面一层SOA层是有很多组件构建成的。利用面向服务的构建思想云计算能力封装成标准的服务（WebService），用户可以通过SOA层获得服务接口、服务注册、服务查询、服务访问和工作流。管理中间层该层以中间件的形式提供四个主要功能，资源管理通过对虚拟资源情况的实时监控达到使云计算资源使用均衡的目标，各个资源节点故障监测和恢复也是通过资源管理来实现的；任务管理的功能是对用户所提交的任务找到相应的资源进行部署和管理，同时负责管理任务调度的生命周期；用户管理功能包括：环境配置、用户账号管理、资源使用计费。资源池层这层又叫虚拟化资源层。云计算通过应用虚拟化技术，将数据中心包含的基础设施硬件资源虚拟化为各种虚拟资源池。管理中间层的任务管理在接受到用户请求后从虚拟资源池中找到相应的虚拟资源分配给用户使用。物理资源层该层是由分布不同地域数据中心的物理资源基础设施所组成，包括存储器，数据库，网络设备，计算机等。2.2.2计算编程模式之——hadoop目前，比较流行的云计算编程模式是Google提出的MapReduce，该编程模式是为了使用后和进行云计算服务的开发人员能够方便的利用云中心的资源，不考虑复杂的软件环境，从而保证云计算的安全性，通过分布式计算可以把一个需要巨大计算量的问题划分成很小的问题分配给不同的计算机来并行运算求解，最后综合各个计算机结果就是最终的结果。最近分布式计算机已经被用于解决一些有趣的问题，因特网上成千上万志愿者计算的闲置计算机被用于分析外太空的电讯信息，探索宇宙的奥秘。Hadoop实现了一个分布式文件系统简称HDFS。HDFS有高容错性的特点，并且设计用来部署在低廉的硬件上；而且它提高吞吐量来访问应用程序的数据，适合那些有着超大数据集的应用程序，HDFS放宽了POSIX的要求，可以以流的形式访问文件系统的数据。Apache云平台以开源的精神，将底层代码全部开放给热爱软件的社区，使得越来越多的IT技术人员开始研究Apache云平台的工作原理和实现，例如腾讯、阿里、京东、百度等国内物联网一线的IT公司分别对Apache的云平台hadoop进行底层的改写，来解决自己的实现问题。Hadoop在国内的发展迅猛，越来越多的项目开始倾向于hdaoop云计算来处理事务，其版本也在不断的升级改进，对于1.X的版本在稳定性和多计算框架上进行完善，为克服hadoop1.x中HDFS文件系统和MapReduce存在各种问题而提出，如下图2-2hadoop1.x中单点故障问题的解决提出了分离管理。图2-2云计算计算框架的升级YARN是hadoop2.0中资源管理系统，它是一个通用的资源管理模块，可谓各类应用程序进行资源的管理和调度，YARN不仅限于MapReduce一种计算框架，也可以供其他框架使用，比如Tez、spark、storm等，由于YARN的通用性，下一代的MapReduce的核心已经从简单的支持单一应用的计算框架MapReduce转移到通用的资源管理系统YARN。YARN基本组成架构，总体上仍然采用Master/Slave架构，在整个资源管理框架中，ResourceManager为Master,nodemanager为slave，ResourceManager负责对各个NodeManager上的资源进行统一的管理和调度，当用户提交一个应用程序时，需要提供一个用以跟踪和管理这个程序的ApplicationMaster负责对各个NodeManager上的资源进行统一的管理和调度，当用户提交一个应用程序时，需要提供一个用以跟踪和管理这个应用程序的ApplicationMaster，它负责向ResourceManager申请资源，并要求NodeManager启动可以占用的资源。下图2-3是YARN的构架图图2-3YARN计算框架YARN的工作流程：用户向YARN中提交应用程序。ResourceManager为应用程序分配第一个Container，并且与对应的NodeManager通信，要求它在这个Container中启动应用程序ApplicationMaster。ApplicationMaster首先向ResourceManager注册，这样用户可以直接通过ResourceManager查看应用程序的运行状态，然后它将为各个任务申请资源，并监控它的运行状态，直到运行结束。ApplicationMaster采用轮询的方式通过RPC协议向ResourceManager申请资源和领取资源。NodeManager为任务设置好运行环境，将任务通过某个RPC协议向ApplicationMaster汇报自己的状态和速度，以让ApplicationMaster随时掌握各个任务的运行状态，从而可以在任务失败时重新执行任务。2.2.2云计算任务调度基本问题对于分布式系统，应用程序通常被看成集合，在执行的过程中任务被分成很小的任务分配到不同的机器上执行，一般来说子任务的执行有两种方式，一个好似并行执行，就是应用程序被分割成很多子任务，由所有的主机同时执行，另一种方式是串行执行，由于某些子任务会被分配到同一个机器上，此时的子任务是顺序执行的，。任务调度问题的宗旨是：满足优先约束关系和优先顺序的前提下，先按事先规定的资源分配策略，执行并行的任务，确定任务的执行顺序，最后将所有任务分发到各个主机上，这种任务调度方式是为了减少总的执行时间。资源调度优劣的评价主要体现在两个方面，性能和效率。对于商业模式的应用主要关心的就是这两点，本文我们主要从这两点出发来解决云计算任务调度问题，云环境下的任务调度是一个映射过程，它根据云环境中资源、任务两者的状态和预测信息，在一定的约束条件下，将相互独立的用户所提交的任务，映射到合适的虚拟机资源上执行，最后返回处理结果，良好的任务调度算法能有效地协调和分配虚拟资源，有效降低任务的总执行时间和资源总耗费量，从而使云系统达到最大性能。任务调度的实质就是把个任务以合理的方式调度到个异构资源中去，使任务能高效的执行，具体描述：是个需要调度的任务集合，表示第个任务。每个任务的执行可能包含成千上万的指令，并且每个任务只能在一个虚拟机资源上执行完成。是个可用的资源集合，表示第个资源。每个资源的计算能力用性能参数来衡量。个任务在个资源上的预测执行时间ETC是一个的矩阵，表示第个任务在第个资源上的执行时间。资源的最早可用时间为；第个任务在第个资源上最早完成时间如下：任务的最早完成时间为，当把任务分配给第个资源时，；所有任务执行完成的时间为时间跨度；任务调度其实是一个求最优解的过程，传统的任务调度人们的侧重点在于完成任务的最短为目标函数，本文研究的是在响应服务性能和资源的利用率两个最为重要点。第3章改进的蚁群算法--算法融合3.1经典蚁群算法3.1.1经典蚁群算法简介蚁群算法起源于20世纪意大利的一位学者从生物进化的机制中得到启发，他通过观测自然界的生物蚂蚁在需找食物的过程中进行蚂蚁之间的信息交流，模拟这一行为，提出一种新型的机器学习算法，成为群体智能理论研究的主要算法，蚁群算法主要是通过信息素的政府机制和群体之间的自催化行为来找到通向食物的最短路径，蚂蚁在寻找食物的过程中，会在他经过的路上留下一种生物信息叫做“信息素”的物质，这种物质是蚂蚁之间进行信息交流的主要直接的途径，它会影响后来的蚂蚁在路径的选择，随着时间的推移。留有信息素较多的路线通过的蚂蚁会越来越多，相反通过蚂蚁少的路线上的信息素会越来越少，最后逐渐消失。3.1.2经典蚁群算法原理介绍蚁群算法的基本原理如下图3-1图3-1经典蚁群算法原理图假设A点为蚂蚁的蚁穴，D点为食物源，蚂蚁从蚁穴出发寻找D点食物可以有很多选择路径，最简单快速的路径就是从A点到D点之间的直线路径，由于现实世界的限制，很多时候蚂蚁是不能直接到达D点的，假设在A点和D点之间有很多障碍物，蚂蚁有两条路径可以到达D点寻找食物，一条是，另一条路线是，假设最开始的时候蚂蚁从蚁穴出发通过这两条路径的概率是一样的，也就是所有路径上的蚂蚁的数量是一样的，在这个过程中每条路径上通过的蚂蚁数量是一样的，所以每条路径上蚂蚁留下的信息素浓度是一样的，这对刚开始出来觅食的蚂蚁来说影响他们选择路径作用是一样的概率，但是随着时间的推移，由于路径上的蚂蚁选择的路线相对短一些，通过的蚂蚁数相对多一些，根据信息素的正反馈机制，时间长了遗留在路上的信息素会随时间的推移浓度逐渐降低，而路径上的蚂蚁相对时间内通过的蚂蚁数量低于路径上的蚂蚁数，因此，路线上的信息素浓度较高，当其它蚂蚁从蚁穴出发，当他到达B点的时候，他首先会通过信息素的浓度高低来决定他走哪条路线去寻找食物，信息素会影响以后所有蚂蚁的觅食路线。遗传算法也经常被用于解决TSP问题，其原来也是从整个蚂蚁群体发起搜索过程，有比较好的并行特点。由于蚁群算法具有正反馈机制和很好的鲁棒性，上述特点使得蚁群算法成为云计算任务调度算法的一个很好的选择，我们可以将云计算资源的计算能力用信息素来描述，可以非常有效的将云计算任务调度问题表示为蚂蚁的寻找食物的过程，进而可以基于蚁群算法进行任务调度的求解，但是再怎么完美的东西都会有瑕疵之处，蚁群算法也是如此，它也有不足之处，其主要表现在蚁群初始的数量比较大时，在算法的初期由于信息素的缺乏会导致觅食路线很难收敛，因此需要对蚁群算法进行改进。3.1.3经典蚁群算法数学模型蚁群算法比较容易理解，可谓通俗易懂，而且很容易实现，不会因为系统的复杂程度高使得算法难于理解。蚁群算法常用于商旅来寻找最短路，这个实际问题类似于蚂蚁的觅食过程。算法可以用TSP的组合优化问题来验证算法的有效性。TSP问题的符号含义如下所示：蚂蚁的初始数量表示城市的距离时刻城市上蚂蚁的数目用城市与距离定义的启发系数城市到路径上的信息素浓度值大小城市到的单位长度信息素浓度值蚂蚁从城市转移到城市的概率值其中公式为：蚁群算法在解决TSP的时候有如下特点：蚂蚁从城市移动到城市的概率是这两个城市之间距离和信息素的相关的函数。为了满足约束的条件，蚂蚁在遍历整个城市的过程中，不能再次挑选已经经过的城市。蚂蚁一次完成遍历所有城市之后在经过的边上留下信息素。假设为TSP的城市数量，蚂蚁的数量有个，表示T时刻边上的信息素浓度，表示城市到城市的距离，表示各个城市之间的初始信息素浓度，开始时将蚂蚁随机分配到各个城市的节点，蚂蚁遍历所有城市建立一条封闭曲线圈，对于每只蚂蚁在建立路径的过程是：J是随机比例规则：

其中，表示蚂蚁访问城市的概率大小，=是启发式信息，该值的大小反应蚂蚁从城市到城市的启发程度，参数反应在该访问路径的过程中信息的积极量，值大说明蚂蚁倾向于选择其它蚂蚁频繁经过的路径，值越大时蚂蚁越倾向选择路径较短的。为的常数，allowed表示蚂蚁下一个城市选择哪个：随着时间的改变蚂蚁从禁忌表中选取未经过的城市，并且每条边的信息素浓度也在更新，假设已访问过的城市的信息素浓度在随时间的改变不断更新，更新公式为：公式3-1参数介绍，的取值为0.1，的取值是，通过获得最近临方法所得路径的长度，避免蚂蚁陷入局部更新而停滞。全局的信息素也在更新，在每次迭代之后，本次迭代的最优蚂蚁或者全局最优蚂蚁的信息，建立一个信息素释放的规则：，表示整个蚁群中成果最好的蚂蚁，也就是全局最优的蚂蚁，经过的路径长度是最短的。参数值在[0.1]之间的信息素蒸发的速度，在蚁群算法中的值通常取值为0.1，全局的信息素的更新强调最优路径的搜索，可使搜索过程具有强大的导向性。3.1.4经典蚁群算法优点稳定性高，鲁棒性好，蚂蚁拥有明确的觅食规则，它们不会因为一些异常现象或危险情况的出现而找不到食物。首先，蚁群算法整个求解过程中不需要进行人工干预，而且对初始路线的要求并不高，蚁群算法的求解结果不依赖于初始路线的选择。其次，蚁群算法本身复杂度不高，算法涉及的参数较少，而且研究学者们还提出来许多基于原始算法的改进算法，甚至与相应的启发式调度算法结合使用，能很有效的改善算法的性能。蚁群算法是一种基于种群生存过程的拟生态算法，蚂蚁在系统中进行觅食的操作是独立的而且是并行的。蚁群算法本质上可以看做是并行算法，每只蚂蚁觅食的操作是相互独立的，彼此间没有内部信息的依赖，它们一旦找到食物源是通过分泌信息素来与其他蚂蚁进行信息交互的，并不会直接告诉其它的蚂蚁。这种独立并行的搜索行为使得蚁群算法搜索可靠性提高，并且有较强的全局搜索能力。3.1.5经典蚁群算法缺点蚁群算法的设计计算规模有限，当应用问题规模比较大或者规模动态发生变化，蚁群算法性能不稳定。虽然蚁群算法的复杂度不高，但他的收敛过程可能需要较长的时间。由于在搜索初期每天路径上的信息素浓度差别并不明显，可能会有许多蚂蚁同时选择一条并不理想的路线，此时该路线信息素浓度变得很大，从而给其它蚂蚁较少容易出现原地打转停滞的现象，降低搜索效率，使系统出现停滞状态，最终使目标的寻找时间变长，在经过较长一段时间后，较好路径上的信息素明显才会明显的高于其它不好的路径，随着时间爱你的推移，这种差别将越来越明显，从而最终收敛。但当群体规模逐渐增加到一定规模后，该记录表中的路径数目将无比庞大，在短时间内从大量杂乱无章的路径中寻找到一条比较好的路径时比价困难的，因此导致整个系统的运行速度变慢。3.2粒子群算法3.2.1粒子群算法的介绍粒子群算法于1995年由Kennedy和Eberhart等人提出，该算法也是模拟群体生物智能行为的一种优化算法，粒子群算法主要是模仿鸟类在飞行的过程中通过群聚能有效的觅食和躲避危险的行为，在群体生物中，个体除了具有自身的行为能力之外还具有群体的行为特征，整个群体之间的信息是被群体每个个体共享的，如计算机的共享目录一样，每个个体都能访问到群体的特征，群体中的每个个体也是可以彼此之间进行信息交换，粒子群算法是以模拟群体智能为解决连续组合优化问题而出现的，这个算法相对比较简单，参数相对比较少，能有效的加快收敛速度。每个个体在群体中有自己的位置和速度，还有一个优化函数求出来的适应值，种群内的每个个体在运动的过程中都会具有最优位置的粒子靠近，在求解的过程中如果有粒子找到更优的位置，种群将会在此位置的基础上寻找下一个更优解，这个过程总是在一直不停的变动种群的未来来调整当前的位置，找到种群的最优解。3.2.2粒子群算法的数学模型粒子群算法中，每个粒子拥有自己的速度和位置，这些速度和位置都对应一个可行解，设粒子自身的最优解为。粒子群在搜索食物的过程中，会存在一个粒子距离食物最近，此粒子的位置就是最好的位置，也是整个粒子群的最优解。粒子群算法的参数和公式：粒子自身的位置：公式3-5粒子自身的飞行速度：公式3-6个体最好位置：公式3-7全局最好位置：公式3-8公式解释：公式3-5个体最好位置是粒子在飞行的过程中所记录的最好位置。公式3-8表示当所有个体达到最好位置的时候，整体的最好位置。以下是粒子群的速度和位置的迭代方程式：公式3-9公式3-10算法在初始阶段首先要初始化一组随机粒子，在每次求解循环中，单粒子根据两个不同的值来更改自己的位置，表示第一个个体极值点，就是该粒子本身所在的最优解，表示群体的全局极值点，表示整个群体的此时刻的最优解，首先找到这两个极值点后，个体粒子就根据3-5和3-6来跟新自己的位置和速度。粒子群算法的粒子速度迭代可以看成三个部分：粒子先前的速度，是作为平衡全局的状态，粒子在飞行过程中通过自身的位置的思考，做决策，在下一次迭代时如何变化。这部分是粒子的认知过程，粒子通过自身的调解，使整体的粒子在空间的搜索能力增强，避免出现局部最优现象。最后一部分是通过信息的共享来发挥各自的作用，找到离食物最近的位置。参数的作用：公式3-9中参数的作用是协调粒子本身的记忆和同伴的记忆，防止出现混淆，的值合理控制可以避免出现局部最优的同时也加快算法的收敛速度。此外，粒子先前的速度必然会对当前的粒子飞行速度造成影响，因此我们使用参数惯性质量来控制，由于参数的选择对全局的极值影响很大，我们进行多次实验来确定粒子算法的惯性质量[0.9,1.1]之间是最好的。3.2.2粒子群算法的优缺点粒子群算法的优点主要体现在是一种群体智能的研究领域，群体中的每个粒子通过自身的调解和群体之间的合作机制，同时也有群体的相互竞争，靠这种机制来指导粒子群进行优化搜索，该算法的实现比较简单。粒子群算法的缺点主要体现在粒子的搜索空间是一个很有限的空间，不能实现所有区域的搜索；粒子群算法的状态更新比较简单，模型表现出群体智能比较低；算法的参数比较难以控制，不合理的选取参数将导致算法的早熟。3.3算法改进--两种算法的融合从上面一下节我们可以知道蚁群算法和粒子群算法都是很好的群体智能优化算法，对云计算的任务调度问题有很好的应用，但是我们知道不管是蚁群算法还是粒子群算法都是有自身的缺点。本小节主要工作是首先对蚁群算法和粒子群算法进行融合，再对融合算法进行调整，设计出改进算法，以弥补蚁群单一算法的不足之处。3.3.1改进算法的思想蚁群算法对于离散问题常常有显著的作用，粒子群算法主要优势在求解连续空间问题是效果显著，对于这种情况，我们根据蚁群算法的缺点，利用粒子群算法进行弥补。粒子群中的个体是拥有自身的速度和位置，并且知道群体的全局极值、个体极值等参数，粒子群中的粒子就是根据这些特点进行迭代的，由于蚁群算法是某种启发式算法和正反馈机制的结合，这种机制容易使算法陷入一个误区，产生局部最优解导致早熟现象，我们采用粒子群优化算法能很快速的找到全局的最优解，计算效率相比较与传统的算法而言具有更高的效率。我们通过对比蚁群算法和粒子群算法的优缺点以及不足之处进行比较，如下表3-12所示：3-12蚁群算法和粒子群算法的优缺点比较算法自身的优点自身的缺点粒子群算法收敛速度快，参数少搜索使用评价函数启发大范围全局搜索能力具有扩展性，易于其他算法结合算法后期局部搜索能力差反馈信息利用不充分蚁群算法分布式计算启发式搜索通用型随机化方法初期信息素缺乏收敛速度慢通过上面的表格我们可以看出使用粒子群算法和蚁群算法进行融合来达到相互弥补的效果，融合步骤如下：首先使用蚁群算法，让蚂蚁遍历所有路径一次。此时我们让蚂蚁具有“粒子”的特性，蚂蚁在第一次选择路径时会根据自己的局部最优解以及整体蚂蚁的最优解进行调整，由于粒子群算法中的速度对蚂蚁不能表示，因此我们采用遗传算法来对其进行表示，主要方式是使用遗传算法的交叉策略和变异策略。3.3.2改进算法的融合在上小节说明融合算法的思想，可以知道融合算法的好处，本节实现融合的过程，我们首先让蚂蚁遍历路径，然后让蚂蚁具有“粒子”的特征，下一步使用粒子群算法对蚁群算法进行改进，由于粒子的自身速度在蚂蚁解决TSP问题中无法描述，因此我们采用遗传算法中的交叉和变异策略来进行描述，粒子群算法的公式3-9中和刚好符合遗传算法中的交叉操作，让当前解与个体极值交叉，当前解与全局极值交叉，利用这种方法产生粒子的新位置。我们以旅行商问题来阐述变异的操作。假设存在个城市，路径变异到，可以使用如下方法。变异：变异1：在编号个访问城市，随机选择第次和第次访问的城市，在路径中第次和第次访问的城市之间的子路径以反方向插入，其它不变，变异到，如下：变异到变异2：在编号个访问城市中，随机选择第次访问的城市，在路径中交换第次和第次访问的城市，其它不变。变异3：在编号个访问城市中，随机选择第和次访问的城市，在路径中将第和次访问的城市交换位置，其它不变，形成路径。交叉策略：（1）交叉1：假设有两个父路径和，在中随机选择一个交叉区域，在中的相应位置插入的交叉区域，在中删除存在的交叉区出现过的城市，例：选择的交叉区域是，交叉后为：。交叉2：假设有两个父路径和，在中随机选择一个交叉区域。将的交叉区域加到后面，在中删除中的交叉区域出现过的城市。例：选择的交叉区域是，交叉后为：。3.3.2改进算法在求解TSP问题中的有效性验证为了检验遗传算法对粒子群算法中粒子速度的描述的有效性，采用MATLAB软件对蚁群算法、融合算法进行验证解决TSP问题的结果，我们选取31个城市坐标，数据来源自己编写。蚁群算法的参数设定：迭代次数为：40 蚂蚁个数为：50 信息椅子为：1 期望因子：10 信息素挥发因子：0.5 信息素强度：100改进算法--融合算法蚁群算法采用6种方法进行比较，6种方法来源于3中变异和2种交叉的组合，参数设置：蚁群算计改进算法代码见附录三。如下图表3-13是蚁群算法和融合算法通过变异和交叉策略描述的解决TSP问题的结果。算法平均值最好解最差解遗传算法483.45467.68502.57蚁群算法550.03491.95599.93交叉策略1+变异策略1439.50425.65456.78交叉策略1+变异策略2441.93428.73455.33交叉策略1+变异策略3437.00426.60446.24交叉策略2+变异策略1438.77425.47445.30交叉策略2+变异策略1431.94424.63457.90交叉策略2+变异策略1431.50423.74447.68从上表中可以看出，蚁群算法采用变异策略和交叉策略的最好解都比较优图4-14基于改进蚁群算法的最优解利用改进算法解决云计算任务调度问题随着虚拟技术广泛应用到商业模式，云计算作为底层的数据访问平台，其性能的优劣直接影响到用户的使用质量，为了提高用户的服务请求的质量和访问响应的实时性，同时降低硬件的投入成本，提高资源的利用率，因此我们提出绿色概念的云计算，主要是针对云计算任务调度考虑负载均衡的问题，随着移动终端的迅猛增加，用户对服务提供商的要求也越来越高，既要保证用户的服务质量又要考虑服务提供商的经济效益。我们提出一种新的任务调度算法，蚁群改进算法来合理分配任务调度、减轻云计算的负载、提高资源的利用率。4.1任务调度的实现和参数设置4.1.1基于改进算法任务调度的实现本小节我们主要是研究蚁群算法的改进算法应用用云计算资源调度，由第二章节我们分析了云计算的资源调度问题和云平台hadoop的资源调度模型，此处应用Google的Map/Reduce云计算架构模型，该构架模型将每个单元都分成两个部分：一个是任务的管理者；另一个是任务的执行者。主节点主要负责任务的调度分发，这些任务的数据资源并不是集中在一起的，他们分布在集群的数据节点上，对用户是透明的，整个调度流程是：map端输出数据写入本地磁盘，然后任务的执行者来完成子任务，完成子任务后进入Reduce阶段，并从相应的Map端输出。将数据节点域作为一个无向图，存在一个区域，这里用来表示该无向图区域中所有slave节点的集合，连接各个slave节点的网络集合用来表示。资源调度算法考虑的几个参数是：网络宽带：路径所提供的网络最大宽带。网络延迟：路径产生的最大网络延迟。预计执行时间：路径尽头的计算资源处理作业要消耗的时间。第一步：初始化（M为迭代次数搜索次数），，利用蚁群算法让蚂蚁完成一次所有路径的遍历（形成个可行解，即条资源分配序列），按公式4-1计算适应值（见下小节），设置粒子当前的适应值为自身的极值，当前可行解为个体极值的可行解为。根据各个粒子的自身极值，找出全局极值，全局极值可行解。第二步：将只蚂蚁随机放到个虚拟资源节点上。从开始循环到，将蚂蚁出发的初始资源节点放置在当前资源列表中，即初始资源分配序列。从中删除该资源节点。第三步：从开始循环到，按4-2和4-3（见下小节）的概率选择一个计算资源节点，将节点置于当前资源序列中，从删除。第四步：从开始循环到，第只蚂蚁形成的资源分配序列与交叉根据上节中的交叉策略得到，与交叉得到，以一定的概率变异到。如果当前资源分配序列能完成当前所分配的任务，根据适应值的计算公式计算其使用值。如果得到的新的目标函数变得更优，那么就接受新值。否则不取新值，第只蚂蚁形成的资源分配序列仍然为，重新找出各只蚂蚁的个体极值和极值资源调度序列，找出全局极值和全局极值资源调度。第五步：根据适应值公式计算出蚂蚁形成资源分配序列的完成时间，记录当前的最好解。再根据信息素量的更新规则对路径上的信息素进行更新。第六步：设置执行重新执行第二部第七步：输出最优资源分配序列以及完成的时间值是多少。4.1.2改进算法的参数设置可行解的定义：假设系统中有个任务集合在资源节点集合上完成，其中，为独立任务，为计算资源节点，粒子群算法中的粒子的位置就是一个可行解，即一个可行的资源分配序列，假设任务要在资源节点上完成，则粒子的位置为：这是一个维向量，其中数据表示任务被分配到资源号是，。表示一个可行的分配方案。适应值的定义：资源调度问题描述为个任务集合在资源节点的集合上完成资源调度，其中为要完成调整的任务，为计算资源调度节点，资源调度问题中，各个资源节点都是存在一个速度，改值表示为单位时间的指令数量，任务长度也表示为指令数量，完成每个任务需要的指令数以及资源节点的速度都有规定。本文中粒子群算法中的每一个粒子就是调度序列，比如粒子位置表示任务0分配到资源节点6上，任务1分配到资源节点人，任务2分配到资源节点3，依次类推，各个节点资源处理所有分配到该资源的任务总的执行时间为，比如资源节点2计算任务3和1的总指令数除以资源节点2的速度，取所有资源的中最大的值，即公式4-1蚁群算法蚂蚁对下一步目标的选择的设定：虚拟集群的资源的数量多少和资源在某个位置都是不确切的，另外网络的拓扑结构不稳定，使得云计算环境结构和资源的分布呈现不透明状态，在蚁群算法中，蚂蚁是靠信息素浓度来抉择如何选择路径的，因此，开始阶段，网络结构处于初始阶段，其中每一条路径上含有相同浓度的信息，随着时间的流式，每条路径上的信息素浓度逐渐消失。假设：蚂蚁在时刻节点，蚂蚁在下一次选择节点为：公式4-2公式4-3路径上的信息素更新变化规则是：信息素的浓度是在不断更新变化的，信息素浓度的修改策略是局部更新的策略，更新规则如3-1所示，该规则适用于信息素浓度不为0的节点：经过个时刻，蚂蚁完成一次循环，每一条路径上留下的信息素浓度的更新公式如下：为本次循环中蚂蚁在链路上留下的信息素数量，蚂蚁轨迹的持久性用来表示。为链路的信息量增加量。4.2改进算法在任务调度中的应用4.2.1云计算平台环境介绍Hadoop云计算集群搭建在Linux环境下，集群规模为20台主机，每台主机的配置cpu：4核；内存：32GB；宽带：1Mbps。Hadoop版本为2.2.0，目前2.X之后的稳定版本为2.2.0，在此我们搭建的云计算平台选择的版本也是2.2.0，JDK选择1.7.1版本，数据库选择为分布式数据库和列式数据库存储于HDFS上，使用hive、HBASE对其进行管理。集群架构，采用主从架构，一个主节点，十九个数据节点，数据分布在集群中，为了能提高计算效率，我们将数据默认备份为3份从上表中可以看出，蚁群算法采用变异策略和交叉策略的最好解都比较优。4.2.2调度算法的生效将改进蚁群任务调度算法代码（见附录）打包拷贝到hadoop的lib目录下，由于hadoop平台是使用java开发的，是开源项目，热爱软件的人士可以研究其编写代码，以及对hadoop的工作原理进行修改，因此hadoop的API能实现对底层的修改，然后在hadoop的conf目录下修改配置文件，将融合算法任务调度模块加入到配置文件中，当hadoop执行任务之前会先将配置文件的信息加载到内存中，读取配置文件的信息，从而将融合算法应用到任务调度中。修改完配置之后需要重新启动云计算平台，使配置文件生效。4.2.3用于测试的应用程序介绍我们先将程序部署在云平台上，本程序为风险管理系统，主要功能是预测保险公司在对保户进行承保的时候对其保户出险率进行评估得分的平台，主要是对保险公司和对其管理部门使用，因此对其响应速度有很高的要求，由于保险公司为了提高出单率，承保过程的每个环节都需要节约时间，为了节约保险公司的成本，机房的机器每天都在运行着很多的应用投保历史查询、理赔历史查询、投保确认程序等，因此对机器的压力比较大，保险行业以前通常采用的是先将数据存储在临时数据库中，等夜间对其数据进行处理，速度是提高了，但是对于没有投保记录的新增用户的出险率的得分就很难测评，因此保费通常是收取经验值，很多未知风险无法预测，为了解决此问题，实现在线实时查询的功能，即要保证保险公司的出单率又要保证对投保客户出险风险的正确得分，我们在其原来程序的基础上做修改，在优化底层数据库的基础上改进任务调度算法。4.2.4测试实验使用loadrunner商业版压力测试模拟上千万用户实施并发负载及实时性能监测的方式来确认和查找问题，loadrunner的主要功能是能最大限度地缩短测试时间，以虚拟用户的方式模拟真实用户的业务操作行为，一旦测试完毕之后，loadrunner收集汇总所有测试的数据，并提供高级的分析和报告工具。 我们通过对比基于蚁群融合算法的云平台任务执行和未修改任务调度的云平台任务调度的环境，采用压力测试，在相同的环境下，测试两种任务调度算法在高并发的状态下所达到的最大并发数，通过最大并发数我们可以知道两种任务调度算法的性能优劣。测试环境：PC机：华硕笔记本操作系统：windows7测试机与被测试服务器保证网络通信，排除网速限制及网速不稳定。第一步：首先我们在本机win7系统上安装虚拟光驱，将loadrunner加载到虚拟光驱，并保证本机网络和远程云平台通信。第二部：编写loadrunner压测脚本见附录一，参数选取start100vuser，表示最大的并发数，duration压测时间，一般压测在五分钟左右，simultaneously表示每多少秒增加多少并发数，在此设定每十秒增加十个用户，测试结果如下：图4-4融合算法并发数图4-5未进行改进算法并发数说明：用户的整个执行过程中的录制在Action部分，所以开始和结束部分为空。从上图4-4和4-5我们可以看出，RunningVusers（测试过程中的并发数），显示录制过程中并发数的执行情况，该图所展示的信息是Vuser状态和完成的的脚本以及用户的数量统计信息，上图显示了风险管理系统性能测试过程中优化的运行情况，从结果可以看出使用蚁群改融合进算法的云平台环境能响应的最大并发数是60左右，在60个并发数压力一分三十秒的时候，模拟系统崩溃，而任务调度未修改的云平台环境能响应的最大并发数是25，当并发数达到25个压测四十秒左右时模拟测试系统崩溃，本系统采用的应用程序是一套风险管理系统的程序，因此程序的执行效率不高。图4-6未进行改进算任务调度每分钟成功的点击量图4-7蚁群融合改进算任务调度每分钟成功的点击量由4-6和4-7图对比可以看出，在高并发的状态下，对任务调度算法进行修改的云平台在每分钟内响应的任务数高于未做修改的云平台。图4-8蚁群融合改进算任务调度用户的平均响应时间图4-9未修任务调度云平台用户的平均响应时间由以上结果显示，平均响应时间是，在此并发数下90%的用户完成任务的时间，图4-8显示的是蚁群改进算法的任务调度结果展示图，从图中我们可以看出，平均响应时间在0.00012~0.00028之间跳动，相对波动不是很大，最开始的时候平均响应时间比较长，在30秒之后响应时间逐渐降下来，分析原因可能是30秒之后程序内存极值导致运行速度提高，之后一直保持在平稳的小幅度波动，而图4-9显示，在测试开始时平均响应时间一直在增大，从0.0003增加至0.0008出于平稳状态，我们可以得知蚁群粒子群改进算法可以大大提高云平台任务的响应速度，提高资源的利用效率，避免虚拟资源的浪费，节约云平台的成本，达到云计算商业用途的真正目的。结论云计算日益受到学者和IT界的青睐，云技术也逐渐走向成熟，越来越多的软件项目开始选择云计算作为项目平台，国内的物联网公司更是投入了很大的硬件成本，目前云计算的效果也是可以看的到的，然而随着数据的急剧增加，用户的访问量呈现指数增长，服务请求的响应质量直接影响到用户，因此云计算的任务调度成为了云计算中一环必不可缺少的重点任务。通过阅读大量中英文文献，从了解云计算体系结构、任务调度、资源分配特点入手，学习和借鉴他人设计的调度算法的经验，在研究蚁群算法和粒子群算法的特点以及优缺点，结合他们的优缺点设计了一种基于改进蚁群算法—融合算法的任务调度策略来解决云计算负载均衡的问题，在满足用户需求的同时节约服务提供商的投入成本，首先使用MATLAB软件测试改进算法在求解TSP问题中的有效性证明，结果发现改进蚁群算法的任务调度算法能很好的解决TSP问题，比单一算法的任务调度更优。最后利用实验，实验结果表明，该调度策略达到设计目标，而且通过对资源选择约束函数和资源选择效用评价函数的选取，能够充分考虑用户任务的不同特点，满足用户实际的服务质量要求。致谢在我的论文完成之际，首先我要感谢石端银老师，是她从百忙的工作中抽出时间，从选题到论文研究的方向一直耐心的为我指导，不厌其烦的帮助我修改论文的内容和结构，在这个过程中我学会了写论文的技巧，怎么样体现论文的主题，再次诚挚的感谢石老师。。参考文献[1]虚拟化与云计算小组.虚拟化与云计算[M].北京:电子工业出版社,2009.[2]DorigoM,CaroGD.Antcolonyoptimization:Anewmeta-heuristic[A].Proc.ofthe1999CongressonEvolutionaryComputation[C].Washington:IEEEPress,1999.14701477.[3]张晓杰,孟庆春,曲卫芬.基于蚁群优化算法的服务网格的作业调度[J].计算机工程,2006,8(32):216218.［4］李丽，牛奔．粒子群优化算法［Ｍ］．北京，冶金工业出版社,2009．［5］李建锋，彭舰．云计算环境下基于改进遗传算法任务调度算法［Ｊ］．计算机应用,2011,31(1):184-186.［6］陈全，邓倩妮．云计算及其关键技术［Ｊ］．计算机应用，2009,29(9):562-2568［7］刘万军，张孟华，郭文越．基于ＭＰＳＯ算法的云计算资源调度策略［Ｊ］．计算机工程，2011,37(11):43-48.［8］申丽君，刘丽，陆锐．基于改进免疫进化算法的云计算任务调度［Ｊ］．计算机工程，2012,38(9):208-210.[9]CusumanoM..Cloudcomput