Header menu link for other important links
X
3-SAT using island-based genetic algorithm
S.M.Z. Mohammed, A.T. Khader,
Published in Institute of Electrical Engineers of Japan
2016
Volume: 136
   
Issue: 12
Pages: 1694 - 1698
Abstract
SAT problem, also known as a three conjunctive normal form (3-CNF), is an expression where every clause consists of exactly three literals but with the unrestricted number of literals and clauses. The 3-SAT problem is known to be an NP-hard and very difficult to solve. Where to solve the 3-SAT is to find an assignment of true or false to each of the literals in the clauses such that 3-SAT expression is evaluated to true. This study implemented the island model genetic algorithm (Island-based GA) to solve the 3-SAT problem. Hence, the solution involves the novel use of Island-based GA to improve the performance of solving 3-SAT problem. The benchmark SAT problems of four suits (URSAT1, URSAT2, URSAT3, and URSAT4) in SATLIB were used to test the performance of the Island-based GA and were compared with MAEA-SAT and Standard GA (SGA). The Island-based GA obtained good results and performance in solving large-scale SAT problems. © 2016 The Institute of Electrical Engineers of Japan.
About the journal
JournalIEEJ Transactions on Electronics, Information and Systems
PublisherInstitute of Electrical Engineers of Japan
ISSN03854221