| 摘要: |
| 联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值的总和的联盟结构，但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.给出了一个算法,可在最小搜索量内保证找到一个与最优解相距在一个限界内的联盟结构.然后,这个任一时间算法进一步搜索,渐进地给出越来越低的限界,并急剧地降低这个限界,在这一阶段,此算法明显地优于由Sandholm等人给出的算法. |
| 关键词: 联盟 联盟结构 算法 多Agent系统 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金资助项目(69733020;69973023);福建省自然科学基金资助项目(F00012) |
|
| An Anytime Coalition Structure Generation Algorithm |
|
HU Shan li,SHI Chun yi
|
| 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. |
| Key words: coalition coalition structure algorithm multi agent system |
