Local Search Algorithm
Jump to navigation
Jump to search
A Local Search Algorithm is a search algorithm that moves from solution to solution in the space of candidate solutions until a solution deemed optimal is found or a time bound is elapsed.
- Context:
- It can range from being a Deterministic Local Search Algorithm to being a Stochastic Local Search Algorithm.
- Example(s):
- …
- See: Search Task, Approximation Algorithm, Greedy Hill-Climbing Algorithm, Candidate Solution, WalkSAT.
References
2016
- (Wikipedia, 2016) ⇒ http://wikipedia.org/wiki/Local_search_(optimization) Retrieved:2016-2-18.
- 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. Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.
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. Examples of local search algorithms are WalkSAT and the 2-opt algorithm for the Traveling Salesman Problem.
- 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. Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.
2010
- http://en.wikipedia.org/wiki/Local_search_%28optimization%29
- … Some problems where local search has been applied are:
- the vertex cover problem, in which a solution is a vertex cover of a graph, and the target is to find a solution with a minimal number of nodes;
- the travelling salesman problem, in which a solution is a cycle containing all nodes of the graph and the target is to minimize the total length of the cycle;
- the boolean satisfiability problem, in which a candidate solution is a truth assignment, and the target is to maximize the number of clauses satisfied by the assignment; in this case, the final solution is of use only if it satisfies all clauses.
- the nurse scheduling problem where a solution is an assignment of nurses to shifts which satisfies all established constraints.
- the k-medoid clustering problem and other related facility location problems for which local search offers the best known approximation ratios from a worst-case perespective.
- Most problems can be formulated in terms of search space and target in several different manners. For example, for the travelling salesman problem a solution can be a cycle and the criterion to maximize is a combination of the number of nodes and the length of the cycle. But a solution can also be a path, and being a cycle is part of the target.
- A local search algorithm starts from a candidate solution and then iteratively moves to a neighbor solution. This is only possible if a neighborhood relation is defined on the search space. As an example, the neighborhood of a vertex cover is another vertex cover only differing by one node. For boolean satisfiability, the neighbors of a truth assignment are usually the truth assignments only differing from it by the evaluation of a variable. The same problem may have multiple different neighborhoods defined on it; local optimization with neighborhoods that involve changing up to [math]\displaystyle{ k }[/math] components of the solution is often referred to as k-opt.
- … Some problems where local search has been applied are:
- http://en.wikipedia.org/wiki/Hill_climbing
2007
- (Michiels et al., 2007) ⇒ Wil Michiels, Emile H. L. Aarts, and Jan Korst. (2007). “Theoretical Aspects of Local Search." Springer. ISBN:3540358536
- BOOK OVERVIEW: Local search has been applied successfully to a diverse collection of optimization problems. It's appreciated for its basic conceptual foundation, its general applicability, and its power to serve as a source for new search paradigms. The typical characteristics of combinatorial optimization problems to which local search can be applied, its relation to complexity theory, and the combination with randomized search features have led to a wealth of interesting theoretical results. However, these results are scattered throughout the literature. This is the first book that presents a large collection of theoretical results in a consistent manner, thus providing the reader with a coherent overview of the achievements obtained so far, but also serving as a source of inspiration for the development of novel results in the challenging field of local search.