基于溢出性原理的联盟结构生成算法分析

《基于溢出性原理的联盟结构生成算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、绪论1绪论1．1研究背景和意义自然界中，合作是普遍存在的。动物社会中，出于本能，也为了更好地牛存。它们会形成4i同的合作团体。比如，动物在觅食的过程中会分．T和合作。又比如排成人字形或者一字型的大雁，是最好的飞行方式⋯。这将更加有利于它们的迁徙，因为它们借助彼此的羽翼产生的空气动力，大大减少了飞行的阻力。而人与人之间则通过理性产生不同的合作，形成各式各样的合作团体。例如政党，民间组织，公益经济组织，甚至是临时的团体，比如拼车一族。团体中的人们协调彼此的行为，交流合作无间。开放的分布式计算的J’+泛应用，使得各种团体的合作也U益频繁。多个agent组成一个多agent系统(MAS)，

2、在这样的复杂的环境下，agent产生相互作用是不口J‘避免的，．日．他们在agent系统中的行为并非都口J．以预知。多Agent系统MAS(Multi-agentsystems)的研究成为分布式人工智能研究的热点。MAS丰要研究自主的智能体之间智能行为的协调，它们会为了一‘个共同的任务互相协作，互相配合，通过有关问题和求解方法的知识的共享，最终进行问题的求解。根据现有Agent的概念，人工智能有了新的定义：“人工智能是计算机科学的一个分支，它的目标是构造能表现出一定智能行为的agent”幢’。所以，Agent的研究是人工智能的主要领域之一。联盟可以这样定义：由合作产生的合作团体。联

3、盟主要应用与联盟博弈中，比如特征函数论。怎样形成联盟，形成联盟后如何分配收益，是博弈论研究中的一个重要问题，这就是联盟博弈。联盟博弈是博弈论的一个蕈要方面，日益引起人们的关注，模拟真实的环境是其中的一个重要的原因。在特定的环境中．多智能体为达到特定的目标而相互合作，形成联盟，在研究开发协议和政治活动巾都有广泛的应用，其巾在自动协商和电子商务巾尤为突出m一1。在多agent系统叶l，哪些agent会形成联盟，如何形成联盟和联盟结构是主要课题。对此，对策论提供了解决问题的方案，即在确定的博弈中，挑选稳定的结粜。但是这样的挑战性较高，原因在于MAS中的agent形成的联盟的数日是按照{f

4、}彳数增K的。当agent个数比较火时，要想穷尽搜索足很困难的。绪论Agent为更好的完成日标本身具备自主的决策能力，根据特定的环境，单个agent可以被定义为独立的计算机系统。自主性就是指各个代理在作出各自的决策时不受人或者其他因素控制的一种能力特性。针对具体目标，每个agent都有自身的一套行为可供选择。通过自主决策对群体的收益产生作用。关键问题是这些独立的agent采取何种行为才可以达到预期目标。如果一个agent能够灵活作出自丰行为，则可以认为它是智能的。除了智能性以外，agent还有实践性，反应性，社会性等性质，都可以包括在agent的灵活性当中，文中把MAS系统LfJ的

5、agent都默认为是智能的，这是在科学研究中最多的，在实际的应用中也多是这样旧1。在如今的应用研究中，agent被定义为相互协作的，以提高整个多agent系统的整体收益为目的，而不是为了个体本身。而在其它的应用中，各个agent之间是相互竞争的，冈为它们的目标不同。当agent之间相互竞争时，这些agent被认为是自私的。在此种情况下，需要做一些设定，强迫再个agent采取以系统收益最大化作为自己行为选择的宗旨。竞争的实质其实足就是博弈。不管是合作还是竞争，实验的设计者都要确保agent经过严街的组织，确定各个agent的任务以及它们相互之间的关系，联盟和联盟结构的不同层次等。不同

6、的组织规范适应的问题不同。联盟的特殊性质使得它在多agent系统中具有极其重要的应用。联盟中的agent小存在中枢代理，但是却可以解决代理问因为相互作用所产生的可能冲突。因为agent联盟在电了商务，传感器网络，行程安排等方面的应用日渐引起人们的关注b，。1．2国内外研究现状当前，联盟结构的生成问题实际上就是独立自主的agent排列划分形成集合的问题。它在合作博弈理论巾有很深入的研究，最近在多agent系统中是很重要的研究课题，MAS中的agent形成联盟可以实现收益最大化以及提高效率。Agent联盟研究的问题有三个方面m1：(1)联盟结构生成，此领域研究如何对多个agent进行划

7、分，使得整个联盟结构的收益最高，主要关注的足整个联盟结构的总收益，而不足个体收益。(2)联盟值的优化，此领域描述多个agent组成联盟，合伙经营它们的任务、资源、能力，使得这些agent的收益最高。2绪论(3)联盟值的分配，此领域描述如何在组成联盟的多个agent之间进行收益分配，强调agent完成合作取得收益后如何正确有效地进行收益分配，从而建立长期的联盟。本文研究的是agent的第一个问题。联盟结构生成问题日渐引起学者们的关注。联盟结构生成算法，口J．以分为以下几