论文部分内容阅读
联盟形成一直是多agent系统(multi-agent systems,MAS)和人工智能领域的一个研究热点,主要研究如何形成联盟以及形成哪些联盟可以使系统的总收益最大。然而,已有工作大都不考虑agent对于目标的偏好性,即每个agent可以参与任何目标,即使agent对这些目标毫无兴趣。在一些特殊应用场景,如角度视角受限的多摄像头协同监控系统,每个智能摄像头的行为具有很强的目标偏好性,它只会响应其监控区域内能捕捉到的目标,而对于监控区域外的目标则无能为力;又例如在灾害应急响应中,由于应急响应在时效性上的高要求,每个储备点都会优先满足就近的受灾点的需求,而不可能耗费大量人力和物力去响应很远的受灾点的需求。鉴于上述背景,本文在传统资源结盟博弈的基础上考虑agent对响应目标的严格偏好性,研究严格目标偏好下的最大成功联盟问题,本文主要研究工作如下:(1)介绍了相关的研究背景,以及国内外对联盟形成问题、尤其是资源结盟博弈的研究现状,分析并总结了当前最大成功联盟生成问题研究中存在的不足,以确定本文的研究动力和主要研究内容。(2)介绍了相关基础理论知识,包括MAS和联盟的相关概念,以及联盟形成相关理论。最后介绍了几种与本文有关的经典的优化算法,包括遗传算法、粒子群算法和最大流算法等。(3)根据agent对目标的严格偏好,基于“资源贡献量”和“资源剩余量”对传统资源结盟博弈模型进行了改进,并从理论上分析了成功联盟的充分必要条件以及搜索最大成功联盟问题的计算复杂性。(4)针对严格目标偏好下的最大成功联盟(largest successful coalition,LSC)问题,首先基于最大流网络设计了一个指数级的确定性求解算法(flow-network based exhaust algorithm,FNet EA)以获取LSC问题的全局最优解。为了提高问题的求解效率,又基于遗传算法、二维二进制编码和启发式修正方法设计了一个二维混合搜索算法(two-dimensional hybrid algorithm,2D-HA)。对比实验结果表明,2D-HA算法在求解LSC问题上表现出了很好的有效性和求解效率,可以在大规模LSC问题上耗费很短的时间就能找到和确定性算法FNet EA一样的最优解,且2D-HA算法性能不受agent数、目标数和资源数的影响,具有很强的鲁棒性。