大规模(脑)图匹配的快速近似二次规划
本研究提出了一种新的半定规划 (SDP) 方法来解决二部图的匹配问题,采用正半定矩阵进行松弛,并通过聚类来加强松弛,使得计算复杂度和运行时间得到了缩减,可以应用于核磁共振光谱 (NMR) 等领域的匹配问题。
Mar, 2017
通过深度强化学习的方法解决 Quadratic Assignment Problem(QAP)的 Koopmans-Beckman 公式,使用双指针网络(double pointer network)在选择下一个设施放置位置和上一个位置放置设施之间交替,并通过 A2C 算法在一系列合成实例上进行模型训练。在样本外测试中,我们的解决方案与高质量的局部搜索基线相比,平均准确率达到了 97.5%,在 1.2% 的实例中表现优于基线。
Oct, 2023
探究加速解决二次分配问题(QAP)的新方法,利用特殊的优化函数方法在傅里叶空间中优化对称群 Sn,以及在多个优化任务中学习参数。实验表明,新方法在实际领域中可以优于现有方法。
Jun, 2012
本文提出了一种基于深度强化学习模型的两阶段图指示器网络(GPN)来解决二次分配问题(QAP),实验结果表明它可以为 TSPLib 和 QAPLIB 的基准问题提供半最优解。
Mar, 2024
利用机器学习的能力,针对组合优化中的 Quadratic Assignment Problem (QAP) 提出了第一种针对 QAP 的学习优化方案,该方案使用 Solutions AWare Transformer (SAWT) 架构来有效捕捉 QAP 的高阶信息。
Jun, 2024
本研究探讨了 Quadratic Assignment Problem 的相变现象,通过引入新的基于子模块性的 QAP-SAT 设计来捕捉问题的复杂度,并使用分支界限和禁忌搜索求解器对其进行实验研究,在此基础上提出了相变参数,发现禁忌搜索的相变满意度和解决努力与关键参数高度相关,从而可以预测出困难的实例。
Mar, 2024
我们研究了不完全多图匹配问题,该问题是配对多个有限集合的 NP 难问题的推广,多图匹配在计算机视觉中起着关键作用,已经提出了许多专门的优化技术。我们填补了这一差距,并将已知的多维分配问题近似算法转化为不完全多图匹配问题。通过实验证明,我们的新方法在目标和运行时间方面显著优于以前的技术水平。我们的算法能够在两分钟内匹配超过 500 个关键点的 29 个图像,而考虑的最快竞争方法至少需要半小时,同时产生了更差的结果。
Jun, 2024
本文提出了在 Hilbert 空间中的一些规则,引入了新的外积算法,可以在重现核 Hilbert 空间中将 Lawler 的 QAP 视为 Koopmans-Beckmann 的对齐,有效地解决了大规模亲和力矩阵的问题。提出基于熵正则化的 Frank-Wolfe 算法 (EnFW) 对 QAP 进行优化,具有与原始 FW 算法相同的收敛速率,同时显著减少每个外层迭代的计算负担,实验表明我们提出的算法在匹配准确性和可扩展性方面显著优于现有技术。
Nov, 2019
本篇论文提出了一种利用权值矩阵进行学习的网络来解决 Quadratic Assignment Problem (QAP) 及图匹配的问题,该模型利用嵌入网络对顶点进行分类,并通过 Sinkhorn 归一化和交叉熵损失进行端到端的学习。实验结果表明,该方法在合成数据和现实图像上均取得了很好的效果。
Nov, 2019
本文研究的是图匹配问题,提出了一种基于学习的方法,用于解决基于图的模式识别问题。通过训练示例和标签,我们可以学习节点与边之间的兼容性,在解决问题时可以取得更好的效果。实验结果表明,该方法比现有算法更为有效。
Jun, 2008