The paper presents an evolutionary method for solving the satisfiability problem. It is based on a parallel cellular genetic algorithm which performs global search on a random initial population of individuals and local selective generation of new strings according to new defined genetic operators. The algorithm adopts a diffusion model of information among chromosomes by realizing a two dimensional cellular automaton. Global search is then specialized in local search by changing the assignment of a variable that leads to the greatest decrease in the total number of unsatisfied clauses. A parallel implementation of the algorithm has been realized on a CS-2 parallel machine. © 1998 IEEE.
Add the full text or supplementary notes for the publication here using Markdown formatting.