- ICLR提高 TSP 求解器泛化能力的博弈论方法
利用基于 PSRO(Policy Space Response Oracle)方法的两人零和博弈进行深度学习解算器的泛化能力提升,实现在不同的 TSP 任务中最大程度的通用性表现,最终实现了解算器人口的效用降低和达到 Nash 均衡。
- NeuroLKH: 结合深度学习模型与 Lin-Kernighan-Helsgaun 启发式算法求解旅行商问题
NeuroLKH 采用深度学习和 LKH 启发式算法相结合,通过训练 Sparse Graph Network 模型来解决旅行商问题等路由问题,得出实验结果表明能够优于传统启发式算法并泛化到更大范围问题。
- 旅行商问题的 Transformer 网络
本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法,相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现
- 将小型预训练模型推广到任意大的 TSP 实例
本文针对旅行商问题,通过训练一个能够根据图形采样、转化和热力图合并等技术建立任意规模的热力图的小型模型,并采用强化学习算法进行高质量解的搜索,显著提高了该模型的泛化能力和性能。该方法优于现有基于机器学习的 TSP 算法。
- AAAI将强化学习与 Lin-Kernighan-Helsgaun 算法相结合解决旅行商问题
本文提出了一个基于增强学习的启发式算法 VSR-LKH,它运用 Q-learning、Sarsa、Monte Carlo 三种方法改进了已有的 TSP 算法 Lin-Kernighan-Helsgaun (LKH),将其高效应用于 111 - ICML解释创造性艺术品
本研究开发了一个逆向问题公式,将组合和组合创造的产物转化为联想链以进行事后解释。该公式结构化为通过联想元素的知识图解决旅行商问题,并将旅行商路径的长度视为创造力中新奇性的度量。
- 通过深度强化学习学习旅行商问题的 2-opt 启发式算法
本论文使用基于深度加强学习方法的策略梯度算法,通过 2-opt 操作符学习本地搜索启发式,提出了一种可以轻松扩展到更一般 k-opt 移动的策略神经网络,实验结果表明,所学习的策略比之前的具有最先进性能的深度学习方法更快接近最优解。
- 图形指针网络和层次强化学习的组合优化
本研究提出使用强化学习训练的图指针网络(Graph Pointer Networks,GPNs)来解决旅行商问题。我们使用 GPNs 对输入图进行嵌入并通过学习分层策略来优化城市排列。实验结果表明,GPNs 对小规模的 TSP50/100 - ICLR强化学习的神经组合优化
本文提出了一种利用神经网络和强化学习解决组合优化问题的框架,特别关注旅行推销员问题和背包问题,证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果,并且可以得到具有多达 200 个项目实例的最优解。
- 一种轻量度量钳
本文研究了低倍指标度量空间中的 (1+ε)-stretch spanners 及其在旅行商问题中的应用,通过证明这种空间可以通过快速算法解决,提出了更好的多项式时间近似方案。