Local search

from Wikipedia, the free encyclopedia

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:

  1. Determine a starting solution .
  2. Define a neighborhood of too "similar" solutions.
  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.
  • 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.



  • 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