Q14Principles of Artificial Intelligence

Standard local search algorithms (like Hill Climbing) suffer a catastrophic mathematical flaw: they get permanently trapped in Local Maxima/Minima. They aggressively climb the nearest hill, reach the top, look around, see that every step is down, and halt, completely missing the massive Mount Everest located just across a small valley. Simulated Annealing is the absolute mathematical solution to this crisis, inspired by the physical metallurgy process of cooling molten metals.

The Mathematical Mechanism

The algorithm violently alters the standard Hill Climbing logic by intentionally injecting Chaos (Probability).

• The Temperature Parameter ($T$): The algorithm initializes with a massive mathematical "Temperature." When $T$ is high, the system is chaotic and molten.
• Accepting Bad Moves: In Hill Climbing, a move that worsens the score is absolutely rejected. In Simulated Annealing, if a move is worse (it goes down into the valley), the algorithm calculates a strict mathematical probability based on the Boltzmann distribution: $P=e^{\Delta E/T}$.
• The Escape: Because $T$ is massive at the beginning, this probability $P$ is very high. The AI will frequently and aggressively accept "bad" moves. This violently throws the algorithm out of the local minimum trap and across the valley.
• The Cooling Schedule: Over time, the algorithm mathematically decays $T$ (cooling). As $T$ approaches zero, the probability of accepting bad moves drops to absolute zero. The chaotic system crystallizes, locking into a standard, greedy Hill Climb right as it hits the global maximum.