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

多Agent系统是分布式人工智能领域的两个重要研究分支之一,其研究已经为智能机器人系统、云计算、搜索引擎、交通控制、网络通信等诸多应用领域核心问题的解决开辟了新的思路,并推动了相关应用领域中实际复杂系统的形成与发展。在多Agent系统研究领域,多个Agent如何进行有效合作和效用分配的问题是该领域的核心问题之一。基于合作博弈理论进行多Agent系统的联盟形成与效用分配问题的研究已经取得了诸多成果,其基于合作博弈理论的研究方法也得到了普遍的认可。然而,由于多Agent系统本身的复杂性和合作博弈理论到具体应用的难点,使得基于合作博弈理论对多Agent系统的联盟形成和效用分配问题的研究仍然存在许多待解决的问题。针对现有研究仍待解决的问题,论文基于合作博弈理论对多Agent系统的联盟形成与分配问题进行了深入的研究,其研究工作具有一定的理论意义。论文具体的研究工作如下： (1)以公平分配为原则基于合作博弈理论中Shapley值的公平分配特性针对多Agent系统的动态联盟形成和分配问题进行了研究。首先,论文提出了一种快速的静态初始化联盟形成算法。其次,针对Agent个体的参与能力和任务发生动态变化的情况,论文提出了一种联盟形成的快速动态更新算法；针对Shapley值求解效率差的问题,论文提出一种快速求解联盟中各个Agent近似Shapley值分配的算法。实验结果表明所提算法不仅获得了预期联盟形成结果和合理分配,而且具有较低的算法复杂度。 (2)以稳定分配为原则基于合作博弈理论中谈判集的稳定分配特性对多Agent系统的联盟形成与分配问题进行了研究。针对求解谈判集的复杂博弈问题,借助删除谈判劣势联盟后获得的精简联盟集合,提出了一种基于遗传算法的稳定分配向量的求解算法,并给出了基于精简联盟集合获得的谈判集与经典谈判集相等的证明。论文进一步提出了一种基于字典序比较寻找联盟结构集合中最稳定联盟结构及稳定分配向量的算法。实验结果表明所提出算法不仅保证了求解的成功率,而且具有较低的算法复杂度。 (3)针对多选择合作博弈关于稳定分配解理论的不足,论文将经典合作博弈中谈判集、内核和核仁等与稳定分配相关的概念拓展到多选择合作博弈中,并证明了谈判集的存在性、核仁的存在且唯一性、以及内核、核仁和谈判集三者之间的关系。借助拓展的稳定分配解,论文提出了基于多选择合作博弈求解复杂多Agent系统稳定分配向量的方法,并给出了一种基于遗传算法求解多个Agent在不同级别上稳定分配向量的算法。