组合嵌套 Monte Carlo 与局部搜索方法解决 MaxSAT 问题
本文介绍了一种结合 solution prediction model 和神经网络的方法 ——NLocalSAT,用于提高 stochastic local search 在解 Boolean satisfiability problem 时的有效性,并且在 SAT Competition 2018 的实验中取得了 27% ~ 62% 的性能提升。
Jan, 2020
本文提出使用蒙特卡罗搜索设计数学表达式作为蒙特卡罗树搜索算法的探索项,优化了 PUCT 和 SHUSS 树搜索算法的根探索项,使得在小型搜索预算下,这些发现的根探索项使得两种算法与常规的 PUCT 算法有竞争力。
Apr, 2024
该研究通过合理连接基于 MCTS 的两种不同种类算法来实现在短时间内寻求合理 good action,同时保持 BRUE 算法的优秀的收敛性能和指数级性能提高的保障。
Sep, 2013
提出了并行化算法 WU-UCT,引入了一组统计数据来跟踪未完成的模拟查询数量,并且这些统计数据被用于修改选择步骤中的 UCT 树策略,从而在最耗时的拓展和模拟步骤并行化时保持有效的探索 - 开发折衷,并且实验表明 WU-UCT 相比现有技术具有线性加速和卓越性能。
Oct, 2018
通过结合更新蒙特卡洛树搜索法和强化学习技术,本文提出了一种名为更新蒙特卡洛树搜索的高效优化算法,用于寻找适宜的桁架结构设计,数值结果表明该方法比传统方法计算时间至少快十倍且能稳定获得更好的解。
Sep, 2023
提出一种基于连续局部搜索与信念传播结合的算法 GradSAT,能在求解混合布尔约束问题方面有很好的应用表现,对称布尔约束和小系数伪布尔约束也可适用,并有望成为解决布尔满足性和优化问题的有效方法之一。
Dec, 2020
该研究提出了一种基于整数规划和强化学习算法的统一框架 DCSAT,用于解决不同类型的布尔可满足性问题,包括 MaxSAT、Weighted MaxSAT、PMS 和 WPMS 等。通过调整目标函数系数,构建了统一的整数规划表示方法,并基于 0-1 整数规划构建了适当的强化学习模型。基于二叉树搜索结构,在 SAT 问题上应用了蒙特卡罗树搜索(MCTS)方法,证明了该方法能够基于维纳 - 欣钦大数定律找到所有最优的布尔赋值。实验证明,该方法能够剪枝不必要的搜索空间,找到问题的最优布尔赋值,同时为 SAT 问题的监督学习方法提供多样的标签。
Dec, 2023
本文调查了 Monte Carlo Tree Search (MCTS) 在领域特定修改和混合方法方面的应用,这种方法依赖于智能树搜索并平衡探索和利用。
Mar, 2021
在本文中,我们进一步深入研究了计划任务中使用的理想赌博机,并提出了两种赌博机 UCB1-Uniform/Power,然后将它们应用于传统计划的 MCTS 中,我们正式证明了它们的遗憾界限,并在传统计划中实证展示了它们的性能。
May, 2024
本文介绍了一种基于贝叶斯框架与高斯近似算法的 Monte-Carlo Tree Search 方法,旨在更准确地估算节点价值和不确定性,并证明了该方法的在策略和非策略情境下的收敛性和实现的优越性。
Mar, 2012