Algorithm Performance on the Satisfiability Problem

Overview

Objectives/Goals The objective was the find an effective method to solve the Satisfiability problem. Methods/Materials Methods 1. Write the Clause Check subprogram 2. Write a program to generate random problems with the ability to regenerate problems 3. Write the Genetic algorithm 4. Write the GSAT algorithm 5. Write the Simulated Annealing algorithm 6. Write the Exhaustive algorithm 7. Make sure the algorithms run properly 8. Run a 100 clauses 10 variables problem with the Genetic algorithm, GSAT, and Simulated Annealing. Do this 10 times for each algorithm 9. Repeat step 8 for 200 clauses and 20 variables, 300 clauses and 30 variables, 400 clauses 40 variables, 500 clauses and 50 variables, 10 clauses and 10 variables, 30 clauses and 30 variables, 50 clauses and 50 variables, 42 clauses and 10 variables, 127 clauses and 30 variables, 212 clauses and 50 variables. 10. Record data and analyze which algorithm had a higher performance level in terms of states taken to achieve a solution, and number of clauses satisfied Materials 1 Computer Software: Microsoft Visual C++ Introductory Edition Compiler Microsoft Word Microsoft Excel Results The Hillclimbing algorithm performed worse, in terms of the number of clauses satisfied. The Genetic algorithm performed the worse, in terms of number of states taken to find a candidate. Conclusions/Discussion The Simulated Annealing Performed the best out of all algorithms

Competition history

• CSEF 2004 Mathematics & Software · Entry S1220

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2004 project