MAX-SAT问题一种改进的局部搜索算法

An Improved Local Search Method for the MAX-SAT Problem

局部搜索算法是求解大规模SAT问题的高效算法。经典的局部搜索算法有GSAT、WSAT、TSAT、NSAT等,但这些算法的初始解都是随机产生的。本文提出了用单纯形法产生"初始概率"(每个变量取1的概率) ,用"初始概率"对局部搜索算法中变量的初始随机指派进行适当的约束,使在局部搜索的开始阶段,满足的子句数大大增加,加快了收敛的速度。通过对不同规模的随机STA问题实例的实验表明,这些改进有效地提高了局部搜索算法求解SAT问题的效率。

Local search methods are efficient for solving the large-scale SAT problem. Classic local search algorithms such as GSAT,WSAT, TSAT, NSAT build initial solutions randomly. In this paper, the initial probability obtained by the simplex algorithm is put forward, which can constrain the random initial assignment of variables in the construction phase of the local search method, The strategies are helpful in increasing the number of satisfied clauses at the beginning of local search and in making the local search convergence fast. Compared with the classic local search algorithms, the experimental results show that the proposed algorithm improves the efficiency of solving the SAT problem and performs well in many instances.