| dbpprop:abstract
|
- In computer science, local search is a metaheuristic 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) until a solution deemed optimal is found or a time bound is elapsed. 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. 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 k components of the solution is often referred to as k-opt. Typically, every candidate solution has more than one neighbor solution; the choice of which one to move to is taken using only information about the solutions in the neighborhood of the current one, hence the name local search. When the choice of the neighbor solution is done by taking the one locally maximizing the criterion, the metaheuristic takes the name hill climbing. Termination of local search can be based on a time bound. Another common choice is to terminate when the best solution found by the algorithm has not been improved in a given number of steps. Local search algorithms are typically incomplete algorithms, as the search may stop even if the best solution found by the algorithm is not optimal. This can happen even if termination is due to the impossibility of improving the solution, as the optimal solution can lie far from the neighborhood of the solutions crossed by the algorithms. Local search algorithms are widely applied to numerous hard computational problems, including problems from computer science, mathematics, operations research, engineering, and bioinformatics. Examples of local search algorithm are WalkSAT and the 2-opt algorithm for the TSP. For specific problems it is possible to devise neighborhoods which are very large, possibly exponentially sized. If the best solution within the neighborhood can be found efficiently, such algorithms are referred to as very large-scale neighborhood search algorithms.
- Die lokale Suche ist ein Oberbegriff für eine Reihe von metaheuristischen Suchverfahren der kombinatorischen Optimierung. Die Verfahren werden in vielen Variationen dafür genutzt, schwere Optimierungsprobleme näherungsweise zu lösen. Das Grundprinzip besteht darin, ausgehend von einer gegebenen Startlösung alle ähnlichen Lösungen in einer geeignet definierten Nachbarschaft abzusuchen und von diesen die beste auszuwählen.
- Un algorithme de recherche locale part d'une solution candidate et la déplace de façon itérative vers une solution voisine. Cette méthode est applicable seulement si une notion de voisinage est définie sur l'espace de recherche. Par exemple, le voisinage d'un arbre recouvrant est un autre arbre recouvrant qui diffère seulement par un nœud. Pour le problème SAT, les voisins d'une bonne affectation sont habituellement les affectations qui diffèrent seulement par la valeur d'une variable. Le même problème peut avoir plusieurs définitions différentes de voisinage; l'optimisation locale avec des voisinages qui limitent les changements à k composantes de la solution est souvent appelée k-optimale Habituellement, chaque solution candidate a plus d'une solution voisine; le choix de celle vers laquelle se déplacer est pris en utilisant seulement l'information sur les solutions voisines de la solution courante, d'où le terme de recherche locale. Quand le choix de la solution voisine est fait uniquement en prenant celle qui maximise le critère, la métaheuristique prend le nom de hill climbing (escalade de colline). Le critère d'arrêt de la recherche locale peut être une limite en durée. Une autre possibilité est de s'arrêter quand la meilleure solution trouvée par l'algorithme n'a pas été améliorée depuis un nombre donné d'itérations. Les algorithmes de recherche locale sont des algorithmes sous-optimaux puisque la recherche peut s'arrêter alors que la meilleure solution trouvée par l'algorithme n'est pas la meilleure de l'espace de recherche. Cette situation peut se produire même si l'arrêt est provoqué par l'impossibilité d'améliorer la solution courante car la solution optimale peut se trouver loin du voisinage des solutions parcourues par l'algorithme. Les algorithmes de recherche locale sont largement utilisés dans les problèmes d'optimisation difficiles, tels que les problèmes informatiques, mathématiques, de recherche opérationnelle, d'ingénierie et de bio-informatique.
- 局所探索法（きょくしょたんさくほう、英: local search）は、アルゴリズムの一種である。逐次改善法（ちくじかいぜんほう）あるいは近傍探索法（きんぼうたんさくほう）ともいう。
- Алгоритмы локального поиска — группа алгоритмов, в которых поиск ведется только на основании текущего состояния, а ранее пройденные состояния не учитываются и не запоминаются. Основной целью поиска является не нахождение оптимального пути к целевой точке, а оптимизация некоторой целевой функции, поэтому задачи, решаемые подобными алгоритмами, называют задачами оптимизации. Для описания пространства состояний в таких задачах используют ландшафт пространства состояний, в этом представлении задача сводится к поиску состояния глобального максимума (или минумума) на данном ландшафте.
|
| rdfs:comment
|
- In computer science, local search is a metaheuristic 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) until a solution deemed optimal is found or a time bound is elapsed.
- Die lokale Suche ist ein Oberbegriff für eine Reihe von metaheuristischen Suchverfahren der kombinatorischen Optimierung. Die Verfahren werden in vielen Variationen dafür genutzt, schwere Optimierungsprobleme näherungsweise zu lösen. Das Grundprinzip besteht darin, ausgehend von einer gegebenen Startlösung alle ähnlichen Lösungen in einer geeignet definierten Nachbarschaft abzusuchen und von diesen die beste auszuwählen.
- Un algorithme de recherche locale part d'une solution candidate et la déplace de façon itérative vers une solution voisine. Cette méthode est applicable seulement si une notion de voisinage est définie sur l'espace de recherche. Par exemple, le voisinage d'un arbre recouvrant est un autre arbre recouvrant qui diffère seulement par un nœud. Pour le problème SAT, les voisins d'une bonne affectation sont habituellement les affectations qui diffèrent seulement par la valeur d'une variable.
- 局所探索法（きょくしょたんさくほう、英: local search）は、アルゴリズムの一種である。逐次改善法（ちくじかいぜんほう）あるいは近傍探索法（きんぼうたんさくほう）ともいう。
- Алгоритмы локального поиска — группа алгоритмов, в которых поиск ведется только на основании текущего состояния, а ранее пройденные состояния не учитываются и не запоминаются.
|
![[RDF Data]](/statics/sw-cube.png)
