Local search (constraint satisfaction)

In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms typically modify the value of a variable in an assignment at each step. The new assignment is close to the previous one in the space of assignment, hence the name local search.

All local search algorithms use a function that evaluates the quality of assignment, for example the number of constraints violated by the assignment. This amount is called the cost of the assignment. The aim of local search is that of finding an assignment of minimal cost, which is a solution if any exists.

Two classes of local search algorithms exist. The first one is that of greedy or non-randomized algorithms. These algorithms proceed by changing the current assignment by always trying to decrease (or at least, non-increase) its cost. The main problem of these algorithms is the possible presence of plateaus, which are regions of the space of assignments where no local move decreases cost. The second class of local search algorithm have been invented to solve this problem. They escape these plateaus by doing random moves, and are called randomized local search algorithms.

The most basic form of local search is based on choosing the change that maximally decreases the cost of the solution. This method, called hill climbing, proceeds as follows: first, a random assignment is chosen; then, a value is changed so as to maximally improve the quality of the resulting assignment. If no solution has been found after a given number of changes, a new random assignment is selected. Hill climbing algorithms can only escape a plateau by doing changes that do not change the quality of the assignment. As a result, they can be stuck in a plateau where the quality of assignment has a local maxima.

GSAT (greedy sat) was the first local search algorithm for satisfiability, and is a form of hill climbing.

A method for escaping from a local minimum is that of using a weighted sum of violated constraints as a measure of cost, and changing some weights when no improving move is available. More precisely, if no change reduces the cost of the assignment, the algorithm increases the weight of constraints violated by the current assignment.

This way, every move that would not otherwise change the cost of the solution decreases it. Moreover, the weight of constraints that remain violated for a large number of moves keeps increasing. Therefore, during a number of moves not satisfying a constraint, the cost of moves to assignments satisfying that constraint keeps increasing.

...
Wikipedia