联盟博弈中最优联盟结构的生成算法：研究综述.docVIP

 联盟博弈中最优联盟结构的生成算法：研究 综述# 韩格1，岳昆1，李劲2，赵小明3，刘惟一1** 5 10 15 20 25 30 （1. 云南大学信息学院，昆明 650091； 2. 云南大学软件学院，昆明 650091； 3. 云南机电职业技术学院工业信息与技术系，昆明 650203） 摘要：博弈现象广泛存在于现实中的各个领域，基于智能系统的多 Agent 联盟博弈受到了学 术界的广泛关注，生成最优的联盟格局和结构是多 Agent 联盟博弈的关键问题。有哪些信誉好的足球投注网站最优联 盟结构是一个 NP 问题，一直是多 Agent 联盟博弈研究中的重要挑战之一。本文分析总结了 目前最优联盟结构的有哪些信誉好的足球投注网站算法，主要包括：动态规划算法、启发式有哪些信誉好的足球投注网站算法、任意时间复杂 度算法。比较了各类算法的优缺点与适用性，也讨论了该领域进一步的研究工作和将来的研 究思路。 关键词：多 Agent；联盟博弈；最优联盟结构；任意时间复杂度算法 中图分类号：TP18 Algorithms for generating optimal coalition structures in the coalitional game: A survey HAN Ge1, YUE Kun1, LI Jin2, ZHAO Xiaoming3, LIU Weiyi1 (1. School of Information Science and Engineering, Kunming 650091; 2. School of Software, Kunming 650091; 3. Department of Industrial Information and Technology, Yunnan Vocational College of Mechanical and Electrical Technology, Kunming 65020) Abstract: Game phenomenon exists widely in various fields in the real world. Intelligent- system-based multi-agent coalition game has attracted great attention in academic areas. Generating optimal coalition structures is the critical problem of the coalitional game with multiple agents. To Search the optimal coalition structure is NP-hard and is one of the challenges in the study of multi-agent coalitional game. In this paper, we summarize and analyze the main algorithms for searching the optimal coalition structure, including dynamic programming, heuristics algorithm and anytime algorithm. We compare the advantages, disadvantages and suitability of these algorithms respectively. As well, we discuss the research work and ideas that may be considered in the future.. Key words: Multi-agent; Coalition game; Optimal coalition structure; Algorithm 35 0 引言 从“石头-剪刀-布”游戏到房地产经济策略调控，这些多参与者行为相互影响的普遍现象 都是博弈现象，广泛存在于现实生活中的各个领域[1-3]，如经济、计算机、军事、政治及外 交等。博弈论[4]是研究博弈现象并对其进行建模和计算的一门学科，研究若干利益冲突者在 40 同一环境中如何进行决策以满足自身利益。 博弈论最早被归为经济学的一个分枝，并在相关领域取得了一系列成果。实际上，博弈 基金项目：国家自然科学基金项目；教育部博士点基金新教师类课题 （20105301120001）；教育部科学技术研究重点项目（211172）；云南省应用基础研究项目（2011FZ013）； 云南省教育厅科研基金重点项目（2011Z