Close
Local search is a class of heuristics
for solving optimization problems that has been the focus of
much attention lately. Although there is no a-prori
guarantee on the solution quality or on the execution time (in most cases),
the solutions
found by local search in practice are of very good quality and
they are found relatively quickly.
Generally speaking, local search methods move iteratively through the solution set
of the problem.
Based on the current and maybe on the previous visited solutions, a new
solution is chosen. The choice of the new solution is restricted to those that are
somehow close to the one at hand
(in the neighborhood of the current
solution).
In their most basic versions, local search methods return the first local optimum found. They are equivalent to greedy algorithms and thereore typically end in polynomial time. More sophisticated heuristics (such as simulated annealing) allow the search to escape local optima, by moving to solutions that do not necessarily improve the value of the objective function. These heuristics may have variable running time, which is generally an option under the user's control.
In their most basic versions, local search methods return the first local optimum found. They are equivalent to greedy algorithms and thereore typically end in polynomial time. More sophisticated heuristics (such as simulated annealing) allow the search to escape local optima, by moving to solutions that do not necessarily improve the value of the objective function. These heuristics may have variable running time, which is generally an option under the user's control.