A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning

📄 arXiv: 2311.16277v1 📥 PDF

作者: Redwan Ahmed Rizvee, Raheeb Hassan, Md. Mosaddek Khan

分类: cs.LG, cs.AI

发布日期: 2023-11-27

💡 一句话要点

提出基于图神经网络的QUBO形式哈密顿启发损失函数以解决组合优化问题

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

关键词: 图神经网络 组合优化 强化学习 QUBO 哈密顿量 蒙特卡洛树搜索 约束满足

📋 核心要点

  1. 现有的PI-GNN方法在处理组合优化问题时，随着图密度增加，约束满足度显著下降，影响了其性能。
  2. 本文提出了一种基于QUBO形式哈密顿启发的损失函数，并将其作为强化学习中的通用奖励函数，以提升组合优化的效果。
  3. 实验结果显示，采用新方法后，约束违反数量相比PI-GNN减少了44%，显著提升了优化性能。

📝 摘要（中文）

二次无约束二进制优化（QUBO）是一种通用技术，用于将各种NP难度组合优化问题建模为二进制变量。哈密顿量用于建模系统的能量函数。QUBO与哈密顿量的关系被视为通过量子优化算法解决各种经典优化问题的技术。最近，提出了PI-GNN框架，基于图神经网络架构解决组合优化问题。本文识别了PI-GNN在约束满足度下降的行为模式，并提出改进策略。同时，我们探讨了强化学习与QUBO形式哈密顿量之间的桥梁，提出了基于蒙特卡洛树搜索的策略，经过实验证明，与PI-GNN相比，约束违反数量提高了44%。

🔬 方法详解

问题定义：本文旨在解决组合优化问题中的约束满足度下降问题，现有的PI-GNN方法在图密度增加时性能显著下降。

核心思路：通过将QUBO形式哈密顿量作为强化学习中的奖励函数，构建一种新的损失函数，以此提升组合优化的效果。

技术框架：整体架构包括图神经网络（GNN）模块和强化学习（RL）模块，结合蒙特卡洛树搜索（MCTS）策略，通过手动扰动节点标签进行引导搜索。

关键创新：最重要的创新在于将QUBO形式哈密顿量引入强化学习框架，形成新的奖励机制，区别于传统的基于问题特定的奖励函数。

关键设计：在网络结构上，采用图神经网络进行特征提取，损失函数设计为QUBO形式哈密顿量，参数设置经过多次实验优化，以确保模型的收敛性和性能提升。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，采用新提出的基于QUBO形式哈密顿量的损失函数后，约束违反数量相比PI-GNN减少了44%。这一显著提升展示了新方法在组合优化问题中的有效性，具有重要的参考价值。

🎯 应用场景

该研究的潜在应用领域包括物流调度、网络设计和资源分配等组合优化问题。通过提升约束满足度，能够在实际应用中实现更高效的解决方案，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Quadratic Unconstrained Binary Optimization (QUBO) is a generic technique to model various NP-hard Combinatorial Optimization problems (CO) in the form of binary variables. Ising Hamiltonian is used to model the energy function of a system. QUBO to Ising Hamiltonian is regarded as a technique to solve various canonical optimization problems through quantum optimization algorithms. Recently, PI-GNN, a generic framework, has been proposed to address CO problems over graphs based on Graph Neural Network (GNN) architecture. They introduced a generic QUBO-formulated Hamiltonian-inspired loss function that was directly optimized using GNN. PI-GNN is highly scalable but there lies a noticeable decrease in the number of satisfied constraints when compared to problem-specific algorithms and becomes more pronounced with increased graph densities. Here, We identify a behavioral pattern related to it and devise strategies to improve its performance. Another group of literature uses Reinforcement learning (RL) to solve the aforementioned NP-hard problems using problem-specific reward functions. In this work, we also focus on creating a bridge between the RL-based solutions and the QUBO-formulated Hamiltonian. We formulate and empirically evaluate the compatibility of the QUBO-formulated Hamiltonian as the generic reward function in the RL-based paradigm in the form of rewards. Furthermore, we also introduce a novel Monty Carlo Tree Search-based strategy with GNN where we apply a guided search through manual perturbation of node labels during training. We empirically evaluated our methods and observed up to 44% improvement in the number of constraint violations compared to the PI-GNN.