Remember that next week, Wednesday's lecture will be replaced by a makeup
lecture on Friday February 9.
When discussing local search, children found by expansion are typically called neighbors. The set of all neighbors is called the moveset. Ties are typically broken randomlychoose a random initial state
while not termination-condition do
expand current state to find its children
evaluate the h value of each child state
let new current state be child with lowest h value
The termination condition can be any of the following: a goal state
is found (h = 0), no state in the moveset has a strictly better
h
value, or a time limit has been reached.
One critical choice in designing a search algorithm, whether local or global, is how to define the moveset. Here, we will define the neighbors of a truth assignment to be the states reachable by flipping the value of a single variable in the original (i.e. parent) assignment. So in words the algorithm is "Flip the value of one variable whose flipping results in the highest number of satisfied clauses."
This algorithm is called GSAT and is due to Bart Selman, Hector Levesque, and David Mitchell (1992).
Importantly, we always flip a variable even if no improvement is possible. In this case, we choose a variable that yields the least possible deterioration. If two or more variables are equally good to flip, we choose one randomly.
For example, suppose we want to satisfy the sentence (A v C)
& (-A v C) & (B v -C) and we start with the all-false
truth assignment. Then GSAT proceeds as follows (example due to Selman):
| A | B | C | A v C | -A v C | B v -C | h |
| F | F | F | F | T | T | 1 |
| F | F | T | T | T | F | 1 |
| F | T | T | T | T | T | 0 |
We also need to specify a termination condition for GSAT. This will be either h = 0, or a fixed number maxflips of iterations has been exceeded. As a rule of thumb, we can take maxflips = O(n log n) where n is the number of variables.
An optimized implementation of GSAT does not re-evaluate the h value of each child of the current state at each iteration. Most of these values can be reused from previous iterations. Good implementations of GSAT in C achieve over 100 000 flips per second on a standard workstation.
GSAT is a sound but not complete algorithm. If it terminates with h = 0, we have indeed found a satisfying assignment. On the other hand, if it terminates with h > 0, we cannot say whether or not the sentence is satisfiable. In practice, we run the algorithm again with a fresh random starting assignment.
Intuitively, with perfect guidance GSAT would always proceed to a solution
in at most n steps. In practice, GSAT proceeds to a candidate
solution with most clauses satisfied (h small) in O(n)
steps and then spends its remaining steps "bouncing around" trying to achieve
h
= 0.
Note that a global optimum may be a plateau and therefore not a strict local optimum.
In some applications of local search, the best achievable value of h is unknown, so a local search algorithm can never know when a global optimum has been achieved. With GSAT, if we achieve h = 0 we know this is optimal, but if we reach a local optimum or plateau with h > 0, we do not know whether it is a global optimum.
In search spaces with many dimensions, i.e. where each state has many neighbors, strict local optima tend to be rare compared to plateaus.
The general local search algorithm, and GSAT in particular, do not automatically get stuck on plateaus or local optima, because they always take a step away from the current state, even if the step is not an improvement. However GSAT can get stuck moving back and forth on a plateau consisting of two states, for example.
GSAT performs remarkably well in practice. It is exponentially
faster than the Davis-Putnam-Loveland procedure and hence capable of solving
problems many times larger, up to 600 variables or more in a few hours.
Specifically, the simulated annealing algorithm of Metropolis et al. (1953) and Kirkpatrick et al. (1982) is:
In this algorithm T is called the temperature parameter. Moving to the randomly chosen neighbor is certain if the neighbor is an improvement. Otherwise, the probability p of moving is higher for larger T and lower for larger absolute value of delta. At high temperatures where T >> |delta|, almost all moves are taken, while as T tends towards 0 from above, the probability of moving tends to zero for any given delta.choose a random initial state
while not termination-condition do
pick a random neighbor of the current state
let delta be the improvement in the h function
if delta > 0 then
let new current state be neighbor
else with probability p = e-|delta/T|
let new current state be neighbor
Simulated annealing was invented based on a metaphor from physics, but no one has succeeded in making the relationship precise. All that can be proved is that if T tends to zero exponentially slowly, then simulated annealing will converge to a global optimum. Unfortunately, all that this result really says is that with time proportional to the number of states, a random walk will eventually visit all states, and can be biased to remain longer in better states.
With the right cooling schedule chosen empirically, simulated annealing
outperforms GSAT.
This algorithm is called Walksat. Note that at each step, the randomly chosen clause is satisfied, but other clauses may become unsatisfied.choose a random initial truth assignment
while not termination condition do
randomly choose an unsatisfied clause
flip one variable of this clause as follows:
with fixed probability p
select the variable randomly
or, with probability 1-p:
select the variable greedily, i.e. select
the variable that yields the best h value
The parameter p is called the "mixing probability" and determined approximately by experiment for a given class of CNF formulas. For random hard 3SAT problems p = 0.5 works well.
Walksat is the best known algorithm for 3SAT. It outperforms simulated
annealing and is capable of solving problems with around 2000 variables
in a few hours.