Title :
Solving the satisfiability problem by a parallel cellular genetic algorithm
Author :
Folino, Gianluigi ; Pizzuti, Clara ; Spezzano, Giandomenico
Author_Institution :
Calabria Univ., Italy
Abstract :
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
Keywords :
cellular automata; computability; genetic algorithms; parallel algorithms; parallel machines; search problems; CS-2 parallel machine; chromosomes; diffusion model; evolutionary method; genetic operators; global search; local search; local selective generation; parallel cellular genetic algorithm; parallel implementation; random initial population; satisfiability problem; strings; two dimensional cellular automaton; unsatisfied clauses; Artificial intelligence; Calculus; Circuit synthesis; Genetic algorithms; Logic; NP-complete problem; Parallel machines; Random number generation;
Conference_Titel :
Euromicro Conference, 1998. Proceedings. 24th
Conference_Location :
Vasteras
Print_ISBN :
0-8186-8646-4
DOI :
10.1109/EURMIC.1998.708093
