04.3 Hill Climbing and Simulated Annealing

Local search

refers to search algorithm that operate within a single candidate solution and iteratively improve it based on a neighboring solution

Local search

uses more compact representation and is well-suited for optimization problems where the path to the solution is less important than the final state

Current state only

focuses on _ _ _, what is local search (1)

Path history

doesn’t care about _ _, what is local search (2)

Climb to best spot

goal of local search, what is local search (3)

Hill Climbing

a specific of local search algorithm that continuously moves to a neighboring state with a higher evaluation (or lower cost)

Solution, No Better Neighbors

hill climbing is to incrementally improve the _ until _ _ _ exists

Local maxima, plateaus, ridges

hill climbing, is prone to _ , , _, where the algorithm may prematurely converge without finding the global optimum

Better neighbor

always move to _ _, hill climbing

Greedy

super _, hill climbing

Stuck at local peak

risk of hill climbing

Simulated annealing

probabilistic variant of local search inspired by the annealing process in metallurgy

Worse, Probability, Local optima

it allows the algorithm to accept _ solutions with some _ in order to escape _ _

Increasingly conservative

as the “temp” decreases over time, the algorithm becomes _ _