发布时间：2024-06-13 16:15:21 栏目：精选百科
局部搜索方法是近年来解决组合优化问题的新兴方法，许多先进的基于局部搜索的不完全最大可满足性(MaxSAT)求解器在最近的 MaxSAT 评测中表现出色，甚至与许多完全求解器相媲美。然而，据我们所知，使用局部搜索方法求解伪布尔优化(PBO)的研究非常有限，蔡教授提出的求解器 LS-PBO 是近年来第一个基于局部搜索的 PBO 求解器。研究人员发现可以通过一些机制来提高 LS-PBO 的性能。
为解决这一问题，欧阳丹彤领导的研究团队 于2024年4月15日在 高等教育出版社和施普林格·自然集团联合出版的《计算机科学前沿》杂志上发表了他们的新研究成果。
该团队提出了一种用于解决伪布尔优化问题的新型局部搜索方法。在 LS-PBO 工作的基础上，他们提出了两个新组件，包括一种新的初始解决方案生成方法和一种在子句上定义的新启发式算法，以提高求解器的性能。新方法在许多实际应用实例以及最近 PB 竞赛中的 1600 个实例中进行了测试。与现有的完全和不完全 PBO 求解器相比，所提出的方法可以获得最多的最佳解决方案，这表明新求解器的性能令人鼓舞。
在研究中，他们采用了一种称为单元传播的技术来生成更好的初始解决方案，然后算法进入循环以改进它。为了将这种技术应用于PBO问题，他们将“单元子句”的概念扩展到PBO。单元传播之前已被广泛用于解决可满足性问题，其工作原理是收集所有单元子句，然后将其文字赋值为真以满足所有单元子句。它提供了一种直观的方法来提高初始解决方案的质量。此外，局部搜索算法有一个常见的现象，即它们很容易陷入局部最优。该团队还提出了一种新方案，以帮助算法在陷入局部最优时更快地找到可行解。他们发现现有的局部搜索算法主要利用定义在变量上的启发式来指导搜索。然而，子句作为在变量和给定公式之间架起桥梁的中介，也是算法的重要信息。因此，他们引入了一种定义在子句上的新启发式方法来指导搜索，重点关注总是被证伪的子句，这样算法就可以更快地获得可行解。
首先，他们利用三个实际应用问题的 PBO 实例对 DeciLS-PBO 进行了评估，包括最小宽度置信带、无线传感器网络优化和座位安排问题。他们还利用最近一次伪布尔竞赛中的 1600 个基准测试对新求解器进行了评估。实验结果表明，DeciLS-PBO 在大多数基准测试实例上的表现优于其竞争对手，并且在大规模实例上其性能远远超过完整求解器，这表明新求解器的优越性。
未来的工作可以集中在寻找更微妙的机制来改进局部搜索方法，并设计一种更有效的方法来解决大规模伪布尔优化问题。
免责声明：本文由用户上传，如有侵权请联系删除！
