Jun, 2020

Erdos Goes Neural: 图形组合优化的无监督学习框架

PDF
TL;DR本文提出了一种基于无标签示例的图上 CO 问题的无监督学习框架，该框架可以提供具有保证质量的整数解，实现方法为使用神经网络参数化一组概率分布，并基于 Erdos 的概率方法来对其进行优化，最后将解码得到所需的解。该方法在实际数据集和复杂实例上取得了具有竞争力的结果。
发现论文，激发创造
  • 使用无数据神经网络的可微组合优化方法

    本研究提出了一种基于神经网络的无数据训练方法，用于解决组合优化问题，特别是最大独立集和最大团的问题，并提出了通用的图缩小过程来处理大规模图形。这种方法在无需数据的情况下，可与有监督学习、强化学习和基于机器学习的现有方法相媲美或更优，具有广泛的适用性。

    Mar, 2022

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

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

    Jun, 2024

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

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

    Jul, 2021

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

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

    Jan, 2024

  • 组合优化的无监督学习需要元学习

    提出了一种基于元学习的训练流程，用于寻找未来遇到的问题实例的良好初始化而不是直接给出答案。该方法在各种评估设置下都取得了良好的实证性能。

    Jan, 2023

  • 基于图神经网络的组合优化和推理

    本文通过对近年来在组合优化、运筹学和机器学习等领域出现的基于图神经网络（GNNs）的组合优化求解方法和算法进行概述，以此向优化和机器学习研究者介绍这一领域的最新进展。

    Feb, 2021

  • 图上组合优化的统一预训练和适应框架

    通过最大可满足性问题（Max-SAT）提出了一种统一的图上组合优化问题（CO）的预训练和适应框架，能够提取可转移和可推广的特征，以解决图上不同 CO 问题。

    Dec, 2023

  • 无监督神经组合优化的扩散模型框架

    通过引入一种可以上界反向 Kullback-Leibler 散度且避免要求确切样本似然的损失函数，本研究提出了一种能够解决在不依赖相应训练数据的情况下从难以处理的离散集合中进行采样的问题的方法，并展示了该方法在无数据组合优化中实现了最先进的性能。

    Jun, 2024

  • 神经组合优化：领域的新玩家

    本文对神经网络在传统组合优化框架中的性能、可迁移性、计算成本和对更大样本的普适性进行了详细研究，并在 NP-hard 问题线性排序问题上开发了神经组合优化模型。

    May, 2022

  • 现代图神经网络在解决诸如最大独立集等组合优化问题方面表现不如传统的贪心算法

    该论文引入了一种物理启发的无监督图神经网络以解决稀疏图上的组合优化问题，作者展示了在最大割和最大独立集问题上这些 GNNs 的性能可以与或优于现有求解器，并且具有处理百万变量问题的能力。然而，该评论提出了一个简单贪心算法可以找到比 GNN 更好的质量的解决方案。此外，该评论者还建议通过基于真正困难的问题的标准基准测试未来的神经网络优化器。

    Jun, 2022