Dec, 2023

BalMCTS: 在 MCTS 中平衡目标函数和搜索节点，用于约束优化问题

PDF
TL;DR该论文探讨了针对约束优化问题，采用深度优先搜索算法以在前 n 个解中寻找最优或近似最优解，并提出了一种基于 MCTS 的新型启发式神经网络算法，结合编码约束优化问题和利用图神经网络聚合变量和约束信息的方法，实验结果表明该方法能够快速找到初始的 5 个可行解中与最优解间隔小于 17.63% 的解，并在应用于约束满足问题时，与最先进方法相比，搜索节点数减少不到 5%。
constraint optimization problemsbranch and bound methodsdepth-first search algorithmheuristic neural network algorithmgraph neural networks
发现论文，激发创造
  • TreeDQN：学习最小化分枝定界树

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

    Jun, 2023

  • 图卷积分支与界

    使用深度学习模型在优化流程中的有效性进行了论证，通过将图卷积分支限界与经典的分支限界算法相结合，实现了更快速的解决旅行商问题的路径的识别。

    Jun, 2024

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

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

    Aug, 2022

  • 分布式约束优化问题的预训练成本模型

    该论文提出了一种基于图神经网络的 DCOPs 解决方案，通过预训练的优化标签数据构建出有效的启发式方法，在分布式环境中实现了去中心化的模型推理，并结合局部搜索或回溯搜索算法，在各种测试中都取得了显著的优异表现。

    Dec, 2021

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

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

    Oct, 2018

  • 使用图卷积神经网络进行精确组合优化

    本文提出了一种基于图卷积神经网络的分支定界变量选择新模型，通过模仿学习和强分支专家规则训练，成功解决了组合优化问题。实验结果表明，该方法不仅在分支机制上优于现有的机器学习方法，而且在大问题上也优于现有的专家设计分支规则。

    Jun, 2019

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

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

    Aug, 2023

  • BnB-ADOPT：一种异步分支界限 DCOP 算法

    本文介紹了一種名為 Branch-and-Bound ADOPT 的內存有限的異步 DCOP 搜索算法，它用於協調解決代理問題，該算法對於相應的問題可以比 ADOPT 和 NCBB 更快地找到代價最小的解決方案，同時實現了相對誤差邊界。

    Jan, 2014

  • 组合优化的多目标指针网络

    这项研究提出了一种名为 MOPN 的多目标指针网络单模型深度强化学习框架，用于有效解决多目标组合优化问题，在不同应用场景下深度增强学习与代表性模型、迁移学习等策略相结合下取得了更好的性能。

    Apr, 2022

  • Moco: 一个可学习的元优化器用于组合优化

    Moco 是一个完全可学习的元优化器，使用基于当前搜索状态提取的特征来更新解构建过程，适应不同的计算预算，表现优于其他方法。

    Feb, 2024