local search
In plain wordsA family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch.
A class of search and optimization methods that work on complete candidate solutions, moving from the current solution to a neighbor defined by a small change — flipping one variable, swapping two cities in a tour, reassigning one task — guided by an objective function. Because they keep only the current state (or a few), they need little memory and scale to very large problems, but they are incomplete: they cannot prove that no solution exists or that the one found is optimal. Members include hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak., simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops., tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends., the min-conflicts heuristic for constraint satisfactionconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., GSAT and WalkSAT for SATBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., and 2-opt and Lin–Kernighan moves for the traveling salesman problem; population-based metaheuristicsmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one. combine local search with recombination.
Origin
Neighborhood-improvement methods for the traveling salesman problem date from G. A. Croes's 2-opt (1958) and Shen Lin and Brian Kernighan's 1973 algorithm. In AI, the min-conflicts heuristic (Steven Minton and colleagues, 1990) and GSAT (Bart Selman, Hector Levesque and David Mitchell, 1992) showed local search solving constraint and SAT problems far larger than systematic methods could handle.
Related
- hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak.
- simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops.
- tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends.
- metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one.
- constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes.
- Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions.
- state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
Sources
- Selman, B., Levesque, H. & Mitchell, D. (1992). A New Method for Solving Hard Satisfiability Problems. Proceedings of AAAI-92, 440–446.
- Hoos, H. H. & Stützle, T. (2004). Stochastic Local Search: Foundations and Applications. Morgan Kaufmann.
Mentioned in
constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., hill climbinghill climbing, n.: A simple search method that keeps making whichever small change improves things, like climbing in fog by always stepping uphill — which can leave it stuck on a small hill instead of the highest peak., simulated annealingsimulated annealing, n.: An optimization method inspired by slowly cooling metal: early on it sometimes accepts worse solutions, to escape dead ends, and becomes pickier as a 'temperature' setting gradually drops., traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added., ant colony optimizationant colony optimization, n.: A method for finding good routes and schedules inspired by how ants find short paths to food: simulated ants leave 'scent' on good paths, which attracts other ants, so the best routes gradually stand out., metaheuristicmetaheuristic, n.: A general-purpose strategy for finding good answers to hard problems, such as imitating evolution or cooling metal, that can be adapted to many different problems instead of being designed for just one., tabu searchtabu search, n.: A search method that improves an answer by small changes while keeping a short memory of recent moves and forbidding their reversal for a while, so it does not circle back to the same dead ends.