本文提出一种名为 Graph Temporal Attention with Reinforcement Learning (GTA-RL) 的新型框架,针对动态组合优化问题学习启发式解决方案。该框架结构包括一个能够嵌入组合问题实例的时间特征的编码器和一个能够动态聚焦于嵌入特征以找到所需组合问题实例的解码器,并针对实时版本组合优化问题进行了扩展。实验证明,与现有方法相比,该方法在动态和实时图组合优化方面具有更高的效率和优化求解器的有效性。
Jan, 2022
使用机器学习方法来加速组合优化问题,具体研究了集合覆盖问题,并提出了图神经网络方法 Graph-SCP,通过学习识别包含解空间的较小子问题来增强现有优化求解器,实验结果表明,Graph-SCP 与商业求解器相比可将问题规模减少 30-70%,运行时间加速高达 25 倍,并能够达到或甚至优于给定最优性阈值,相比快速贪心解法,Graph-SCP 在保持高质量解的同时实现多项式运行时间保证,可推广到更大的问题,并与其他传统或机器学习增强的组合优化求解器结合使用以进一步提高运行时间。
Oct, 2023
本文提出了一种基于可扩展序列注意力机制、归纳图神经网络和端到端可转移的深度强化学习方法,用于解决机器学习编译器生成高效机器代码时的图优化问题,并在多个图优化任务中取得显著性能提升。
Oct, 2020
在在线教育领域,设计一个几何问题的自动求解器被认为是通往普适数学人工智能的关键一步。本研究提出了一种基于深度强化学习框架的图形注意力机制和 BERT 等语言模型的算法 A3C-RL,通过在特定空间中选择最佳策略,显著提高了准确性和效率,并在中国高考几何问题上超越了人类的表现。
Mar, 2024
本文介绍一种使用强化学习训练图神经网络求解单人游戏定义的图组合优化问题的新框架,可以处理最小生成树、最短路径、旅行商问题和车辆路径问题等一系列问题,该方法可在线性运行时间内输出近似解,并且能够推广到多种情况,包括 NP 困难的问题和真实世界的图。
Jun, 2020
本文提出一种深度强化学习方法,以最小化优化器中神经网络计算图的执行成本。该方法通过离线训练优化器,然后推广到以前未见过的图形,以避免在同一图形上进行更多的训练。通过比较广泛的基线,我们的方法在运行时间和峰值内存使用量上比经典和其他基于学习的方法都取得了显着的改进。
May, 2019
文章提出一种基于深度学习和启发式算法的图卷积网络方法,用于解决某些 NP 困难问题,并在四个 NP 困难问题和五个数据集上进行了评估,结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平,并具有较强的泛化性和扩展性。
Oct, 2018
本文提出了一种简化梯度攻击的方法,可以通过多阶段攻击框架在只需较小子图的情况下使图神经网络误分类。此外,作者还提出了度同配改变这一实用指标来衡量对图数据的对抗攻击的影响。
Sep, 2020
该研究提出了一种对图神经网络 (GNNs) 进行攻击的方法,称为 AGSOA,该方法通过平均梯度计算和结构优化模块来提高攻击的性能。通过在所有时刻计算梯度信息的平均值来引导攻击生成扰动边,从而稳定攻击更新的方向并避免不良局部最大值;通过计算目标节点与其他节点的相似性和均匀性来调整图结构,从而提高攻击的隐蔽性和可转移性。在三个常用数据集上的实验证明,相比其他先进模型,AGSOA 提高了误分类率 2% 至 8%。
Jun, 2024
本文介绍了结合强化学习和图嵌入的方法,使用元算法来解决 NP-hard 组合优化问题和图上的最小点集覆盖、最大割和旅行商问题等优化问题。
Apr, 2017