Journal of Software:2001.12(5):729-734

(福州大学计算机科学与技术系,福建福州 350002)
An Anytime Coalition Structure Generation Algorithm
HU Shan li,SHI Chun yi
Chart / table
Similar Articles
Article :Browse 2895   Download 2770
Received:July 13, 1999    Revised:October 28, 1999
> 中文摘要: 联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值的总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.给出了一个算法,可在最小搜索量内保证找到一个与最优解相距在一个限界内的联盟结构.然后,这个任一时间算法进一步搜索,渐进地给出越来越低的限界,并急剧地降低这个限界,在这一阶段,此算法明显地优于由Sandholm等人给出的算法.
中文关键词: 联盟  联盟结构  算法  多Agent系统
Abstract:Coalition formation is a key topic in multi agent systems. People try to search for coalition structure that maximizes the sum of the values of the coalitions, but in most cases the number of coalition structures is too large to search for the optimal one exhaustively. In this paper, an algorithm is presented that within the minimal amount of search can guarantee to find a coalition structure which is within a bound from optimum. Then, the anytime algorithm searches further, and establishes a progressively lower bound, and lowers the bound rapidly.In this stage, it evidently outperforms the algorithm presented by Sandholm etc, which is the new-made better result in this area.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金资助项目(69733020;69973023);福建省自然科学基金资助项目(F00012) 国家自然科学基金资助项目(69733020;69973023);福建省自然科学基金资助项目(F00012)
Foundation items:
Reference text:


HU Shan li,SHI Chun yi.An Anytime Coalition Structure Generation Algorithm.Journal of Software,2001,12(5):729-734