通过深度强化学习的方法解决 Quadratic Assignment Problem(QAP)的 Koopmans-Beckman 公式,使用双指针网络(double pointer network)在选择下一个设施放置位置和上一个位置放置设施之间交替,并通过 A2C 算法在一系列合成实例上进行模型训练。在样本外测试中,我们的解决方案与高质量的局部搜索基线相比,平均准确率达到了 97.5%,在 1.2% 的实例中表现优于基线。
Oct, 2023
本研究提出使用强化学习训练的图指针网络(Graph Pointer Networks,GPNs)来解决旅行商问题。我们使用 GPNs 对输入图进行嵌入并通过学习分层策略来优化城市排列。实验结果表明,GPNs 对小规模的 TSP50/100 问题的泛化性能不错,且在 TSP500/1000 问题中获得了更短的旅行路径和更快的计算时间,同时当问题涉及时间窗口约束时,支持最优解的分层强化学习训练优于以往的基准方法。
Nov, 2019
利用机器学习的能力,针对组合优化中的 Quadratic Assignment Problem (QAP) 提出了第一种针对 QAP 的学习优化方案,该方案使用 Solutions AWare Transformer (SAWT) 架构来有效捕捉 QAP 的高阶信息。
Jun, 2024
本文介绍了一种快速的近似二次分配算法(FAQ),能够更高效地在大数据和图值数据上处理 QAP 问题,通过在 C.elegans 连通图匹配案例上的实证表明其优越性。
Dec, 2011
本篇论文提出了一种利用权值矩阵进行学习的网络来解决 Quadratic Assignment Problem (QAP) 及图匹配的问题,该模型利用嵌入网络对顶点进行分类,并通过 Sinkhorn 归一化和交叉熵损失进行端到端的学习。实验结果表明,该方法在合成数据和现实图像上均取得了很好的效果。
该研究揭示了指针 Q 网络 (PQN) 这种创新方法的架构和效率,展示了其在管理导向问题 (OP) 情境中的卓越能力。
Nov, 2023
本研究提出了一种新的半定规划 (SDP) 方法来解决二部图的匹配问题,采用正半定矩阵进行松弛,并通过聚类来加强松弛,使得计算复杂度和运行时间得到了缩减,可以应用于核磁共振光谱 (NMR) 等领域的匹配问题。
Mar, 2017
本研究探讨了 Quadratic Assignment Problem 的相变现象,通过引入新的基于子模块性的 QAP-SAT 设计来捕捉问题的复杂度,并使用分支界限和禁忌搜索求解器对其进行实验研究,在此基础上提出了相变参数,发现禁忌搜索的相变满意度和解决努力与关键参数高度相关,从而可以预测出困难的实例。
Mar, 2024
本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法,通过使用图卷积网络构建 TSP 图表示,并通过高度并行化的 Beam Search 非自回归方法输出巡回路径,我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好,最终平均优化差距从 50 个节点降低到 0.01%,100 个节点从 2.26%降至 1.39%,尽管相较于标准的运筹学求解器,我们的方法还有所欠缺。
Jun, 2019
用连续和混合整数设置的情况下,我们研究了图神经网络在二次规划任务中的表达或代表能力,证明了存在可靠地表示二次规划关键属性的消息传递图神经网络,并通过数值结果验证了我们的理论。