Jan, 2023

在通用约束编程求解器内训练深度 Q 学习代理

PDF
TL;DR本文提出了一种结合深度 Q 学习算法、定制奖励信号和异构图神经网络架构的通用学习过程，用于在约束编程求解器中获取值选择启发式，并在图着色、最大独立集和最大割问题上进行实验，表明该框架能够在通用的前提下，找到更接近最优解的更好解决方案，而无需大量回溯。
constraint programmingbranching heuristicsmachine learningvalue-selection heuristicdeep q-learning algorithm
发现论文，激发创造
  • 结合强化学习和约束编程用于组合优化

    本文介绍了一种基于深度强化学习和约束编程的混合算法，应用于复杂的组合优化问题，并在实验中成功运用于旅行商问题和投资组合优化问题，表现优于单独的深度强化学习和约束编程算法，同时也达到了与工业级求解器相竞争的水平。

    Jun, 2020

  • 在图上学习组合优化算法

    本文介绍了结合强化学习和图嵌入的方法，使用元算法来解决 NP-hard 组合优化问题和图上的最小点集覆盖、最大割和旅行商问题等优化问题。

    Apr, 2017

  • TreeDQN：学习最小化分枝定界树

    本文介绍了一种基于强化学习的组合优化问题解决方法，使用树马尔可夫决策过程视角选择变量分支，并且优化学习对象，相较之前的强化学习方法，训练数据量更小，生成树的大小更小。

    Jun, 2023

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

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

    Jan, 2020

  • 能否通过 Graph Networks 的 Q-Learning 学习适用于 SAT Solver 的可推广分支启发式策略？

    本文介绍了使用图神经网络进行函数逼近的增强学习的 Graph-Q-SAT 分支启发式算法，该算法可用于解决 SAT 问题，并且在使用 MiniSat 求解器进行交互时可以减少解决 SAT 问题所需的迭代次数 2-3 倍。

    Sep, 2019

  • 图卷积网络与引导树搜索的组合优化

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

    Oct, 2018

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

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

    Mar, 2019

  • 一个模型，适用于任何 CSP: 图神经网络作为快速全局搜索启发式算法用于约束满足

    提出了一种通用的图神经网络架构，该架构可以作为任何约束满足问题的端到端搜索启发式进行训练。该方法基于一种新颖的 CSP 图形表示，可以以纯数据驱动的方式为任何 CSP 生成问题特定的启发式，对于从随机数据中学习启发式，该方法在已知的 CSP 上优于以前的 RL 方法，并且可以与传统搜索启发式竞争或更好地处理结构更为复杂的测试实例。

    Aug, 2022

  • 分支定界算法中的变量选择强化学习

    文章提出了一种名为 FMSTS 的新型增强学习方法，采用一种全新的分支策略来优化整数线性规划问题，具有一致性和泛化能力，并在计算实验中验证了其有效性。

    May, 2020

  • 基于 QP 和 MPC 的强化学习之间的桥梁

    本文采用基于 QP（Quadratic Programs）的方法，取代采用 DNN 的方法来学习 RL 中的价值函数和策略，以此提高其可解释性和简化结构，并且给出了调整可解释性和简化结构的方法。

    May, 2022