Local search

The local search is a generic term for a number of metaheuristic search techniques of combinatorial optimization . The methods are used in many variations to approximately solve complicated optimization problems (e.g. the traveling salesman problem ). The basic principle is to find a better solution based on a given starting solution by finding a better solution from the neighborhood under consideration by locally changing the current solution.

Formal definition

An instance of a combinatorial optimization problem is a pair in which the set denotes the set of all possible solutions and the function assigns a cost value to each solution. The aim of optimization is (in the case of a minimization problem) to find a solution so that applies to all . The local search works as follows: ${\displaystyle (L,f)}$ ${\displaystyle L}$ ${\displaystyle f\colon L\rightarrow \mathbb {R} }$ ${\displaystyle i\in L}$ ${\displaystyle f(i)\leq f(u)}$ ${\displaystyle u\in L}$

1. Determine a starting solution . ${\displaystyle i\in L}$
2. Define a neighborhood of too "similar" solutions. ${\displaystyle i}$
3. Search this neighborhood or part of it and determine the best solution.

The exact type of local search is determined by how a starting solution is generated (e.g. randomly generated or by a construction heuristic), how the concept of neighborhood is defined and how the termination conditions are set. These definitions are usually problem-specific. Some examples of neighborhood functions are given below:

• With the K-Opt heuristics for the problem of the traveling salesman , two solutions (in this case round trips) are adjacent if the other tour can be constructed by removing edges and adding other edges in one tour. ${\displaystyle k}$ ${\displaystyle k}$
• In the case of integer linear programs , two solutions can be adjacent if a certain set of variables in both solutions has the same value. A possible local search strategy here is to fix these variables on the common value and to solve the rest of the problem exactly.

Algorithms

• Simulated cooling
• Taboo Search

literature

• Local Search in Combinatorial Optimization, Emile Aarts and Jan Karel Lenstra, John Wiley & Sons, 1997, ISBN 0471948225

Individual evidence

1. ↑ Juraj Hromkovic, Theoretical Computer Science : p. 279