带有联盟个数约束的最优联盟结构生成

• 作者: 刘惊雷 徐广斌
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: 联盟结构 联盟个数约束 动态规划 联盟约束动态规划(CCDP) 时间复杂度
• 年，卷（期）: 2015,（4）
• 页码范围: 749-761
• 页数: 13页
• 分类号: TP181
• 字数: 7919字
• 语种: 中文
• DOI: 10.13232/j.cnki.jnju.2015.04.013

摘要

形成有效的联盟是多 Agent 系统研究中的关键问题。为了有效地完成个体的或共同的目标,Agent 集合划分成相互独立的团体,即联盟的形成。联盟结构生成(coalition structure generation,CSG)问题研究的是 Agent 集合划分成联盟,从而使得收益最大化。传统的算法利用不同的方法来解决这个问题,但都没有对联盟个数进行约束。利用动态规划(dynamic programming,DP)原理设计了新的算法—联盟约束动态规划(coalition constrain dynamic programming,CCDP)算法,并通过该算法生成最优(福利最大化)联盟结构。随后证明了算法的时间复杂度为O(3n )。最后通过实验,分析并验证了 Agent 个数对算法性能的影响,以及联盟个数约束值的大小对算法性能的影响。实验结果证明在 Agent 集合的个数较大的情况下,在联盟结构搜索图中越靠近中间部分,即联盟个数约束条件的取值越靠近中间部分,算法的效果越好。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘惊雷	烟台大学计算机与控制工程学院	63	262	8.0	13.0
2	徐广斌	烟台大学计算机与控制工程学院	1	6	1.0	1.0