CSC396 - Project 2
Searching Neighborhoods

Assigned Feb 19th
Due Feb 28th 2pm

Overview

In this project, you will implement three local search algorithms and compare them using randomly generated Satisfiability problems.

Satisfiability

Satisfiability problems (SAT) were the first computational tasks shown to be NP-complete, i.e. problems that requires an exponential ammount of computing time to solve. If we have N propositions, each one can have the value of T or F, therefore the number of possible interpretations of the propositions is 2N. Many interesting problems in Computer Science turn out to be NP-complete, such as N-queens, graph coloring, and the traveling salesman problem. What's even more interesting is that every NP-complete problem can be reduced to any other one; solving just one will give us a solution to every one. It is not necessary for this assignment to understand NP-competeness, but you should at least see that SAT is not just about conjunctions and disjunctions in logic, but central to solving a number of open problems in computer science.

For this problem of the homework, we will examine two algorithms which try to solve SAT problems in a polynomial amount of time or less, and develop one of your own.

WalkSAT

First you will implement WalkSAT, a randomized and restarting hill-climbing search algorithm. 

for MAXTRIES times
    pick random starting assignment to be currentNode
    for MAXFLIPS times or clause is satisfied
        with probability p
            choose a random variable and flip it
        otherwise
            choose the neighbor which results in the highest score

You will need to tune the parameter p for these type of problems by running your code multiple times and selecting the value which performs the best.

Simulated Annealing

The second algorithm you will implement is Simulated Annealing. 

for MAXTRIES times
    pick random starting assignment to be currentNode
    initialize temperature T
    while T > stopping-epsilon
		choose a random neighbor newNode
		delta = eval(newNode) - eval(currentNode)
        if delta > 0
            currentNode = newNode
        otherwise
            with probability e ^ (delta / T)
                currentNode = newNode
        T *= decay

As for the temperature schedule used, we will begin with a temperature T. Each iteration of the algorithm we will reduce the temperature by a percentage amount, called decay. For instance, we could start our temperature at 100, and reduce it each time by 10%. Our schedule would then become 100, 90, 81, 72.9 ... . To stop our algorithm we specify a minimum temperature, such at 0.01, and return the best node found so far. Since each problem requires its own specific paramaters, you should tune the starting temperature and reduction percentage to best fit this 3SAT problem.

Personal Algorithm

For the third algorithm, you are free to implement a new method of your own devising to perform local search. This can be related to the two above algorithms, TABU search, or an original search method.

Base Code for ThreeCNF

In all three algorithms, your nodes will be instances of the ThreeCNF class provided for you, which stands for Conjunctive Normal Form. Neighbors are reached by flipping the truth value of one of the propositions. Your score, or value for each node, will be the number of satisfied clauses. The goal is to have all clauses of your sentence satisfied, the more clauses the better the node.

What to do

Write a program, in either Java or Python called either Satisfiable.java or satisfiable.py, which implements in a main method for WalkSAT, Simulated Annealing and your personal algorithm for 3SAT problems. Your program should not take any arguments, and when executed, it should run the following experiment. Use your program to solve randomly generated 3SAT problems of different sizes. There are two key parameters: N, the number of proposiional symbols, and C, the number of clauses. Investigate the effects of the C/N ratio on the execution time of your two algorithms. With N fixed at 20, record the average number of restarts and climbs used by WalkSAT for C/N from 1 to 10. Record the average number of steps taken and the average temperature for Simulated Annealing for C/N from 1 to 10. Do not consider instances when your algorithms do not find solutions. Also. for all three algorithms, record the number of times a solution is found. You should run your algorithms 20 times for each C/N ratio. Use N as the value of MAXTRIES and 5N as the value of MAXFLIPS.

What to turn in

You must turn in your program Satisfiable.java or satisfiable.py to your csc204 directory on cs.centenary.edu under the folder project2.

In a file project2_evaluation.txt, report on your results, the difficulty of 3SAT problems for different values of C/N, which algorithm you believe worked better for this problem and why. Also report on the values you selected as parameters for each algorithm and the tuning method you performed. Describe in detail your personal algorithm and why you believe it will perform well on local search problems.