分布式广义分配问题(D-GAP)的异步优化算法研究

摘要

近年来,随着计算机技术的快速发展,分布式计算作为现代新技术的产物，得到了快速的发展。当分布式系统环境大规模出现在军事、航天、灾难救援等需要相互协作共同完成某个目标的应用领域时，传统的集中式求解算法框架已无法适应大规模、分布式、高异构性问题的求解需求，将现有复杂问题放在分布式算法框架下进行高效求解已成为一种必然趋势。分布式广义分配问题（D-GAP）作为分布式环境下资源分配、任务分配、时序安排等问题的抽象问题模型，已成为多智能体系统领域研究的重点。然而，由于分布式环境对智能体间的通信量限制、D-GAP存在的资源异构性等问题，D-GAP求解的现有方法无法适应大规模问题求解时对通信量及运算量的苛刻要求。因此，如何实现 D-GAP在大规模分布式环境下的高效求解，是本文关注的重点。
　　1.为了减少分布式环境下求解D-GAP消耗的大量通信量，我们将D-GAP问题的求解建立于非集中式多智能体系统。在多智能体系统中，建立三种不同类型的智能体模型，通过多智能体间联合搜索方式，实现问题的最优求解。在非集中式框架下，每个智能体独立完成自己的行为决策，进而共同实现团队的全局目标。非集中式控制方式以其健壮、低通信量、低计算机性等特性，能很好适应大规模团队协作问题的求解需求。
　　2.针对分布式环境下，智能体只能获得局部信息，而无法在求解 D-GAP时做出最优决策的问题，我们为智能体建立启发式算法。通过为每个智能体建立局部决策模型，利用网络中传递的消息，推测其他智能体的执行能力，判断网络中哪个智能体更倾向于实现当前问题的求解，动态的调整传递顺序，提高传递方向的明确性，达到加速全局可行解生成的目的。
　　3.通过实验验证启发式优化算法在求解 D-GAP时能以较少的通信量消耗获得近似最优的全局可行解，具有较好的可扩展性与稳定性。并将D-GAP置于UAV协同控制、大规模团队协作、城市救援搜索等典型应用场景中，根据不同应用场景的特性，通过特性参数模拟方式，对启发式优化算法的性能进行分析，验证了算法的可行性、扩展性及稳定性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究背景及意义

1.2 研究的难点

1.3 国内外研究现状

1.4 研究概要及创新性

1.5 论文结构

第二章 D-GAP问题描述及相关算法

2.1 分布式广义分配问题（D-GAP）概述

2.2 分布式广义分配问题（D-GAP）问题描述

2.3 D-GAP求解的常用算法

2.4 本章小结

第三章 D-GAP在多智能体系统中的求解方法

3.1 多智能体系统求解D-GAP的总体架构

3.2 多智能体系统中智能体模型

3.3 多智能体系统求解D-GAP的算法流程

3.4 本章小结

第四章 D-GAP异步启发式求解方法

4.1 D-GAP异步启发式优化求解方法概述

4.2 求解智能体模型扩展

4.3 局部决策模型

4.4 智能体决策过程

4.5 本章小结

第五章 D-GAP异步启发式算法优化方法

5.1 局部决策模型更新机制

5.2 相似度优化局部决策模型

5.3 本章小结

第六章 实验仿真

6.1 算法性能的验证性实验

6.2 算法在典型应用场景中的验证性实验

6.3 本章小结

第七章 结论

致谢

参考文献

攻硕期间取得的研究成果