众所周知，智能体或称为Agent可以通过相互协作来实现他们的共同目标，以提高其整体的性能。在多Agent系统中，这种相互协作通常采用Agent联盟的形式来完成。所谓联盟就是多个同意协作的Agents在一起解决某个共同的问题，这些问题可能是单个Agent很难完成的或者完成的效率没有Agent组合的高。当多个Agent作为Agent联盟形式时，每个Agent都能从联盟获得额外的收益。因此可以看出，联盟形成(CF)是一种将分布的自治的多个Agents联合起来共同解决某个问题有效机制，在这个联盟中，每个Agent个体都有它们自身的能力，当Agents作为联盟工作时，每个Agent在联盟中都有实现了自己的功能价值。由此，在多Agent系统(MAS)中，联盟形成(CF)是十分必要及有用的交互协作形式，它能够以一种有效的方式提高Agent完成任务和实现目标的能力。已经证实，多Agent联盟已经被运用到很多领域，比如:资源分配，合作问题求解，商业交易等多个领域。在资源分配问题中，资源Agents组成联盟来完成服务任务，能完成单个资源Agent不能完成或不能高效完成的服务任务。在合作问题求解时，多个Agents组成联盟共同完成任务，使完成任务的同时能争取整体利益最大化。在商业交易中，Agent与其他个体相互合作，形成联盟，可获得批量折扣，增加自身收益。然而，在实际的应用中面临的主要问题是，怎样在单个Agent的能力有限不能单独完成任务时，通过相互合作的Agent形成联盟的合作形式，从而使Agent更好的实现目标，并实现整体利益的最大化。　　联盟形成问题是MAS研究领域中挑战性问题之一。这个问题的关键是，如何高效的在多Agents之间构建联盟，这也是本论文着力研究的主要内容。对联盟形成的研究主要从两个方面进行，一个是联盟如何形成，它的形成过程，形成方法，形成的模型等，另一个是联盟评估。其中，前者涉及到的是联盟形成方面的（如联盟的结构，联盟值），后者提到的是联盟形成的结果（如收益分配等）。当前大多数研究工作将联盟形成看成一个优化问题，主要是寻找拥有最大效用值的最优联盟，而不是关注联盟的形成问题以及通过哪些有效的方法获得那些合适的联盟结构。毋庸置疑，采用穷尽搜索方式可以找到使Agent组合的全局效用值（比如社会福利）最大化的Agent联盟结构，然而，实际情况是，多Agent系统中的这些Agent都是以分散的形式存在。　　为了某个特定的目标，需要将这些分散的Agent形成联盟来解决问题时，当每个agent都只有其邻居的局部信息时，形成联盟时很难通过穷尽搜索方式找到全局的最优联盟结构。在这些情况下，我们无法找到或者及时的找到全局的最优解，我们不得不考虑次最优解，这些次最优解虽然不能达到联盟的最高性能，但是能满足形成联盟的最低要求。因此，本文致力于提高这类多Agent联盟形成的质量的研究。　　本文的主要贡献也都集中于此，本文主要呈现了多Agent系统中基于Agent图的联盟形成算法。该算法是在分布式多Agent系统中，对来自一个Agent图中的智能体构建联盟。其中，所谓Agent图是指Agent互相关联的拓扑结构图。这种系统是由一些自治Agent构成，这些Agent可以在没有控制中心的情况下自发的与其他Agent对话以及实现它们的功能。因为，真实世界环境中，Agent都是只有局部的不完全信息，在这种情况下要为某个特定的目标形成联盟，我们必须提出并实现一些可行的高效的算法形成联盟。基于上述的分析，它可以通过搜索agent图中的联盟伙伴来实现，这不仅可以提高联盟形成的质量也可以提高联盟形成的效率。　　据此，本文从四个方面进行阐述上述的联盟形成算法研究。第一，提出了一种新型的联盟形成机制，这种联盟机制从一种新的角度考虑了Agent之间的联盟，同时对价值不断变化的Agent之间如何形成联盟也进行考虑。它的优点不在于形成一个最优联盟，而是通过Agent与它的邻居们的协商过程，从协商的Agent集中获得一个有效的联盟集，这些邻居是从Agent图中的邻接点（如，直接相邻的）获取的。在有些情况下，Agent具有完成任务所需的所有功能，因而它可以完全靠自己来完成自己的目标。然而，有些时候Agent的功能有限，不能单个的完成某个任务，或者对某些任务它就无法像其他Agent那样有效的完成。这种情况下，Agent可以通过交流将任务分配给它的邻居。这种分配就可以通过Agent之间的协商来完成，通过协商分配任务给他的邻居以致使任务的完成质量更高。第二，本论文扩展了Agents之间的协作关系，除了Agent图中直接相连的Agents的协作，还包括了间接相连的Agents之间的协作。该协作关系是通过搜索带有权值函数的Agent图实现的。所谓的带有权值函数的图是用来标记联盟的，这种联盟是为了实现特定的目标而存在的。当Agent并没有实现目标所需要的所有能力时，Agent需要和那些能够实现一些子任务的Agents形成联盟，进而完成整个任务。否则，Agent将无法完成整个任务。第三，论文研究自治的Agent如何获得批量的折扣。作为联盟的成员，Agents可以以折扣价的成本实现部分或者全部的目标，从而使Agent获得收益。这表明Agent联盟是根据联盟价值的特定约束形成的。第四，是第三方面的扩张，讨论了如何获得稳定的联盟。本文假设agent是同构的，共享相同的目标，它们可以形成稳定的联盟通过在核中心的收益回报分布。它的稳定性指的是Agent满足一定稳定性条件的花销分担规则。综上，本文重点在于找到实用的解决算法，在现实环境中，通过搜索Agent图中的联盟伙伴形成联盟，以改善联盟的形成过程和联盟形成的质量，这就是本文的主要的研究内容。　　根据前段的阐述，本文首先在Agent和它的邻居之间提出了一种新颖实用的基于模糊逻辑的决策理论的分布式协商模型。运用这种模型可以自动克服复杂的谈判过程，并且可以在Agent拥有邻居的不完全信息的情况下，帮助Agent形成联盟。这种谈判模型是形成有效联盟的基础。该模型包括三个主要的内容:(1)分布式协商模型形成联盟;(2)基于模糊逻辑的评价模型和(3)一组最佳的有效联盟集。　　其中，分布式协商模型采用基于交替提议协商协议，Agent和它们的直接邻居之间可以协商多个议题（如，价格和质量等）。每一方在此过程中都是通过提供建议和反建议进行协商，最终都想达到对自己是最低价格的协议（比如，一个联盟伙伴）。依赖于推理组件模型的模糊评价方式，该部分主要是专注于评估Agent所提的建议，从而决定接受还是拒绝对方的提议，并生成提议，/反提议。它利用一个集合的模糊隶属函数（即低或高）来推理相关数据以及If-Then决策规则来支持灵活的协商过程。用模糊模型做出的决策是依赖于一系列的提议接收的程度，这使得决策更能贴近现实的真实世界，并且拥有更好的灵活性。基于模糊理论的评估包含三个步骤（即模糊化步骤、推理步骤和去模糊化步骤），它能够决定提议是否接收和接受的程度。在模糊化步骤中，定义输入变量的隶属函数应用它们的实际价值来决定真实的程度。在推理步骤中，每个规则的真实值会被计算出来，然后应用到每个规则的结论部分。在一个模糊子集中的结果将会被分配给每个规则的输出变量中，在去模糊化的步骤中，模糊输出结果将会被去模糊化变成一个清晰的数。然后根据每个协商Agent的行为制定相应的协商策略，决定每次提议是接受或拒绝还是重来。比如，Agent利用时间依赖策略与其他Agent协商，当一个协商发生是，Agent都会有一个时间期限。应用时间限制策略的重点在于保证Agent的协商不能是无限期的，相反的，要让协商在一个合理的时间范围（或者是最大回合数）内完成。因此，当一些Agent经过成功的协商完成某个目标后，最有效的联盟集能够在这些Agents中形成。　　利用基于模糊逻辑的方法的原因在于，需要处理关于对手的有限的信息和谈判对手的不同偏好，而模糊逻辑能够很好的解决利用不完整的信息进行推理的问题。采用传统的模型来评估一个多议题的协商提议，太过复杂。而基于模糊逻辑的方法在克服评估提议复杂性上有更突出的实际意义。因此，在本文所提出的这个基于模糊逻辑的模型中，我们应用模糊逻辑建立议题之间的关系（比如价格，交货期限等），并且允许Agent表达它们的偏好，评估系统也是充分考虑Agent的需求（即Agent的效用最大化）。协商的核心是用一个最低价格达成协议并帮助形成一个有效的联盟。我们要考虑的问题在于，协商模型的有效性、实用性，以及如何在Agent图中，以一种分散的形式找到潜在的联盟伙伴。　　本文提出的基于模糊逻辑的协商模型的性能评估通过与其他的传统模型的对比来进行。文章中提到的传统模型包括:1）战术策略模型和2）得分函数模型。在战术模型中，该模型是根据Agent自身的标准来评估和决策提议的接受与否，但这个并不能保证最佳的交易结果，因为它没有考虑Agent在协商过程中的偏好，而且还允许Agent快速让步到它们的保留值以达成协议。虽然在得分函数模型中，Agent在计算提议评估的得分函数时考虑了每个议题的权重，但是它没有考虑在协商过程中所有提出的议题和推理之间的关系。　　仿真实验表明，本文提出的基于模糊逻辑的协商模型，可以在协商Agent中获得更好的协商结果。实验证明基于模糊理论协商模型的协商成功率比战术模型的高了12％，比得分模型的成功率高了34％到48％。并且，它动态的提高了获得有效联盟集的机会，它的最高效率比战术模型提高了27％到70％。在有大量的Agent参入的情况下，与得分模型相比效率高出98％以上。在一个合理分配的时间范围内，模糊理论的决策者协商模型获得的最高效率比得分模型的最高效用值高了44％到86％，通过设置谈判进程的最后期限，以避免无休止的协商，模糊理论的决策者协商模型节省的协商时间与战术模型相比高了35％到65％。在社会福利方面，在大量有Agents参入的情况下，基于模糊理论的模型获得社会福利比战术协商模型高出至少70％在比小数量Agents的情况下，比得分模型高出至少29％的。综上，可以得出结论，本文提出的分布式基于模糊逻辑协商模型比其他模型在提高联盟的形成质量上更加的有实用和高效。　　某些时候联盟伙伴是可以扩展的，也就是联盟的伙伴可以从Agent的直接相邻邻居扩展到它的间接相邻邻居，这样可以为Agent提供更多的机会来实现它们的任务或者求得子任务的解。参入考虑的Agents的数量越多，所组成的联盟的可能性就越多，还有就是每个Agent都有自己的功能，这样整个联盟的功能集就会相应增强了。尤其是当在解决一个任务或者理解为一个实现某个功能时，如果它的直接邻居的资源或能力有限，不通过扩展可能会导致任务的失败，因为在这个集合中没有Agent有能力解决问题。因此，构建一个可行的联盟的联盟伙伴不仅可以从直接邻居获得也可以从有用的间接邻居中获得。我们知道可以从带有加权值的Agent图中可以得到这些邻居，其中有些Agent扮演经纪人的角色，推荐相关Agent，并且获得了一些奖励。如何构建支持间接邻居的多Agent联盟算法，将是本文呢阐述的第二个内容。　　基于上述想法，本文提出的算法是找到次最优可行解算法来实现某个特定的目标，这种次最优可行解它是接近最优最小成本的解，这时Agent不得不找到合适的联盟伙伴来共同完成任务，并形成可行的联盟(FC)。这个可行联盟指的是，为了实现某个特定的任务或目标，联盟中所有的成员可以是间接关联的。在加权Agent图中进行搜索联盟伙伴，形成可行联盟获得最好的或者次最优的解取决与这个搜索过程。求最优最小成本解，搜索过程需要完成对整个图的搜索——完全搜索。虽然，这个最优解保证了全局最小值（即最小成本），但是这是一种不考虑时间和空间复杂度的穷尽搜索方法。市级存在这样的环境因素（比如在有大量的agent和大量的任务的情况下）制约这种最优联盟形成。但是这些因素会促进所有参与联盟的Agent，通过搜寻临近最优可行解来构建协作联盟。这种临近最优可行方案，通过使用一个贪婪算法，在每个搜索阶段，试图从下一个的搜索阶段放弃不良的Agent，从而保证达到在计算复杂度上局部的最小值（相对于它的邻居成本来说是最小的）。　　文章中提到的最优最小成本算法是基于广度优先搜索的(BFS)，通过完全搜索层次化的Agent权重图能够找到全局最优解。其算法的核心思想是:首先，是给出一个Agent的请求，访问与请求动作相关的第一层Agents;然后一层层的检查所有的于此相邻的Agent，这些Agents都是远离访问Agent的;最后将这些访问过的远距离Agents分配到一个新的层。然后继续以相同的方式搜索，检查那些与请求的Agent相邻的Agents，对于那些先前分配到一个层的Agents不做动作。当Agent图中的所有的Agents都被遍历到了，这个过程将会终止，这时用最低成本实现任务的联盟伙伴就已经被找到了。　　本文提出的临近最优可行解算法同样也是基于广度优先搜索方法的，通过扩展那些最接近目标的结点来实现局部最优。在这种方法中，搜索的深度是根据最有可能的结点的深度来的决定的。首先，它有一个提出请求的Agent，作为访问点在第一层访问与请求动作相关的Agent，然后检查那些远离访问Agent的边缘有效Agents（即可以承担请求动作的Agent）。从检查过的Agents中选择出最有前途的Agent（即可以提供最低成本的Agent），进而扩展它的分支作为下个搜索区域，忽略其他的分支Agents。一直重复这个过程，当没有有效的Agent或者没有遗留下需要检查的Agent时，我们将停止搜索，这时，可以为请求动作提供最小成本的可行联盟伙伴已经被找到。临近最优方案算法通过采用子图的形式，在搜索的每一步中，及时在每个子图中（即以最少的成本，提供动作）消除没有用Agents（顶点）。可以得出，临近最优解算法在降低计算复杂度方面比最优最低开销的算法更加实用。通过最可行的Agent邻居进行搜索，集中根据这个目标，可以通过临近最优解决方案实现局部最优解。这种解相对于全局最优解具有较低的平均处理时间和较小的区域复杂性，它更适用于现实世界中构建协作联盟。　　通过实验的仿真和验证，本文提出的临近最优可行解算法获得的平均效用值为最优最小成本解算法得到平均效用值的91％至97％之间。根据性能比，临近最优的可行解，可以保证解的质量不逊于最优解的91％。虽然，最优最小成本的解能够得到全局最优效用值，但临近最优可行算法解决方案在实现局部最优上是非常有效和实用的。随着Agents数目增加，临近最优可行算法具有较低的处理时间形成可行的联盟，其时间复杂性是最优最低成本算法的42％到57％，之间下降到32％。这些结果表明，本文的第二个研究内容已经完成，并且证明了所提出的临近最优可行解方案的有效性。　　通过考虑与联盟形成相关的搜索成本，我们提出了一个称为次优折扣联盟形成（次优DGF）的算法。该算法允许Agent以一个折扣价获取它们部分或者全部的目标（例如，请求操作）。在这种情况下，联盟成员通过Agents之间的合作取得折扣价可以增加Agents的效益。这种合作从直接的Agent邻居扩展到间接Agent邻居，其中可以通过在对Agent图中的Agents分布式搜索来发现潜在的合作机会。考虑到搜索成本，Agent的目标是找到潜在的机会的最佳集合，该集合在形成的联盟的最大整体功用上以分散的方式用满足联盟请求。这正是本文第三个研究工作的主要内容。　　具体来说，在次优DGF算法中的每一个Agent将每个提供的操作都与一个价格计划相关联，并通过搜索有价值的联盟来提供基于请求的操作数目（即数量）的折扣价。Agent使用一个联盟价值约束条件(CVC)在继续搜索（可能会由于扩展联盟而导致更好的机会）与接受当前联盟的形成（从当前有价值的联盟之中获得即时收益）之间进行权衡。它寻求一个合作机会通过分派来自Agent图中的请求Agent子集来给所有的联盟成员产生最大效用，该子集在可能的联盟中拥有最大的联盟价值。DGF的次优解决方案算法应该保证在与其他的解决方案相比时获得更好的结果，包括:1）单独的Agent搜索，其中的每个Agent都比在团体中更高的成本获得其目标（即不享受团体折扣）;2）优化算法是在效用的基础上计算最优联盟;3）通过考虑搜索成本作为一个参数来影响一个最优解的形成。　　第三个研究工作的主要成就之一是从团队中搜索得到收益。这种搜索可以利用被单独Agent抛弃的搜索机会。通过这样的收益，少量Agent实现目标的失败率能够从24％减少到4％，如果有大量Agents参入，则失败率几乎为零。同时，次优DGF算法也表现出其高效性，在实现一个目标的平均处理时间上它比单独Agent搜索快了15％到34％。通过不同数量的agent形成的联盟的实验分析，提出的解决方案获得了在时间上比其他优化模型快5％到24％。随着Agents数量的增长，次优DGF算法的平均效用以98％的比率接近最优效用，并且在考虑搜索成本作为一个影响最优联盟的搜索的参数时高于平均联盟价值6％。因此，DGF的次优解决方案算法在与搜索成本相关的真实世界的环境中有它的优势。Agent更倾向于通过合作搜索折扣价朝向特定的目标形成联盟而不是通过单独搜索的方式。　　最后，我们进一步的扩展上述的研究内容，即不仅要获得一组联盟的形成，还要根据收益分配的核心值来获得稳定的联盟形成(SCF)。一个联盟的稳定要求根据成本分摊原则在联盟成员之间进行收益分配，要对拒绝参与并形成自己的联盟的Agent团体不予分配收益。该核心值是用来描述这个属性的最常用概念。当形成联盟时，Agents由于实现一个目标而收到奖励或者回报，并且要决定如何以一个稳定的方式在成员Agents中划分奖励。我们考虑的情况是，Agents在一定意义上是同质的，每个Agent都有相同的目标（以折扣价—最低价获得操作动作）。形成这样的稳定联盟时与搜索成本有关的。这个搜索成本反映了在搜索活动中需要投入的资源，例如寻找其他Agents以及确定最有价值的稳定联盟。因此，一个基于联盟价值的策略(CVS)以及成本分摊规则用于在对SCF进行搜索的过程中评估不同的形成联盟的机会。为了这个目的，我们为SCF提出了一个半最优解决方案算法。该解决方案应该保证通过寻找可行的联盟伙伴集合来达成一个稳定的联盟（即核心值在联盟内的收益分配是稳定的）。这些联盟伙伴可以在Agent图中从直接邻居（Agent的邻居）扩展到间接邻居（临近Agent邻居的Agent）来获得批量折扣。联盟形成与成本分摊规则应该给在联盟中的Agent提供激励使其不是被强迫使其留在联盟中，这是作为个人理性(IR)与预算平衡(BB)的合理结果。根据IR，联盟成员的所有个人花费都不大于相应底价。与此同时在BB中，联盟掌管在联盟中产生的花费。因此，agent的花费是其底价的非减函数。　　SCF的半最优解决方案算法应根据其核心保证一个高效的收益分配结果相对于其他解决方案，包括:1）导致最佳收益的最优算法;2）通过考虑搜索成本作为一个参数来影响稳定最优联盟的搜索方法。另外，在核心中形成稳定联盟依赖于联盟内的成本分摊规则。根据提出的成本分摊规则，本文通过实验证明SCF能够获得以95％到99.98％的比率接近最佳收益的平均收益。同时在考虑搜索成本作为一个参数影响最有价值稳定联盟的决定时，它比平均的联盟价值高了9％。在考虑搜索成本时，本文提出的SCF算法依据Agents数量的不同也相应减少了15％至24％的平均处理时间，并且以比最优时间快不少于75％的时间证明该方法形成稳定联盟的效率。这样的解决方案的实验结果表明，Agent更倾向于把它们的决策建立在价格优势、能够达到的折扣数以及它们之中公平的收益分配上，由此，本文提出的半最优解决方案通过最大化可行联盟的价值来搜索最有价值稳定联盟，该方案在核心也应该是稳定的。　　综上所述，本文为多Agent系统中联盟形成提出了一系列新型的算法，它们一个共同的特点是有效且快速获得一个满足实际需要的联盟结果，它们强调联盟形成过程的质量以及适应真实环境的联盟形成的实用性。