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

《基于推理的分布式约束优化完备算法研究及实验平台实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于推理的分布式约束优化完备算法研究及实验平台实现重庆大学硕士学位论文(专业学位)学生姓名：何振指导教师：陈自郁讲师学位类别：工程硕士（计算机技术领域）重庆大学计算机学院二O一六年四月TheStudyonInferenceBasedCompleteDCOPAlgorithmsandExperimentPlatformImplementationAThesisSubmittedtoChongqingUniversityinPartialFulfillmentoftheRequirementfortheMaster’sDegreeofEng

2、ineeringByHeZhenSupervisedbyLec.ChenZiyuSpecialty:ME(ComputerTechnologyAreaField)CollegeofComputerScienceofChongqingUniversity,Chongqing,China.April,2016中文摘要摘要分布式约束优化是对多Agent系统的建模，广泛应用于求解分布式计划、分布式调度和分布式资源分配问题，典型应用有灾难救援、多Agent小组合作、分布式机器人、会议调度、传感器网络等。DPOP算法是一种基于动态规划思想的推理式算

3、法，也是当前分布式约束优化完备算法中效率最高的算法之一。DPOP算法的性能和效率远远高于许多搜索类算法，非常适合于实际应用问题的求解。本文基于DPOP算法，从通信结构的角度提出改进和优化思路，并在自主开发的分布式约束优化算法实验平台DCOPSolver上实验和证明思路的可行性，具体研究工作如下：①介绍了分布式约束优化的研究现状和最新研究动态，详细阐述了分布式约束优化的基本概念和定义，包括约束图、通信结构和图着色、会议调度、随机DCOP三类典型问题，并重点介绍了本文的主要研究对象DPOP算法。②提出一种新的以广度优先搜索伪树为通信结构的B

4、FSDPOP算法。相比DPOP采用的深度优先搜索伪树通信结构，BFSDPOP采用的广度优先搜索伪树通信结构具有分支多、通信路径短的特点，使得BFSDPOP算法的并行运算性能和通信效率更优。同时，本文提出ClusterRemoving算法通过合理分配伪树中的交叉边，很好地控制了算法中生成的最大消息大小。③提出一种新的以深度优先搜索伪树为通信结构的CVDPOP算法，它以最佳割点和最大度数优先的策略构建其伪树通信结构。CVDPOP算法的创新之处在于引入割点引导深度优先搜索伪树的构建，借助割点促进分支生成的特点构建分支更多、质量更优的深度优先搜

5、索伪树，从而提高算法性能。④鉴于已有实验平台的复杂性，本文自主开发了一套新的分布式约束优化算法实验平台DCOPSolver，它具有功能模块更加精简，新算法扩展集成难度更小、速度更快的特点。本文的所有实验均在DCOPSolver上实施，实验比较了DPOP、BFSDPOP、CVDPOP三种算法分别求解图着色问题、会议调度问题和随机DCOP问题时的运行时间和最大消息维度。实验结果显示BFSDPOP和CVDPOP算法相比原始DPOP算法均具有显著优势，证明了广度优先搜索伪树和最佳割点最大度数优先策略对提高算法效率和性能的积极作用。关键词：分布式

6、约束优化，动态规划，通信结构，广度优先搜索，割点I英文摘要ABSTRACTDistributedConstraintOptimizationisthemodelforMultiagentSystemandiswidelyappliedinsolvingproblemsofdistributedplanning,distributedschedulinganddistributedresourceallocation,wheredisasterrescue,multiagentteamwork,distributedrobots,meet

7、ingschedulingandsensornetworksaretypicalapplications.TheDPOPalgorithmisaDynamicProgrammingbasedinferencingalgorithmandisalsooneofthemostefficientDCOPcompletealgorithm.Itsprominentadvantageovermanyotheralgorithmsmakesitreallyappropriatetosolvereal-lifeproblems.Thispaperca

8、rriesouttheresearchworkbyimprovingtheperformanceofDPOPalgorithmfromcommunicationstructureandconductsthe