Algorithm for Maximal Successful Coalition Generation with Goals Preferences
ZHANG Guofu, DU Xiaodong, SU Zhaopin, JIANG Jianguo
School of Computer and Information, Hefei University of Technology, Heifei 230009 Engineering Research Center of Safety Critical Industrial Measurement and Control Technology, Ministry of Education, Hefei University of Technology, Hefei 230009
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.
Fund:Supported by National Natural Science Foundation of China(No.61573125,61371155), Natural Science Foundation of Anhui Pro-vince(No.1608085MF131,1508085MF132,1508085QF129)
About author:: (ZHANG Guofu(Corresponding author), born in 1979, Ph.D., associate professor. His research interests include complex systems, coalitional games and computational intelligence.) (DU Xiaodong, born in 1992, master student. Her research interests include multi-agent systems and evolutionary computation.) (SU Zhaopin, born in 1983, Ph.D., associate professor. Her research interests include evolutionary computation, disaster emergency decision-making and multimedia security.) (JIANG Jianguo, born in 1955, master, professor. His research interests include distributed intelligent systems and digital image processing and analysis.)
[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.983n)时间复杂度的最优联盟结构生成算法.软件学报, 2011, 22(5): 938-950. (LIU J L, ZHANG W, TONG X R, et al. O(2.983n) 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, DERNYI 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] CECHLROV 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.
2017, Vol. 30 
