A new parallel hybrid method for solving the satisfiability problem that combines cellular genetic algorithms and the random walk (WSAT) strategy of GSAT is presented. The method, called CGWSAT, uses a cellular genetic algorithm to perform a global search on a random initial population of candidate solutions and a local selective generation of new strings. Global search is specialized in local search by adopting the WSAT strategy. CGWSAT has been implemented on a Meiko CS-2 parallel machine using a two-dimensional cellular automaton as parallel computation model. The algorithm has been tested on randomly generated problems and some classes of problems from the DIMACS test set.
Combining cellular genetic algorithms and local search for solving satisfiability problems
Folino G;Pizzuti C;Spezzano;
1998
Abstract
A new parallel hybrid method for solving the satisfiability problem that combines cellular genetic algorithms and the random walk (WSAT) strategy of GSAT is presented. The method, called CGWSAT, uses a cellular genetic algorithm to perform a global search on a random initial population of candidate solutions and a local selective generation of new strings. Global search is specialized in local search by adopting the WSAT strategy. CGWSAT has been implemented on a Meiko CS-2 parallel machine using a two-dimensional cellular automaton as parallel computation model. The algorithm has been tested on randomly generated problems and some classes of problems from the DIMACS test set.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
