Modules 3 & 4

Hill Climbing & Simulated Annealing

Q17, Q22, Q4, Q5, Q6, Q9, Q7

Green = exact question bank answer Amber = clarification only

Part A — Hill Climbing

Q17

What is the Hill Climbing algorithm, and how does it work?

📋 Question bank answer

Hill Climbing is a local search optimization algorithm that starts with an initial solution and iteratively moves towards better neighboring solutions. It stops when no improvement can be made. It's simple but can get stuck in local optima.

Three Hill Climbing types (Q22)
Simple Check neighbors left to right → move to first better one
Fast but may miss the steepest climb
Steepest-Ascent Check all neighbors → pick the best one
Thorough but slower per step
Stochastic Pick a random neighbor that is better
Adds randomness, more exploration
Q22

What are the main types of Hill Climbing algorithms? Briefly describe each.

📋 Question bank answer
  • Simple Hill Climbing: Moves to the first better neighbor found.
  • Steepest-Ascent Hill Climbing: Evaluates all neighbors and chooses the best one.
  • Stochastic Hill Climbing: Randomly selects a better neighbor.
💡 Clarification

The three cards above summarize the same answer visually.

Three traps Hill Climbing falls into

Memorize these exact bank answers — high-value exam questions.

Q4

What is the "Local Maximum" problem in Hill Climbing, and how can it be addressed?

📋 Question bank answer

A local maximum occurs when no neighbors improve the solution, but better solutions exist elsewhere. It can be addressed by random restarts or backtracking to explore different regions of the search space.

Q5

Explain the "Plateau" problem in Hill Climbing, and provide a solution.

📋 Question bank answer

A plateau is a flat region where neighbors have the same value, making it hard to decide the next move. It can be addressed by larger steps or random restarts to escape the plateau.

Q6

What is the "Ridge" problem in Hill Climbing, and how can it be overcome?

📋 Question bank answer

A ridge is a region where the algorithm can't progress due to the slope of the landscape. It can be overcome by larger steps or using simulated annealing to allow some "downhill" moves, helping escape ridges.

💡 Clarification

See the landscape diagram below — each trap is labeled on the curve.

The three traps on a fitness landscape
Global peak Local max ● Q4: stuck, better elsewhere Plateau — Q5 all neighbors same height Ridge Q6 can't step uphill
Local max (Q4)All neighbors worse, but global peak exists
Fix: restarts / backtracking
Plateau (Q5)Flat area — neighbors all equal
Fix: larger steps / restarts
Ridge (Q6)Diagonal slope blocks progress
Fix: larger steps / SA

Part B — Simulated Annealing

Q9

What is the main inspiration behind the Simulated Annealing (SA) algorithm?

📋 Question bank answer

SA is inspired by the metallurgical process of annealing, where a material is heated to a high temperature and then slowly cooled to reduce defects and achieve a more stable, low-energy state. Similarly, SA starts with a high "temperature" to explore the search space broadly and gradually "cools" to refine the solution, helping it escape local optima and converge toward a global optimum.

💡 Clarification

The diagram below maps real metal annealing to the algorithm side by side.

SA inspiration (Q9) — metal annealing ↔ algorithm
🔥 Real annealing Heat metal hot → atoms move freely
Cool slowly → stable, low-energy crystal
↔
🌡️ Simulated Annealing High temperature → accept bad moves
Cool down → only accept improvements
Temperature over time
High T Explore the search space widely Accepts worse moves
cools →
Low T Refine toward the best solution Mostly uphill only
Q7

Describe the key parameters in SA?

📋 Question bank answer

Temperature: Controls the acceptance probability of worse solutions. High temperatures allow more exploration.
Cooling Rate: Determines how quickly the temperature reduces.
Initial Solution: Starting point for the search.

💡 Clarification

SA also solves the ridge problem (Q6) by accepting downhill moves early, then tightening as it cools — see the temperature curve above.

Flashcard drill

6 cards from this lesson — recall the bank answer, then reveal to check.

Card 1 of 6
Q4

Cover the area below, answer from memory, then tap Reveal.