The general framework for local search is:
choose an 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
Here h is the heuristic value of a state, similar to h as used for A*. The goal is to find a state with h = 0.
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 we reach a time limit, or a limit on the number of moves.
If the algorithm terminates but has not found a goal state, then we
can restart with a different initial state.
Often the most 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).
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 |
Note that we move from the state in line 1 to the state in line 2
even though this move does not improve the h value.
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.
We need to specify a termination condition for GSAT. This will be either h = 0, or that 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.
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.
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 1000 000 flips per second on a
standard workstation.
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 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 DPLL procedure and hence capable of solving problems
many times larger, up to 600 variables or more in an hour.
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 (those with the ratio of clauses to variables around 4.25) p = 0.5 works well. For 3SAT formulas with more structure, as generated in many applications, slightly more greediness, i.e. p < 0.5, is often better.
Because of its random walk component, Walksat is less likely than GSAT to become stuck in the region around a local optimum. Therefore, it is more likely to find a solution without any restarts and the termination condition, which says when to restart with a new random assignment, should be more stringent. Empirically, restarting after O(n2) flips, where n is the number of variables, 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 an hour.