Local search
|
|
Local search is a metaheuristic that is commonly used for solving computationally hard problem such as the traveling salesman problem (TSP). Suppose we have a (typically very large) space of candidate solutions of a given problem instance and a neighborhood relation on this space. The basic principle underlying local search is to start from an initial candidate solution and then, iteratively, make moves from one candidate solution to another candidate solution from its direct neighbourhood. The moves are based on local information, and continue until a termination condition is met.
A typical example of a local search method is the 2-opt algorithm for the TSP.
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.