Local search (optimization)

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution that maximizes a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed. Local search algorithms are widely applied to numerous hard computational problems, including problems from computer science (particularly artificial intelligence), mathematics, operations research, engineering, and bioinformatics. Examples of local search algorithms are WalkSAT, the 2-opt algorithm for the traveling salesman problem and the Metropolis–Hastings algorithm. While it is sometimes possible to substitute gradient descent for a local search algorithm, gradient descent is not in the same family: although it is an iterative method for local optimization, it relies on an objective function’s gradient rather than an explicit exploration of the solution space.

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution that maximizes a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed. Local search algorithms are widely applied to numerous hard computational problems, including problems from computer science (particularly artificial intelligence), mathematics, operations research, engineering, and bioinformatics. Examples of local search algorithms are WalkSAT, the 2-opt algorithm for the traveling salesman problem and the Metropolis–Hastings algorithm. While it is sometimes possible to substitute gradient descent for a local search algorithm, gradient descent is not in the same family: although it is an iterative method for local optimization, it relies on an objective function’s gradient rather than an explicit exploration of the solution space.

See also

Local search is a sub-field of: Metaheuristics Stochastic optimization Optimization Fields within local search include: Hill climbing Simulated annealing (suited for either local or global search) Tabu search Late acceptance hill climbing Reactive search optimization (combining machine learning and local search heuristics)

Real-valued search-spaces

Several methods exist for performing local search of real-valued search-spaces: Luus–Jaakola searches locally using a uniform distribution and an exponentially decreasing search-range. Random optimization searches locally using a normal distribution. Random search searches locally by sampling a hypersphere surrounding the current position. Pattern search takes steps along the axes of the search-space using exponentially decreasing step sizes.

Bibliography

Hoos, H.H. and Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann. Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k-Median and Facility Location Problems, SIAM Journal of Computing 33(3). Juraj Hromkovič: Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics (Springer) Wil Michiels, Emile Aarts, Jan Korst: Theoretical Aspects of Local Search (Springer)

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377433281 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.