带有目标偏好的最大成功联盟生成算法<sup>*</sup>

doi:10.16451/j.cnki.issn1003-6059.201706002

摘要
图/表
参考文献
相关文章 (15)

全文: PDF (939 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要资源结盟博弈(CRGs)研究均假设每个agent可以响应所有目标,即使目标不在其感兴趣的子目标集内.针对此问题,文中提出带有目标偏好的CRGs模型,即每个agent只愿意把自己的有限资源贡献给自己的兴趣集中的目标.此外,设计基于二维二进制编码的最大成功联盟生成算法,并提出编码修正启发式算法解决多个目标竞争同一agent资源可能引起的的资源冲突.最后,通过与已有相关算法的对比实验验证文中算法的有效性.

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	张国富
	杜晓东
	苏兆品
	蒋建国

关键词 ：资源结盟博弈(CRGs), 目标偏好, 最大成功联盟, 启发式算法

Abstract：In the traditional research on coalitional resource games(CRGs), it is assumed that an agent can respond to any goal, even if the agent is not interested in the goal at all. In this paper, a natural variation of CRGs with goals preferences is discussed. An agent only contributes its resources to the goals in its own goal (or interest) set. For this purpose, an improved CRGs model is firstly proposed on the basis of goals preferences. Moreover, a two-dimensional binary encoding based algorithm for maximal successful coalition (MAXSC) generation is designed and a heuristic algorithm is developed to resolve the potential conflicts of agents scrambling for scarce resources. Finally, the proposed approach is compared with the previous algorithms for the MAXSC problem.The results demonstrate the effectiveness of the proposed approach.

Key words： Coalitional Resource Games(CRGs) Goals Preferences Maximal Successful Coalition Heuristic algorithm

收稿日期: 2016-12-29

ZTFLH:

TP 181

基金资助:国家自然科学基金项目(No.61573125,61371155)、安徽省自然科学基金项目(No.1608085MF131,1508085MF132,1508085QF129)资助

作者简介: 张国富(通讯作者),男,1979年生,博士,副教授,主要研究方向为复杂系统、联盟博弈、计算智能.E-mail:zgf@hfut.edu.cn.
杜晓东,女,1992年生,硕士研究生,主要研究方向为多agent系统、演化计算.E-mail:roxana92@mail.hfut.edu.cn.
苏兆品,女,1983年生,博士,副教授,主要研究方向为演化计算、灾害应急决策、多媒体安全.E-mail:szp@hfut.edu.cn.
蒋建国,男,1955年生,硕士,教授,主要研究方向为分布式智能系统、数字图像处理与分析.E-mail:jgjiang@hfut.edu.cn.

引用本文:

张国富，杜晓东，苏兆品，蒋建国. 带有目标偏好的最大成功联盟生成算法^*[J]. 模式识别与人工智能, 2017, 30(6): 489-498. ZHANG Guofu, DU Xiaodong, SU Zhaopin, JIANG Jianguo. Algorithm for Maximal Successful Coalition Generation with Goals Preferences. , 2017, 30(6): 489-498.

链接本文:

http://manu46.magtech.com.cn/Jweb_prai/CN/10.16451/j.cnki.issn1003-6059.201706002 或 http://manu46.magtech.com.cn/Jweb_prai/CN/Y2017/V30/I6/489

[1] SERVICE T C, ADAMS J A. Coalition Formation for Task Allocation: Theory and Algorithms. Autonomous Agents and Multi-agent Systems, 2011, 22(2): 225-248.
[2] RAHWAN T, MICHALAK T P, WOOLDRIDGE M, et al. Coalition Structure Generation: A Survey. Artificial Intelligence, 2015, 229: 139-174.
[3] 胡山立,石纯一,李少芳.给定限界的势结构分组与联盟结构生成.计算机学报, 2012, 35(12): 2618-2624.
(HU S L, SHI C Y, LI S F. Cardinality Structure Grouping and Coalition Structure Generation with Given Required Bound. Chinese Journal of Computers, 2012, 35(12): 2618-2624.)
[4] CHALKIADAKIS G, GRECO G, MARKAKIS E. Characteristic Function Games with Restricted Agent Interactions: Core-Stability and Coalition Structures. Artificial Intelligence, 2016, 232: 76-113.
[5] ZICK Y, MARKAKIS E, ELKIND E. Arbitration and Stability in Cooperative Games with Overlapping Coalitions. Journal of Artificial Intelligence Research, 2014, 50(1): 847-884.
[6] 张国富,周鹏,苏兆品,等.基于讨价还价的重叠联盟效用划分策略.模式识别与人工智能, 2014, 27(10): 930-938.
(ZHANG G F, ZHOU P, SU Z P, et al. A Payoff Distribution Strategy for Overlapping Coalitions Based on Bargaining. Pattern Recognition and Artificial Intelligence, 2014, 27(10): 930-938.)
[7] WOOLDRIDGE M, DUNNE P E. On the Computational Complexity of Coalitional Resource Games. Artificial Intelligence, 2006, 170(10): 853-871.
[8] DUNNE P E, KRAUS S, MANISTERSKI E, et al. Solving Coalitional Resource Games. Artificial Intelligence, 2010, 174(1): 20-50.
[9] 刘惊雷,张伟,童向荣,等.一种O(2.983ⁿ)时间复杂度的最优联盟结构生成算法.软件学报, 2011, 22(5): 938-950.
(LIU J L, ZHANG W, TONG X R, et al. O(2.983ⁿ) Time Complexity Algorithm for Optimal Coalition Structure Generation. Journal of Software, 2011, 22(5): 938-950.)
[10] RAHWAN T, MICHALAK T, WOOLDRIDGE M, et al. Anytime Coalition Structure Generation in Multi-agent Systems with Positive or Negative Externalities. Artificial Intelligence, 2012, 186: 95-122.
[11] PALLA G, DERNYI I, FARKAS I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature, 2005, 435(7043): 814-818.
[12] CHALKIADAKIS G, ELKIND E, MARKAKIS E, et al. Cooperative Games with Overlapping Coalitions. Journal of Artificial Intelligence Research, 2010, 39(1): 179-216.
[13] SHROT T, AUMANN Y, KRAUS S. Easy and Hard Coalition Resource Game Formation Problems: A Parameterized Complexity Analysis // Proc of the 8th International Conference on Autonomous Agents and Multi-agent Systems. Budapest, Hungary: IFAAMAS, 2009: 433-440.
[14] CECHLROV K. On Max-Min Linear Inequalities and Coalitional Resource Games with Sharable Resources. Linear Algebra and Its Applications, 2010, 433(1): 127-135.
[15] ALECHINA N, LOGAN B, NGA N H, et al. Logic for Coalitions with Bounded Resources. Journal of Logic and Computation, 2011, 21(6): 907-937.
[16] ALECHINA N, BULLING N, LOGAN B, et al. The Virtues of Idleness: A Decidable Fragment of Resource Agent Logic. Artificial Intelligence, 2017, 245: 56-85.
[17] CHITNIS R, HAJIAGHAYI M T, LIAGHAT V. Parameterized Complexity of Problems in Coalitional Resource Games // Proc of the 25th AAAI Conference on Artificial Intelligence. Palo Alto, USA: AAAI Press, 2011: 620-625.
[18] ZHANG G F, YANG R Z, SU Z P, et al. Using Binary Particle Swarm Optimization to Search for Maximal Successful Coalition. Applied Intelligence, 2015, 42(2): 195-209.
[19] 徐义春,肖人彬.一种改进的二进制粒子群算法.模式识别与人工智能, 2007, 20(6): 788-793.
(XU Y C, XIAO R B. An Improved Binary Particle Swarm Optimizer. Pattern Recognition and Artificial Intelligence, 2007, 20(6): 788-793.)
[20] MIRJALILI S, LEWIS A. S-Shaped versus V-Shaped Transfer Functions for Binary Particle Swarm Optimization. Swarm and Evolutionary Computation, 2013, 9: 1-14.
[21] JIANG Y C, ZHOU Y F, WANG W Y. Task Allocation for Undependable Multiagent Systems in Social Networks. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(8): 1671-1681.
[22] JIANG Y C, ZHOU Y F, LI Y P. Reliable Task Allocation with Load Balancing in Multiplex Networks. ACM Transactions on Autonomous and Adaptive Systems, 2015, 10(1). DOI: 10.1145/2700327.
[23] 蒋建国,顾占冰,胡珍珍,等.多摄像机视域内的目标活动分析.电子学报, 2014, 42(2): 306-311.
(JIANG J G, GU Z B, HU Z Z, et al. Activity Analysis Cross Multi-camera. Acta Electronica Sinica, 2014, 42(2): 306-311.)
[24] SU Z P, ZHANG G F, LIU Y, et al. Multiple Emergency Resource Allocation for Concurrent Incidents in Natural Disasters. International Journal of Disaster Risk Reduction, 2016, 17: 199-212.
[25] 徐义春,董方敏,刘勇,等.带平衡约束矩形布局优化问题的遗
传算法.模式识别与人工智能, 2010, 23(6): 794-801.
(XU Y C, DONG F M, LIU Y, et al. Genetic Algorithm for Rectangle Layout Optimization with Equilibrium Constraints. Pattern Recognition and Artificial Intelligence, 2010, 23(6): 794-801.)
[26] 武志峰,黄厚宽,赵翔.二进制编码差异演化算法在Agent联盟形成中的应用.计算机研究与发展, 2008, 45(5): 848-852.
(WU Z F, HUANG H K, ZHAO X. A Binary-Encoding Differential Evolution Algorithm for Agent Coalition. Journal of Computer Research and Development, 2008, 45(5): 848-852.)
[27] LIU J H, MEI Y, LI X D. An Analysis of the Inertia Weight Parameter for Binary Particle Swarm Optimization. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 666-681.
[28] LIU Y, ZHANG G F, SU Z P, et al. Using Computational Intelligence Algorithms to Solve the Coalition Structure Generation Problem in Coalitional Skill Games. Journal of Computer Science and Technology, 2016, 31(6): 1136-1150.