基于局部搜索的分布式约束优化问题求解算法研究.pdf

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




重庆大学硕士学位论文
（学术学位）

学生姓名：余浙鹏
指导教师：何静媛 副教授
副 导 师：陈自郁 讲 师
专 业：计算机科学与技术
学科门类：工 学


重庆大学计算机学院
二 O 一七年四月
The Study on Local Search Algorithms for
Distributed Constraint Optimization
Problems


A Thesis Submitted to Chongqing University
in Partial Fulfillment of the Requirement for the
Master’s Degree of Engineering
By
Yu Zhepeng

Supervised by . He Jingyuan
Assistant Supervised by Lec. Chen Ziyu
Specialty: Computer Science and Technology


College of Computer Science of
Chongqing University, Chongqing, China
April, 2017
中文摘要

摘 要

分布式约束优化问题(DCOP)作为多 Agent 系统协作问题的重要抽象，具有隐
私性、信息局部性、控制分散化等特点，是对分布式智能系统和多目标优化等问
题的有效建模技术。因此，对分布式约束优化问题的求解成为该领域的研究热点。
局部搜索算法作为一类求解 DCOP 的非完备算法，由于其简单的逻辑结构和灵活
的优化方式，受到了广泛的关注。本文介绍了分布式约束优化问题求解算法的国
内外研究现状，分析了各类算法的优点和局限性，并针对局部搜索算法存在的局
限性以及智能优化引导两个方面展开研究，主要工作如下：
① 针对局部搜索算法中相邻 Agent 之间赋值相互依赖的限制，提出了部分决
策机制(PDS)。该机制通过 Agent 在决策过程中忽略部分邻居结点的赋值信息来打
破相邻 Agent 之间的赋值依赖关系，获取更大的决策空间，做出更优的决策，从
而以较小的代价有效地提高了算法的求解质量。PDS 包含两个部分决策过程：触
发式部分决策和递归式部分决策。前者在 Agent 不能提高自身利益时触发，通过
忽略邻居的取值信息来跳出赋值依赖造成的潜在局部收敛状态；而后者不断地由
被忽略的 Agent 触发来提升全局利益。此外，PDS 通过一个包含自适应概率的触
发条件来控制部分决策的执行。该机制可以结合任意局部搜索算法进行优化，具
有很大的普适性。本文从理论上论证了部分决策机制的可行性和收敛性，并通过
实验验证了该机制的有效性。
②提出了基于局部搜索的遗传优化算法(LS-GA)。算法结合了遗传优化的智能
性和局部搜索的灵活性，作为智能优化算法求解