Apr, 2023

利用图神经网络协助蒙特卡罗树搜索实现近乎最优斯坦纳树

PDF
TL;DR本研究介绍了一种通过结合图神经网络和蒙特卡罗树搜索来计算 Steiner 树的方法，该方法在许多不同类型的图上反复优于标准的 2 逼近算法，通常找到最优解。
graph neural networkssteiner treesmonte carlo tree searchcombinatorial problemslearning
发现论文，激发创造
  • 利用神经网络辅助的蒙特卡罗树搜索对图进行稀疏化

    图神经网络与蒙特卡罗树搜索相结合的方法对多种类型的图进行计算，超过了多个标准近似算法，并经常找到最优解。

    Nov, 2023

  • NN-Steiner: 直线 Steiner 最小树问题的混合神经算法方法

    近年来，神经网络在解决组合优化问题方面取得了快速发展。在本文中，我们提出了 NN-Steiner，这是一种新颖的混合神经 - 算法框架，用于计算矩形斯坦纳最小生成树（RSMT），并展示了其在处理复杂示例方面的泛化性和与现有方法的比较效果。

    Dec, 2023

  • GAT-Steiner: 使用 GNN 进行直角斯坦纳最小树预测

    研究论文提出了 GAT-Steiner，一种基于图注意力网络模型，能够高准确率地预测 ISPD19 基准测试中 99.846% 的网段，并在次优网长中仅产生 0.480% 的平均增加。在随机生成的基准测试中，GAT-Steiner 在 99.942% 的网段中高准确率地预测，并且在次优网长中仅产生 0.420% 的平均增加。

    Jul, 2024

  • 在图中学习剪枝斯坦纳树问题的实例

    本文使用基于机器学习的学习剪枝框架来解决史泰纳树问题，结果显示该框架可在商业整数线性规划求解器所需时间的一小部分时间内计算出近乎最优的解决方案，进一步证明了学习剪枝框架在解决各种组合优化问题方面的潜力。

    Aug, 2022

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

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

    Oct, 2018

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

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

    Jan, 2022

  • 以 MCTS 引导遗传算法优化神经网络权重

    本研究探讨了在遗传算法中应用搜索策略以探索整个基因树结构的可能性。我们尝试优化神经网络使用遗传算法，以生成最佳结果，结合了蒙特卡洛树搜索等方法。

    Aug, 2023

  • 蒙特卡罗树搜索用于策略优化

    本文提出了一种基于蒙特卡罗树搜索和无梯度优化的策略优化方法，称为 MCTSPO，通过使用上界置信度启发式获得更好的探索 - 利用平衡，相对于基于梯度和深度遗传算法的基准，在具有欺骗性或稀疏奖励函数的强化学习任务中表现更佳。

    Dec, 2019

  • 使用 MCTSnets 学习搜索

    该论文提出了一种名为 MCTSnet 的体系架构，其将基于模拟的搜索嵌入神经网络中，并通过向量嵌入扩展，评估和备份。该网络的参数进行端到端的训练优化，应用于小范围的搜索中，显著优于 MCTS 基线的性能。

    Feb, 2018

  • 在线斯坦纳树学习增强算法

    本文考虑了将机器学习与在线算法设计相结合的新型 “超越最坏情况” 算法分析模型在在线 Steiner 树问题上的应用，其中预测的终端节点可能不正确，算法性能取决于错误预测的数量，可以通过正确预测来突破在线下界并且具有良好的竞争比，同时实验证明该理论具有预测性。

    Dec, 2021