Nov, 2019

图形指针网络和层次强化学习的组合优化

HTML
PDF
TL;DR本研究提出使用强化学习训练的图指针网络（Graph Pointer Networks，GPNs）来解决旅行商问题。我们使用GPNs对输入图进行嵌入并通过学习分层策略来优化城市排列。实验结果表明，GPNs对小规模的TSP50/100问题的泛化性能不错，且在TSP500/1000问题中获得了更短的旅行路径和更快的计算时间，同时当问题涉及时间窗口约束时，支持最优解的分层强化学习训练优于以往的基准方法。
发现论文，激发创造
  • 强化学习的神经组合优化

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

    Nov, 2016

  • 在图上学习组合优化算法

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

    Apr, 2017

  • 旅行商问题学习范式

    探讨学习典范对旅行推销员问题的深度神经网络训练的影响，研究发现相较于受控实验的有标记数据的SL模型，强化学习（RL）模型对于变量大小的图形具有更好的紧急普遍性并是学习新组合问题的规模无关解算器的重要组成部分。

    Oct, 2019

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

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

    Jun, 2020

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

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

    Feb, 2021

  • 旅行商问题的Transformer网络

    本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法，相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现

    Mar, 2021

  • 超越TSP的神经组合优化：现有架构在图结构下表现不足

    本文研究如何将深度强化学习和图神经网络应用于无线网络中的电力和信道分配问题，研究结果表明现有结构还不能很好地识别图的结构和特征，并且对于对图产生影响的问题不太适用，但研究还是取得了一些积极进展，比如通过距离编码来增强问题的表示方法。

    Jan, 2022

  • H-TSP：层次化解决大规模旅行推销员问题

    本研究提出了一种基于层次强化学习的端到端学习框架，称为H-TSP，用于解决大规模TSP问题，通过选择子集并使用深度学习模型直接生成解决方案，具有可扩展和高效性。

    Apr, 2023

  • 通过两阶段图指针网络和强化学习解决QAP问题

    本文提出了一种基于深度强化学习模型的两阶段图指示器网络（GPN）来解决二次分配问题（QAP），实验结果表明它可以为TSPLib和QAPLIB的基准问题提供半最优解。

    Mar, 2024

  • 组合优化的图强化学习：调查与统一视角

    图离散结构上关于决策制定方法的综合视角，通过采用强化学习算法解决图优化问题。

    Apr, 2024