《基于Gridsim和遗传算法对组合双向拍卖问题的研究毕业论文》由会员分享，可在线阅读，更多相关《基于Gridsim和遗传算法对组合双向拍卖问题的研究毕业论文（33页珍藏版）》请在金锄头文库上搜索。
1、本 科 毕 业 设 计（论文）题目: 基于Gridsim和遗传算法对组合双向拍卖问题的研究姓 名 2008年 6月基于Gridsim和遗传算法对组合双向拍卖问题的研究摘 要在计算机和网络技术高速发展的今天，计算机的用户对计算量的需求和拥有呈现一种不合理分配的状态：即有些大需求的用户拥有资源较少不能满足需求，而小需求的用户使得其拥有的资源闲置。人们希望像家庭用电一样来使用计算资源，这需要通过网络来完成，如同家庭用电通过电网来传输。于是越来越多的人开始关注如何使连入网络的计算机的资源合理分配。为了在目前的互联网状态下解决此问题，需要推出成熟的新协议。在这之前，在小范围内的模拟资源调度是必不可少的。
2、于是网格计算应运而生，结合各种经典计算方法，在此领域中有了很多新的应用形式。与此同时，一些经济现象也出现在这种资源调度的过程里，例如拍卖。遗传算法是解决货郎担问题(VSP)，车辆路径调度问题(VRP)等NP问题的成熟算法。本文中需要解决的问题也是一个NP问题，故选择使用遗传算法作为工具。本文需要解决的问题是利用遗传算法解决组合双向拍卖的用户和资源的选择问题，再利用由澳大利亚墨尔本大学Rajkumar Buyya领导开发的Gridsim在Java环境下进行资源调度的仿真。经过多次实验，以上两个问题得到了较好的解决。本文对遗传算法中的参数设置进行了多次对比实验，得出了特定例子的近似最优设置，为使用
3、遗传算法解决此类问题提出了一些建议和方法。关键字 网络资源调度 网格计算 组合双向拍卖 遗传算法 GridsimThe Design and Realization of Interactive Demonstration System of the Protocol of VPN&NATABSTRACTAt present, the distribution of computation resources among computer users all over the world has shown a unreasonable state: that some users who h
4、ave heavy demands own comparatively lesser resources when the resources of users that have little demands are left unused. People want to utilize the computation resources as convenient as electricity in their house. So there is a growing number of people who devote themselves to figuring out the wa
5、y of scheduling resources of this kind.It can be imagined that a new fully-fledged protocol should be applied to solve the problem above. Before this happened, simulations of resource scheduling in an area-wide are required. So grid-computation has emerged because of this opportunity and varies of a
6、pplications appear when lots of classic algorithms are added in. Simultaneously, some economic phenomenon presented in the process of resources scheduling, for instance, the auction.Genetic algorithm have been a mature method to solve NP problems like VSP and VRP. One problem in this article, the op
7、timizing of selection of users and resources in combinational auctions, is also an NP problem. Considering GA is very robust and popular, so we take genetic algorithm for the tool to slove the problem.In this article, we figure out the way to decide which users and resources suppliers will be select
8、ed to join the final trade with genetic algorithm. Then we start the trade simulation of this chosen users and suppliers on the platform of Java combine with gridsim which have been exploiting by the group that leaded by Rajkumar Buyya in University of Melbourne in Australia. The two main targets ab
9、ove are sloved well, and some analyzation of solving user choosing problems by using genetic algorithm are presented at the end.KEY WORDS Resources Scheduling in Network Grid computation Combinational auction Genetic algorithm Gridsim目 录第一章经济网络简介51.1经济网络研究的起源与应用51.2经济网络研究的最新发展网格技术61.3Gridsim开发平台简介10
10、1.4组合双向拍卖简介101.4.1拍卖的概念101.4.2拍卖的竞价方式101.4.3组合双向拍卖11第二章基于Gridsim模拟组合双向拍卖122.1问题描述122.2解决过程122.2.1主要流程122.2.2body()函数的设计132.3结果对比14第三章遗传算法简介183.1遗传算法定义183.2遗传算法特点193.3遗传算法应用193.4遗传算法现状203.5遗传算法的一般算法21第四章模拟退火算法简介234.1模拟退火算法简介234.2模拟退火算法的模型234.3模拟退火算法的简单应用244.4模拟退火算法的参数控制问题26第五章基于遗传算法解决用户资源选择问题265.1待解决
11、问题描述265.2设计思路275.2.1染色体编码275.2.2初始种群选择275.2.3适应函数的设计285.2.4选择双亲285.2.5交配285.2.6变异及不可行解处理285.2.7进化295.2.8跳出条件295.2.9算法描述295.3实验分析305.3.1结果对比305.3.2算法中参数对结果影响的讨论31第一章经济网络简介1.1经济网络研究的起源与应用在信息量膨胀的今天，网络上有关经济的搜索量急剧上升。众多证据表明，网络对社会和经济的推动作用是十分重要的。很多著名的例子已经说明了网络在求职上面（Holzer 1987, Montgomery 1991），交易（ Lazerson
12、 1993, Nishiguchi 1994）,促进信贷（McMillan and Woodruff 1999），互助保险（Fafchamps and Lund 2001），以及福利参与（Bertrand,Luttmer, and Mullainathan 2000）上的积极作用。由于之前极少有对网络具有实验性工作，渐渐的，经济网络的理论研究引起了人们浓厚的兴趣。在当时，关于网络的实验工作数量仍然很少，但相关文献已经开始出现。这些论文出现的目的是对目前存在的实验性工程的一个概括，并指出对该领域未来研究的一些道路。 在实验室里完成的实验为分析经济问题提供了一些强大的，有帮助的技术。实验的主要优点
13、在于控制变量的能力（例如花费，信息，时间等）。这些变量很可能影响个人和集体的行为，而在现实中，这些也许是无法模拟的。博弈理论为特殊模型中的假设提供了精确的公式，所以和理论模型一样，这种被设计好的实验对于使经济学变成一个经验主义的科学来说，是关键的因素。 在经验主义的经济学家发现经济网络之前，另外的一些社会学家已经着手调查各个领域中现有的网络效应。也许最早的网络实验就是五十年代早期，在麻省理工的社会心理学家Alex Bavelas和他的同事进行的“MIT experiments”。在这些实验中，一组中的每个人都被分配解决一个问题。有代表性的是，每个人都拿到了一张标有很多不同符号的卡片。他们的任务
14、是找到所有人都有的一个符号。每个人可以通过写纸条的方式交流，但仅限于通过外部设置好的一个网络来传递信息。Bavelas和他的同事提出了四种网络结构：链式，圈式，星式，Y式，后来发现，星式和Y式是解决问题最快的网络。而且如果限定传送信息的条数，用这种网络可以得到最少的错误。在接下来的几年里，通信的向心性以及网络的组成的效果被更加深入的研究。（可以参考Shaw在1964年做的一个批判性的回顾）。Freeman在19791980年定义并检测了三种不同结构的向心性概念，使得此领域的用辞和术语变得明晰。 买卖网络，是经济网络的一个具体分支，代表了一个对经济无论从理论还是经验的研究都比较新的领域。 Kra
15、nton和Minehart在早期对组成特殊网络结构中买卖双方的个体行为十分感兴趣，并做了研究。Ninshigushi 1994年在Japanese electronics industry，Lazerson 1993年在Italian garment industry也做了研究。特别的是，他们想知道是什么使得买卖双方各自建立对多个交易伙伴的连接关系；然后评价这些网络结构是否能够有效率的工作。1.2经济网络研究的最新发展网格技术网络的出现，改变了人们使用计算机的方式，而Internet的出现，又改变了人们使用网络的方式。纵观互联网的发展历程，Internet技术和Web技术的主要成就是实现了计算机和网页的连通，提供收发邮件、浏览和下载网页信息等相关服务，它所关注的问题是如何使信息传输流量更大、传输速度更快、传输更加安全。而网格技术则关注如何有效安全地管理和共享连接到Internet上的各种资源，并提供相应的服务，网格所关注的问题无论从范围、程度还是本质上都已经与互联网所关心的互连问题有了很大的不同。网格在连通计算机和网页的基础上，还将各种信息资源，例如数据库、软件以
