一种基于神经网络的分布式最大权匹配算法

摘要

二部图的最大权匹配是一个基础的组合优化问题。该问题可以广泛地应用在许多实际工程中，如任务分配和资源分配。最大权匹配问题的传统解决方法要求将所有的权值都收集到一个集中式的实体中，进行集中式求解。该方法容易造成计算过程中，花费更多的软、硬件资源并且造成计算数据冗余，从而带来资源浪费。而且在集中式运算时，必须有一台服务器能够提供集中式的服务。
　　提出了一种多Agent分布式方法来求解最大权匹配问题，所有相关的Agents之间采用并行的方式传递消息。这种分布式算法的提出是基于以下两个相关因素：第一，在某些情况下没有服务器能够提供集中式的服务。第二，不同的Agents之间可能并不希望将自带的权重信息进行共享和传递。在上面提出的方法中，首先将一个最大权匹配问题转化为一个对偶线性规划问题，并且引入一个非线性动态方程不断更新最优解。在与其他Agent进行信息传递之前，需要定义一个由最大权匹配问题的权值矩阵大小决定的步长参数，每个Agent根据动态方程不断更新对偶线性规划问题的目标值。根据动态过程，对该对偶线性规划问题进行求解，根据步长参数对系统进行不断地更新迭代得到最大权匹配结果。将结果与单纯形法进行比较和验证，证明算法的正确性。
　　我们构造了合适的Lyapunov函数证明算法能够达到全局最优并证明算法收敛。最后通过模拟一些典型问题，研究并测试了实验结果。实验表明，提出的算法是有效的。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 本文的研究内容

2 关键技术分析

2.1 最大权匹配算法

2.2 多Agent分布式算法

2.3 线性规划问题

2.4 梯度下降法

2.5 本章小结

3 基于神经网络的分布式最大权匹配算法

3.1 匈牙利算法

3.2 构造线性规划问题

3.3 多Agent分布式算法实现

3.4 构造Lyapunov函数

3.5 本章小结

4 实验设计与结果分析

4.1 实验假设与模型

4.2 数据生成

4.3 实验结果分析

4.4 实验结果定量分析

4.5 本章小结

5 总结与展望

5.1 全文总结

5.2 展望

致谢

参考文献