AAAIApr, 2022

学会使用硬度自适应课程解决旅行商问题

PDF
TL;DR本文研究了使用自适应难度方法的基于学习的旅行商问题方法，通过定义硬度测量，使用硬度自适应生成器生成不同难度的实例，再利用课程学习器完全利用这些实例来训练 TSP 求解器。实验结果表明，我们的硬度自适应生成器可以生成比现有方法更困难的实例，而我们提出的方法在最优性差距方面显著优于最先进的模型。
neural network modelscombinatorial optimization problemstravelling salesman problemtraining and testing dataadaptive-hardness
发现论文，激发创造
  • 学会解决旅行商问题要重新思考泛化

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

    Jun, 2020

  • 用神经算法进行组合优化的推理

    本研究针对组合优化问题，提出了在深度学习模型训练前进行预训练以利用相关算法对于解决 TSP 问题具有提升作用的算法推理方法，并证明该方法能够优于传统深度学习模型。

    May, 2023

  • 无监督学习中旅行商问题的规模和难度泛化

    探讨无监督学习在解决旅行推销员问题中的泛化能力，通过训练图神经网络并使用嵌入来构建边缘的热图，同时研究不同的训练实例大小、嵌入维度和分布对无监督学习方法结果的影响，结果表明使用较大的实例规模和增加嵌入维度可以构建更有效的表示，提高解决旅行推销员问题的能力，并发现在不同分布上进行泛化评估时，选择更困难的实例作为训练数据可以使模型具备更好的泛化能力。

    Mar, 2024

  • 旅行商问题的 Transformer 网络

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

    Mar, 2021

  • 同行之路：一种新的 TSP 求解策略

    本研究提出了一种基于模仿学习框架的策略来解决旅行商问题，并展示了所训练的图神经网络在大规模的 TSP 实例上的较快求解能力。

    Oct, 2022

  • 提前预计以避免迟到：解决困难约束旅行推销员问题

    使用前瞻信息作为特征，提出一种利用学习方法改善具有时间窗口的 TSP 解决方案合法性的新方法，并构建了具有硬约束条件的 TSPTW 数据集进行准确评估和基准测试。通过对多种数据集进行综合实验，MUSLA 优于现有基线算法且具有一定的泛化能力。

    Mar, 2024

  • 将小型预训练模型推广到任意大的 TSP 实例

    本文针对旅行商问题，通过训练一个能够根据图形采样、转化和热力图合并等技术建立任意规模的热力图的小型模型，并采用强化学习算法进行高质量解的搜索，显著提高了该模型的泛化能力和性能。该方法优于现有基于机器学习的 TSP 算法。

    Dec, 2020

  • 使用置换不变汇聚网络学习多个旅行商问题

    本文设计一种神经网络方法，利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合，通过搜索方法和特定的损失函数来输出最优解，实验结果表明该方法优于现有领域最先进的元启发式算法。

    Mar, 2018

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

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

    Nov, 2016

  • 时变旅行商问题的割、原始启发和学习分支

    本研究探讨了时间依赖旅行商问题（TDTSP），证明了其为 NP-hard 和 APX-hard，并针对该问题提出了两个 IP 公式以及不同的定价算法、割平面和基于 LP 的凸先发方法、传播方法和分支规则。同时，开展了计算实验以评估这些方法的有效性，并首次尝试学习 TDTSP 的强分支决策，但该方法目前并未改善运行时间。

    May, 2018