面向多Agent系统的博弈联盟形成与分配问题研究

发布时间：2018-06-21 13:08

本文选题：多Agent系统 + 联盟形成　；参考：《云南大学》2013年博士论文

【摘要】：多Agent系统是分布式人工智能领域的两个重要研究分支之一,其研究已经为智能机器人系统、云计算、搜索引擎、交通控制、网络通信等诸多应用领域核心问题的解决开辟了新的思路,并推动了相关应用领域中实际复杂系统的形成与发展。在多Agent系统研究领域,多个Agent如何进行有效合作和效用分配的问题是该领域的核心问题之一。基于合作博弈理论进行多Agent系统的联盟形成与效用分配问题的研究已经取得了诸多成果,其基于合作博弈理论的研究方法也得到了普遍的认可。然而,由于多Agent系统本身的复杂性和合作博弈理论到具体应用的难点,使得基于合作博弈理论对多Agent系统的联盟形成和效用分配问题的研究仍然存在许多待解决的问题。针对现有研究仍待解决的问题,论文基于合作博弈理论对多Agent系统的联盟形成与分配问题进行了深入的研究,其研究工作具有一定的理论意义。论文具体的研究工作如下： (1)以公平分配为原则基于合作博弈理论中Shapley值的公平分配特性针对多Agent系统的动态联盟形成和分配问题进行了研究。首先,论文提出了一种快速的静态初始化联盟形成算法。其次,针对Agent个体的参与能力和任务发生动态变化的情况,论文提出了一种联盟形成的快速动态更新算法；针对Shapley值求解效率差的问题,论文提出一种快速求解联盟中各个Agent近似Shapley值分配的算法。实验结果表明所提算法不仅获得了预期联盟形成结果和合理分配,而且具有较低的算法复杂度。 (2)以稳定分配为原则基于合作博弈理论中谈判集的稳定分配特性对多Agent系统的联盟形成与分配问题进行了研究。针对求解谈判集的复杂博弈问题,借助删除谈判劣势联盟后获得的精简联盟集合,提出了一种基于遗传算法的稳定分配向量的求解算法,并给出了基于精简联盟集合获得的谈判集与经典谈判集相等的证明。论文进一步提出了一种基于字典序比较寻找联盟结构集合中最稳定联盟结构及稳定分配向量的算法。实验结果表明所提出算法不仅保证了求解的成功率,而且具有较低的算法复杂度。 (3)针对多选择合作博弈关于稳定分配解理论的不足,论文将经典合作博弈中谈判集、内核和核仁等与稳定分配相关的概念拓展到多选择合作博弈中,并证明了谈判集的存在性、核仁的存在且唯一性、以及内核、核仁和谈判集三者之间的关系。借助拓展的稳定分配解,论文提出了基于多选择合作博弈求解复杂多Agent系统稳定分配向量的方法,并给出了一种基于遗传算法求解多个Agent在不同级别上稳定分配向量的算法。
[Abstract]:Multiple Agent system is one of the two important research branches in the field of distributed artificial intelligence. It has been studied as intelligent robot system, cloud computing, search engine, traffic control, etc. The solution of many core problems in application fields such as network communication has opened up new ideas and promoted the formation and development of practical complex systems in related application fields. In the research field of multiple Agent systems, how to effectively cooperate and allocate the utility of multiple Agent is one of the core problems in this field. The research on alliance formation and utility allocation of multiple Agent systems based on cooperative game theory has made many achievements, and its research methods based on cooperative game theory have been generally accepted. However, due to the complexity of multiple Agent systems and the difficulties of cooperative game theory to specific application, there are still many problems to be solved in the research of alliance formation and utility allocation of multi-Agent systems based on cooperative game theory. Aiming at the problems that still remain to be solved, this paper makes a deep study on the formation and distribution of alliances in multiple Agent systems based on the cooperative game theory, which has a certain theoretical significance. The main work of this paper is as follows: 1) based on the principle of fair distribution, the paper studies the formation and allocation of dynamic alliances in multiple Agent systems based on the Shapley value in cooperative game theory. Firstly, a fast static initialization algorithm is proposed. Secondly, in view of the dynamic change of Agent individual's participation ability and task, this paper proposes a fast dynamic updating algorithm to form alliance, aiming at the problem of poor efficiency of solving Shapley value. In this paper, a fast algorithm to solve the Agent approximate Shapley value assignment in the alliance is proposed. Experimental results show that the proposed algorithm not only obtains the expected alliance formation results and reasonable allocation, Based on the stable assignment characteristics of negotiation sets in cooperative game theory, the formation and allocation of alliances in multi-Agent systems are studied. In order to solve the complex game problem of negotiation set, a stable assignment vector solving algorithm based on genetic algorithm is proposed by means of the reduced alliance set obtained after deleting the negotiating inferior alliance. The proof that the negotiation set based on the reduced alliance set is equal to the classical negotiation set is given. This paper further proposes an algorithm based on dictionary order comparison to find the most stable alliance structure and stable assignment vector in the set of alliance structures. The experimental results show that the proposed algorithm not only guarantees the success rate of the solution, but also has low computational complexity. The concepts of kernel and nucleolus which are related to stable distribution are extended to multi-choice cooperative game. The existence and uniqueness of negotiation set, the existence and uniqueness of nuclear kernel, and the relationship among kernel, nucleolus and negotiation set are proved. Based on the extended stable assignment solution, this paper proposes a method to solve the stable allocation vector of complex Agent system based on multi-selection cooperative game, and gives an algorithm based on genetic algorithm to solve the stable assignment vector of multiple Agent at different levels.
【学位授予单位】：云南大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP18

【参考文献】