计算机应用 ›› 2021, Vol. 41 ›› Issue (1): 103-111.DOI: 10.11772/j.issn.1001-9081.2020060973
所属专题: 第八届中国数据挖掘会议(CCDM 2020)
• 第八届中国数据挖掘会议(CCDM 2020) • 上一篇 下一篇
收稿日期:
2020-05-31
修回日期:
2020-07-27
出版日期:
2021-01-10
发布日期:
2020-09-02
通讯作者:
刘惊雷
作者简介:
郭志鹏(1996-),男,山东菏泽人,硕士研究生,主要研究方向:多agent系统、重叠联盟博弈;刘惊雷(1970-),男,山西临猗人,教授,博士,主要研究方向:人工智能、理论计算机科学。
基金资助:
Received:
2020-05-31
Revised:
2020-07-27
Online:
2021-01-10
Published:
2020-09-02
Supported by:
摘要: 针对重叠联盟的合作博弈框架(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可解的,而且拥有更好的适用性。
中图分类号:
郭志鹏, 刘惊雷. 单调重叠联盟下的最优联盟结构生成[J]. 计算机应用, 2021, 41(1): 103-111.
GUO Zhipeng, LIU Jinglei. Optimal coalition structure generation in monotonous overlapping coalition[J]. Journal of Computer Applications, 2021, 41(1): 103-111.
[1] 蒋伟进, 钟珞, 张莲梅, 等. 基于时序活动逻辑的复杂系统多Agent动态协作模型[J]. 计算机学报,2013,36(5):1115-1124. (JIANG W J, ZHONG L, ZHANG L M, et al. Dynamic cooperative multi-agent model of complex system based-on sequential actions'logic[J]. Chinese Journal of Computers,2013, 36(5):1115-1124.) [2] ZHANG G,JIANG J,SU Z,et al. Searching for overlapping coalitions in multiple virtual organizations[J]. Information Sciences,2010,180(17):3140-3156. [3] 戴瑞海, 施亦治, 姜于, 等. 基于多Agent的海岛微电网分布式双层控制方法[J]. 电力系统及其自动化学报,2020,32(3):75-81.(DAI R H,SHI Y Z,JIANG Y,et al. Multi-agent based distributed two-layer control method for islanded microgrids[J]. Proceedings of the CSU-EPSA,2020,32(3):75-81.) [4] 宋欢, 王建娜. 博弈论在无线传感器网络数据转发机制中的应用[J]. 通信技术,2018,51(4):852-856.(SONG H,WANG J N. Application of game theory in data forwarding mechanism of wireless sensor networks[J]. Communications Technology,2018, 51(4):852-856.) [5] SERVICE T C, ADAMS J A. Coalition formation for task allocation:theory and algorithms[J]. Autonomous Agents and Multi-Agent Systems,2011,22(2):225-248. [6] YE D, ZHANG M, SUTANTO D. Decentralised dispatch of distributed energy resources in smart grids via multi-agent coalition formation[J]. Journal of Parallel and Distributed Computing, 2015,83:30-43. [7] RAHWAN T, MICHALAK T P, WOOLDRIDGE M, et al. Coalition structure generation:a survey[J]. Artificial Intelligence, 2015,229:139-174. [8] FATIMA S, WOOLDRIDGE M. Computing optimal coalition structures in polynomial time[J]. Autonomous Agents and MultiAgent Systems,2019,33(1/2):35-83. [9] PRÄNTARE F,HEINTZ F. An anytime algorithm for optimal simultaneous coalition structure generation and assignment[J]. Autonomous Agents and Multi-Agent Systems,2020,34(1):No. 29. [10] ZICK Y,CHALKIADAKIS G,ELKIND E,et al. Cooperative games with overlapping coalitions:charting the tractability frontier[J]. Artificial Intelligence,2019,271:74-97. [11] SERVICE T C,ADAMS J A. Randomized coalition structure generation[J]. Artificial Intelligence,2011,175(16/17):2061-2074. [12] SANDHOLM T,LARSON K,ANDERSSON M,et al. Coalition structure generation with worst case guarantees[J]. Artificial Intelligence,1999,111(1/2):209-238. [13] LARSON K S,SANDHOLM T W. Anytime coalition structure generation:an average case study[J]. Journal of Experimental and Theoretical Artificial Intelligence,2000,12(1):23-42. [14] YEH Y D. A dynamic programming approach to the complete set partitioning problem[J]. Bit Numerical Mathematics,1986,26(4):467-474. [15] 张新良, 石纯一. 多agent联盟结构动态生成算法[J]. 软件学报,2007,18(3):574-581.(ZHANG X L,SHI C Y. A dynamic formation algorithm of multi-agent coalition structure[J]. Journal of Software,2007,18(3):574-581.) [16] UEDA S,IWASAKI A,CONITZER V,et al. Coalition structure generation in cooperative games with compact representations[J]. Autonomous Agents and Multi-Agent Systems,2018,32(4):503-533. [17] RAHWAN T,JENNINGS N R. Coalition structure generation:dynamic programming meets anytime optimization[C]//Proceedings of the 23rd AAAI Conference on Artificial Intelligence. Palo Alto,CA:AAAI Press,2008:156-161. [18] RAHWAN T, JENNINGS N R. An improved dynamic programming algorithm for coalition structure generation[C]//Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi-Agent Systems. Richland,SC:International Foundation for Autonomous Agents and Multiagent Systems,2008:1417-1420. [19] GRECO G, LUPIA F, SCARCELLO F. Coalitional games induced by matching problems:complexity and islands of tractability for the Shapley value[J]. Artificial Intelligence, 2020,278:No. 103180. [20] THRALL R M,LUCAS W F. N-person games in partition function form[J]. Naval Research Logs Quarterly,1963,10(1):281-298. [21] RAHWAN T,MICHALAK T,WOOLDRIDGE M,et al. Anytime coalition structure generation in multi-agent systems with positive or negative externalities[J]. Artificial Intelligence,2012,186:95-122. [22] CHALKIADAKIS G, ELKIND E, MARKAKIS E, et al. Cooperative games with overlapping coalitions[J]. Journal of Artificial Intelligence Research,2010,39(1):179-216. [23] 魏冰茹, 张国富, 苏兆品, 等. 成本最小化的最优重叠联盟结构生成算法[J]. 计算机工程,2019,45(11):198-203.(WEI B R, ZHANG G F,SU Z P,et al. Optimal overlapping coalition structure generation algorithm with cost minimization[J]. Computer Engineering,2019,45(11):198-203.) [24] 徐广斌,刘惊雷. 带有联盟个数约束的最优联盟结构生成[J]. 南京大学学报(自然科学),2015,51(4):749-761.(XU G B, LIU J L. The optimal coalition structure generation with the constrained number of coalition[J]. Journal of Nanjing University (Natural Science),2015,51(4):749-761.) [25] RAHWAN T,RAMCHURN S D,JENNINGS N R,et al. An anytime algorithm for optimal coalition structure generation[J]. Journal of Artificial Intelligence Research, 2009, 34(1):521-567. |
[1] | 杜航原 郝思聪 王文剑. 结合图自编码器与聚类的半监督表示学习方法[J]. 计算机应用, 0, (): 0-0. |
[2] | 陈露 张晓霞 于洪. 基于先验知识的非负矩阵半可解释三因子分解算法[J]. 计算机应用, 0, (): 0-0. |
[3] | 韩舒宁 徐敏 董学士 林青 沈凡凡. 混合伊藤算法求解多尺度着色旅行商问题[J]. 计算机应用, 0, (): 0-0. |
[4] | 李晓杰 崔超然 宋广乐 苏雅茜 吴天泽 张春云. 基于时序超图卷积神经网络的股票趋势预测方法[J]. 计算机应用, 0, (): 0-0. |
[5] | 张建 严珂 马祥. 基于神经网络的复杂垃圾信息过滤算法分析[J]. 计算机应用, 0, (): 0-0. |
[6] | 邱云志 汪廷华 戴小路. 双重特征加权模糊支持向量机[J]. 计算机应用, 0, (): 0-0. |
[7] | 李宗正 周恺卿 丁雷 欧云. 基于基因交换的自适应人工鱼群算法[J]. 计算机应用, 0, (): 0-0. |
[8] | 刘清华 廖士中. 基于随机素描方法的在线核回归[J]. 计算机应用, 0, (): 0-0. |
[9] | 张小清 王晨曦 吕彦 林耀进. 基于ReliefF的层次分类在线流特征选择算法[J]. 计算机应用, 0, (): 0-0. |
[10] | 于婉莹 梁美玉 王笑笑 陈徵 曹晓雯. 基于深度注意力网络的课堂教学视频中学生表情识别与智能教学评估[J]. 计算机应用, 0, (): 0-0. |
[11] | 黄勇康 梁美玉 王笑笑 陈徵 曹晓雯. 基于深度时空残差卷积神经网络的课堂教学视频中多人课堂行为识别[J]. 计算机应用, 0, (): 0-0. |
[12] | 康猛 蒙祖强. 基于局部条件区分能力的高效属性约简算法[J]. 计算机应用, 0, (): 0-0. |
[13] | 谢鑫 张贤勇 王旋晔 唐鹏飞. 变精度邻域等价粒邻域决策树构造算法[J]. 计算机应用, 0, (): 0-0. |
[14] | 刘忠慧 王梓宥 闵帆. 近似概念的遗传生成算法及其推荐应用[J]. 计算机应用, 0, (): 0-0. |
[15] | 潘仁志 钱付兰 赵姝 张燕平. 基于卷积神经网络交互的用户属性偏好建模的推荐模型[J]. 计算机应用, 0, (): 0-0. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||