Questions: Local Search Optimization

Question 1

A hill-climbing algorithm is applied to a scheduling problem and quickly converges to a solution. When evaluated, the solution is mediocre — far from optimal. What is the most likely explanation?

• A. Hill climbing is not designed for scheduling problems; a different algorithm class should have been used
• B. The algorithm terminated at a local optimum — a state better than all its neighbors but not the best state globally
• C. The neighborhood definition was too broad, causing the algorithm to skip over the global optimum
• D. The algorithm ran too many iterations and overfit to the initial starting state

Answer: (B)

Local optima are the fundamental limitation of hill climbing. The algorithm moves to better neighbors until no better neighbor exists, then stops — but this criterion only guarantees a local optimum, not a global one. In a landscape with many hills, hill climbing climbs to the top of whichever hill it starts on and declares victory, regardless of whether taller peaks exist elsewhere. This is not a bug in the implementation; it is a structural property of the greedy-local-improvement strategy. Random restarts and algorithms like simulated annealing exist specifically to address this.

Question 2

Simulated annealing outperforms hill climbing on a highly multimodal optimization landscape. Which feature of simulated annealing is responsible for this improvement?

• A. Simulated annealing evaluates more neighbors per step, giving it more options to improve
• B. Simulated annealing maintains a list of all previously visited states and avoids revisiting them
• C. Simulated annealing occasionally accepts moves to worse states, allowing escape from local optima
• D. Simulated annealing uses gradient information about the landscape to navigate toward the global optimum

Answer: (C)

The key innovation of simulated annealing over hill climbing is probabilistic acceptance of worse moves. At high 'temperature,' the algorithm accepts downhill moves frequently, allowing it to escape local optima basins and explore the landscape broadly. As temperature decreases, acceptance probability falls and the algorithm becomes increasingly greedy, settling into the best region found. Option B describes tabu search. Option D describes gradient-based methods, which are neither local search nor applicable to discrete combinatorial problems. Pure hill climbing never accepts worse moves, which is why it traps in local optima.

Question 3

Local search algorithms like hill climbing are incomplete: they may fail to find a solution even when one exists, because they can become trapped in states from which no better neighbor is reachable.

• T. True
• F. False

Answer: True

Completeness means an algorithm is guaranteed to find a solution if one exists. Hill climbing is incomplete because it terminates at local optima — states where all neighbors are worse — even if the global optimum exists elsewhere in the space. This is an intentional tradeoff: local search sacrifices completeness and optimality guarantees to handle problems too large for exhaustive methods. Algorithms that are complete (like BFS or A*) explore systematically but scale poorly to large state spaces.

Question 4

Because local search primarily maintains a single current state rather than a search tree, it can seldom be used to solve problems with millions of possible states.

• T. True
• F. False

Answer: False

This is exactly backwards. The key advantage of local search is that maintaining only a single state makes it memory-efficient and scalable to massive state spaces where tree-based search methods would be completely intractable. A scheduling problem with thousands of courses has a combinatorially enormous state space — exponentially too large for systematic search — but local search can operate on it by evaluating only the current state and its neighbors. The tradeoff is that local search is not complete or optimal, but it can produce good solutions quickly on problems where exact methods fail.

Question 5

Why does the starting state matter so much for hill climbing, and what strategy do practitioners use to mitigate this dependency?

Model answer: Because hill climbing follows the gradient of improvement locally and terminates at whatever local optimum it first reaches, the starting state determines which basin of attraction the algorithm falls into. Different starting states lead to different local optima, which may vary dramatically in quality. To mitigate this, practitioners use random restarts: run hill climbing many times from different randomly chosen starting states and keep the best result found. This does not eliminate the local optimum problem but samples the landscape more broadly, increasing the probability of landing near the global optimum.

The sensitivity to initialization is the most practically important limitation of hill climbing. In a landscape with many local optima, no single run can be trusted. Random restarts convert a deterministic algorithm into a stochastic one by varying the entry point. An alternative is to use simulated annealing, which modifies the search dynamics to escape local optima during the run rather than relying on re-entry. Both strategies address the same underlying problem: the inability of pure hill climbing to traverse valleys between peaks.