基于图神经网络的最大化代数连通度算法

随着智能体数量的增加,多智能体系统中潜在的通信链路数量呈指数级增长.过多冗余链路的存在给系统带来了大量的能源浪费和维护成本,而盲目地去除链路又会降低系统的稳定性和安全性.代数连通度是衡量图连通性的重要指标之一.然而,传统的半正定规划(SDP)方法和启发式算法在求解大规模场景下的最大化代数连通度问题时非常耗时.在本文中,我们提出了一种监督式的图神经网络模型来优化多智能体系统的代数连通度.我们将传统的SDP方法应用于小规模任务场景中,得到足够丰富的训练样本和标签.在此基础上,我们训练了一个图神经网络模型,该模型可用于更大规模的任务场景中.实验结果表明,当需要去除15条边时,我们的模型的平均性能达到了传统SDP方法的98.39%.此外,我们的模型计算时间极其有限,可以推广到实时场景中去.