GOMEA-SAT: Applying Gene-pool Optimal Mixing Evolutionary Algorithm for the Boolean Satisfiability Problem

Abstract

This paper explains the process of creating and optimizing GOMEA-SAT. It is a new Genetic Algorithm designed to solve the Satisfiability Problem in a fashion which is competitive with currently existing stochastic search solvers. A closer look is taken into the Gene-pool Optimal Mixing Evolutionary Algorithm. This algorithm is adapted to solve the SAT Problem, then modified and extensively tested in order to acquire the most optimal results. A local search is then added into the GOMEA-SAT and the results are contrasted against known SAT Problem solving algorithms such as Walksat and GASAT. Finally, Linkage Tree GA is modified and used to determine if learning the structure of a SAT Problem could be a next step in improving its solutions.