《基于Gridsim和遗传算法对组合双向拍卖问题的研究毕业论文.doc》由会员分享，可在线阅读，更多相关《基于Gridsim和遗传算法对组合双向拍卖问题的研究毕业论文.doc（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技术的主要成就是实现了计算
16、机和网页的连通，提供收发邮件、浏览和下载网页信息等相关服务，它所关注的问题是如何使信息传输流量更大、传输速度更快、传输更加安全。而网格技术则关注如何有效安全地管理和共享连接到Internet上的各种资源，并提供相应的服务，网格所关注的问题无论从范围、程度还是本质上都已经与互联网所关心的互连问题有了很大的不同。网格在连通计算机和网页的基础上，还将各种信息资源，例如数据库、软件以及各种信息获取设备都连接成一个整体，整个网络如同一台巨大无比的计算机，向每个用户提供包括计算能力、数据存储能力以及各种应用工具等一体化的透明服务。它强调的是全面地共享资源、全面地应用服务。目前的技术还没有实现资源层面的全面
17、共享，只是信息的传输，所以属于网络技术，而非网格技术。互联网新一次浪潮的实质，就是要将万维网（World Wide Web）升华为网格（Great Global Grid），即实现WWW到GGG的变革。 网格作为一个集成的计算与资源环境，能够吸收各种计算资源，将它们转化成一种随处可得的、可靠的、标准的且相对经济的计算能力，其吸收的计算资源包括各种类型的计算机、网络通信能力、数据资料、仪器设备甚至有操作能力的人等各种相关资源。 网格是借鉴电力网的概念提出的，网格的最终目的是希望用户在使用网格计算能力解决问题时像使用电力一样方便，用户不用去考虑得到的服务来自于哪个地理位置，由什么样的计算设施提供。
18、也就是说，网格给最终的使用者提供的是一种通用的计算能力。 电力网中需要有大量的变电站等设施对电网进行调控，相应的网格中也需要大量的管理站点来维护网格的正常运行。网格的结构及资源的调控将更复杂，需要解决的问题也更多。因为网格所关心的问题不再是文件交换，而是直接访问计算机、软件、数据和其他资源。这就要求网格具备解决资源与任务的分配和调度、安全传输与通信实时性保障、人与系统以及人与人之间的交互等能力。网格提供的资源是随时间动态变化的，原来拥有的资源或者功能，在下一时刻可能就会出现故障或者拒绝被使用，而原来没有的资源，可能随着时间的进展会不断加入进来。 一、网络的典型体系结构 网格技术不断地发展使人们
19、逐渐地意识到了网格体系结构的重要性。网格体系结构用来划分系统的基本组件，指定系统组件的目的和功能，说明组件之间如何相互作用，规定了网格各部分相互的关系与集成的方法。可以说，网格体系结构是网格的骨架和灵魂，是网格技术中最核心的部分。 1五层沙漏结构 五层沙漏结构是一种早期的抽象层次结构，以“协议”为中心，强调协议在网格的资源共享和互操作中的地位。通过协议实现一种机制，使得虚拟组织的用户与资源之间可以进行资源使用的协商、建立共享关系，并且可以进一步管理和开发新的共享关系。这一标准化的开放结构对网格的扩展性、互操作性、一致性以及代码共享都很有好处。图1为五层沙漏结构的典型结构图。应用层汇集层资源层连
20、接层构造层应用程序，工具目录服务，资源分配 资源检测诊断，负荷控制，日程安排资源与服务的安全访问可供共享的资源物理实体和逻辑实体图1 五层沙漏的典型结构五层结构之所以形如沙漏，是由各部分协议数量的分布不均匀引起的。考虑到核心的移植、升级的方便性，核心部分的协议数量相对比较少 (例如Internet上的TCP和HTTP)，对于其最核心的部分，要实现上层协议（沙漏的顶层）向核心协议的映射，同时实现核心协议向下层协议（沙漏的底层）的映射。按照定义，核心协议的数量不能太多，这样核心协议就成了一个协议层次结构的瓶颈。在五层结构中，资源层和连接层共同组成这一核心的瓶颈部分，它促进了单独的资源共享。 2.
21、开放网格服务结构 开放网格服务结构OGSA是Global Grid Forum4的重要标准建议,是目前最新也最有影响力的一种网格体系结构，被称为是下一代的网格结构。OGSA的目的就是要将Grid的一些功能，更确切的说是Globus的一些功能融合到Web Service这个框架中。与前期网格不同的是，OGSA是面向服务的结构，将所有事务都表示成一个Grid服务，计算资源、存储资源、网络、程序、数据等都是服务，所有的服务都联系对应的接口，所以，OGSA被称为是以服务为中心的“服务结构”，通过标准的接口和协议支持创建、终止、管理和开发透明的服务，其发展象征着Web Service的一个进步，结合目前
22、的Web Service技术，支持透明安全的服务实例，OGSA有效地扩展了Web Service架构的功能。五层模型与OGSA都相当重视互操作性，但OGSA更强调服务的观点，将互操作性问题转化为定义服务的接口和识别激活特定接口的协议。这一面向服务模型具有很多优点，环境中的所有组件都是虚拟化的，通过提供一个所有Grid服务实现基础的一致接口的核心集，可以使得分级的、更高级别的服务的构建能够跨多个抽象层以一种统一的方式进行处理。虚拟化还促使从多个逻辑资源实例到同一物理资源的映射，不考虑实现的服务组合，以及一个VO内的基于低级资源组合的资源管理。正是Grid服务的虚拟化加强了通用服务语义行为无缝地映
23、射到本地平台设施的能力。 二、网格协议Globus工具包 由于现在的互联网结构并不是针对网格计算设计的，为了使网格计算和现有的结构兼容，一个可扩展的中间件是必需的，也就是基于操作系统之上的网格管理软件。在网络化应用成为主流的时代，单机操作系统如NT、Windows等的地位已经降低，网格管理软件实际上是更高层次的网格操作系统，其核心技术主要是一体化的信息平台、语义网站、智能代理和知识本体技术等。建立网格服务的协议与标准是网格发展的重点和难点。Globus项目是目前国际上最有影响力的与网格计算相关的项目之一，是来自世界各地关注网格技术的研究人员和开发人员共同努力的成果。它是围绕四种主要活动来组织的
24、：研究、软件工具、实验台和应用程序。Globus对资源管理安全、信息服务及数据管理等网格计算的关键技术进行研究，开发能在各种平台上运行的网格计算工具软件，帮助规划和组建大型的网格实验平台，开发适合大型网格系统运行的大型应用程序。Globus工具包是Globus最重要的实践成果，它是一个开放源码的关键Grid协议的参考实现，支持大量的主要的电子科学项目。该工具包基于开放结构、开放服务资源和软件库并支持网格和网格应用，致力于安全、信息发现、资源管理、数据管理、通信错误诊断等问题。Globus的网格计算协议是建立在互联网协议之上的，以互联网协议中的通信、路由、名字解析等功能为基础。Globus的协议
25、分为5层：构造层、连接层、资源层、汇聚层和应用层。上层协议可调用下层协议的服务。网格内的全局应用都通过协议提供的服务来调用操作系统。Globus工具包包括网格安全、网格信息获取与分布、网格资源管理及网格远程传输等内容，这些都是网格开发中的关键技术和必须解决的重要问题。 三、网格核心技术 为解决不同领域复杂科学计算与海量数据服务问题，人们以网络互连为基础构造了不同的网格，有代表性的如计算网格、拾遗网格、数据网格等，它们在体系结构和需要解决的问题类型等方面不尽相同，但都需要共同的关键技术，主要有如下几种: 高性能调度技术 在网格系统中，大量的应用共享网格的各种资源，如何使得这些应用获得最大的性能，
26、这就是调度所要解决的问题。网格调度技术比传统高性能计算中的调度技术更复杂，这主要是因为网格具有一些独有的特征，例如，网格资源的动态变化性、资源的类型异构性和多样性、调度器的局部管理性等。所以网格的调度需要建立随时间变化的性能预测模型，充分利用网格的动态信息来表示网格性能的波动。在网格调度中，还需要考虑移植性、扩展性、效率、可重复性以及网格调度和本地调度的结合等一系列问题。 资源管理技术 资源管理的关键问题是为用户有效地分配资源。高效分配涉及到资源分配和调度两个问题，一般通过一个包含系统模型的调度模型来体现，而系统模型则是潜在资源的一个抽象，系统模型为分配器及时地提供所有节点上可见的资源信息，分
27、配器获得信息后将资源合理地分配给任务，从而优化系统性能。 网格安全技术 网格计算环境对安全的要求比 Internet的安全要求更为复杂。网格计算环境中的用户数量、资源数量都很大且动态可变，一个计算过程中的多个进程间存在不同的通信机制，资源支持不同的认证和授权机制且可以属于多个组织。正是由于这些网格独有的特征，使得它的安全要求性更高，具体包括支持在网格计算环境中主体之间的安全通信，防止主体假冒和数据泄密；支持跨虚拟组织的安全；支持网格计算环境中用户的单点登录，包括跨多个资源和地点的信任委托和信任转移等。 网格研究最初的目标是希望能够将超级计算机连接成为一个可远程控制的元计算机系统（MetaCom
28、puters），现在，这一目标已经深化为建立大规模计算和数据处理的通用基础支撑结构，将网络上的各种高性能计算机、服务器、PC、信息系统、海量数据存储和处理系统、应用模拟系统、虚拟现实系统、仪器设备和信息获取设备（例如传感器）集成在一起，为各种应用开发提供底层技术支撑，将Internet变为一个功能强大、无处不在的计算设施，最终实现资源共享和分布协同工作。网格的这种概念可以清晰地指导行业和企业中各个部门的资源进行行业或企业整体上的统一规划、部署、整合和共享，而不仅仅是行业或大企业中的各个部门自己规划、占有和使用资源。这种思想的沟通和认同对行业和企业是至关重要的，将提升或改变整个行业或企业信息系统
29、的规划部署、运行和管理机制。1.3Gridsim开发平台简介GridSim由澳大利亚墨尔本大学Rajkumar Buyya领导开发，它的首要目标是通过模拟来研究基于计算经济模型的有效资源分配方法。GridSim通过资源的买和卖来引入经济模型，从而达到控制网格资源的使用的目的。 GridSim是在SimJava的基础上开发的，它提供丰富的函数库以支持模拟网格环境中的异构资源(时间共享和空间共享)，用户，应用程序,用户代理和调度器。网格资源,用户和用户代理被视为不同的实体，它们通过消息事件(输入和输出)来进行通信。除了通过手工编程来实现模拟外，GridSim还提供了一套图形界面工具Visual M
30、odeler(VM)帮助用户配置网格环境并产生相应的代码。模拟结束后，用户可以调用GridSim中的称为GridStatistics的库函数来收集各种模拟的统计数据。1.4组合双向拍卖简介1.4.1拍卖的概念 拍卖是专门经营拍卖业务的拍卖行接受货主的委托，在规定时间和地点，按照一定的章程和规则，将货物公开展示，由买主出价竞购，把货物卖给出价最高的买主。1.4.2拍卖的竞价方式增价拍卖，又称英国式拍卖，这是最常见的一种拍卖方式。拍卖时，由拍卖人宣布预定的最低价，然后竟买者相继出价竞购。拍卖行可规定每次加价的金额限度。至某一价格，经拍卖人三次提示而无人加价时，则为最高价，由拍卖人击槌表示成交。按拍
31、卖章程规定，在拍卖人落锤前，叫价人可以撤销出价；如果货主与拍卖人事先商定了最低限价，而竟买人的叫价低于该价，拍卖人可终止拍卖。 减价拍卖。又称荷兰式拍卖，源于世界上最大的荷兰花卉拍卖市场，由拍卖人先开出最高价格，然后渐次降低价格，直到有人表示接受，即达成交易。这种拍卖方式买主之间无反复竞价的过程，且买主一旦表示接受，不能再行撤销。由于减价拍卖成交迅速，特别适合于数量大，批次多的鲜活商品。 密封递价拍卖。又称招标式拍卖。由买主在规定的时间内将密封的报价单（也称标书）递交拍卖人，由拍卖人选择买主。这种拍卖方式，和上述两种方式相比较，有以下两个特点：一是除价格条件外，还可能有其他交易条件需要考虑：二
32、是可以采取公开开标方式，也可以采取不公开开标方式。拍卖大型设施或数量较大的库存物资或政府罚没物资时，可能采用这种方式。1.4.3组合双向拍卖基于以上的基本拍卖方式，我们似乎可以找到很多种适合网格资源拍卖的方式方法。而本题目所要研究的问题，是组合双向拍卖，下面来扼要介绍一下组合双向拍卖的机制以及特点。以上所介绍的英式拍卖以及荷兰式拍卖均为简单的单向拍卖方式，那么什么是双向拍卖呢？单向拍卖，意即买卖双方只有一方调整价格，而与之相对应的双向拍卖，则是买卖双方均要调整价格，以期快速达成交易。这种方式，显然会比荷兰式拍卖更加快速的完成交易。“双向”介绍完了，那么“组合”的概念是什么呢？在本文研究的范围里
33、，虚拟的网格资源从简单的计算资源扩展到了三种虚拟资源：计算资源，存储资源，带宽资源。每一台电脑，或者说每一个买家都可能需求不同数量的这三种资源，而每一个资源提供者也都可能提供不同数量的三种资源。这个问题显然要比单件物品的英式拍卖或荷兰式拍卖要复杂的多，我们当然不会像真正拍卖那样随机出价，这样的出价是不理性也不适合网格资源分配的交易理念的。对组合双向拍卖的具体的设计解决过程详见后文第四章“基于Gridsim模拟组合双向拍卖”。从以上的基本描述可以看出，双向拍卖这种出价形式要比单向拍卖从时间上和金钱上都更容易达成交易。买方卖方均以一折中的价格购买或出售商品，这同时也很大程度上促进了交易量的提升。经
34、典的英国式拍卖由于最终价格过高最后成交的人数是很有限的，这不符合网络资源合理分配的理念，与网格计划背道而驰；而荷兰式拍卖又在一定程度上可能损害出售者的积极性，因为从现今来看，网络中的购买者总是希望甚至可以说十分吝啬的对自己需求的商品给极低的出价，所以荷兰式拍卖很可能到这样一个局面：普遍价格都被消费者压得很低，导致出售者的利益被大大损害。故此双向拍卖的折中方法比较适合网络资源的交易。而组合的方式更加仿真，因为日后的世界网格里不会只有计算资源这一种资源，所以此研究具有一定的适应性。第二章基于Gridsim模拟组合双向拍卖2.1问题描述此阶段的主要工作内容是通过Gridsim工具包来创建用户资源并编
35、写资源调度函数body()来实现组合双向拍卖的过程。此过程是在Gridsim中关于auction的例子Example_6上修改的，这个例子原先是模拟单向拍卖过程的一段程序，修改上主要需要把单一的计算资源分为三种资源，同时修改用户创建函数中的参数，使之有三种资源的需求并且提交任务时可以与三种资源相结合。调用startGridsimulation的时候会自动调用编写好的body()函数，这里的body()函数是修改的重点，需要重新编写判断用户寻找资源并提交任务的方法。2.2解决过程2.2.1主要流程1 通过初步设置买家卖家个数以及需求提供数量和出价，使用遗传算法来确定要参与的买家和卖家。由于可对比
36、的结果目前只是有一个6买方，10卖方例子的最优解，故此处设计的参数值为6和10，后面的两个50指的分别是初始种群规模和判断进化停止的代数。遗传算法相关见后续章节。Totalusers test = new Totalusers(6, 10, 50, 50); 2 初始化Gridsim包，其中的参数均为原Gridsim类中必需的参数。GridSim.init(num_user, calendar, trace_flag, exclude_from_file,exclude_from_processing, report_name);3 初始化用户信息。将遗传算法需要用到的出价和需求提供数量直接赋
37、值给用户里的参量。由于遗传算法需要的是用户的总出价，而模拟组合双向拍卖需要的是用户的平均出价，所以再计算出平均出价来重新赋值给出价。userj = new Example6(User_ + i, 560.00, total_resource, test.ask_supplyi*3, test.ask_supplyi*3+1, test.ask_supplyi*3+2, bidsj); bidsn = bidsn/(putation + usern.storage + usern.bandwidth);4 初始化资源信息，基本和初始化用户信息相同。但由于资源数量是用户的三倍，故麻烦了一些，不再赘
38、述。5 启动Gridsim仿真系统，这是gridsim.jar中自带的函数，会调用body()来完成仿真，body()函数则需要使用者根据需要来编写。原先的Example_6是单向拍卖的body()函数，所以基本上完全重写了。到此仿真结束。GridSim.startGridSimulation();2.2.2body()函数的设计1 选择当前竞争力最强的用户if (averagebid usersi.averagebid & usersi.finished != true) break; else if (i = numofuser-1) start = true;2 当前最优用户对资源的选择
39、while (resource_numsid = 0) id += 3; for (j = 0; j this.totalResource_/3; j+) if (g = = 0) if (averagepricej min & resource_nums3*j != 0) min = averagepricej; id = 3*j; if (g = = 1) if (averagepricej min & resource_nums3*j+1 != 0) min = averagepricej; id = 3*j+1; if (g = 2) if (averagepricej min & r
40、esource_nums3*j+2 != 0) min = averagepricej; id = 3*j+2; 3 完成当前用户所有任务并提交，此处代码多为Gridsim.jar中已被封装的函数。大意是某用户从某资源提供者得到资源并输出此过程，并计算各类参数例如虚拟交易时间，虚拟交易货币等等，与本文关联不大，此处不多赘述。2.3结果对比此处模拟过程的结果对比意义在于证明程序的正确性，直接利用已有的一个结果来做比较。此结果是下面这个6用户，10资源提供者经验证的正确结果：收入66 A B C PA B C P1 0 3 3 104*9 -2 -3 -1 -802 4 3 3 13610 -1
41、-3 0 -363 3 3 4 14411 -2 -2 0 -38*4 2 0 1 3312 0 -1 -3 -705 4 3 2 12513 -3 -3 -1 -936 1 5 1 93*14 -2 0 -3 -717 0 -2 -2 -5915 0 -3 -3 -768 -3 -2 -3 -11016 -3 -1 -1 -54其中序号16的为买家，716的为卖家，序号前带*号的表示被遗传算法抛弃的单位，不能参与交易。所以真正参与交易的是买家1 2 3 5 6和卖家7 8 10 11 12 13 15 16，相当于是5买家，8卖家。根据买卖双方的竞争力分别排序如下（括号内数字为程序）：买家按
42、照平均价格降序排列 卖家按照平均价格升序排列 A B C A B C (0)1： 03317.3 (2)10： 1 309(2)3： 33414.4 (3)11： 2 209.5(4)5： 43213.9 (7)16： 3 1110.8(1)2： 43313.6 (6)15； 0 3312.7(5)6； 15113.2 (5)13： 3 3113.3 (1)8 ： 3 2313.8 (0)7 ： 0 2214.8 (4)12： 0 1317.5最后的正确交易结果如下：1 get 3B from 10 for 13.21 get 1C from 16 for 14.11 get 2C from 15 for 15.03 get 1A from 10 for 11.73 get 2A from 11 for 12.03 get 2B from 11 for 12.03 get 1C from 15 for 13.63 get 1C from 13 for 13.93 get 2C from 8 for 14.15 get 3A from 16 for 12.45 get 1A from 13 for 13.65 get 3B from 13 for 13.35 get 1C from
