Zhang Zaijun, Zhou Jincheng, Wang Xiaoxia, Yang Heng, Fan Yi
School of Mathematics and Statistics, Qiannan Normal University for Nationalities, Duyun 558000, China.
Key Laboratory of Complex Systems and Intelligent Optimization of Guizhou Province, Duyun 558000, China.
Entropy (Basel). 2022 Dec 18;24(12):1846. doi: 10.3390/e24121846.
The (weighted) partial maximum satisfiability ((W)PMS) problem is an important generalization of the classic problem of propositional (Boolean) satisfiability with a wide range of real-world applications. In this paper, we propose an initialization and a diversification strategy to improve local search for the (W)PMS problem. Our initialization strategy is based on a novel definition of variables' structural entropy, and it aims to generate a solution that is close to a high-quality feasible one. Then, our diversification strategy picks a variable in two possible ways, depending on a parameter: continuing to pick variables with the best benefits or focusing on a clause with the greatest penalty and then selecting variables probabilistically. Based on these strategies, we developed a local search solver dubbed ImSATLike, as well as a hybrid solver ImSATLike-TT, and experimental results on (weighted) partial MaxSAT instances in recent MaxSAT Evaluations show that they outperform or have nearly the same performances as state-of-the-art local search and hybrid competitors, respectively, in general. Furthermore, we carried out experiments to confirm the individual impacts of each proposed strategy.
（加权）部分最大可满足性（（W）PMS）问题是经典命题（布尔）可满足性问题的一个重要推广，具有广泛的实际应用。在本文中，我们提出了一种初始化和多样化策略，以改进对（W）PMS问题的局部搜索。我们的初始化策略基于变量结构熵的新定义，旨在生成一个接近高质量可行解的解。然后，我们的多样化策略根据一个参数以两种可能的方式选择一个变量：继续选择收益最佳的变量，或者关注惩罚最大的子句，然后概率性地选择变量。基于这些策略，我们开发了一个名为ImSATLike的局部搜索求解器，以及一个混合求解器ImSATLike-TT，并且在最近的MaxSAT评估中对（加权）部分MaxSAT实例的实验结果表明，总体而言，它们分别优于或具有与最先进的局部搜索和混合竞争对手几乎相同的性能。此外，我们进行了实验以确认每个提出的策略的单独影响。
