Acceptance probability determines whether an optimization algorithm accepts a proposed transition. In simulated annealing, lower-cost transitions are accepted with probability 1, while higher-cost transitions receive a temperature- and cost-difference-dependent probability. section 17.1.3
At high temperature, the probability of accepting uphill moves is close to 1, allowing broad exploration and escapes from local minima. As temperature falls, such moves become unlikely, shifting the search toward better solutions. The constant k is calibrated using the initial temperature and maximum cost difference. section 17.1.3
Cooling through the search landscape
Imagine an unconstrained update that can jump across the domain. Early in the simulation, nearly any move may be accepted; later, worse moves are effectively forbidden while improvements remain accepted. section 17.1.3
Figure 17.6 The effect of temperature on the probability of transitioning to a higher-energy state, and in turn on the annealing algorithm. (A) Initially, the temperature is high enough that any transition is allowed. At this stage, the algorithm behaves like random sampling (without storing the best result) and explores a large section of the domain. (B) When the system cools down, transitions to higher states become unlikely, and above some threshold they become so unlikely as to be considered forbidden. Transitions to lower states are always allowed. (C) When we are close to the end of the annealing simulation, the probability of moving to higher-energy states is so slim as to be negligible; the system can only move to better solutions.
Compare how temperature changes acceptance of higher-energy transitions across the beginning, middle, and end of annealing. section 17.1.3
