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

发布时间：2024-02-18 04:15

　　分布式约束优化问题(DCOP)是多智能体系统(MAS)的基本框架,是对分布式问题解决、多智能体协作的重要建模方式,现已成功应用于任务调度、电力系统等领域。非对称分布式约束优化问题(ADCOP)在DCOP的基础上增加了Agent的私有偏好,具有更强的建模的能力和更大的应用前景。以最大和算法(Max-sum)为代表的推理算法作为求解DCOP/ADCOP的重要手段,广泛地应用于各种实际场景中。然而,现有的非完备推理算法普遍存在着难以收敛、解的质量较差的问题。此外,由于ADCOP对隐私性的要求,传统用于求解DCOP的完备推理算法无法直接用于ADCOP,而现有的求解ADCOP的完备搜索算法普遍存在着求解问题规模较小、隐私性较差等问题。针对以上问题,本文拟从求解DCOP的非完备推理算法和求解ADCOP的完备算法开展研究。具体研究内容如下:(1)深入分析了值传播机制Max-sum类算法的影响。本文从理论上证明了虽然值传播可以极大地提高算法的性能,但是其同时阻碍了Max-sum类算法的信念传播。特别地,本文证明了当在换向有向无环图上连续执行值传播机制时,智能体将完全无法利用全局累加的信念,因此算法将等...

【文章页数】：89 页

【学位级别】：硕士

【部分图文】：

图1.2ADCOP求解算法分类Fig.1.2TaxonomyofADCOPalgorithms

在计算消息时，考虑其所收到的取值信息。相比于Max-sum_AD，Max-sum_ADVP更加倾向于利用且可以保证跨阶段收敛（CrossPhaseConvergence，CPC）。但是，尽管它能极大地提高Max-sum_AD的解的质量，值传播同时也限制了算法的探索能力。....

图2.2ADCOP实例

重庆大学硕士学位论文问题（ADCOP）在DCOP的基础上增加了个体偏好和隐私性个约束关系，每个Agent都有自己的约束代价函数（偏好），被其他Agent所知。因此，ADCOP中的约束代价函数可以(2.3约束各方给出的代价值不同。ADCOP的求解目标同样是使最小。图....

图2.6图着色实例

(b)约束矩阵图2.6图着色实例Fig.2.6Agraphcoloringinstan法求解时，因子图中的各个下方式计算发送给的消息，尚未收到，给的消息：环图，在一个阶段内会产

图2.7DCOPSolver平台的图形化界面

图2.7DCOPSolver平台的图形化界面Fig.2.7GUIofDCOPSolverOPSolver由三个模块：基础设施模块、算法模块和指标统计模块。基础为平台提供了基本的类型定义、标准测试问题生成与解析、线程间通信面等功能。其中，基本类型定义规定了平台中A....

本文编号：3901883