Y. Kilani (Jordan)
GASAT, DLM, and SAT.
The satisfiability problem (SAT), as one of the six basic core NP-complete problems, has been the deserving object of many studies in the last two decades [3, 2]. GASAT [4, 3, 2] is one of the current state-of-the-art genetic algo rithms for solving SATs. Besides, the discrete lagrange multiplier (DLM) [7, 8] is one of the current state-of-the art local search algorithms for solving SATs. GASAT is a hybrid algorithm of the genetic and tabu search techniques. GASAT uses tabu search to avoid restarting the search once it converges. In this paper, we improve GASAT by replac ing the tabu search by the DLM algorithm. We show that the performance of the new algorithm is far better than the performance of GASAT in solving most of the benchmark instances.
Important Links:
Go Back
