A flipping genetic algorithm for hard 3-SAT problems
Elena Marchiori, Cláudio Rossi · 1999
In this paper we propose a novel heuristic based genetic algorithm for solving the satisfiability problem. The idea is to act repeatedly on a population of candidate solutions: at each iteration, first a simple local search procedure is applied to each element of the population; next the genetic operators (selection, recombination and mutation) are applied to the resulting population. Extensive experiments are performed on benchmark instances from the literature. The results of the experiments are rather satisfactory, and indicate that our algorithm outperforms three recent algorithms based on evolutionary computation that have been reported to be rather effective for solving hard 3-SAT problems. 1 Introduction The satisfiability problem (SAT) is a paradigmatic NP-complete problem (Garey and Johnson, 1979) with relevant practical applications, like consistency check in expert system knowledge bases (Nguyen et al., 1985), asynchronous circuit synthesis (Gu and Puri, 19...