基于Gridsim和遗传算法对组合双向拍卖问题的研究_毕业论文.doc

本科毕业设计（论文）题目:基于Gridsim和遗传算法对组合双向拍卖问题的研究姓名2008年6月基于Gridsim和遗传算法对组合双向拍卖问题的研究摘要在计算机和网络技术高速发展的今天，计算机的用户对计算量的需求和拥有呈现一种不合理分配的状态：即有些大需求的用户拥有资源较少不能满足需求，而小需求的用户使得其拥有的资源闲置。人们希望像家庭用电一样来使用计算资源，这需要通过网络来完成，如同家庭用电通过电网来传输。于是越来越多的人开始关注如何使连入网络的计算机的资源合理分配。为了在目前的互联网状态下解决此问题，需要推出成熟的新协议。在这之前，在小范围内的模拟资源调度是必不可少的。于是网格计算应运而生，结合各种经典计算方法，在此领域中有了很多新的应用形式。与此同时，一些经济现象也出现在这种资源调度的过程里，例如拍卖。遗传算法是解决货郎担问题(VSP)，车辆路径调度问题(VRP)等NP问题的成熟算法。本文中需要解决的问题也是一个NP问题，故选择使用遗传算法作为工具。本文需要解决的问题是利用遗传算法解决组合双向拍卖的用户和资源的选择问题，再利用由澳大利亚墨尔本大学RajkumarBuyya领导开发的Gridsim在Java环境下进行资源调度的仿真。经过多次实验，以上两个问题得到了较好的解决。本文对遗传算法中的参数设置进行了多次对比实验，得出了特定例子的近似最优设置，为使用遗传算法解决此类问题提出了一些建议和方法。关键字网络资源调度网格计算组合双向拍卖遗传算法GridsimTheDesignandRealizationofInteractiveDemonstrationSystemoftheProtocolofVPN&NATABSTRACTAtpresent,thedistributionofcomputationresourcesamongcomputerusersallovertheworldhasshownaunreasonablestate:thatsomeuserswhohaveheavydemandsowncomparativelylesserresourceswhentheresourcesofusersthathavelittledemandsareleftunused.Peoplewanttoutilizethecomputationresourcesasconvenientaselectricityintheirhouse.Sothereisagrowingnumberofpeoplewhodevotethemselvestofiguringoutthewayofschedulingresourcesofthiskind.Itcanbeimaginedthatanewfully-fledgedprotocolshouldbeappliedtosolvetheproblemabove.Beforethishappened,simulationsofresourceschedulinginanarea-widearerequired.Sogrid-computationhasemergedbecauseofthisopportunityandvariesofapplicationsappearwhenlotsofclassicalgorithmsareaddedin.Simultaneously,someeconomicphenomenonpresentedintheprocessofresourcesscheduling,forinstance,theauction.GeneticalgorithmhavebeenamaturemethodtosolveNPproblemslikeVSPandVRP.Oneprobleminthisarticle,theoptimizingofselectionofusersandresourcesincombinationalauctions,isalsoanNPproblem.ConsideringGAisveryrobustandpopular,sowetakegeneticalgorithmforthetooltoslovetheproblem.Inthisarticle,wefigureoutthewaytodecidewhichusersandresourcessupplierswillbeselectedtojointhefinaltradewithgeneticalgorithm.ThenwestartthetradesimulationofthischosenusersandsuppliersontheplatformofJavacombinewithgridsimwhichhavebeenexploitingbythegroupthatleadedbyRajkumarBuyyainUniversityofMelbourneinAustralia.Thetwomaintargetsaboveareslovedwell,andsomeanalyzationofsolvinguserchoosingproblemsbyusinggeneticalgorithmarepresentedattheend.KEYWORDSResourcesSchedulinginNetworkGridcomputationCombinationalauctionGeneticalgorithmGridsim目录第一章经济网络简介.41.1经济网络研究的起源与应用.41.2经济网络研究的最新发展网格技术.51.3Gridsim开发平台简介.91.4组合双向拍卖简介.101.4.1拍卖的概念.101.4.2拍卖的竞价方式.101.4.3组合双向拍卖.10第二章基于Gridsim模拟组合双向拍卖.112.1问题描述.112.2解决过程.122.2.1主要流程.122.2.2body()函数的设计.122.3结果对比.14第三章遗传算法简介.183.1遗传算法定义.183.2遗传算法特点.183.3遗传算法应用.193.4遗传算法现状.193.5遗传算法的一般算法.21第四章模拟退火算法简介.224.1模拟退火算法简介.224.2模拟退火算法的模型.234.3模拟退火算法的简单应用.244.4模拟退火算法的参数控制问题.25第五章基于遗传算法解决用户资源选择问题.265.1待解决问题描述.265.2设计思路.265.2.1染色体编码.265.2.2初始种群选择.275.2.3适应函数的设计.275.2.4选择双亲.285.2.5交配.285.2.6变异及不可行解处理.285.2.7进化.285.2.8跳出条件.295.2.9算法描述.295.3实验分析.295.3.1结果对比.295.3.2算法中参数对结果影响的讨论.30第一章经济网络简介1.1经济网络研究的起源与应用在信息量膨胀的今天，网络上有关经济的搜索量急剧上升。众多证据表明，网络对社会和经济的推动作用是十分重要的。很多著名的例子已经说明了网络在求职上面（Holzer1987,Montgomery1991），交易（Lazerson1993,Nishiguchi1994）,促进信贷（McMillanandWoodruff1999），互助保险（FafchampsandLund2001），以及福利参与（Bertrand,Luttmer,andMullainathan2000）上的积极作用。由于之前极少有对网络具有实验性工作，渐渐的，经济网络的理论研究引起了人们浓厚的兴趣。在当时，关于网络的实验工作数量仍然很少，但相关文献已经开始出现。这些论文出现的目的是对目前存在的实验性工程的一个概括，并指出对该领域未来研究的一些道路。在实验室里完成的实验为分析经济问题提供了一些强大的，有帮助的技术。实验的主要优点在于控制变量的能力（例如花费，信息，时间等）。这些变量很可能影响个人和集体的行为，而在现实中，这些也许是无法模拟的。博弈理论为特殊模型中的假设提供了精确的公式，所以和理论模型一样，这种被设计好的实验对于使经济学变成一个经验主义的科学来说，是关键的因素。在经验主义的经济学家发现经济网络之前，另外的一些社会学家已经着手调查各个领域中现有的网络效应。也许最早的网络实验就是五十年代早期，在麻省理工的社会心理学家AlexBavelas和他的同事进行的“MITexperiments”。在这些实验中，一组中的每个人都被分配解决一个问题。有代表性的是，每个人都拿到了一张标有很多不同符号的卡片。他们的任务是找到所有人都有的一个符号。每个人可以通过写纸条的方式交流，但仅限于通过外部设置好的一个网络来传递信息。Bavelas和他的同事提出了四种网络结构：链式，圈式，星式，Y式，后来发现，星式和Y式是解决问题最快的网络。而且如果限定传送信息的条数，用这种网络可以得到最少的错误。在接下来的几年里，通信的向心性以及网络的组成的效果被更加深入的研究。（可以参考Shaw在1964年做的一个批判性的回顾）。Freeman在19791980年定义并检测了三种不同结构的向心性概念，使得此领域的用辞和术语变得明晰。买卖网络，是经济网络的一个具体分支，代表了一个对经济无论从理论还是经验的研究都比较新的领域。Kranton和Minehart在早期对组成特殊网络结构中买卖双方的个体行为十分感兴趣，并做了研究。Ninshigushi1994年在Japaneseelectronicsindustry，Lazerson1993年在Italiangarmentindustry也做了研究。特别的是，他们想知道是什么使得买卖双方各自建立对多个交易伙伴的连接关系；然后评价这些网络结构是否能够有效率的工作。1.2经济网络研究的最新发展网格技术网络的出现，改变了人们使用计算机的方式，而Internet的出现，又改变了人们使用网络的方式。纵观互联网的发展历程，Internet技术和Web技术的主要成就是实现了计算机和网页的连通，提供收发邮件、浏览和下载网页信息等相关服务，它所关注的问题是如何使信息传输流量更大、传输速度更快、传输更加安全。而网格技术则关注如何有效安全地管理和共享连接到Internet上的各种资源，并提供相应的服务，网格所关注的问题无论从范围、程度还是本质上都已经与互联网所关心的互连问题有了很大的不同。网格在连通计算机和网页的基础上，还将各种信息资源，例如数据库、软件以及各种信息获取设备都连接成一个整体，整个网络如同一台巨大无比的计算机，向每个用户提供包括计算能力、数据存储能力以及各种应用工具等一体化的透明服务。它强调的是全面地共享资源、全面地应用服务。目前的技术还没有实现资源层面的全面共享，只是信息的传输，所以属于网络技术，而非网格技术。互联网新一次浪潮的实质，就是要将万维网（WorldWideWeb）升华为网格（GreatGlobalGrid），即实现WWW到GGG的变革。网格作为一个集成的计算与资源环境，能够吸收各种计算资源，将它们转化成一种随处可得的、可靠的、标准的且相对经济的计算能力，其吸收的计算资源包括各种类型的计算机、网络通信能力、数据资料、仪器设备甚至有操作能力的人等各种相关资源。网格是借鉴电力网的概念提出的，网格的最终目的是希望用户在使用网格计算能力解决问题时像使用电力一样方便，用户不用去考虑得到的服务来自于哪个地理位置，由什么样的计算设施提供。也就是说，网格给最终的使用者提供的是一种通用的计算能力。电力网中需要有大量的变电站等设施对电网进行调控，相应的网格中也需要大量的管理站点来维护网格的正常运行。网格的结构及资源的调控将更复杂，需要解决的问题也更多。因为网格所关心的问题不再是文件交换，而是直接访问计算机、软件、数据和其他资源。这就要求网格具备解决资源与任务的分配和调度、安全传输与通信实时性保障、人与系统以及人与人之间的交互等能力。网格提供的资源是随时间动态变化的，原来拥有的资源或者功能，在下一时刻可能就会出现故障或者拒绝被使用，而原来没有的资源，可能随着时间的进展会不断加入进来。一、网络的典型体系结构网格技术不断地发展使人们逐渐地意识到了网格体系结构的重要性。网格体系结构用来划分系统的基本组件，指定系统组件的目的和功能，说明组件之间如何相互作用，规定了网格各部分相互的关系与集成的方法。可以说，网格体系结构是网格的骨架和灵魂，是网格技术中最核心的部分。1五层沙漏结构五层沙漏结构是一种早期的抽象层次结构，以“协议”为中心，强调协议在网格的资源共享和互操作中的地位。通过协议实现一种机制，使得虚拟组织的用户与资源之间可以进行资源使用的协商、建立共享关系，并且可以进一步管理和开发新的共享关系。这一标准化的开放结构对网格的扩展性、互操作性、一致性以及代码共享都很有好处。图1为五层沙漏结构的典型结构图。五层结构之所以形如沙漏，是由各部分协议数量的分布不均匀引起的。考虑到核心的移植、升级的方便性，核心部分的协议数量相对比较少(例如Internet上的TCP和HTTP)，对于其最