最优联盟结构生成的研究以层为单位有哪些信誉好的足球投注网站或计算.pdfVIP

最优联盟结构生成的研究：以层为单位有哪些信誉好的足球投注网站或计算 胡山立1’3_石纯一2 1(福州大学计算机科学与技术系，福卅l，350002) 2(清华大学计算机科学与技术系，北京．100084) 3(中国科学院软件研究所计算机科学重点实验室，北京，100080) E-maih edu．c“ husl@fzu 摘要：联盟形成己成为多agent系统中一个非常活跃的研究领域。大部分研究集中在agent 如何通过协商来形成联盟和分配联盟的收益。另一种研究方法研究agents的最优划分，耙agems 划分为若干个联盟(两两互不相交的子集)，使各个联盟收益的总和最大。这就是最优联盟结 构生成问题。这可以通过在联盟结构图上有哪些信誉好的足球投注网站或直接计算。文章讨论了在～个联盟的收益与 非该联盟成员的活动无关”的一般假设下，最优联盟结构生成的这两种方法。 关键词：联盟；联盟结构；算法；多agent系统 1．引言 联盟形成是多agent系统研究中的一个令人感兴趣的关键问题。由于单个agent的资源 和能力有限，agent可能希望通过互相合作来完成或更有效地完成任务。从单agent的观点 参加一个联盟的动机是为了能完成或更有效地完成任务，以便能增加它能得到的收益。这 样，通过协商来形成联盟的过程在多agent系统的研究中已受到相当的重视[1—51。 然而，从系统设计者的观点，从整个系统来看，对该系统中所有联盟得到的总的收益， 可能更感兴趣。这时系统的设计者想要知道什么样的联盟组合能够产生这最大的收益。这 样产生了联盟结构的概念，～个联盟结构(cS)被定义为一个系统中所有agents的一个划 分，所有agents被划分为两两互不相交的联盟。系统设计者的目标是寻求这最优的联盟结 构，即能产生最大收益的联盟结构。 当然，一个联盟结构能产生最大的收益并不意味着这个联盟结构将在实践中实现。因为 这还涉及收益在agents之闻的分配问题，总体收益最大不一定能保证每个个体的收益晟大 (由于各个agent在各个联盟中的作用不同)。然而知道关于这最优联盟结构的知识将有助于 系统设计者提出激励agents构成最优联盟结构的措施，引导最优联盟结构的生成。至少关于 最优联盟结构的知识将使系统设计者能更有效地评估系统中当前联盟结构的优劣。 在资源的最优组合利用问题中，更直接地提出类似的问题，多个资源如何进行组合利 用才能得到最大的总的效益。这就是寻求最优资源结构问题。显然最优联盟结构生成的方 法可直接应用于资源的最优结构生成。 本文第2节介绍联盟结构图和特征函数。第3节讨论在联盟结构图上有哪些信誉好的足球投注网站最优联盟结 构的各种方法。第4节讨论商接通过计算求解最优联盟结构的方法。第5节比较有哪些信誉好的足球投注网站与计 资助项目：本课题得到国家自然科学基金州o60573076)资助。 联系作者：胡山立(I钳4f)．男，福建福州^．教授，研究方向为人工智能应用基础，多agent系统i一矗吨一(}j)，男 河北山海关人．教授．博士生导师，研究方向为人工智自E应用基础。 668 第三部分第一届全国普适计算学术会议 算这两种方法的优劣并给出结论。 2．联盟结构图和特征函数 =Ml，我们定义一个联盟s是一的一个非空子集， 设4={4，4，…，4)是agent集，且n 从而同一个联盟结构中的联盟是互不相交的，称 一个联盟结构cs是agent集的一个划分， 所有联盟结构的集合为M。 对于有n个agent的系统，所有可能的联盟结构及其关系能够用联盟结构陶来表示。 图中结点代表联盟结构，共有n层，由底向上第i层中的结点代表含有i个联盟的联盟结 构。结点间的弧线代表联盟结构之间的关系。沿弧线向下代表上面那个联盟结构中的两个 联盟合并产生下面那个联盟结构。沿弧线向上代表下面那个联盟结构中的一个联盟分裂为 两个联盟而产生上面那个联盟结构。以n=4为例，如图1所示。 层(4)