AAAIApr, 2023

指针转换器：用于旅行商问题的深度强化多指针 Transformer

PDF
TL;DR本文提出了一种新的端到端深度强化学习方法 Pointerformer，基于多指针变压器，可解决旅行商问题（TSP）的内存消耗和算力问题，通过特征增强方法探索 TSP 的对称性以及增强上下文嵌入方法以包含更多综合上下文信息，此方法在小规模和大规模问题上均表现出了竞争优势。
发现论文，激发创造
  • 旅行商问题的 Transformer 网络

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

    Mar, 2021

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

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

    Nov, 2019

  • 学会解决旅行商问题要重新思考泛化

    本文提出了一种神经组合优化方法，将学习算法与模型架构相结合，以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究，控制实验提供了第一手数据，并提供了深度学习的新方向。

    Jun, 2020

  • 深度强化学习与旅行购买问题

    基于深度强化学习的旅行购货问题（TPP）解决方案，通过使用双向图表示 TPP、策略网络逐步构建路线，并通过线性规划获取购货计划，利用元学习策略稳定训练策略网络。在综合合成和标准基准测试上，相较于已有启发式算法，我们的 DRL 方法能够显著提升解决方案质量（降低 40%-90% 的最优性差距），尤其在大型实例上具备高效性。

    Apr, 2024

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

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

    Apr, 2023

  • 基于强化学习的无自回归旅行商问题求解器

    NAR4TSP 是第一个成功结合强化学习和非循环解码的解决 TSP 问题的算法，通过使用一个特殊设计的图神经网络以非循环的方式生成 TSP 解决方案，实现更快的推理速度，其训练使用了增强型强化学习策略，消除了传统基于监督学习的非循环模型的昂贵标签依赖，实验结果表明 NAR4TSP 在解决质量、推理延迟和泛化能力方面优于四个最先进的模型，此外，我们展示了 NAR4TSP 解码过程和整体路径规划的可行性和有效性的可视化。

    Aug, 2023

  • 注意力学习解决路径规划问题！

    我们提出了一种基于注意力层的模型来解决组合优化问题，并使用基于确定性贪心策略的简单基线进行训练，在解决旅行商问题（TSP）和车辆路径问题（VRP）方面取得了很好的结果。

    Mar, 2018

  • 结合强化学习和最优传输的旅行商问题

    利用熵正则化最优传输技术作为深度强化学习网络中的一层，以实现更快速的学习并在端到端训练期间强制执行分配约束和规定，从而对于解决组合优化问题的效率进行优化。

    Mar, 2022

  • 一种轻量级的 CNN-Transformer 模型用于学习旅行商问题

    本研究提出了一种基于 CNN 嵌入层和局部自注意力的轻量级 CNN-Transformer 模型，相对于标准 Transformer 模型，该模型能够更好地从输入数据中学习空间特征，同时通过局部自注意力减少全连接注意模型中的冗余性。实验结果表明，我们提出的模型在解决 TSP 问题的质量、GPU 内存使用和推理时间等方面优于其他最先进的 Transformer-based 模型。

    May, 2023

  • 解决车辆路径问题的跨问题学习

    通过跨问题学习和细调不同变种目标问题的 Transformer 模型，本论文提出了一种用于改善车辆路线问题的神经启发式训练方法，展示了与从头开始训练相比较，全细调和适配器细调技术能够取得更好性能和参数效率的优势，并证明了该方法在交叉分布应用和通用性方面的有利影响。

    Apr, 2024