Solving the Quadratic Assignment Problem using Deep Reinforcement Learning

📄 arXiv: 2310.01604v1 📥 PDF

作者: Puneet S. Bagga, Arthur Delarue

分类: cs.LG, cs.AI, math.OC

发布日期: 2023-10-02

💡 一句话要点

提出深度强化学习方法以解决二次分配问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 二次分配问题 深度强化学习 双指针网络 组合优化 A2C算法 设施布局 电子线路设计

📋 核心要点

  1. 二次分配问题（QAP）是NP难题，现有方法在解决大于30个位置的实例时面临重大挑战。
  2. 本文提出了一种新颖的双指针网络，结合深度强化学习，交替选择设施位置和设施，旨在高效解决QAP。
  3. 实验结果表明，所提方法在无实例特定重训练的情况下，平均解决方案与基线相差7.5%，并在部分实例中表现优于基线。

📝 摘要（中文）

二次分配问题（QAP）是一类NP难题，解决起来极具挑战性。与其他组合问题（如旅行商问题）不同，目前尚无已知方法能精确解决超过30个位置的QAP实例。尽管如此，QAP在电子线路设计和设施布局选择等多个关键应用中具有重要意义。本文提出了一种基于深度强化学习的解决方案，利用新颖的双指针网络交替选择位置和设施。通过在大型合成实例数据集上使用A2C训练模型，我们的方案在无实例特定重训练的情况下，平均解决方案与高质量局部搜索基线相差7.5%，并在1.2%的实例中超越了该基线。

🔬 方法详解

问题定义：本文旨在解决二次分配问题（QAP），该问题在组合优化中极具挑战性，现有方法在处理超过30个位置的实例时无法提供精确解。

核心思路：我们提出了一种基于深度强化学习的解决方案，利用双指针网络结构，交替选择设施位置和设施，以实现高效的解算过程。这样的设计使得模型能够在复杂的搜索空间中有效探索。

技术框架：整体架构包括数据预处理、模型训练和解算三个主要阶段。首先生成合成实例数据，然后使用A2C算法训练双指针网络，最后通过模型生成解。

关键创新：最重要的创新在于双指针网络的设计，使得模型能够在选择设施和位置时进行有效的交替，从而提高了解的质量和效率。这一方法与传统的整数规划方法有本质区别。

关键设计：模型采用A2C算法进行训练，损失函数设计为结合了策略梯度和价值函数的损失，网络结构则包括多个层次的全连接层，以捕捉复杂的特征关系。具体参数设置和超参数调优在实验中进行了详细探讨。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果显示，所提方法在无实例特定重训练的情况下，平均解决方案与高质量局部搜索基线相差仅7.5%，并在1.2%的实例中超越了该基线，展现出良好的性能和实用性。

🎯 应用场景

该研究的潜在应用领域包括电子线路设计、设施布局选择、物流优化等。通过有效解决二次分配问题，能够显著提升这些领域的设计效率和资源利用率，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

The Quadratic Assignment Problem (QAP) is an NP-hard problem which has proven particularly challenging to solve: unlike other combinatorial problems like the traveling salesman problem (TSP), which can be solved to optimality for instances with hundreds or even thousands of locations using advanced integer programming techniques, no methods are known to exactly solve QAP instances of size greater than 30. Solving the QAP is nevertheless important because of its many critical applications, such as electronic wiring design and facility layout selection. We propose a method to solve the original Koopmans-Beckman formulation of the QAP using deep reinforcement learning. Our approach relies on a novel double pointer network, which alternates between selecting a location in which to place the next facility and a facility to place in the previous location. We train our model using A2C on a large dataset of synthetic instances, producing solutions with no instance-specific retraining necessary. Out of sample, our solutions are on average within 7.5% of a high-quality local search baseline, and even outperform it on 1.2% of instances.