期刊名称：Journal of Computer Sciences and Applications
印刷版ISSN：2328-7268
电子版ISSN：2328-725X
出版年度：2015
卷号：3
期号：2
页码：33-39
DOI：10.12691/jcsa-3-2-3
语种：English
出版社：Science and Education Publishing
摘要：SAT-3 is an NP-complete problem for determining whether there exists a solution satisfying a given Boolean formula in the Conjunctive Normal Form, wherein each clause has at most three literals. Existing approaches of this problem take exponential time and are also memory inefficient. The work uses Genetic Algorithms for finding an optimal solution to this problem. The central idea is the intelligent exploitation of a random search used to solve optimization problems. The work explores previous works to direct the search into regions of better performance within the search space, thus reducing the time and space complexity. It thus establishes the ability of Genetic Algorithms for finding optimal solutions from a huge set of solutions. The work has been implemented and analyzed with satisfactory results.
