Jun, 2020

线性时间内学习在实际图中求解组合优化问题

PDF
TL;DR本文介绍一种使用强化学习训练图神经网络求解单人游戏定义的图组合优化问题的新框架，可以处理最小生成树、最短路径、旅行商问题和车辆路径问题等一系列问题，该方法可在线性运行时间内输出近似解，并且能够推广到多种情况，包括 NP 困难的问题和真实世界的图。
combinatorial optimizationgraph problemsgraph neural networkreinforcement learningnp-hard problems
发现论文，激发创造
  • 在图上学习组合优化算法

    本文介绍了结合强化学习和图嵌入的方法，使用元算法来解决 NP-hard 组合优化问题和图上的最小点集覆盖、最大割和旅行商问题等优化问题。

    Apr, 2017

  • 强化学习的神经组合优化

    本文提出了一种利用神经网络和强化学习解决组合优化问题的框架，特别关注旅行推销员问题和背包问题，证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果，并且可以得到具有多达 200 个项目实例的最优解。

    Nov, 2016

  • 在图上学习组合优化问题：一份调查及其在网络中的应用

    介绍了解决图上组合优化问题的现有方法存在的问题，调查了与计算复杂性相关的机器学习研究的发展，并组织和比较了解决组合优化问题的学习结构。

    May, 2020

  • 物理启发图神经网络的组合优化

    本文介绍了如何使用图神经网络来解决组合优化问题，包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略，我们生成了一个可区分的损失函数，并在无监督训练过程结束后对整数变量进行简单的投影。实验表明，我们的方法在解决包含数百万个变量的问题时能够胜任。

    Jul, 2021

  • 基于图神经网络的组合优化和推理

    本文通过对近年来在组合优化、运筹学和机器学习等领域出现的基于图神经网络（GNNs）的组合优化求解方法和算法进行概述，以此向优化和机器学习研究者介绍这一领域的最新进展。

    Feb, 2021

  • 图形 Q-Learning 用于组合优化

    本论文提出并证明了图神经网络可以应用于解决组合优化问题，通过将优化过程视为顺序决策问题，使用 Q-Learning 训练图神经网络可以在参数和训练时间上只占一小部分的情况下接近达到最先进的启发式求解器的性能。

    Jan, 2024

  • 可逆行动设计与强化学习在组合优化中的应用

    利用图神经网络和深度 Q 学习的强化学习方法，针对组合优化问题提出了一种无需问题特定设计即可实现状态最优化策略搜索的通用模型，并在最大 k-Cut 问题和旅行商问题上实验验证了其优越性。

    Feb, 2021

  • 神经组合优化：领域的新玩家

    本文对神经网络在传统组合优化框架中的性能、可迁移性、计算成本和对更大样本的普适性进行了详细研究，并在 NP-hard 问题线性排序问题上开发了神经组合优化模型。

    May, 2022

  • 图卷积网络与引导树搜索的组合优化

    文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些 NP 困难问题，并在四个 NP 困难问题和五个数据集上进行了评估，结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

    Oct, 2018

  • 强化学习的组合探索优化

    在解决复杂优化问题方面，探索式组合优化（ECO-DQN）通过连续改进解决方案，从而有效地学习有效的启发式方法来解决图上的组合优化问题，并在最大割问题上展示了最先进的强化学习性能。

    Sep, 2019