近年来,人工智能领域的多agent系统逐渐引起学者的关注。在多agent系统中,各个agent为了更好的完成任务,提高效率,采用相互合作的方式。与独立工作相比,采用合作的方式效率更高。多agent系统中的各个agent通过不同的排列组合,被划分成为不同的联盟结构。由于求解最优联盟结构是一个NP难的问题,联盟的增加是根据agent个数增加呈现指数增长的。因而,通过遍历所有的联盟结构获得最优结果,只是理论上可行,在实际的应用当中,由于时间和资源的限制,通常可以获得次优的联盟结构。本文首先对联盟结构生成问题的背景和所遇到的挑战进行阐述,同时详细地描述了agent的基础理论,对当前联盟结构生成问题主要研究方法以及存在的问题进行探讨,从而提出本文研究的突破点。提出了利用剪枝函数对联盟结构图进行剪枝的方法。在特征函数论中,多agent系统中联盟结构的联盟收益值都是相互独立的。在联盟结构的生成过程中,一个联盟的收益值不受其它agent划分排列的影响。将联盟结构图中的联盟结构用整数拆分的形式进行表示,通过剪枝函数,对搜索空间进行横向剪枝和纵向剪枝。此方法对于提高联盟结构图的搜索效率取得了良好效果。提出了一种基于溢出性质的联盟结构生成的任意时间算法,可以在任意时间得到一个次优值。与特征函数论不同的是,在联盟结构生成的过程中,同一个联盟在不同的联盟结构中的收益值是变化的,即为溢出性质。根据溢出性质,算法使用新的建立最坏情况下边界值的方法。即对任意不相交的联盟集合计算其上下边界的值,通过搜索特定的联盟结构集合建立最坏情况下的边界值。结果表明,边界值越高,需要搜索的联盟结构数目越少,而符合条件的近似最优值越容易达到。随着最坏情况下的边界值的优化,程序运行的时间逐渐加长,所求得的结果会越来越接近最优联盟结构。