最优联盟结构生成算法中的分支限界技术
刘惊雷
张伟
童向荣
1.烟台大学,计算机学院,山东,烟台,2640052.烟台大学,计算机学院,山东,烟台,2640053.烟台大学,计算机学院,山东,烟台,264005
摘要：讨论多Agent系统中的最优联盟结构生成问题.对于联盟值以特征函数表示的情况下,提出了一种分支限界技术.该技术用联盟大小所代表的整数多个二部拆分作为当前搜索空间的多个分支,以已经求得的局部联盟值的下界和当前所得到的最优值所构造出的剪枝函数来限界.这样,若当前要搜索的一个分支--二部拆分的上界小于所构造的剪枝函数时,该二部拆分分支所对应的大量二部划分就不需进行分解,从而减少了搜索时间.该分支限界技术可整合到当前所出现的各种联盟结构生成算法中.为了测试该技术的有效性,本文将该技术应用到了Rothkopf所提出的DP算法和Rahwan等人所提出的IDP算法中.在具有21个Agent系统中,带有分支限界的BBDP(Branch Bound Dynamitic Programming)算法比不带有分支限界的DP算法可节省时间58.2%;带有分支限界的比不带有分支限界的IDP算法可节省时间17.8%.
关键词：最优联盟结构整数二部拆分二部划分联盟值的上界和下界分支限界
分类号：TP182(自动化基础理论)
资助基金：国家自然科学基金(60496323)山东省教育厅科技项目(J07JYJ24)
论文发表日期：2009-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：5( 76-80 )
英文信息