| 基于势结构的任一时间联盟结构生成算法 |
| |
| 引用本文： | 苏射雄,胡山立,郑盛福,林超峰,骆剑彬.基于势结构的任一时间联盟结构生成算法[J].计算机研究与发展,2008,45(10). |
| |
| 作者姓名： | 苏射雄 胡山立 郑盛福 林超峰 骆剑彬 |
| |
| 作者单位： | 福州大学计算机科学与技术系,福州,350002 |
| |
| 摘 要： | 联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.Sandholm等人已经证明,要建立最坏情况下的限界K(n),搜索联盟结构图的最底两层是必要且是充分的.Dang等人给出的算法是所见到的第1个不以层为单位的搜索算法,对于较小的限界明显地优于Sandholm等人给出的算法.深刻分析了联盟结构间的关系,采用更小的搜索粒度(势结构),提出基于势结构的任一时间算法,在搜索最底两层及顶层后,进一步搜索势结构集合CCS(n,6)对应的未搜索过的联盟结构,渐进地给出越来越低的限界,大大改进了Sandholm等人(快1035倍,当n=100,K=2)和Dang等人(快1018倍,当n=100,K=3)的工作.
|
| 关 键 词： | 多Agent系统 联盟形成 任一时间算法 联盟结构生成 势结构 特征函数 |
An Anytime Coalition Structure Generation Algorithm Based on Cardinality Structure |
| |
| Su Shexiong,Hu Shanli,Zheng Shengfu,Lin Chaofeng,Luo Jianbin.An Anytime Coalition Structure Generation Algorithm Based on Cardinality Structure[J].Journal of Computer Research and Development,2008,45(10). |
| |
| Authors: | Su Shexiong Hu Shanli Zheng Shengfu Lin Chaofeng Luo Jianbin |
| |
| Affiliation: | Su Shexiong,Hu Shanli,Zheng Shengfu,Lin Chaofeng,, Luo Jianbin(Department of Computer Science , Technology,Fuzhou University,Fuzhou 350002) |
| |
| Abstract: | Coalition formation is a key topic in multi-agent systems.One may prefer a coalition structure that maximizes the sum of the values of the coalitions,but often the number of coalition structures is too large to allow exhaustive search for the optimal one.Furthermore,finding the optimal coalition structure is NP-hard and even finding a sub-optimal solution requires searching an exponential number of solutions.But then,can the coalition structure found via a partial search be guaranteed to be within a bound f... |
| |
| Keywords: | multi-agent system coalition formation anytime algorithm coalition structure generation cardinality structure characteristic function |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
