论文总字数：30570字

摘 要

随着计算机通信技术的发展，对代理的研究不仅成为分布式人工智能的研究热点，也是信息技术关注的热点。它涉及到分布式人工智能、软件工程、分布式计算、网络、虚拟现实等多个领域。

和积算法是DCOP的一种有效求解方法。DCOP能够对多代理系统（MAS）的各种分布式推理任务进行建模，广泛运用于资源分配、时刻表调度等问题中。

本文首先介绍了多代理系统和分布式约束优化问题目前国内外的发展现状，以及本课题研究的意义；并对多代理协调和和积算法进行了简单的概述；然后通过对和积算法的复杂度和不足的分析，进行了一些改进；接着对改进的有界最大和算法进行了理论分析，并将最大和算法和改进的有界最大和算法的收敛效率进行对比；最后，将最大和算法应用到了传感器网络中。实验结果表明，改进最大和算法比和积算法在算法效率上有显著的提高。

关键字：代理 协调问题 和积算法 最大和算法 传感器网络

Multi-Agent-Based Decentralised Coordination

via the Sum-Product Algorithm

Abstract

With the development of the computer network and communication technology, researches on agent become not only a hot spot in distributed artificial intelligence, but also a focus of information technology. It refers to distributed artificial intelligence, software engineering, parallel and distributed computing, Internet, virtual reality and many other domain.

Sum-product algorithm is one of the valid methods of distributed constraint optimization problem(DCOP). DCOP is able to model a variety of distributed reasoning tasks of multi-agent systems(MAS), used widely in resource allocation, schedules and so forth.

Firstly, we introduce the foreign and domestic current research status on multi-agent systems and distributed constraint optimization problem and the meaning of the research on this subject. Then multi-agent-based decentralised coordination and sum-product algorithm are briefly outlined. We later improve the original approach through analyzing the computation and communication overhead of the sum-product algorithm. Afterwards, we make a theoretical analysis of the modified bounded max-sum algorithm. And then contrast between the original and modified max-sum algorithm in convergence efficiecy. Finally, the max-sum algorithm are used in sensor networks and we present an empirical evaluation of our bounded algorithm. The experimental results suggest that the bounded max-sum algorithm improves the computation and communication overhead significantly compared with the sum-product algorithm.

Keywords: agent; coordination; sum-product algorithm; max-sum algorithm; sensor network;

目 录

摘要 Ⅰ

Abstract Ⅱ

第一章 引言 1

1.1 国内外研究现状 1

1.2 课题研究意义 2

第二章 多代理协调问题 4

2.1 代理的概念及特性 4

2.2 分布式人工智能和多代理系统 5

2.3 代理学习 6

2.4 约束满足和分布式约束优化问题 7

2.4.1 问题定义描述及建模 7

2.4.2 问题求解算法 9

第三章 和积算法的基本知识概述 11

3.1 问题描述 11

3.2 因子图 11

3.3 信息传播方法 12

3.3.1 和积算法 12

3.3.2 最大积算法 15

3.3.3 最大和算法 16

3.4 图形着色问题 18

3.4.1 问题描述和建模 19

3.4.2 算法执行步骤模拟 21

3.4.3 主要实现代码 23

3.4.4 实现效果图 24

第四章 有界最大和算法 25

4.1 算法基本描述 25

4.2 理论分析 27

4.2.1 有界分析 27

4.2.2 构造树结构因子图 28

4.2.3 近似比 29

4.3 剪枝技术 30

4.4 实验分析 31

第五章 最大和算法在传感器网络中的应用 33

5.1 问题描述 33

5.2 问题建模 33

5.3 运用最大和算法 36

5.4 实现效果图 38

结束语 41

参考文献 43

致谢 46

引言

1.1 国内外研究现状

人工智能（Artificial Intelligence，AI）是一门技术科学。它主要研究关于模拟和拓展人的智能的理论和方法。AI自1956年达特矛斯会议上被正式提出以来，就开始了关于搜索算法和通用问题求解的研究。组合求解问题广泛存在于现实生活环境中，例如：生产调度、神经网络、社交网络、机器人、模式识别、智能控制、智能检索、智能调度和指挥等。这些问题的求解复杂，且没有算法可遵循，一般是NP（非确定多项式，Non-Polynomial）问题。因此，利用计算机高效的运算能力，将复杂的问题简化，具有更高的实际应用价值。约束满足问题可以很好地描述AI领域许多关于调度的应用问题，已成为AI中成功的问题求解范例之一。

目前，计算机的应用越发广泛，随着计算机通讯等技术的发展，分布式计算已成为发展趋势。需要处理解决的问题所涉及的数据量越来越庞大，很难被集中处理。这样，传统的约束满足的求解方法已无法适应当前的分布式问题的求解。

请支付后下载全文，论文总字数：30570字