使用 AlphaGoZero 着色大规模图
该研究提出了一种新的基于 AlphaGo Zero 的学习策略,将其与图嵌入和图神经网络相结合,解决了复杂的组合优化问题,同时取得了比相关方法更好的性能表现。
May, 2019
本文探讨了深度强化学习在解决图着色问题中的应用,提出了一个名为 ReLCol 的构造启发式方法,该方法结合了深度 Q 学习和图神经网络,通过一种新颖方法对图进行参数化,相对现有的构造算法性能有所提升。在标准基准图上进行了实验证明了强化学习是进一步研究图着色问题的一个有前途的方向。
Apr, 2023
本文介绍了如何使用简单的 GNN 架构来解决图着色的基本组合问题,并且展示了该模型在独立于训练数据的图数据上的泛化能力以及优于其他基线模型的表现。同时,我们还展示了如何将节点嵌入在多维空间中进行聚类,从而获得构造性解决方案。我们的结果有助于缩小人们对 GNN 算法学习的差距,并提供了符号推理与深度学习系统集成的可靠方法。
Mar, 2019
利用图神经网络解决图着色问题,将图着色视为多类节点分类问题,利用基于统计物理学的 Potts 模型的无监督训练策略。我们展示了该方法在实际应用中的性能,并提供了数值基准结果。
Feb, 2022
通过对给定规模下最大化边数且无 3 或 4 - 循环的图形的研究,将问题建模为一个顺序决策问题,并比较了 AlphaZero 和 tabu 搜索两种方法的效果,通过引入课程,即使用在较小规模下找到的良好图形来启动搜索更大图形的过程,我们改进了对于多个规模的现有下界。同时,我们还提出了一个灵活的图形生成环境和一个对于在图形空间中进行搜索的排列不变的网络架构。
Nov, 2023
本研究分析了现有图嵌入神经网络(GNN)在图着色问题中的表现差异主要是由于其无法应对节点异质性以及其局部性;通过研究聚集 - 合并 GNN(AC-GNN)的性能以及其基于局部搜索的特性,我们得出了一系列在实践中使 GNN 在图着色问题中更具有等变性和强大性的规则,并提出了一个简单的 AC-GNN 变体以验证我们的理论,并实现了比现有启发式算法更高质量和更快速运行的结果。
Aug, 2022
采用 AlphaZero 算法中的深度神经网络和引导树搜索,结合深度前瞻技术, 实现了量子优化过程的全新探索方式。AlphaZero 算法在三类控制问题上经过应用和基准测试, 能够显著提高优质解集的质量和数量,并能够自主学习预期外的隐藏结构和全局对称性。
Jul, 2019
本文提出了一种 AlphaZero 启发的 MCTS 包装器,将其与时间差异学习智能体相结合,在不需要 GPU 或 TPU 等高性能计算资源的情况下,在多个复杂的游戏中成功打败强劲对手,取得了显著优势。
Apr, 2022
文章提出一种基于深度学习和启发式算法的图卷积网络方法,用于解决某些 NP 困难问题,并在四个 NP 困难问题和五个数据集上进行了评估,结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平,并具有较强的泛化性和扩展性。
Oct, 2018