May, 2022

通过高效探索学习解决组合图分割问题

PDF
TL;DR本文介绍了一种名为 ECORD 的新型强化学习算法，它通过限制图神经网络的使用，提升了在最大割问题上的表现和可扩展性。在 500 个节点的图上，ECORD 相较于最接近的竞争者，优化效果缩小了最多 73%。同时，ECORD 在具有多达 10000 个节点的图的普适性方面保持了强有力的表现。
combinatorial optimisationreinforcement learninggraph neural networksmaximum cut problemscalability
发现论文，激发创造
  • 强化学习的组合探索优化

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

    Sep, 2019

  • 基于图的鲁棒强化学习在物流优化中的应用

    我们结合了图神经网络和强化学习，在纽约市的广义交通网络中，运用强化学习方法，分别比较了 GAT，Pro-CNN 和 PTDNet 三种算法。最终我们利用 PTDNet 和 GNN 进行强化训练，在 AMOD 系统优化问题上取得了 SOTA 结果。

    May, 2022

  • 线性时间内学习在实际图中求解组合优化问题

    本文介绍一种使用强化学习训练图神经网络求解单人游戏定义的图组合优化问题的新框架，可以处理最小生成树、最短路径、旅行商问题和车辆路径问题等一系列问题，该方法可在线性运行时间内输出近似解，并且能够推广到多种情况，包括 NP 困难的问题和真实世界的图。

    Jun, 2020

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

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

    Jan, 2024

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

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

    Jun, 2020

  • 可逆行动设计与强化学习在组合优化中的应用

    利用图神经网络和深度 Q 学习的强化学习方法，针对组合优化问题提出了一种无需问题特定设计即可实现状态最优化策略搜索的通用模型，并在最大 k-Cut 问题和旅行商问题上实验验证了其优越性。

    Feb, 2021

  • 神经组合优化算法用于解决车辆路径问题：综述与展望

    基于对相关出版物和预印本的全面审查，我们将所有神经组合优化求解器分为四个不同的类别，并提出了克服当前最先进求解器不足之处的有希望和可行的方向，并对来自强化、监督和无监督学习范例的代表性神经组合优化求解器在小规模和大规模车辆路径问题上的性能进行了比较。

    Jun, 2024

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

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

    Jun, 2024

  • 利用强化学习进行 IR 感知的 ECO 时序优化

    工程变更订单（ECOs）通过集成 IR-drop 感知时序分析和强化学习（RL）优化方法，在物理设计和功率网格综合后通过门尺寸调整来修复由 IR-drop 引起的时序退化，以保持时序改进的性能，具有良好的可迁移性。

    Feb, 2024

  • 通过深度强化学习在大规模图上学习启发式算法

    本文介绍了一种名为 GCOMB 的框架，利用概率贪心机制通过训练图卷积网络 (GCN) 预测一个节点的质量，以此解决图上的组合问题。实验表明，GCOMB 比学术界最先进的组合算法快 100 倍、质量略高。此外，GCOMB 在实际的 Influence Maximization（IM）组合问题上也展现了强大的性能。

    Mar, 2019