Local Search and Simulated Annealing › Disadvantages

Hill climbing's central failure is the local optimum. Because it only accepts strict improvements, it halts the moment every neighbor is at least as bad as the current point, even if a better solution sits one move further away. A local minimum can occur before the global optimum is reached. The fix, restarts, helps, but it spends the budget on independent attempts rather than systematically exploring, and there is no guarantee that the next restart will find a better basin. Perturbations and larger neighborhoods offer other ways to leave a local minimum.

Annealing permits uphill moves instead of stopping solely because no improving neighbor is available; a finite evaluation budget still terminates the run. The choice of initial temperature, cooling schedule, and number of moves at each temperature strongly affects quality. Too hot and the search wanders; too cold and it behaves like a slow hill climber. Classical asymptotic convergence results include sufficiently slow logarithmic schedules under finite-state and energy-barrier conditions. They do not certify a result after our 300-evaluation run; an independent bound or exhaustive reference is needed for that. We must therefore judge quality empirically, not by appeal to the asymptotic theory.

Both methods are also sensitive to the representation and the neighborhood. If the neighborhood is disconnected, a local walk from a fixed start stays in its component. Full-permutation random restarts can enter other components, but each epoch still refines only the component it starts in. If it is too wide, a full scan of the neighborhood becomes expensive. If it is too narrow, progress stalls. A move that changes the split between two vehicles in a routing problem has a very different effect from a move that only re-orders stops within one vehicle, and picking the wrong move set silently restricts local refinement between restarts. Finally, an equal number of objective evaluations does not imply equal runtime: a nearest-neighbor scan examines arcs cheaply, while each objective call here checks ten travel arcs for feasibility and traverses ten arcs again for distance, so two methods with the same nominal budget can take very different wall-clock time.