Jun, 2024

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

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

    文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些NP困难问题，并在四个NP困难问题和五个数据集上进行了评估，结果表明该方法在某些NP困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

    Oct, 2018

  • 强化学习的组合探索优化

    在解决复杂优化问题方面，探索式组合优化（ECO-DQN）通过连续改进解决方案，从而有效地学习有效的启发式方法来解决图上的组合优化问题，并在最大割问题上展示了最先进的强化学习性能。

    Sep, 2019

  • 组合优化中的细粒度搜索空间剪枝和启发式学习

    该研究提出了一种基于机器学习的框架来扩大组合优化算法，并使用可解释的学习模型来提供更深层次的洞见，以设计更好的启发式方法，在最大团枚举问题中展示了该框架的性能，并从中获得启示设计了一种新的启发式方法。

    Jan, 2020

  • 深度学习在组合优化树搜索中的问题

    本研究提出了一个开源基准套件，对最大独立集问题进行了深入分析，结果表明现有的机器学习算法未能学习最优解的结构，算法技术仍是获得有效解决方案的关键。

    Jan, 2022

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

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

    Jun, 2022

  • 图神经网络启发式算法无法在解决如Max-Cut等组合优化问题中超越贪婪算法

    Schuetz等人提出了一种使用图神经网络作为启发式方法来解决各种组合优化问题的方案，该方法通过样例实例对网络进行训练，并应用广泛使用的技术来评估其成功的能力，尽管报告的结果只比梯度下降略有改善，但该方法承诺具有高度可伸缩性和计算成本线性。

    Oct, 2022

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

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

    Jan, 2024

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

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

    May, 2024

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

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

    Jun, 2024

  • 结合启发式方法的无监督学习框架用于最大最小割问题

    该研究针对最大最小割问题（MMCP），这是一个因双连通约束而较少受到关注的NP难度组合优化问题。本研究提出了一个结合启发式方法的无监督学习框架，首次探索了机器学习和启发式方法在解决MMCP中的应用，实验证明该框架能够提供有效且高质量的解决方案，显著改进了该领域的研究。

    Aug, 2024