Aug, 2023

关于在图上的组合优化中的 QUBO 基于哈密顿函数用于 Max Cut (MC) 问题的研究

PDF
TL;DR利用强化学习与哈密顿函数结合的方法在二次无约束二进制优化（QUBO）问题中处理组合优化问题。使用图神经网络作为节点之间信息传递的消息传递架构，并使用 Monty-Carlo Tree Search with GNN-based RL（MCTS-GNN）、DQN with GNN-based RL 和 GRL 三种结构进行研究。发现 RL 范式中，QUBO 公式中基于哈密顿函数的优化可以带来模型收敛，并可作为通用的奖励函数；并通过对不同密度图上的实验，从违反约束、学习稳定性和计算成本的角度比较了不同结构的性能。
发现论文，激发创造
  • 基于图神经网络的 QUBO 规划激发哈密顿损失函数用于组合优化的强化学习

    通过引入 QUBO 变换哈密顿量和建立 RL 模型的奖励函数，我们提出了一种改进 PI-GNN 算法的方法，并采用 Monty Carlo Tree Search 策略和 GNN 结合进行训练，实验结果表明在满足约束条件方面有 44% 的改进。

    Nov, 2023

  • QUBO 模型的表述和应用教程

    该论文介绍了 QUBO 模型的基本特征，以及它在优化领域中的重要性，涵盖了与物理中的 Ising 问题，量子退火，神经形态计算等领域密切相关的专业术语，并详细阐述了如何使用 QUBO 模型在许多不同的应用中展示其潜力和灵活性。

    Nov, 2018

  • 二次无约束二进制优化问题预处理：理论与实证分析

    此研究提出了一种通过识别可以预定的最优变量来减少 QUBO 矩阵的规模并从而改善优化问题解决质量和时间的方法，并分析了对此规模减小技术最有影响的 QUBO 结构特征。

    May, 2017

  • 物理启发图神经网络的组合优化

    本文介绍了如何使用图神经网络来解决组合优化问题，包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略，我们生成了一个可区分的损失函数，并在无监督训练过程结束后对整数变量进行简单的投影。实验表明，我们的方法在解决包含数百万个变量的问题时能够胜任。

    Jul, 2021

  • 图学习用于量子近似优化算法参数预测

    我们的研究通过使用图神经网络（GNN）作为热启动技术来优化 QAOA 初始化，为了减少量子计算资源的开销，牺牲了大量的经济计算资源，从而提高了 QAOA 的效果；实验结果表明 GNN 有助于提高 QAOA 的性能，为量子计算中的混合量子 - 经典方法开辟了新的途径，也为实际应用做出了贡献。

    Mar, 2024

  • 基于哈密顿量的量子强化学习用于神经计算组合优化

    基于 Hamiltonian 的量子强化学习（QRL）是将量子计算与神经组合优化相结合的一种方法，通过对组合优化问题的 Hamiltonian 公式建模，拥有较好的训练性能，适用于广泛的问题类别，并与 QAOA 进行了比较。

    May, 2024

  • 图形 Q-Learning 用于组合优化

    本论文提出并证明了图神经网络可以应用于解决组合优化问题，通过将优化过程视为顺序决策问题，使用 Q-Learning 训练图神经网络可以在参数和训练时间上只占一小部分的情况下接近达到最先进的启发式求解器的性能。

    Jan, 2024

  • 面向决策的图神经网络在组合优化中的应用

    我们的研究工作的重点是通过决策导向的图学习，在组合优化问题中采用神经网络框架，提出了一个更高效和精确的框架。此外，我们引入了一个决策导向的框架，利用图神经网络解决具有辅助支持的组合优化问题。实验结果表明，我们的方法在经典组合优化问题上优于独立的图神经网络方法和传统方法。

    Jun, 2024

  • 面向组合优化的通用图神经网络框架

    图神经网络在解决节点分类、图分类和链接预测等任务方面取得了巨大成功。然而，将图神经网络和机器学习应用于组合优化问题的研究相对较少。本文引入了一种新颖的图神经网络架构，利用复杂的滤波器组和局部化注意机制来解决图上的组合优化问题。我们展示了我们的方法如何与以往基于图神经网络的组合优化求解器区别开来，并在自监督学习设置下有效地应用于最大团、最小支配集和最大割问题。除了证明在各项任务上具有竞争力的整体性能外，我们还为最大割问题建立了最新的研究结果。

    May, 2024

  • 最大割的基准：朝着组合优化的学习启发式评估的标准化

    设计适用于基于图的组合优化问题的通用启发式方法，通过引入图神经网络 (GNN) 来学习分布特定的解决方案结构。通过提出开源基准测试套件 MaxCut-Bench，对多个学习方法进行系统验证，并发现某些学习启发式方法无法胜过贪婪算法，只有一种方法在各个维度上具有一致的优越性能。

    Jun, 2024