Genetic Algorithm Based Solution to SAT-3 Problem

Umme Aiman^1, and Nausheen Asrar¹

¹Department of Computer Science, Jamia Hamdard, New Delhi, India

Cite this paper:
Umme Aiman and Nausheen Asrar. Genetic Algorithm Based Solution to SAT-3 Problem. Journal of Computer Sciences and Applications. 2015; 3(2):33-39. doi: 10.12691/jcsa-3-2-3

Abstract

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.

Keywords:
NP complete problem genetic algorithm SAT-3 problem intraceability optimal solution

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]	David E. Goldberg, “Genetic Algorithm”, Pearson Education.
[2]	Barbara Kitchenham, (July 2003), “Procedures for Performing Systematic Reviews”, Keele University Technical Report TR/SE-0401 ISSN: 1353-7776 and NICTA Technical Report 0400011T.1
[3]	Drogoul, A., and Dubreuil, C. “A distributed approach to n-puzzle solving.” Proceedings of the Distributed Artificial Intelligence Workshop. 1993.
[4]	Harsh Bhasin and NehaSingla, (August 2012),” Genetic based Algorithm for N-Puzzle Problem”, International Journal of Computer Applications (0975-8887), Volume 51-No. 22.
[5]	Eric Angel, Romain Campigotto and Christian Laforest, Algorithms for the Vertex Cover Problem on Large Graphs.
[6]	Harsh Bhasin and Gitanjali, (2012), “Harnessing Genetic Algorithm for Vertex Cover Problem”, International Journal on Computer Science and Engineering (IJCSE), Vol. 1, Issue 2, pp. 218-223.
[7]	Naresh Kumar, Deepkiran Munjal, Modified Genetic Algorithm for Maximum Clique Problem, International Journal of Computer & Organization Trends-Volume 3 Issue 4-May 2013.
[8]	Harsh Bhasinand Rohan Mahajan, (2013),” Genetic Algorithms Based Solution To Maximum Clique Problem”||, International Journal of Computer Science and Engineering, Vol. 4.
[9]	Rong Long Wang, A genetic algorithm for subset sum problem, New Aspects in Neurocomputing: 10th European Symposium on Artificial Neural Networks 2002.
[10]	Harsh Bhasin and NehaSingla, (2012),” Modified Genetic Algorithms Based Solution to Subset Sum Problem”, (IJARAI) International Journal of Advanced Research in Artificial Intelligence, Vol. 1, No. 1.
[11]	Ling Zhao, Notes in Computer Science Volume 2883, 2003, pp 326-344, Tackling Post’s Correspondence Problem.
[12]	Harsh Bhasin and Nishant Gupta, (2012), “Randomized algorithm approach for solving PCP”, International Journal on Computer Science and Engineering (IJCSE),Vol. 4, Issue 1, pp. 106-113.
[13]	Genetic algorithms for the travelling salesman problem: A review of representations and operators-P Larrañaga, CMH Kuijpers, RH Murga, I Inza…-Artificial Intelligence …, 1999-Springer.
[14]	H Braun, On solving travelling salesman problems by genetic algorithms,-Parallel Problem Solving from Nature, 1991-Springer.
[15]	Lintao Zhang, Searching For Truth: Techniques For Satisfiability of Boolean Formulas, PhD Thesis, Princeton University, 2003.
[16]	Yogesh S. Mahajan, Zhaochui Fu and Sharad Malik, Zchaff 2004: An Efficient SAT Solver, Lecture Notes in Computer Science, 2005, Volume 3542/2005, 898.
[17]	www.personal.kent.edu/.../Algorithms/MyAlgorithms/.../npComplete.html
[18]	T.H. Cormen, C.E. Leiserson, and R.L. Rivest, “Introduction to Algorithms”, the MIT Press, Cambridge, Massachusetts, USA, 2009.
[19]	ww3.algorithmdesign.net/sample/ch13-np.pdf
[20]	www.cs.umd.edu/~gasarch/TOPICS/sat/SATtalk.pdf
[21]	“Solving 3-SAT”, (2012), Peter Maandag, Bachelor Thesis, Radboud University Nijmegen.
[22]	“Foundations of Artificial Intelligence, Satisfiability and Model Construction”, Wolfram Burgard, Bernhard Nebel and Martin Riedmiller.
[23]	“Implementing the Davis-Putnam Method”, (1999), Hantao Zhang (Dept. of Computer Science, The University of Iowa), Mark E. Stickel (Artificial Intelligence Center, U.S.A).
[24]	www.cs.ucc.ie/~dgb/courses/ai1/03-notes.pdf
[25]	Algorithms for Random 3-SAT, Abraham D. Flaxman, Microsoft Research
[26]	A. Mishchenko, An Introduction to Zero-Suppressed Binary Decision Diagrams. http://www.ee.pdx.edu/~alanmi/research/, 2001.
[27]	J. M. Howe and A. King, A Pearl on SAT Solving in Prolog, In Functional and Logic Programming, volume 6009 of Lecture Notes in Computer Science, pages 165-174, Springer, 2010
[28]	Norbert Manthey, Improving SAT Solvers Using State-of-the-Art Techniques, Thesis, Technische Universitt Dresden (2010).
[29]	Wikipedia-online encyclopedia.
[30]	http://www.stumptown.com/diss/chapter2.html