Copyright © 1999 Massachusetts Institute of Technology
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 2N Boolean truth assignments, where N is the number of Boolean variables. The SAT problem is of particular interest to computer scientists because many other problems can be efficiently represented as Boolean satisfiability problems. The best traditional methods for solving the SAT problem are based on a systematic backtrack-style search procedure, called the Davis, Putnam, and Loveland procedure (Davis and Putnam 1960; Davis, Logemann, and Loveland 1962). These procedures can currently solve hard, randomly generated instances with up to four hundred variables (Mitchell, Selman, and Levesque 1992; Crawford and Auton 1993; Kirkpatrick and Selman 1994). In 1992, Selman, Livesque, and Mitchell showed that a greedy local search method, called GSAT , could solve instances with up to seven hundred variables. Recent improvements on the local search strategy enable us to solve instances with up to three thousand variables (Selman, Kautz, and Cohen 1994). The GSAT procedure starts with a randomly generated truth assignment. It then considers changing the truth value of one of the Boolean variables in order to satisfy more of the given logical expression. It keeps making those changes until a satisfying truth assignment is found or until the procedure reaches some preset maximum number of changes. When it reaches this maximum, GSAT restarts with a new initial random assignment. (For closely related work in the area of scheduling, see Minton et al. 1992.) One inherent limitation of local search procedures applied to decision problems is that they cannot be used to determine whether a logical expression is inconsistent, that is, no satisfying truth assignment exists. In practice, this means that one has to use model-based formulations, where solutions correspond to models or satisfying assignments.
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.
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.
Copyright © 1999 Massachusetts Institute of Technology