Improving WalkSAT for Random 3-SAT Problems

Huimin Fu, Shuwei Chen, Yang Xu, J. Liu

Research output: Contribution to journalArticle

2 Downloads (Pure)

Abstract

Stochastic local search (SLS) algorithms are well known for their ability to
efficiently find models of random instances of the Boolean satisfiability (SAT) problems. One of the most famous SLS algorithms for SAT is called WalkSAT, which has wide influence and performs well on most of random 3-SAT instances. However, the performance of WalkSAT lags far behind on random 3-SAT instances equal to or greater than the phase transition ratio. Motivated by this limitation, in the present work, firstly an allocation strategy is introduced and utilized in WalkSAT to determine the initial assignment, leading to a new algorithm called WalkSATvav. The experimental results show that WalkSATvav significantly outperforms the state-of-the-art SLS solvers on random 3-SAT instances at the phase transition for SAT Competition 2017. However, WalkSATvav cannot rival its competitors on random 3-SAT instances greater than the phase transition ratio. Accordingly, WalkSATvav is further improved for such instances by utilizing a combination of an improved genetic algorithm and an
improved ant colony algorithm, which complement each other in guiding the search direction. The resulting algorithm, called WalkSATga, is far better than WalkSAT and significantly outperforms some previous known SLS solvers on random 3-SAT instances greater than the phase transition ratio from SAT Competition 2017. Finally, a new SAT solver called WalkSATlg, which combines WalkSATvav and WalkSATga, is proposed, which is
competitive with the winner of random satisfiable category of SAT competition 2017 on random 3-SAT problem.
Original languageEnglish
Pages (from-to)220-243
Number of pages24
JournalJournal of Universal Computer Science
Volume26
Issue number2
Publication statusPublished - 28 Feb 2020

Keywords

  • 3-SAT
  • Allocation strategy
  • Ant colony algorithm
  • Genetic algorithm
  • WalkSAT

Fingerprint Dive into the research topics of 'Improving WalkSAT for Random 3-SAT Problems'. Together they form a unique fingerprint.

  • Cite this