Local search

Local Search is an algorithmic method that is commonly used for solving computationally hard problem such as the traveling salesman problem (TSP). Given a (typically very large) space of candidate solutions of a given problem instance and a neighbourhood relation on this space, the basic principle underlying local search is to start from an initial candidate solution and then to iteratively moves from one candidate solution to one of the candidate solution from its direct neighbourhood, based on local information, 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.