旅行推销员问题的新节点移位编码表示
该论文提出了一种数据驱动的图表示学习方法,用于解决具有不同数量城市的旅行推销员问题,并通过实验证明该方法在解决旅行推销员问题方面具有与最先进的基于学习的方法相媲美的性能。
Oct, 2023
旅行推销员问题(TSP)是文献中研究充分的 NP 困难问题之一。该论文研究了涵盖从 2,000 到 85,900 个城市的问题,并发现人工组合多个求解器的算法能够在解决 10,000 个城市以上的问题时超越现有的最先进求解器的表现。
Aug, 2023
本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法,通过使用图卷积网络构建 TSP 图表示,并通过高度并行化的 Beam Search 非自回归方法输出巡回路径,我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好,最终平均优化差距从 50 个节点降低到 0.01%,100 个节点从 2.26%降至 1.39%,尽管相较于标准的运筹学求解器,我们的方法还有所欠缺。
Jun, 2019
探讨无监督学习在解决旅行推销员问题中的泛化能力,通过训练图神经网络并使用嵌入来构建边缘的热图,同时研究不同的训练实例大小、嵌入维度和分布对无监督学习方法结果的影响,结果表明使用较大的实例规模和增加嵌入维度可以构建更有效的表示,提高解决旅行推销员问题的能力,并发现在不同分布上进行泛化评估时,选择更困难的实例作为训练数据可以使模型具备更好的泛化能力。
Mar, 2024
提出了一种基于图神经网络和引导局部搜索的 TSP(旅行商问题)混合数据驱动方法,该方法能够在不损失解决方案质量的同时,快速求解大规模 TSP 实例,经实验证明,我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%,将 20 个节点实例推广到 100 个节点问题集时,我们将最优性差从 18.845% 减少到 2.622%,提高了 2 倍和 7 倍。
Oct, 2021
本文提出了一种基于树形和线性表示的多表示遗传编程算法,通过跨表示交叉运算符,成功改善了仅使用树形或线性表示的遗传编程在符号回归和动态车间调度问题中的效果。
May, 2024
本文提出了一种神经组合优化方法,将学习算法与模型架构相结合,以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究,控制实验提供了第一手数据,并提供了深度学习的新方向。
Jun, 2020
本文研究 Steiner 旅行商问题(STSP)这一问题,探讨了如何将已有的有效的可行性算法适配到适用于稀疏网络,也对与该问题相关的一些领域进行了讨论。
Mar, 2012