随着人工智能和分布式系统的发展,多Agent系统逐渐成为一个热门研究领域,并且广泛应用于社交网络分析、智能机器人和数据挖掘等领域。在多Agent系统中,Agent之间可以进行交互、协作和合作,互相合作的Agent组成联盟。联盟形成问题是研究Agent合作联盟的问题,是多Agent系统中的一个基本研究问题。现如今,在联盟形成问题上已经有大量的研究成果,大多数的研究重点关注在稳定的联盟结构上,如探究达到核心或纳什均衡的联盟结构的复杂度及其联盟形成算法。然而关于社会福利最大化问题的研究成果相对偏少,社会福利最大化问题旨在生成所有联盟值之和最大的联盟结构。联盟形成问题一般采用博弈论领域中的博弈模型来确定联盟值。Fractional Hedonic博弈在2014年被提出后在博弈论领域中得到了广泛的研究,其定义了Agent在联盟中的收益。一个联盟中Agent的收益是其对联盟中所有其他成员的平均偏好值,联盟值为联盟内成员的收益之和。Fractional Hedonic博弈还是一个可以用图表示的特殊博弈,把图中结点看作Agent,边看作偏好值,其刻画了Agent收益与图的拓扑结构的关系。本文研究基于Fractional Hedonic博弈的社会福利最大化问题。其相关研究数量屈指可数,并且已有的算法存在复杂度高、生成的联盟结构的社会福利不高或不符合现实等不足,有待改进和优化。因此,针对这些问题,本文分别提出了三种基于Fractional Hedonic博弈的社会福利最大化问题的联盟形成算法,在理论上证明其在部分规则图上的最优性,并且实验验证其在此问题上的优越性。此研究不仅在联盟形成领域具有理论意义,并且在社会网络分析包括网络聚类和社区检测领域具有应用价值。本文研究内容主要有以下四个方面:(1)本文提出一个自然的联盟形成机制,在此机制下根据收益分配方式提出了两种联盟形成算法。首先,本文提出了基于多Agent系统的联盟形成机制,每一个自利的Agent相继交互,根据得到的收益轮流选择是否加入其他联盟。根据在联盟形成中的不同分配方式,提出相应的两种联盟形成算法,一种是基于Fractional Hedonic博弈分配方式的联盟形成算法(CFFHG)。然而在这个机制中,CFFHG存在一定缺陷。针对这个缺陷,本文采用Shapley值的分配方式,提出基于Shapley值分配方式的联盟形成算法(CFSV)。(2)针对计算Shapley值的复杂度问题,本文采用了一种近似算法来有效地计算Shapley值,从而形成基于估算Shapley值分配方式的联盟形成(CFASV)算法。计算Shapley值的过程中,因其需要考虑联盟中所有Agent的排列序列中的边际值,计算复杂度高。利用近似的Shapley值计算方法,可以加速计算过程,并且能在规模更大的网络上形成联盟结构来评估算法。(3)本文证明CFFHG算法和CFSV算法能在某些规则图上生成基于Fractional Hedonic博弈的社会最优联盟结构。虽然在Fractional Hedonic博弈上生成社会最优的联盟结构已被证明是NP难问题,但是本文从理论上证明了两种算法在完全图、星图、线图、圆图和平衡完全二分图上的最优性。(4)本文通过实验模拟及分析评估CFFHG算法,CFSV算法和CFASV算法。本文在多个现实社会网络和生成网络上评估提出的算法。在现实社会网络中,生成的联盟结构对现实有一定的参考价值。在生成网络方面,本文使用ER随机网络模型和小世界模型生成网络评估算法。实验结果表明本文提出的算法生成的联盟结构的社会福利大于已知的其他方法。最后,本文进行了真人实验,探究了现实生活中人将如何合作形成联盟,并与本文提出的算法进行比较。