Very large-scale neighborhood search
Encyclopedia
In mathematical optimization, Neighborhood Search is a technique that tries to find good or near-optimal solutions to a mathematical optimization problem by repeatedly trying to improve the current solution by looking for a better solution which is in the neighborhood of the current solution. In that sense, the neighborhood of the current solution includes a possibly large number of solutions which are near to the current solution. Obviously, there is a degree of looseness in that definition in that the neighborhood might include just those solutions that require a single change from the current solution, or it might include the larger set of solutions that differ in two or more values from the current solution. A very large-scale neighborhood search is a local search algorithm
which makes use of a neighborhood definition
, which is large and possibly exponentially sized.
The resulting algorithms are often far superior to algorithms using small neighborhoods because the local improvements are larger. If the neighborhood searched is limited to just one or a very small number of changes from the current solution, then it is often very difficult to escape from local minima and additional meta-heuristic techniques may need to be used such as Simulated Annealing or Tabu Search to allow the search process to escape from a local minimum. In large neighborhood search techniques, the possible changes from one solution to its neighbor may allow tens or hundreds of values to change, and this means that the size of the neighborhood may itself be sufficient to allow the search process to avoid or escape local minima. As a result, it is often unnecessary to introduce additional meta-heuristic techniques.
Local search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
which makes use of a neighborhood definition
Neighbourhood (mathematics)
In topology and related areas of mathematics, a neighbourhood is one of the basic concepts in a topological space. Intuitively speaking, a neighbourhood of a point is a set containing the point where you can move that point some amount without leaving the set.This concept is closely related to the...
, which is large and possibly exponentially sized.
The resulting algorithms are often far superior to algorithms using small neighborhoods because the local improvements are larger. If the neighborhood searched is limited to just one or a very small number of changes from the current solution, then it is often very difficult to escape from local minima and additional meta-heuristic techniques may need to be used such as Simulated Annealing or Tabu Search to allow the search process to escape from a local minimum. In large neighborhood search techniques, the possible changes from one solution to its neighbor may allow tens or hundreds of values to change, and this means that the size of the neighborhood may itself be sufficient to allow the search process to avoid or escape local minima. As a result, it is often unnecessary to introduce additional meta-heuristic techniques.