Oct, 2023

利用深度强化学习解决二次分配问题

PDF
TL;DR通过深度强化学习的方法解决 Quadratic Assignment Problem（QAP）的 Koopmans-Beckman 公式，使用双指针网络（double pointer network）在选择下一个设施放置位置和上一个位置放置设施之间交替，并通过 A2C 算法在一系列合成实例上进行模型训练。在样本外测试中，我们的解决方案与高质量的局部搜索基线相比，平均准确率达到了 97.5%，在 1.2% 的实例中表现优于基线。
quadratic assignment problemnp-hard problemdeep reinforcement learningdouble pointer networka2c
发现论文，激发创造
  • 通过两阶段图指针网络和强化学习解决 QAP 问题

    本文提出了一种基于深度强化学习模型的两阶段图指示器网络（GPN）来解决二次分配问题（QAP），实验结果表明它可以为 TSPLib 和 QAPLIB 的基准问题提供半最优解。

    Mar, 2024

  • 学习解决方案感知的变压器以高效解决二次分配问题

    利用机器学习的能力，针对组合优化中的 Quadratic Assignment Problem (QAP) 提出了第一种针对 QAP 的学习优化方案，该方案使用 Solutions AWare Transformer (SAWT) 架构来有效捕捉 QAP 的高阶信息。

    Jun, 2024

  • 大规模（脑）图匹配的快速近似二次规划

    本文介绍了一种快速的近似二次分配算法（FAQ），能够更高效地在大数据和图值数据上处理 QAP 问题，通过在 C.elegans 连通图匹配案例上的实证表明其优越性。

    Dec, 2011

  • 极具挑战的平方分配问题的研究：QAP-SAT 实例

    本研究探讨了 Quadratic Assignment Problem 的相变现象，通过引入新的基于子模块性的 QAP-SAT 设计来捕捉问题的复杂度，并使用分支界限和禁忌搜索求解器对其进行实验研究，在此基础上提出了相变参数，发现禁忌搜索的相变满意度和解决努力与关键参数高度相关，从而可以预测出困难的实例。

    Mar, 2024

  • 半定规划方法求解稀疏图的二次分配问题

    本研究提出了一种新的半定规划 (SDP) 方法来解决二部图的匹配问题，采用正半定矩阵进行松弛，并通过聚类来加强松弛，使得计算复杂度和运行时间得到了缩减，可以应用于核磁共振光谱 (NMR) 等领域的匹配问题。

    Mar, 2017

  • 利用谐波分析将领域知识纳入匹配问题

    探究加速解决二次分配问题（QAP）的新方法，利用特殊的优化函数方法在傅里叶空间中优化对称群 Sn，以及在多个优化任务中学习参数。实验表明，新方法在实际领域中可以优于现有方法。

    Jun, 2012

  • 运用深度强化学习解决车辆路径问题

    本文介绍了强化学习在处理 NP-Hard 组合优化问题，特别是车辆路径问题方面的应用。作者将问题建模成一个马尔科夫决策过程，并采用了 Actor-Critic 类的 PPO 方法和基于卷积神经网络的神经架构。尽管与最先进的 OR-TOOLS 解算器相比略逊一筹，但该算法具有较好的泛化能力和较短的解答时间。未来的研究方向是提高算法的性能表现。

    Jul, 2022

  • 基于图神经网络的二次分配学习算法修订笔记

    研究逆向问题的计算困难性及使用基于图神经网络的数据驱动模型来解决这类问题的效果。

    Jun, 2017

  • 使用强化学习加速二次优化

    使用强化学习 RLQP 策略自动调整参数，加速求解二次优化问题，与现有算法相比，RLQP 能显著提高性能并普适适用于不同应用场景。

    Jul, 2021

  • 基于交换的网络设施位置问题深度强化学习

    该研究论文提出了一个基于交换的框架和一种新颖的深度强化学习模型，用于解决图上的设施位置问题和设施重新定位问题。与手工启发式方法相比，该方法在复杂图数据集上表现出更好的解决方案质量和运行时间，同时引入了一种图生成过程，以模拟带有需求的现实世界城市道路网络，为经典问题的大规模数据集构建提供了便利。这一综合了交换法和深度强化学习的方法对于解决图上设施位置问题的实际挑战具有重要意义。

    Dec, 2023