利用谐波分析将领域知识纳入匹配问题
本文提出了在 Hilbert 空间中的一些规则,引入了新的外积算法,可以在重现核 Hilbert 空间中将 Lawler 的 QAP 视为 Koopmans-Beckmann 的对齐,有效地解决了大规模亲和力矩阵的问题。提出基于熵正则化的 Frank-Wolfe 算法 (EnFW) 对 QAP 进行优化,具有与原始 FW 算法相同的收敛速率,同时显著减少每个外层迭代的计算负担,实验表明我们提出的算法在匹配准确性和可扩展性方面显著优于现有技术。
Nov, 2019
本文介绍了一种快速的近似二次分配算法(FAQ),能够更高效地在大数据和图值数据上处理 QAP 问题,通过在 C.elegans 连通图匹配案例上的实证表明其优越性。
Dec, 2011
本篇论文提出了一种利用权值矩阵进行学习的网络来解决 Quadratic Assignment Problem (QAP) 及图匹配的问题,该模型利用嵌入网络对顶点进行分类,并通过 Sinkhorn 归一化和交叉熵损失进行端到端的学习。实验结果表明,该方法在合成数据和现实图像上均取得了很好的效果。
Nov, 2019
本文研究的是图匹配问题,提出了一种基于学习的方法,用于解决基于图的模式识别问题。通过训练示例和标签,我们可以学习节点与边之间的兼容性,在解决问题时可以取得更好的效果。实验结果表明,该方法比现有算法更为有效。
Jun, 2008
本研究探讨了 Quadratic Assignment Problem 的相变现象,通过引入新的基于子模块性的 QAP-SAT 设计来捕捉问题的复杂度,并使用分支界限和禁忌搜索求解器对其进行实验研究,在此基础上提出了相变参数,发现禁忌搜索的相变满意度和解决努力与关键参数高度相关,从而可以预测出困难的实例。
Mar, 2024
通过学习相关可扩展的线性分配问题,我们提出了一种对数据进行对齐的方法,该方法在单细胞多组学和神经潜伏空间的数据集上取得了最先进的性能,并且在概念上和计算上非常简单。
Jun, 2024
通过深度强化学习的方法解决 Quadratic Assignment Problem(QAP)的 Koopmans-Beckman 公式,使用双指针网络(double pointer network)在选择下一个设施放置位置和上一个位置放置设施之间交替,并通过 A2C 算法在一系列合成实例上进行模型训练。在样本外测试中,我们的解决方案与高质量的局部搜索基线相比,平均准确率达到了 97.5%,在 1.2% 的实例中表现优于基线。
Oct, 2023
利用机器学习的能力,针对组合优化中的 Quadratic Assignment Problem (QAP) 提出了第一种针对 QAP 的学习优化方案,该方案使用 Solutions AWare Transformer (SAWT) 架构来有效捕捉 QAP 的高阶信息。
Jun, 2024
本研究探讨了使用量子计算技术解决三维形状图像匹配问题,提出了将二次受限二进制优化问题映射到量子硬件的几种重构方法,重点考虑获得足够的频谱间隙,以提高在单次运行中测量最优解和有效置换矩阵的概率。在量子计算机 D-Wave 2000Q 上进行实验,结果表明本文提出的置换矩阵约束的重新表述,增加了数值计算的稳健性。该算法有望在未来的量子计算架构上扩展到更高维度,为 3D 计算机视觉和图形问题的解决开辟多个新方向。
Jul, 2021
我们研究了不完全多图匹配问题,该问题是配对多个有限集合的 NP 难问题的推广,多图匹配在计算机视觉中起着关键作用,已经提出了许多专门的优化技术。我们填补了这一差距,并将已知的多维分配问题近似算法转化为不完全多图匹配问题。通过实验证明,我们的新方法在目标和运行时间方面显著优于以前的技术水平。我们的算法能够在两分钟内匹配超过 500 个关键点的 29 个图像,而考虑的最快竞争方法至少需要半小时,同时产生了更差的结果。
Jun, 2024