Improving GASAT by replacing tabu search by DLM and enhancing the best members

摘要

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 (Lardeux et al. 2005, 2006). GASAT (Lardeux et al. 2005, 2006; Hao et al. 2002) is one of the current state-of-the-art genetic algorithms for solving SATs. Besides, the discrete lagrange-multiplier (DLM) (Wu and Wah 1999a, b) 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 replacing the tabu search by the DLM algorithm. We show that the performance of the new algorithm, DGASAT, is far better than the performance of GASAT in solving most of the benchmark instances. We further improve DGASAT by introducing the notion of improving one of the best members in the current population at a time. We show through experimentation that DGASAT + is far better than DGASAT in solving nearly all the benchmark instances.