单调重叠联盟下的最优联盟结构生成

• 作者: 刘惊雷 郭志鹏
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 重叠联盟结构生成 最优联盟结构 联盟数量约束 单调性 固定参数可解
• 年，卷（期）: 2021,（1）
• 所属期刊栏目: 第八届中国数据挖掘会议(CCDM 2020)
• 页码范围: 103-111
• 页数: 9页
• 分类号: TP18
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2020060973

摘要

针对重叠联盟的合作博弈框架(OCF games)中重叠联盟结构生成(OCSG)求解困难的问题,提出了一种基于贪心方法的有效算法.首先使用了一种带有联盟数量k约束的OCF博弈(kOCF games)模型来限制OCSG问题的规模;然后引入了一种相似度量来表示任意两个联盟结构之间的相似程度,并基于相似度量定义了单调性的性质,这意味着某一联盟结构与最优联盟结构的相似度越高,该联盟的单调性的值就越大;最后对于具有单调性质的kOCF博弈,采用了逐一插入玩家编号以逼近最优联盟结构的方法设计了联盟约束贪心(CCG)算法来求解给定的OCSG问题,并在理论上证明了CCG算法的复杂度是O(n2k+1).通过实验分析和验证了不同参数和联盟值分布对所提算法性能的影响,并把该算法与Zick等提出的算法(ZICK Y,CHALKIADAKIS G,ELKIND E,et al.Cooperative games with overlapping coalitions:charting the tractability frontier.Artificial Intelligence,2019,271:74-97)在约束条件等方面进行了对比,得出了当联盟最大数量k被常数约束时所提算法的搜索次数随agent的个数基本呈线性增长的结果.可见CCG算法是固定参数k可解的,而且拥有更好的适用性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘惊雷		63	262	8.0	13.0
2	郭志鹏		1	0	0.0	0.0