Parallel hybrid method for SAT that couples genetic algorithms and local search

A parallel hybrid method for solving the satisfiability (SAT) problem that combines cellular genetic algorithms (GAs) and the random walk SAT (WSAT) s trategy of greedy SAT (GSAT) is presented. The method, called cellular gene tic WSAT (CGWSAT), uses a cellular GA to perform a global search from a ran dom initial population of candidate solutions and a local selective generat ion of new strings. Global search is then specialized in local search by ad opting the WSAT strategy. A main characteristic of the method is that it in directly provides a parallel implementation of WSAT when the probability of crossover is set to zero. CGWSAT has been implemented on a Meiko CS-2 para llel machine using a two-dimensional cellular automaton as a parallel compu tation model. The algorithm has been tested on randomly generated problems and some classes of problems from the DIMACS and SATLIB test set.