Local search has been demonstrated as an efficient approach for two practical
generalizations of the MaxSAT problem, namely Partial MaxSAT (PMS) and Weighted
PMS (WPMS). In this work, we observe that most local search (W)PMS solvers
usually flip a single variable per iteration. Such a mechanism may lead to
relatively low-quality local optimal solutions, and may limit the diversity of
search directions to escape from local optima. To address this issue, we
propose a general strategy, called farsighted probabilistic sampling (FPS), to
replace the single flipping mechanism so as to boost the local search (W)PMS
algorithms. FPS considers the benefit of continuously flipping a pair of
variables in order to find higher-quality local optimal solutions. Moreover,
FPS proposes an effective approach to escape from local optima by preferring
the best to flip among the best sampled single variable and the best sampled
variable pair. Extensive experiments demonstrate that our proposed FPS strategy
significantly improves the state-of-the-art (W)PMS solvers, and FPS has an
excellent generalization capability to various local search MaxSAT solvers.

本文提出了一种名为 FPS 的策略，通过考虑连续翻转一对变量的好处来替换单一翻转机制，以提高本地搜索算法的效率，解决了局部最优解品质较低的问题，并通过最佳取样的方法避免了局部最优解，实验表明该方法极大地提高了最先进的 (W) PMS 解算器的性能。