Local search solves hard optimization problems. The local search algorithm moves from solution to solutions before the optimal solution is reached or before the time bound elapses. Some of the problems where local searches are applied are :
01) Vertex cover problem where the solution is the vertex cover of a graph and the target is to find the solution with a minimal number of nodes.
02) In the traveling salesman problem, a solution is a cycle which contains all nodes of the graph where the target is to minimize the total length of the cycle.
03) In the Boolean satisfiability problem, a candidate solution is a truth assignment where the target is to maximize the number of clauses and the final solution is of use only when it satisfies all the clauses.
04) The nurse scheduling problem where the solution is an assignment of nurses to shifts with satisfied establishment constraints.
05) The K-medoid clustering problem and other related facility located problems for which local search offers the most valued approximation ratios.
The problems are formulated in terms of search space and target in various different manners. An instance being for the traveling salesman problem, a solution is a cycle and the basic criterion is to maximize a combination of number of nodes and the length of individual cycle. The solution can also be a path and the cycle is a path of the object. The local search algorithm begins from candidate solution and moves up to neighborhood solution. There is the possibility of this occurrence when the neighborhood relation is defined on the search space. The same problem may have multiple different neighborhoods which are defined on it. Basically, all candidate solutions have more than one neighbor solution. The choice of selecting one to move to is considered only for using information about the solutions in the neighborhood and this is termed “local search”.
When the choice of the neighborhood solution is performed locally, it maximizes the criterion and is termed as “hill climbing”. The termination of local search is based on a time band. Another popular choice is to terminate when the best solution found by the algorithm does not find favor in the given number of steps. It is generally observed that local search algorithms are incomplete algorithms as the search may stop even if the best solution found by the algorithm is not optimal. This happens whenever the termination is due to the impossibility of improving the solution since the optimal solution lies far from the neighborhood of solutions crossed by algorithms. Such local search algorithms are applied widely to various tough computational problems. Few examples of local search algorithms are Walk SAT and the 2-opt algorithm for TSP. For specific problems, it is advisable to create a neighborhood which is usually large and exponentially sized. This appears to be the best solution within the neighborhood as it can be found efficiently and are referred to as “large scale neighborhood search algorithm”.