Local search (optimization)

The local search is a general term for a number of metaheuristic search techniques in combinatorial optimization. The procedures are used in many variations for complex optimization problems to be solved approximately (eg the problem of a Salesman ). The basic principle is to be found starting from a given starting solution a better solution by a better solution in the neighborhood under consideration is found by a local change of the current solution.

Formal definition

An instance of a combinatorial optimization problem is a pair, wherein the amount refers to the set of all possible solutions and the function of assigning a cost value to each solution. The aim of the optimization, it is (at a minimization problem ), to find a solution so as to apply to all. The local search proceeds as follows:

The exact nature of local search is determined by how an initial solution is generated (eg, randomly generated, or by a construction heuristic ) as the neighborhood term is defined and how the abort conditions are fixed. These definitions are specific problems in most cases. In the following, some examples will be called for neighborhood functions:

• In the K -Opt heuristics for the traveling salesman problem, two solutions are (in this case round trips ) adjacent if the other tour can be constructed by removing edges and addition of other edges in the tour.
• In integer linear programs, two solutions may be adjacent when a certain set of variables having the same value in the two solutions. A possible local search strategy here is to fix these variables on the common value and solve the remaining problem accurately.

Algorithms

• Simulated cooling
• Tabu Search