基于Gridsim遗传算法对组合双向拍卖问题的研究.doc

本 科 毕 业 设 计（论文） 基于Gridsim和遗传算法对组合双向拍卖问题的研究 摘 要 在计算机和网络技术高速发展的今天，计算机的用户对计算量的需求和拥有呈现一种不合理分配的状态：即有些大需求的用户拥有资源较少不能满足需求，而小需求的用户使得其拥有的资源闲置。人们希望像家庭用电一样来使用计算资源，这需要通过网络来完成，如同家庭用电通过电网来传输。于是越来越多的人开始关注如何使连入网络的计算机的资源合理分配。 为了在目前的互联网状态下解决此问题，需要推出成熟的新协议。在这之前，在小范围内的模拟资源调度是必不可少的。于是网格计算应运而生，结合各种经典计算方法，在此领域中有了很多新的应用形式。与此同时，一些经济现象也出现在这种资源调度的过程里，例如拍卖。 遗传算法是解决货郎担问题(VSP)，车辆路径调度问题(VRP)等NP问题的成熟算法。本文中需要解决的问题也是一个NP问题，故选择使用遗传算法作为工具。 本文需要解决的问题是利用遗传算法解决组合双向拍卖的用户和资源的选择问题，再利用由澳大利亚墨尔本大学Rajkumar Buyya领导开发Gridsim在Java环境下进行资源调度的仿真。经过多次实验，以上两个问题得到了较好的解决。本文对遗传算法中的参数设置进行了多次对比实验，得出了特定例子的近似最优设置，为使用遗传算法解决此类问题提出了一些建议和方法。 关键字 网络资源调度 网格计算 组合双向拍卖 遗传算法 Gridsim The Design and Realization of Interactive Demonstration System of the Protocol of VPNNAT ABSTRACT At present, the distribution of computation resources among computer users all over the world has shown a unreasonable state: that some users who have 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 way 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 applications 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 optimizing 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 ou