导读:本文包含了分布式约束优化问题论文开题报告文献综述及选题提纲参考文献，主要关键词:分布式约束优化问题,非对称约束优化问题,推理算法,最大和
分布式约束优化问题论文文献综述
邓衍晨[1]（2018）在《求解分布式约束优化问题的推理算法研究》一文中研究指出分布式约束优化问题(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在多个测试问题上均优于传统的搜索算法。(本文来源于《重庆大学》期刊2018-04-01）
吴腾飞[2]（2018）在《基于蚁群优化思想的分布式约束优化问题求解算法研究》一文中研究指出分布式约束优化问题(DCOP)和非对称分布式约束优化问题(ADCOP)是解决分布式人工智能领域中多智能体系统(MAS)协同优化问题的重要方法,具有研究意义和实用价值。目前,DCOP求解算法大多是基于集中式单点寻优算法而提出的。而对于ADCOP求解算法的研究尚处于起步阶段,研究成果十分有限。蚁群优化思想(ACO)算法是一种基于种群的集中式优化算法,可以有效地解决集中式中组合优化问题,却很少应用于分布式约束推理问题中。DCOP和ADCOP可以看作是分布式的组合优化问题。因此,本文致力于提出一种基于蚁群优化思想的DCOP和ADCOP求解算法。主要工作如下:①提出了基于蚁群优化思想的DCOP求解算法(ACO_DCOP)。结合DCOP模型特点,本文主要研究了 ACO中构造图结构、转移概率、信息素更新等问题,将ACO应用于求解分布式约束优化问题。因此,本文提出了基于广度优先树结构的构造图。并且转移概率信息素部分考虑了当前上文取值状态,减少了无关信息素对决策的干扰;引入了局部代价预估机制,根据已构造的解来推测Agent赋值可能造成的局部代价预估值,使得启发式信息更加合理的反映Agent局部利益。对于信息素更新部分,本文将解的均值作为评价解的质量的标准,对信息素更新引入奖励惩罚机制,并提出加权信息素增量,来缓解过度惩罚的情况。此外,为了提高算法的并发性,本文引入了流水线技术。在理论分析中,我们证明了ACO_DCOP是一个anytime算法。最后,实验验证了ACO_DCOP算法的性能优于现有的DCOP非完备算法。②提出基于蚁群优化思想的ADCOP求解算法(ACO_ADCOP)。针对ADCOP的不对称性和ACO模型特点,本文主要研究了ADCOP中双向求解问题、隐私性、以及构造图和转移概率等问题。ACO_ADCOP采用深度优先伪树作为构造图结构。针对ADCOP中双向约束求解的问题,本文引入了基于树的反向检测机制,并且消息传递时仅与累加代价相关,保证了 Agent的隐私性。此外,在转移概率中启发式部分引入了局部代价预估机制,即启发式信息不仅考虑当前解与高优先级邻居造成的真实代价,还考虑了其与邻居的代价预估值,可以更好的评估局部利益。最后,本文实验验证了 ACO_ADCOP算法性能优于现有的ADCOP非完备算法。(本文来源于《重庆大学》期刊2018-04-01）
刘建平[3]（2017）在《分布式约束优化在传感器网络目标跟踪问题中的应用研究》一文中研究指出分布式约束优化问题(DCOP)是一种用于解决多Agent系统协作优化问题的重要建模方式,具有隐私性、信息局部性、控制分散化等特点。目前对该领域的研究主要是算法理论方面的研究,应用研究较少。在DCOP的应用研究中,传感器网络是一个主要的应用领域。传感器网络中目标跟踪问题较适用于DCOP建模,受到了广泛关注。但是目前对该问题的DCOP建模存在一些问题,例如模型定义不清晰或缺乏现实物理意义。本文针对该问题,为一类传感器网络的目标跟踪问题提出了一种具有现实物理意义的DCOP模型,并提出了适用于该模型的求解算法,具体研究工作如下:1介绍了传感器网络目标跟踪问题的研究现状,并对使用非分布式方式和使用DCOP建模这两种方式在该问题上研究的重点进行了分析和比较。然后,具体介绍了DCOP的基本定义以及其约束图表述,并较详细地介绍了DSA和MGM两种DCOP近似求解算法。此外,详细描述了传感器网络目标跟踪问题的几类DCOP建模方法,并阐述了这些模型的优缺点。2将一类传感器网络目标跟踪问题抽象为一种图多着色问题,并针对图多着色问题提出两种不同的DCOP模型:ACSV和ACMV。ACSV模型采用一个agent控制一个变量的方式,它的最大特点是变量的取值是一个颜色集合,而不是一个单独的值;ACMV模型采用一个agent控制多变量的方式,它的最大特点是每个变量不仅仅需要考虑外部约束,同时必须满足内部约束。然后对这两种模型的优缺点进行比较。3基于DSA和MGM,提出了两种用于解决图多着色问题的分布式约束优化算法MGCDSA和MGCMGM。针对图多着色问题,MGCDSA和MGCMGM添加了新的预处理过程:“剪枝”和“降维”。剪枝用于忽略每个agent中没有外部约束关系的变量,降维可以减小两个变量之间约束代价矩阵的维度。实验证明了这两种算法都可以较好地解决图多着色问题。4对现有的分布式约束优化问题平台DCOPSolver进行了扩充,添加了传感器网络目标跟踪问题对应的图多着色问题生成和解析模块,并对平台中的通信逻辑以及结果展示模块进行了完善。(本文来源于《重庆大学》期刊2017-04-01）
余浙鹏[4]（2017）在《基于局部搜索的分布式约束优化问题求解算法研究》一文中研究指出分布式约束优化问题(DCOP)作为多Agent系统协作问题的重要抽象,具有隐私性、信息局部性、控制分散化等特点,是对分布式智能系统和多目标优化等问题的有效建模技术。因此,对分布式约束优化问题的求解成为该领域的研究热点。局部搜索算法作为一类求解DCOP的非完备算法,由于其简单的逻辑结构和灵活的优化方式,受到了广泛的关注。本文介绍了分布式约束优化问题求解算法的国内外研究现状,分析了各类算法的优点和局限性,并针对局部搜索算法存在的局限性以及智能优化引导两个方面展开研究,主要工作如下:(1)针对局部搜索算法中相邻Agent之间赋值相互依赖的限制,提出了部分决策机制(PDS)。该机制通过Agent在决策过程中忽略部分邻居结点的赋值信息来打破相邻Agent之间的赋值依赖关系,获取更大的决策空间,做出更优的决策,从而以较小的代价有效地提高了算法的求解质量。PDS包含两个部分决策过程:触发式部分决策和递归式部分决策。前者在Agent不能提高自身利益时触发,通过忽略邻居的取值信息来跳出赋值依赖造成的潜在局部收敛状态;而后者不断地由被忽略的Agent触发来提升全局利益。此外,PDS通过一个包含自适应概率的触发条件来控制部分决策的执行。该机制可以结合任意局部搜索算法进行优化,具有很大的普适性。本文从理论上论证了部分决策机制的可行性和收敛性,并通过实验验证了该机制的有效性。(2)提出了基于局部搜索的遗传优化算法(LS-GA)。算法结合了遗传优化的智能性和局部搜索的灵活性,作为智能优化算法求解DCOP的一种新尝试。本文提出了mALS框架作为ALS框架的改进,使其能够在分布式环境下记录种群的最优个体,并针对DCOP的特点调整了基因的编码方式,以块状区域作为个体的基因片段,提出基于随机策略和竞争策略的两种交叉算子,以及基于mALS框架和预定模式的选择算子,以此确保遗传算法中不同Agent对个体进行交叉变异操作的一致性。最后通过实验对比不同算法,验证LS-GA的有效性。(本文来源于《重庆大学》期刊2017-04-01）
于慧慧,王永丽,陈勇勇,周秀娟[5]（2016）在《求解无约束一致性优化问题的分布式拟牛顿算法》一文中研究指出本文主要针对网络中各个节点相互协作,最大限度地使本地费用函数的总和最小的无约束一致性优化问题,提出了一类分布式拟牛顿算法。算法仅利用了目标函数的一阶导数信息,每步通过选取一个满足拟牛顿方程的正定对角矩阵来作为费用函数Hesse矩阵逆的校正矩阵,克服了校正矩阵的非稀疏性对算法分布式实现造成的困难,减少了计算量和存储空间。在适当条件下,证明了分布式拟牛顿算法的全局收敛性及局部线性收敛速度,并通过数值实验验证了算法的优越性。(本文来源于《山东科技大学学报(自然科学版)》期刊2016年03期）
何琛[6]（2016）在《求解分布式约束优化问题的搜索算法研究》一文中研究指出分布式约束优化问题(DCOP)作为多Agent系统协作问题的重要而有用的抽象,是解决分布式智能系统建模和多目标协同优化的有效技术,具有重要的研究意义和实用价值。与传统的集中控制相比,DCOP提供了强的鲁棒性、隐私性,适用于求解规模大、难度高的组合问题,已成为分布式人工智能领域的研究热点。与此同时,分布式约束优化问题的求解算法也随之被广泛研究,分为完备算法与非完备算法两大类。完备算法旨在搜索所有组合空间,保证最终找到全局最优解;非完备算法旨在在有限的时间内,尽最大努力找到一个较好解。搜索策略是这两类算法采用的典型求解策略,已成为了研究的热点。然而,目前的搜索策略存在较多局限性,不能满足实际问题的需要。在完备算法中主要表现为搜索策略单一;在非完备算法中主要表现为仅依据个体局部信息引导搜索,易陷入局部最优。针对上述问题,论文从策略融合和群智能引导两个方面分别对完备算法与非完备算法展开研究。主要工作如下:(1)介绍了分布式约束优化算法的研究现状、分布式约束优化问题的相关定义和常用通信结构以及分布式约束优化实验的测试问题、实验平台与评价指标。较详细介绍了基于最好优先搜索与深度优先搜索策略的两个典型完备算法以及蚁群优化的相关知识与蚁群优化解决分布式约束满足问题(DCSP)的算法。并且,深入分析了最好优先搜索与深度优先搜索策略各自的特征和存在的问题,探讨了两种搜索策略与伪树的关系,为后面两种策略的结合提供了依据。(2)提出了深度优先搜索与最好优先搜索策略结合的DCOP完备算法。该算法依据两种搜索策略与伪树的关系,采用分层的思想,根据agent在伪树中的位置特点分别采用深度优先搜索策略或最好优先搜索策略,并且给出了分层规则和两种策略的无缝对接方法。该算法不仅充分发挥了两种策略各自的优势,并且保持了原单一策略算法的数据结构与消息类型,没有加剧算法的处理复杂性。本文从理论和实验论证了BD-ADOPT的完备性和有效性。(3)提出了基于蚁群优化引导的DCOP非完备算法。算法引入蚁群优化的群智能特点,依据个体之间协作产生的全局信息引导个体做决策选择从而提高算法的搜索性能。该算法充分考虑了DCSP和DCOP的不同,采用伪树结构作为构造图,提高了搜索的并发性;针对DCOP的特点,设计了对数运算与求倒运算结合的信息素更新与引导概率的计算方式;引入流水线的消息处理机制,提高了搜索效率。最后,通过与其他的算法进行对比验证了该算法的可行性和有效性。(本文来源于《重庆大学》期刊2016-04-01）
李小玲,王怀民,郭长国,丁博,李小勇[7]（2015）在《分布式约束优化问题研究及其进展》一文中研究指出多Agent协作过程中的许多问题都可以被抽象为分布式约束优化问题(DCOP),如规划、行程安排、分布式控制和资源分配等.这些问题关注于如何通过协调多Agent之间的相互决定,以达到一个全局最优决策的目的.相应地,分布式约束优化算法是用来求解此类问题的一种有效方式.该文对分布式约束优化问题进行了综述,首先,阐述了分布式约束优化问题的基本概念,并提出了一种分布式约束优化算法的分类框架.其次,根据该分类框架,介绍了目前已有的分布式约束优化算法,并加以对比分析.此外,分析了分布式约束优化问题的相关应用.最后,指明了分布式约束优化领域的未来研究趋势.(本文来源于《计算机学报》期刊2015年08期）
马轶轶[8]（2015）在《多智能体分布式约束优化问题研究及应用》一文中研究指出随着科技、信息化的飞速发展。计算机系统已经从单机系统向分布式系统方向转变。日益复杂的问题已经逐渐超出了单机所能处理的范畴。越来越多的研究者寻求在多智能体分布式合作领域中进行求解。因此,在分布式环境下,如何最大限度地发挥智能体(Agent)计算和服务能力已经成为一个研究热点。这个领域比较传统的研究如未知环境下的机器人区域覆盖问题。特指利用传感设备,在移动机器人对环境没有任何认知的情况下,尽可能高效地遍历目标环境区域,或者满足覆盖时间短、重复路径少等优化目标。而随着云计算技术的兴起。其逐渐成为智能体计算与服务领域新的研究热点。作为一种全新的信息处理模式。其以虚拟化技术为支撑,将资源抽象成虚拟机的方式提供给用户,极大地对资源以及服务实现了有效利用。但是,伴随着云计算规模的增大,资源的最优化分配问题是一个NP-hard问题。本文以多智能体分布式约束优化问题为研究背景,做了以下几方面的工作。(1)从智能体以及分布式约束优化两个角度出发,研究了多智能体分布式约束优化问题的背景,研究现状以及特点。(2)对分布式约束优化算法相关理论进行了研究。从算法产生,算法流程等方面入手,重点介绍了本文研究所采用的核心算法,Max-sum算法。并通过与其他分布式算法的对比,分析了其在求解NP问题上的优越性。(3)研究云环境下资源分配的问题模型,利用多智能体分布式约束优化理论对其进行建模,并用Max-sum算法求解。重点探究基于Max-sum算法的机制相比于传统机制,在资源分配效益以及用户满意度上的优势。(4)通过对Max-sum算法自身结构的详细分析。提出了基于边际贡献的改进方案。并通过对比实验的方式,将本文提出改进方案与原算法以及Alex,Roger[1]提出的改进方案进行比较,验证了本文提出的改进方案的有效性与优越性。(5)研究了机器人区域覆盖问题模型,从问题概述,模型设计以及运行环境分析入手,详细探究了机器人区域覆盖问题的分布式约束优化建模,以及Max-sum算法在解决机器人最优化决策的具体过程。并与本组之前研究并发表的QLCA方法[2]进行了对比。(本文来源于《扬州大学》期刊2015-04-01）
葛方振,魏臻,陆阳,邱述威,李丽香[9]（2013）在《一种动态分布式约束优化问题协同求解算法》一文中研究指出多Agent协作过程中的许多问题都可在分布式约束优化问题(DCOP)框架下建模,但多局限于规划问题,且一般需Agent具有完全、准确收益函数.针对DCOP局限性,定义动态分布式约束优化问题(DDCOP),分析求解它的两个关键操作:Exploration和Exploitation,提出基于混沌蚂蚁的DDCOP协同求解算法(CA-DDCOP).该算法借鉴单只蚂蚁的混沌行为和蚁群的自组织行为,实现Exploration和Exploitation,根据玻尔兹曼分布,建立平衡Exploration和Exploitation的协同方法.通过多射频多信道无线Ad Hoc网络的信道分配验证该算法的有效性.(本文来源于《模式识别与人工智能》期刊2013年09期）
段沛博[10]（2013）在《分布式约束优化算法若干问题研究》一文中研究指出在实际生活中,许多问题都可以抽象成为多agent模型进行解决,而分布式约束优化(DCOP)算法是近年解决多agent问题的主要算法。多agent问题的求解具有NP难度,如何能够快速的获得最优、完备的解决方案,对提高生产率,促进社会的发展具有重要意义。虽然目前有很多DCOP算法,但由于大部分算法是针对问题的特殊求解目标提出的,而且算法的执行策略各异,求解质量也不尽相同,因此当有新的实际问题抽象成为多agent模型时,算法在选择上就出现了制约。其次,虽然当前有相关研究,将主要DCOP算法进行整合,建立了分布式约束优化问题解决框架(FRODO),但该框架主要用于算法性能分析,在实际问题应用中的算法选择方面存在不足,同时,由于该框架的提出时间较早,因此算法的时效性和性能两个方面也亟待提高。针对这些问题,本文分析了FRODO框架在解决实际问题时存在的不足。并根据分析结果,从算法的扩展性、策略自适应性两方面完善了算法框架。在此基础上,本文根据约束图特征对典型算法进行分类并给出了策略自适应匹配算法,最后,本文设计并实现了支持策略自适应的DCOP算法平台APLODO,针对平台测试过程中发现的MULBS算法的不足,对其进行了改进。在具体实现中,本文首先对实际问题在FRODO框架中的解决过程进行了分析,分析表明,一个支持策略自适应的DCOP算法框架,应具备良好的算法可扩展性以及策略自适应性,针对这两个特性,一方面,本文对DCOP算法的执行过程进行模块划分,并以MULBS算法为例阐述了该模式下的算法实现方式。另一方面,本文根据算法搜索策略、解的完整度、异步性、时效性选取了5种典型算法,在完善的评价指标体系下,从约束图密度、节点数量和取值空间大小叁个特征入手,对算法进行性能的分析、分类。然后,本文结合实际问题求解目标以及算法分类结果,提出策略自适应匹配算法,该算法的核心是算法的打分机制,其次,本文在FRODO框架基础上设计并实现了APLODO平台,最后通过对平台的算法测试,发现MULBS算法在冲突解决机制和算法并行性方面存在缺陷,因此本文给出了MULBS的改进算法MULBS+,实验表明,该算法除增加一定的通信信息外,在测试指标的其他方面都优于原算法。(本文来源于《东北大学》期刊2013-06-01）
分布式约束优化问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
分布式约束优化问题(DCOP)和非对称分布式约束优化问题(ADCOP)是解决分布式人工智能领域中多智能体系统(MAS)协同优化问题的重要方法,具有研究意义和实用价值。目前,DCOP求解算法大多是基于集中式单点寻优算法而提出的。而对于ADCOP求解算法的研究尚处于起步阶段,研究成果十分有限。蚁群优化思想(ACO)算法是一种基于种群的集中式优化算法,可以有效地解决集中式中组合优化问题,却很少应用于分布式约束推理问题中。DCOP和ADCOP可以看作是分布式的组合优化问题。因此,本文致力于提出一种基于蚁群优化思想的DCOP和ADCOP求解算法。主要工作如下:①提出了基于蚁群优化思想的DCOP求解算法(ACO_DCOP)。结合DCOP模型特点,本文主要研究了 ACO中构造图结构、转移概率、信息素更新等问题,将ACO应用于求解分布式约束优化问题。因此,本文提出了基于广度优先树结构的构造图。并且转移概率信息素部分考虑了当前上文取值状态,减少了无关信息素对决策的干扰;引入了局部代价预估机制,根据已构造的解来推测Agent赋值可能造成的局部代价预估值,使得启发式信息更加合理的反映Agent局部利益。对于信息素更新部分,本文将解的均值作为评价解的质量的标准,对信息素更新引入奖励惩罚机制,并提出加权信息素增量,来缓解过度惩罚的情况。此外,为了提高算法的并发性,本文引入了流水线技术。在理论分析中,我们证明了ACO_DCOP是一个anytime算法。最后,实验验证了ACO_DCOP算法的性能优于现有的DCOP非完备算法。②提出基于蚁群优化思想的ADCOP求解算法(ACO_ADCOP)。针对ADCOP的不对称性和ACO模型特点,本文主要研究了ADCOP中双向求解问题、隐私性、以及构造图和转移概率等问题。ACO_ADCOP采用深度优先伪树作为构造图结构。针对ADCOP中双向约束求解的问题,本文引入了基于树的反向检测机制,并且消息传递时仅与累加代价相关,保证了 Agent的隐私性。此外,在转移概率中启发式部分引入了局部代价预估机制,即启发式信息不仅考虑当前解与高优先级邻居造成的真实代价,还考虑了其与邻居的代价预估值,可以更好的评估局部利益。最后,本文实验验证了 ACO_ADCOP算法性能优于现有的ADCOP非完备算法。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
分布式约束优化问题论文参考文献
[1].邓衍晨.求解分布式约束优化问题的推理算法研究[D].重庆大学.2018
[2].吴腾飞.基于蚁群优化思想的分布式约束优化问题求解算法研究[D].重庆大学.2018
[3].刘建平.分布式约束优化在传感器网络目标跟踪问题中的应用研究[D].重庆大学.2017
[4].余浙鹏.基于局部搜索的分布式约束优化问题求解算法研究[D].重庆大学.2017
[5].于慧慧,王永丽,陈勇勇,周秀娟.求解无约束一致性优化问题的分布式拟牛顿算法[J].山东科技大学学报(自然科学版).2016
[6].何琛.求解分布式约束优化问题的搜索算法研究[D].重庆大学.2016
[7].李小玲,王怀民,郭长国,丁博,李小勇.分布式约束优化问题研究及其进展[J].计算机学报.2015
[8].马轶轶.多智能体分布式约束优化问题研究及应用[D].扬州大学.2015
[9].葛方振,魏臻,陆阳,邱述威,李丽香.一种动态分布式约束优化问题协同求解算法[J].模式识别与人工智能.2013
[10].段沛博.分布式约束优化算法若干问题研究[D].东北大学.2013