求解分布式约束优化问题的搜索算法研究

《求解分布式约束优化问题的搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、求解分布式约束优化问题的搜索算法研究重庆大学硕士学位论文（学术学位）学生姓名：何琛指导教师：陈自郁讲师专业：计算机系统结构学科门类：工学重庆大学计算机学院二O一六年四月TheResearchofSearchAlgorithmforSolvingDistributedConstraintOptimizationProblemsAThesisSubmittedtoChongqingUniversityinPartialFulfillmentoftheRequirementfortheMaster’sDegreeofEngineeringByHeChenSupervisedbyLec.Ch

2、enZiyuSpecialty:ComputerSystemandStructureCollegeofComputerScienceofChongqingUniversity,Chongqing,ChinaApril,2016中文摘要摘要分布式约束优化问题（DCOP）作为多Agent系统协作问题的重要而有用的抽象，是解决分布式智能系统建模和多目标协同优化的有效技术，具有重要的研究意义和实用价值。与传统的集中控制相比，DCOP提供了强的鲁棒性、隐私性，适用于求解规模大、难度高的组合问题，已成为分布式人工智能领域的研究热点。与此同时，分布式约束优化问题的求解算法也随之被广泛研究，分为完备

3、算法与非完备算法两大类。完备算法旨在搜索所有组合空间，保证最终找到全局最优解；非完备算法旨在在有限的时间内，尽最大努力找到一个较好解。搜索策略是这两类算法采用的典型求解策略，已成为了研究的热点。然而，目前的搜索策略存在较多局限性，不能满足实际问题的需要。在完备算法中主要表现为搜索策略单一；在非完备算法中主要表现为仅依据个体局部信息引导搜索，易陷入局部最优。针对上述问题，论文从策略融合和群智能引导两个方面分别对完备算法与非完备算法展开研究。主要工作如下：①介绍了分布式约束优化算法的研究现状、分布式约束优化问题的相关定义和常用通信结构以及分布式约束优化实验的测试问题、实验平台与评价指标。

4、较详细介绍了基于最好优先搜索与深度优先搜索策略的两个典型完备算法以及蚁群优化的相关知识与蚁群优化解决分布式约束满足问题（DCSP）的算法。并且，深入分析了最好优先搜索与深度优先搜索策略各自的特征和存在的问题，探讨了两种搜索策略与伪树的关系，为后面两种策略的结合提供了依据。②提出了深度优先搜索与最好优先搜索策略结合的DCOP完备算法。该算法依据两种搜索策略与伪树的关系，采用分层的思想，根据agent在伪树中的位置特点分别采用深度优先搜索策略或最好优先搜索策略，并且给出了分层规则和两种策略的无缝对接方法。该算法不仅充分发挥了两种策略各自的优势，并且保持了原单一策略算法的数据结构与消息类型

5、，没有加剧算法的处理复杂性。本文从理论和实验论证了BD-ADOPT的完备性和有效性。③提出了基于蚁群优化引导的DCOP非完备算法。算法引入蚁群优化的群智能特点，依据个体之间协作产生的全局信息引导个体做决策选择从而提高算法的搜索性能。该算法充分考虑了DCSP和DCOP的不同，采用伪树结构作为构造图，提高了搜索的并发性；针对DCOP的特点，设计了对数运算与求倒运算结合的信息素更新与引导概率的计算方式；引入流水线的消息处理机制，提高了搜索效率。I重庆大学硕士学位论文最后，通过与其他的算法进行对比验证了该算法的可行性和有效性。关键词：分布式约束优化问题，最好优先搜索策略，深度优先搜索策略，蚁

6、群优化II英文摘要ABSTRACTAsanimportantandefficientformulismtosolvecollaborationprobleminmulti-agentsystem,DistributedConstraintOptimizationProblem(DCOP)hasbecomeaneffectivetechniquefordistributedintelligentsystemmodelingandmulti-objectivecoordinationoptimization.Therefore,thestudyforDCOPhasimportantres

7、earchsignificanceandpracticalvalue.Comparedtothetraditionalcentralizedcontrol,DCOPprovidesstrongrobustnessandprivacy,whichissuitabletodealwithlarge-scaleanddifficultcombinatorialproblems.So,DCOPhasbecomearesearchhotspotinthefieldo