Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning

📄 arXiv: 2404.00539v1 📥 PDF

作者: Satoko Iida, Ryota Yasudo

分类: cs.LG

发布日期: 2024-03-31

备注: 7 pages, 7 figures

💡 一句话要点

提出两阶段图指针网络解决二次分配问题

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

关键词: 二次分配问题 图指针网络 深度强化学习 组合优化 旅行商问题 半最优解 算法改进

📋 核心要点

  1. 二次分配问题（QAP）是NP难题，现有启发式方法在大规模实例中效率低下，执行时间长。
  2. 本文提出的两阶段图指针网络（GPN）结合深度强化学习，旨在高效解决QAP，借鉴了针对旅行商问题的GPN结构。
  3. 实验结果显示，所提模型在TSPlib和QAPLIB基准问题上提供了有效的半最优解，展示了其优越性。

📝 摘要（中文）

二次分配问题（QAP）是一类实际的组合优化问题，因其NP难度，解决大规模实例具有挑战性。尽管启发式方法能找到半最优解，但随着问题规模的增加，执行时间显著增加。近年来，利用深度学习解决组合优化问题受到关注，尽管如此，解决大规模QAP依然困难。本文提出了一种名为两阶段图指针网络（GPN）的深度强化学习模型，用于解决QAP。我们首先扩展了GPN以适应一般的旅行商问题（TSP），然后为解决QAP添加了新算法。实验结果表明，所提的两阶段GPN能够为TSPlib和QAPLIB中的基准问题实例提供半最优解。

🔬 方法详解

问题定义：本文聚焦于二次分配问题（QAP），该问题在组合优化中具有广泛应用，但由于其NP难度，现有方法在处理大规模实例时面临显著的时间复杂度挑战。

核心思路：提出的两阶段图指针网络（GPN）模型通过深度强化学习框架，旨在提高QAP的求解效率。该方法首先扩展了现有的GPN结构，使其适应一般的旅行商问题（TSP），然后针对QAP进行了算法改进。

技术框架：整体架构分为两个阶段：第一阶段为图指针网络的构建，处理输入数据并生成初步解；第二阶段则通过强化学习优化解的质量，逐步逼近半最优解。

关键创新：本研究的核心创新在于将图指针网络与强化学习相结合，形成两阶段模型，显著提升了求解QAP的效率和效果。这一方法与传统启发式方法相比，能够更快地找到高质量解。

关键设计：模型设计中，关键参数包括学习率、网络层数和损失函数的选择。损失函数设计为适应QAP特性，确保模型在训练过程中能够有效收敛。

📊 实验亮点

实验结果表明，两阶段图指针网络在TSPlib和QAPLIB基准问题上表现优异，能够提供高质量的半最优解，相较于传统启发式方法，求解速度显著提升，展示了深度学习在组合优化领域的潜力。

🎯 应用场景

该研究的潜在应用领域包括物流优化、资源分配、网络设计等多个组合优化场景。通过提高QAP的求解效率，能够为实际问题提供更快的解决方案，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Quadratic Assignment Problem (QAP) is a practical combinatorial optimization problems that has been studied for several years. Since it is NP-hard, solving large problem instances of QAP is challenging. Although heuristics can find semi-optimal solutions, the execution time significantly increases as the problem size increases. Recently, solving combinatorial optimization problems by deep learning has been attracting attention as a faster solver than heuristics. Even with deep learning, however, solving large QAP is still challenging. In this paper, we propose the deep reinforcement learning model called the two-stage graph pointer network (GPN) for solving QAP. Two-stage GPN relies on GPN, which has been proposed for Euclidean Traveling Salesman Problem (TSP). First, we extend GPN for general TSP, and then we add new algorithms to that model for solving QAP. Our experimental results show that our two-stage GPN provides semi-optimal solutions for benchmark problem instances from TSPlib and QAPLIB.