最优联盟结构生成算法中的分支限界技术

• 作者: 刘惊雷 张伟 童向荣
• 来源期刊: 北京交通大学学报
• 学科: 工学
• 关键词: 最优联盟结构 整数二部拆分 二部划分 联盟值的上界和下界 分支限界
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 机器学习与数据挖掘
• 页码范围: 76-80
• 页数: 5页
• 分类号: TP182
• 字数: 4009字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-0291.2009.06.017

摘要

讨论多Agent系统中的最优联盟结构生成问题.对于联盟值以特征函数表示的情况下,提出了一种分支限界技术.该技术用联盟大小所代表的整数多个二部拆分作为当前搜索空间的多个分支,以已经求得的局部联盟值的下界和当前所得到的最优值所构造出的剪枝函数来限界.这样,若当前要搜索的一个分支--二部拆分的上界小于所构造的剪枝函数时,该二部拆分分支所对应的大量二部划分就不需进行分解,从而减少了搜索时间.该分支限界技术可整合到当前所出现的各种联盟结构生成算法中.为了测试该技术的有效性,本文将该技术应用到了Rothkopf所提出的DP算法和Rahwan等人所提出的IDP算法中.在具有21个Agent系统中,带有分支限界的BBDP(Branch Bound Dynamitic Programming)算法比不带有分支限界的DP算法可节省时间58.2%;带有分支限界的比不带有分支限界的IDP算法可节省时间17.8%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘惊雷	烟台大学计算机学院	63	262	8.0	13.0
2	童向荣	烟台大学计算机学院	50	273	10.0	14.0
3	张伟	烟台大学计算机学院	40	377	12.0	18.0