论文部分内容阅读
分布式约束优化问题(DCOP)是多智能体系统(MAS)的基本框架,是对分布式问题解决、多智能体协作的重要建模方式,现已成功应用于任务调度、电力系统等领域。非对称分布式约束优化问题(ADCOP)在DCOP的基础上增加了Agent的私有偏好,具有更强的建模的能力和更大的应用前景。以最大和算法(Max-sum)为代表的推理算法作为求解DCOP/ADCOP的重要手段,广泛地应用于各种实际场景中。然而,现有的非完备推理算法普遍存在着难以收敛、解的质量较差的问题。此外,由于ADCOP对隐私性的要求,传统用于求解DCOP的完备推理算法无法直接用于ADCOP,而现有的求解ADCOP的完备搜索算法普遍存在着求解问题规模较小、隐私性较差等问题。针对以上问题,本文拟从求解DCOP的非完备推理算法和求解ADCOP的完备算法开展研究。具体研究内容如下:(1)深入分析了值传播机制Max-sum类算法的影响。本文从理论上证明了虽然值传播可以极大地提高算法的性能,但是其同时阻碍了Max-sum类算法的信念传播。特别地,本文证明了当在换向有向无环图上连续执行值传播机制时,智能体将完全无法利用全局累加的信念,因此算法将等价于一个顺序的贪心局部搜索算法。由此,提出了在值传播机制下如何有效地平衡探索与利用这一重要的科学问题。(2)为了解决上述问题,本文提出了一系列基于非连续值传播的Max-sum类算法,包括基于单向值传播的Max-sum_AD算法(Max-sum_ADSSVP),基于混合信念/值传播的Max-sum算法(Max-sum_HBVP)和基于概率值传播的Max-sum_AD算法。这些算法通过打破在有向无环图上反复执行值传播这一桎梏,使得智能体在作出决策时可以同时兼顾个体利益和全体利益。本文还从理论上说明了上述算法不会等价于贪心的局部搜索算法,并分析了其时空复杂度。实验结果表明,上述算法显著优于传统的非完备推理算法,且对值传播机制开始启用的时机不敏感。(3)充分考虑了ADCOP的特点,针对ADCOP对隐私性的要求,创新性地提出了一种基于搜索-推理混合的完备算法PT-ISBB。该算法利用完备推理算法速度较快这一优势,预先求解一面的约束,并将推理结果存储;在搜索阶段,利用伪树中不同分支间相互独立这一事实,不断将问题划分为更小的子问题。在每一个节点上,都使用子树的推理结果作为取值的下界,以实现高效率的剪枝。本文同时在理论上证明了其完备性,并分析了其复杂度。实验结果表明,PT-ISBB在多个测试问题上均优于传统的搜索算法。