Local search improves a feasible solution by repeatedly examining nearby alternatives and moving to a better neighbor. It exploits the current neighborhood rather than exploring the entire search space, making it practical but vulnerable to local optima. section 2.2 section 6.1
Figure 1.10 Search dilemma—there is always a trade-off between branching out to new areas of the search space or focusing on an area with known good or elite solutions.
The exploration–exploitation dilemma contrasts branching into unvisited solutions with concentrating effort around known good solutions; local search emphasizes the latter. section 1.5
A basic local search follows this loop:
- Start with an initial feasible solution. section 6.1
- Generate a neighboring solution by applying one or more local modifications, or moves. section 6.1
- Replace the current solution only when the new solution is better, then repeat until a termination criterion is met. section 6.1
Choosing a resort restaurant
A traveler chooses a restaurant in the resort and considers only nearby options within the resort, rather than searching restaurants outside it or ordering online. Each move changes the current choice within that limited neighborhood. section 6.1
The neighborhood structure defines which small changes are allowed. Considering only one neighbor gives a narrow horizon; considering many alternatives costs more computation. Hill climbing is a greedy form that accepts only improving neighbors, so it can converge prematurely. section 6.1
Tabu search extends local search with adaptive memory, helping the trajectory move beyond local optimality by remembering recent moves or solutions. section 6.0 section 6.7
