This Paper Offers a Parallel Genetic Algorithm Solution to the Satisfiability Problem. It Combines Components of the Davis-Putnam Method and Genetic Algorithms for the Solution. This Solution is Useful in the Areas of Theorem Proving, Constraint Satisfaction Programming, and VLSI Design. the Algorithm is Implemented and Run on a Paragon. the Results Show Performance Improvement by Increasing the Number of Nodes. Two Parallel Methods Are Compared: One that Implements Interprocessor Communication and One that Does Not. the Results Show Performance Improvement with the Method that Uses Interprocessor Communication.
N. Nemer-Preece and R. W. Wilkerson, "Parallel Genetic Algorithm to Solve the Satisfiability Problem," Proceedings of the ACM Symposium on Applied Computing, pp. 23 - 28, Association for Computing Machinery, Feb 1998.
The definitive version is available at https://doi.org/10.1145/330560.330565
Keywords and Phrases
David-Putnam method; Genetic algorithms; Model generation; Parallel processing; Satisfiability problem
Article - Conference proceedings
© 2023 Association for Computing Machinery, All rights reserved.
27 Feb 1998