Improving stochastic local search for uniform k-SAT by generating appropriate initial assignment

Huimin Fu, Wuyang Zhang, Guanfeng Wu, Yang Xu, J. Liu

Research output: Contribution to journalArticlepeer-review

36 Downloads (Pure)

Abstract

Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of random instances of the SAT problem, especially for uniform random k-SAT instances. Two processes affect most SLS solvers—the initial assignment of the variables and the heuristics that select which variable to flip. In the last few years, the work on generating the appropriate initial assignment has not been paid much attention or seen much progress, while most SLS solvers focused on the heuristic algorithm. The present work aims to improve SLS algorithms on uniform random k-SAT instances by developing effective methods for generating the initial assignment of variables in a controlled way. First, the allocation strategy introduced recently for 3-SAT instances is extended to initialize the initial assignment on random k-SAT instances. Then a concept of an initial probability distribution of the clause-to-variable ratio of the instance is introduced to determine the parameters of the allocation strategy. This combined method is added to the beginning of six state-of-the-art SLS algorithms in order to generate initial assignments of variables in a controlled way instead of generating them randomly, resulting in six extended SLS algorithms named WalkSATlm_E, DCCASat_E, Score 2SAT_E, CSCCSat_E, Probsat_E, and Sparrow_E, respectively. They are then evaluated in terms of their capabilities and efficiency on uniform random k-SAT instance from the random track of SAT Competitions in 2016, 2017, and 2018. Experimental results show that these improved SLS solvers outperform their original performance, especially WalkSAT_E, Score 2SAT_E, and CSCCSat_E outperform the winner of the random track of SAT competition in 2017. In addition, based on the initial probability distribution method, the present work proposes a parameter tuning and analysis of random 3-SAT instances and provides an additional comparative analysis with the state-of-the-art random SLS solvers based on large-scale experiments.

Original languageEnglish
Pages (from-to)1-39
Number of pages40
JournalComputational Intelligence
Volume37
Issue number4
Early online date10 Aug 2021
DOIs
Publication statusPublished online - 10 Aug 2021

Bibliographical note

Funding Information:
This work is supported by the National Natural Science Foundation of China (Grant No.61673320) and the Fundamental Research Funds for the Central Universities (Grant No. 2682019ZT16, 2682020CX59).

Publisher Copyright:
© 2021 Wiley Periodicals LLC.

Keywords

  • Artificial Intelligence
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Improving stochastic local search for uniform k-SAT by generating appropriate initial assignment'. Together they form a unique fingerprint.

Cite this