Cellular memetic algorithms evaluated on SAT

Abstract

In this work, we study the behavior of several cellular memetic algorithms (cMAs) when solving the satisfiability problem (SAT). The proposed cMAs are the result of including hybridization techniques in dif- ferent structural ways into a canonical cellular genetic algorithm (cGA). Specifically, we hybridize our cGA with problem dependent recombination and mutation operators, as well as with three local search methods. Furthermore, two different policies for applying the local search methods are proposed. An adaptive fitness function (SAW), specifically designed for SAT, has been used for the evaluation of the individuals. Our conclusion is that the performance of the cGA is largely improved by these hybrid extensions. The accuracy and effciency of the resulting cMAs are even better than those of the best existing heuristics for SAT in many cases.