Greedy local search search methods are widely used to solve challenging computational problems. One of the earliest applications of local search was to find good solutions for the traveling salesman problem (TSP). In this problem, the goal is to find the shortest path for visiting a given set of cities. The TSP is prototypical of a large class of computational problems for which it is widely believed that no efficient (i.e., polynomial time) ALGORITHM exists. Technically speaking, it is an NP-hard optimization problem (Cook 1971; Garey and Johnson 1979; Papadimitriou and Steiglitz 1982). A local search method for the TSP proceeds as follows: start with an arbitrary path that visits all cities, such a path will define an order in which the cities are to be visited. Subsequently, one makes small ("local") changes to the path to try to find a shorter one. An example of such a local change is to swap the position of two cities on the tour. One continues making such changes until no swap leads to a shorter path. Lin (1965) and Lin and Kernighan (1973) show that such a simple procedure, with only a slightly more complex local change, leads to solutions that are surprisingly close to the shortest possible path.

The basic local search framework
allows for several variations. For example, there is the choice
of the initial solution, the nature of the local changes considered,
and the manner in which the actual improvement of the current solution
is selected. Lin and Kernighan found that multiple runs with different
random initial paths lead to the best solutions. Somewhat surprisingly,
starting with good initial paths did not necessarily lead to better
final solutions. The reason for this appears to be that the local
search mechanism itself is powerful enough to improve on the initial
solutions -- often quickly giving better solutions than those
generated using other methods. Choosing the best set of local changes
to be considered generally requires an empirical comparison of various
kinds of local modifications that are feasible. Another issue is
that of how to select the actual improvement to be made to the current
solution. The two extremes are *first-improvement* (also
called "hill- climbing"), in which any favorable
change is accepted, and *steepest-descent,* in which the *best* possible local
improvement is selected at each step. Steepest-descent is sometimes
referred to as *greedy* local search, but this term is also
used to refer to local search in general.

A local search method does not necessarily
reach a global optimum because the algorithm terminates when it
reaches a state where no further improvement can be found. Such
states are referred to as *local optima.* In 1983, Kirkpatrick, Gelatt,
and Vecchi introduced a technique for escaping from such local optima.
The idea is to allow the algorithm to make occasional changes that
do not improve the current solution, that is, changes that lead
to equally good or possibly inferior solutions. Intuitively speaking,
these nonimproving moves can be viewed as injecting *noise* into
the local search process. Kirkpatrick, Gelatt, and Vecchi referred to
their method as *simulated annealing,* because it was inspired
by the annealing technique used to reach low energy states in glasses
and metals. The amount of "noise" introduced is
controlled with a parameter, called the temperature *T*.
Higher values of *T* correspond to more noise. The search
starts off at a high temperature, which is slowly lowered during
the search in order to reach increasingly better solutions.

Another effective way of escaping
from local minima is the *
tabu search* method (Glover 1989). During the search, the algorithm
maintains a "tabu" list containing the last *L* changes,
where *L* is a constant. The local search method is prevented
from making a change that is currently on the tabu list. With the
appropriate choice of *L*, this methods often forces the search
to make upward (nonimproving) changes, again introducing noise into
the search.

Genetic algorithms can also be viewed as performing a form of local search (Holland 1975). In this case, the search process proceeds in parallel. Solutions are selected based on their "fitness" (i.e., solution quality) from an evolving population of candidates. Noise is introduced in the search process via random mutations (see EVOLUTIONARY COMPUTATION).

A recent new area of application
for local search methods is in solving NP-complete *decision
problems,* such as the Boolean satisfiability (SAT) problem.
An instance of SAT is a logical expression over a set of Boolean
variables. An example expression is "(*a* or (not *b*))
and ((not *a*) or (not *c*))." The formula
has *a, b,* and *c* as Boolean variables. The satisfiability problem
is to find an assignment to the Boolean variables such that the
various parts of the logical expression are simultaneously satisfied.
That is, the overall expression should evaluate to "true." In
our example, setting *a* to "true," *b* to "true," and *c* to "false" satisfies
the formula. Finding a satisfying assignment for arbitrary formulas
is a computationally difficult task (Cook 1971). Note that the obvious algorithm
would enumerate all *2 ^{N}* Boolean
truth assignments, where

An important difference in applying
local search to decision problems, as opposed to optimization problems,
is that *near*-solutions are of no particular interest. For
decision problems, the goal is to find a solution that satisfies
all constraints of the problem under consideration (see also CONSTRAINT SATISFACTION and HEURISTIC SEARCH).
In practice, this means that, for example, GSAT and
related local search procedures spend most of their time satisfying
the last few remaining constraints. Recent work has shown that incorporating
random walk-style methods in the search process greatly enhances
the effectiveness of these procedures.

Since Lin and Kernighan's successful application of local search to the TSP , and the many subsequent enhancements to the local search method, local search techniques have proved so powerful and general that such procedures have become the method of choice for solving hard computational problems.

- COMPUTATIONAL COMPLEXITY
- GAME-PLAYING SYSTEMS
- INTELLIGENT AGENT ARCHITECTURE
- PROBLEM SOLVING
- RATIONAL DECISION MAKING

Cook, S. A. (1971). The complexity of theorem - proving procedures. Proc. STOC - 71, pp. 151-158.

Crawford, J. M., and L. D. Auton. (1993). Experimental results on the cross - over point in satisfiability problems. Proc. AAAI - 93, pp. 21-27.

Davis, M., G. Logemann, and D. Loveland. (1962). A machine program for theorem-proving. Comm. Assoc. for Comput. Mach. 5:394-397.

Davis, M., and H. Putnam. (1960). A computing procedure for quantification theory. J. of the ACM 7:201-215.

Garey, M. R., and D. S. Johnson. (1979). Computers and Intractability, A Guide to the Theory of NP-Completeness. New York: W. H. Freeman.

Glover, F. (1989) Tabu search -- part I. ORSA Journal on Computing 1(3):190-206.

Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press.

Kirkpatrick, S., C. D. Gelatt, and M. P. Vecchi. (1983). Optimization by simulated annealing. Science 220:671-680.

Kirkpatrick, S., and B. Selman. (1994). Critical behavior in the satisfiability of random Boolean expressions. Science 264:1297-1301.

Lin, S. (1965). Computer solutions of the traveling salesman problem. BSTJ 44(10):2245-2269.

Lin, S., and B. W. Kernighan. (1973). An effective heuristic for the traveling - salesman problem. Oper. Res. 21:498-516.

Minton, S., M. Johnston, A. B. Philips, and P. Laird. (1992). Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence 58:161-205.

Mitchell, D., B. Selman, and H. J. Levesque. (1992). Hard and easy distributions of SAT problems. Proc. AAAI - 92, pp. 459-465.

Papadimitriou, C. H., and K. Steiglitz. (1982). Combinatorial Optimization. Englewood Cliffs, NJ: Prentice - Hall.

Selman, B., H. A. Kautz, and B. Cohen. (1994). Noise strategies for improving local search. Proc. AAAI - 94, pp. 337-343.

Selman, B., H. J. Levesque, and D. Mitchell. (1992). A new method for solving hard satisfiability problems. Proc. AAAI - 92, pp. 440-446.