In: Computer Science
Local search:
Local search is an optimizing algorithm to find the optimal solution of that problem more quickly. In local search first we need to define the neighborhood structure of the solution and moving from a current solution to a solution which is an improvement in the objective function. Hill climbing, simulated annealing, tabu search are some of the local search algorithms.
Problems of local searches:
1. Local search is a heuristic method for solving optimized problems. It is a rule of thumb or judgmental technique that leads to a solution some of the time but provides no guarantee for success. It may in fact end in failure.
2. When exhaustive search is impractical, it is necessary to compromise for a constrained search which eliminates many paths but offers the promise of success some of the time. Here success may be considered to be finding an optimal solution a fair proposition of the time or just finding good solution much of the time.
3. Local search can return a correct solution even if it is interrupted at any time before it ends. These algorithms are incomplete algorithms because the search may stop even if the best solution found by the search is not optional.
4. Local search methods do not systematically search the whole space, but they are designed to find solutions quickly and average.
5. They operate using a single state or a small number of states and explore the neighbours of that state. They usually don’t store the path.
6. Hill climbing is an example for local search. In this , at each point in the search path, a successor node that appears to lead most quickly to the top of the hill is selected for exploration. This method requires that some information be available with which to evaluate and order the most promising choices. The path that appears most promising is chosen and no further reference to the parent or other children is retained. It suffers from some serious drawbacks when this is not the case.
7. Potential problem types named after certain terrestrial anomalies are the foothill, ridge and plateau traps. The foothill trap results when local maxima or peaks are found. In this case the children all have less promising goal distances than the parent nose. The search is essentially trapped at the local node with no indication of goal direction. Then only way to remedy this problem is to try moving in some arbitrary direction a few generations in the hope that the real goal direction will become evident, back tracing to an ancestor node and trying a secondary path choice.
8. Local search algorithms do not guarantee that a solution will be found, even if one exists. So they are not able to point out that no solution exists.
9. These algorithms works for pure optimized problems. That is one where all the nodes can give a solution, but the target is to find the best solution at the earliest.