Local search (optimization)

In computer science, local search (LS) is a numerical, heuristic or metaheuric method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution that maximizes (or minimizes) a criterion among an objective function (criterion) among a number of candidate solutions. The set of all feasible solutions forms the search space. LS is based on the idea of iteratively moving from one solution to the next within a specific neighborhood of the initial solution in the search space. The definition of that neighborhood relation depends on the definition of the objective function, which is problem specific. This, along with the mechanism used to select a new neighbor at each iteration, are the main features that distinguish different local search algorithms from one another.

The basic principle is to find a better solution starting from a given initial one by making a local change to the current solution to find a better one within the neighborhood currently being considered. The process is repeated until no improvements - or only minor improvements - are achieved within a specified number of consecutive iterations, or until a specified runtime limit or an upper limit on the number of iterations is reached. LS algorithms typically find a local optimum and can in no way guarantee that they will locate the global optimum. They are widely applied to numerous hard computational problems, including problems from computer science (particularly artificial intelligence), mathematics, operations research, engineering, and bioinformatics.

LS methods and gradient descent have in common that both classes of algorithms are iterative methods for local optimization. The main difference, however, is that gradient descent requires the derivative of the objective function, whereas for local search, the objective function itself is sufficient.

Formal Definition

An instance of an optimization problem is a pair (S,f), where the set S denotes the set of all feasible solutions and the function f:S→ℝ assigns a quality value to each solution. The goal of optimization (in the case of a maximization problem) is to find a solution i∈S such that f(i)≥f(u) ∀u∈S holds. Such a solution is also referred to as a global optimum. In contrast, a solution i^ is called a local optimum if ∃ϵ>0 ∀u∈S: ∥u−i^∥<ϵ⇒f(i^)≥f(u) holds. Since max⁡f(u)=−min⁡−f(u), a minimization problem can easily be transformed into the maximization problem considered here. Thus, this does not constitute a restriction on the generality of the problem.

Description

Most problems can be formulated in terms of a search space and target in several different ways. For example, for the traveling salesman problem a solution can be a route visiting all cities and the goal is to find the shortest route. But a solution can also be a path, and being a cycle is part of the target.

A local search algorithm starts from a candidate solution and then iteratively moves to a neighboring solution; a neighborhood being the set of all potential solutions that differ from the current solution by the minimal possible extent. This requires a neighborhood relation to be defined on the search space. As an example, the neighborhood of vertex cover is another vertex cover only differing by one node. For Boolean satisfiability, the neighbors of a Boolean assignment are those that have a single variable in an opposite state. The same problem may have multiple distinct neighborhoods defined on it; local optimization with neighborhoods that involve changing up to k components of the solution is often referred to as k-opt.

Typically, every candidate solution has more than one neighbor solution; the choice of which one to select is taken using only information about the solutions in the neighborhood of the current assignment, hence the name local search. When the choice of the neighbor solution is done by taking the one locally maximizing the criterion, i.e.: a greedy search, the metaheuristic takes the name hill climbing. When no improving neighbors are present, local search is stuck at a locally optimal point. This local-optima problem can be cured by using restarts (repeated local search with different initial conditions), randomization, or more complex schemes based on iterations, like iterated local search, on memory, like reactive search optimization, on memory-less stochastic modifications, like simulated annealing.

Local search does not provide a guarantee that any given solution is optimal. The search can terminate after a given time bound or when the best solution found thus far has not improved in a given number of steps. Local search is an anytime algorithm; it can return a valid solution even if it's interrupted at any time after finding the first valid solution. Local search is typically an approximation or incomplete algorithm because the search may stop even if the current best solution found is not optimal. This can happen even if termination happens because the current best solution could not be improved, as the optimal solution can lie far from the neighborhood of the solutions crossed by the algorithm.

Schuurman & Southey propose three measures of effectiveness for local search (depth, mobility, and coverage):

They hypothesize that local search algorithms work well, not because they have some understanding of the search space but because they quickly move to promising regions, and explore the search space at low depths as quickly, broadly, and systematically as possible.

Examples

Some problems where local search has been applied are:

  1. The vertex cover problem, in which a solution is a vertex cover of a graph, and the target is to find a solution with a minimal number of nodes
  2. The traveling salesman problem, in which a solution is a cycle containing all nodes of the graph and the target is to minimize the total length of the cycle
  3. The Boolean satisfiability problem, in which a candidate solution is a truth assignment, and the target is to maximize the number of clauses satisfied by the assignment; in this case, the final solution is of use only if it satisfies all clauses
  4. The nurse scheduling problem where a solution is an assignment of nurses to shifts which satisfies all established constraints
  5. The k-medoid clustering problem and other related facility location problems for which local search offers the best known approximation ratios from a worst-case perspective
  6. The Hopfield Neural Networks problem involves finding stable configurations in Hopfield network.

See also

Local search is a sub-field of:

Fields within local search include:

Real-valued search-spaces

Several methods exist for performing local search of real-valued search-spaces:

References

  1. 1 2 Moscato, Pablo; Schaerf, Andrea (1998). Local Search Techniques for Scheduling Problems - A Tutorial. p. 3. Retrieved 2026-11-07.
  2. 1 2 Hromkovič, Juraj (2004). "Local Search". Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics. Texts in theoretical computer science. An EATCS series (Second edition, softcover reprint of the hardcover 2nd edition 2004 ed.). Berlin Heidelberg: Springer. pp. 189–208. ISBN 978-3-642-07909-2.
  3. ↑ Blum, Christian; Roli, Andrea (September 2003). "Metaheuristics in combinatorial optimization: Overview and conceptual comparison". ACM Computing Surveys. 35 (3): 268–308. doi:10.1145/937503.937505. ISSN 0360-0300.
  4. ↑ Bäck, Thomas; Hoffmeister, Frank; Schwefel, Hans-Paul (1991). "A Survey of Evolution Strategies". In Belew, Richard K. (ed.). Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA, USA: Morgan Kaufmann. pp. 2–9. ISBN 978-1-55860-208-3.
  5. ↑ Greenwald, Amy; Ewing, Eric (2025-02-24). "Local Search Methods for Discrete Optimization" (PDF). Retrieved 2026-11-10.
  6. ↑ D. Schuurmans and F. Southey. Local search characteristics of in- complete SAT procedures. AI J., 132(2):121–150, 2001.

Bibliography