基于推理的分布式约束优化完备算法研究及实验平台实现

发布时间：2017-11-19 01:18

  本文关键词：基于推理的分布式约束优化完备算法研究及实验平台实现

  更多相关文章： 分布式约束优化 动态规划 通信结构 广度优先搜索 割点

【摘要】：分布式约束优化是对多Agent系统的建模,广泛应用于求解分布式计划、分布式调度和分布式资源分配问题,典型应用有灾难救援、多Agent小组合作、分布式机器人、会议调度、传感器网络等。DPOP算法是一种基于动态规划思想的推理式算法,也是当前分布式约束优化完备算法中效率最高的算法之一。DPOP算法的性能和效率远远高于许多搜索类算法,非常适合于实际应用问题的求解。本文基于DPOP算法,从通信结构的角度提出改进和优化思路,并在自主开发的分布式约束优化算法实验平台DCOPSolver上实验和证明思路的可行性,具体研究工作如下:(1)介绍了分布式约束优化的研究现状和最新研究动态,详细阐述了分布式约束优化的基本概念和定义,包括约束图、通信结构和图着色、会议调度、随机DCOP三类典型问题,并重点介绍了本文的主要研究对象DPOP算法。(2)提出一种新的以广度优先搜索伪树为通信结构的BFSDPOP算法。相比DPOP采用的深度优先搜索伪树通信结构,BFSDPOP采用的广度优先搜索伪树通信结构具有分支多、通信路径短的特点,使得BFSDPOP算法的并行运算性能和通信效率更优。同时,本文提出ClusterRemoving算法通过合理分配伪树中的交叉边,很好地控制了算法中生成的最大消息大小。(3)提出一种新的以深度优先搜索伪树为通信结构的CVDPOP算法,它以最佳割点和最大度数优先的策略构建其伪树通信结构。CVDPOP算法的创新之处在于引入割点引导深度优先搜索伪树的构建,借助割点促进分支生成的特点构建分支更多、质量更优的深度优先搜索伪树,从而提高算法性能。(4)鉴于已有实验平台的复杂性,本文自主开发了一套新的分布式约束优化算法实验平台DCOPSolver,它具有功能模块更加精简,新算法扩展集成难度更小、速度更快的特点。本文的所有实验均在DCOPSolver上实施,实验比较了DPOP、BFSDPOP、CVDPOP三种算法分别求解图着色问题、会议调度问题和随机DCOP问题时的运行时间和最大消息维度。实验结果显示BFSDPOP和CVDPOP算法相比原始DPOP算法均具有显著优势,证明了广度优先搜索伪树和最佳割点最大度数优先策略对提高算法效率和性能的积极作用。
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP181

【相似文献】

中国期刊全文数据库 前1条

1 曾凡刊;求线图树集的综合方法——二模域代数拓扑树组法[J];华中工学院学报;1982年02期

中国硕士学位论文全文数据库 前1条

1 何振;基于推理的分布式约束优化完备算法研究及实验平台实现[D];重庆大学;2016年

，

本文编号：1201824