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.

Greedy algorithms

Hill climbing

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, proceed as follows: first, a random assignment is chosen; then, a value is changed in such 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.

Constraint weighting or breakout method

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.

Tabu search

A drawback of hill climbing with moves that do not decrease cost, is that it may cycle over assignments of the same cost. Tabu search overcomes this problem by maintained a list of "forbidden" assignments, called the tabu list. In particular, the tabu list typically contains the list of the last changes. More precisely, it contains the last variable/value such that the variable has been recently assigned to the value.

This list is updated every time the assignment is changed. If a variable is assigned to a value, the pair variable/value is added to the list, and the oldest pair is removed from it. This way, the list only contains the most recent assignments to a variable. If a variable/value pair is in the tabu list, changing the current assignment by setting the variable to the value is forbidden. The algorithm can only choose the best move among the ones that are not forbidden. This way, it cannot cycle over the same solution unless the number of moves in this cycle is larger than the length of the tabu list.

Random walk

A random walk algorithm sometimes moves like greedy algorithms but sometimes move randomly. They depend on a parameter $p$ , which is a real number between 0 and 1. At every move, with probability $p$ the algorithm prceed like a greedy algorithm, trying to maximally decreasing the cost of the assignment. With probability $1-p$ , however, the solution is changed in some other way, which involves some degree of randomness.

WalkSAT

The random move of WalkSAT is changing the value of a random variable of a random violated constraint. For propositional satisfiability of conjunctive normal form formulae, which is the original settings of this algorithm, every such a move changes the value of the variable from true to false or vice versa, and produce the satisfiability of the violated constraint. As for all random walk strategies, a random move is only done with a given probability, and a move maximally decreasing the cost is done otherwise.

Simulated annealing

The technique of simulated annealing is based on changing the probability of doing a random move over one that maximally decreasing the cost. In particular, the name originates from the strategy of decreasing the probability of doing random moves during the execution of the algorithm, thus virtually "freezing" the space of search.

In particular, if the improvement of cost $d$ of a move is negative (the move increases cost), this move is done with probability $e^{-d\cdot T}$ , where $T$ is real number. Since the probability of doing this move increases with $T$ , this paramter is called the temperature. Simulated annealing decreases this temperature over time, thus allowing more random moves at the beginning and less after time.

Reference

Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7.