Skip to content

Local Searches

  • A heuristic approach for finding solutions to optimization problems.
  • Works by iteratively improving a candidate solution.
  • Explores the "neighbourhood" of the current solution.
  • Aims to find better solutions nearby.

Core Components

Candidate Solution

  • The current "guess" for the best solution.

Neighbourhood

  • The set of possible solutions that are "close" to the current solution.
  • "Close" is defined based on the problem.

Objective Function

  • A function that evaluates the "quality" of a solution.
  • We want to maximize or minimize this function.
  • Example: The height of a mountain in an optimization problem.

Neighbourhood Exploration

  • The strategy for selecting which neighbour to examine next.

How Local Search Works

Algorithm Steps

  1. Start with a random candidate solution.
  2. Define a neighbourhood of possible solutions.
  3. Explore the neighbourhood of the current solution.
  4. If a better neighbour is found, update the current solution.
  5. Repeat steps 3 and 4 until a stopping criterion is met:
  6. Maximum iterations reached.
  7. No better neighbours found.

Key Characteristics

  1. Iterative Improvement

  2. Repeatedly refines the current solution.

  3. Neighbourhood Exploration

  4. Focuses on exploring solutions similar to the current one.

  5. Heuristic Nature

  6. Does not guarantee finding the global optimum.

  7. Aims for a good solution (local optimum) in a reasonable time.

  8. Problem-Specific

  9. The definition of "neighbourhood" and the evaluation function depend on the problem.

Examples of Local Search Algorithms