✦ScienexySCIENCE KNOWLEDGE LIBRARY
Science reference · SCI-CS-003-040

Local Search and Optimization Algorithms

Local search algorithms improve a candidate solution by exploring nearby alternatives, often without storing complete paths from the initial state.

Optimization Objective: x* = arg minₓ f(x) (for a minimization problem)

Explanation

Local search is a family of algorithms used for optimization problems in which the objective is to find a state with a high-quality value. Instead of maintaining a complete search tree, a local search algorithm typically keeps one or a small number of candidate states and explores neighboring alternatives. Hill climbing moves to a neighboring state with a better evaluation value. Simulated annealing sometimes accepts a worse move to escape local optima. Local beam search maintains multiple candidate states and selects promising successors. Genetic algorithms use a population of candidate solutions and apply selection, crossover, and mutation. Local search is useful for problems with very large or continuous state spaces, where systematic exploration is impractical. However, algorithms can become trapped in local optima, plateaus, or ridges. Random restarts, controlled randomness, and population-based methods can help address some of these difficulties. Local search often provides approximate solutions when finding a guaranteed global optimum is too expensive or impossible within available resources.

Variables

SymbolMeaning

x

A candidate solution or state.

f(x)

The objective function that measures the quality or cost of a candidate solution.

x*

A solution that minimizes the objective function.

Neighbor

A candidate solution reachable through a permitted local change.

Example or application

Consider a timetable optimization problem. A candidate timetable is evaluated using a penalty score for overlapping classes and inconvenient schedules. A local search algorithm makes small changes, such as moving one class to another time slot, and keeps changes that improve the score.

Text

Local search focuses on finding a good or optimal state rather than constructing a path through every intermediate state. It repeatedly evaluates neighboring candidates and moves according to an optimization strategy.

Key Points

  • Local search focuses on candidate states and their quality.

  • It usually does not need to store the complete search path.

  • Hill climbing, simulated annealing, and genetic algorithms are common optimization approaches.

  • Local optima can prevent simple algorithms from reaching the global optimum.

  • Randomness and multiple candidate solutions can improve exploration.

Applications

  • Timetable and staff scheduling

  • Traveling Salesperson Problem approximations

  • Machine-learning parameter optimization

  • Engineering design

  • Resource allocation

Learning Outcomes

  • Explain the basic idea of local search.

  • Distinguish local and global optima.

  • Identify common local search and optimization methods.

Practice Questions

  • How does local search differ from systematic tree search?

  • What is a local optimum?

  • How can simulated annealing help escape a local optimum?

Related Concepts

  • Hill Climbing

  • Simulated Annealing

  • Genetic Algorithms

  • Objective Functions

  • Optimization

Common Mistakes

  • Assuming a local optimum is always a global optimum.

  • Confusing the objective function with the search strategy.

  • Assuming every local search method guarantees the best possible solution.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, local search algorithms.
  • Michalewicz, Z. and Fogel, D. B. How to Solve It: Modern Heuristics.

Suggest a correction or source · More in Artificial Intelligence & Machine Learning