Acceptance probability measures whether a stochastic optimization algorithm accepts a proposed transition, including a move to a worse solution. In simulated annealing, improving moves are accepted, while a worsening move is accepted probabilistically to help escape local minima. section 5.2.3 section 5.7
For a minimization problem, let Δf be the increase in objective value and T the current temperature. With k = 1 and γ = 1, the probability is p = e^(−Δf/T). Draw r uniformly from [0, 1]; accept the move when p > r, otherwise reject it. Improving moves are accepted directly. section 5.2.3
Temperature and objective change determine the exploration–exploitation trade-off:
- Higher temperature increases acceptance of worsening moves, allowing broader exploration early in the search. section 5.2.3
- As temperature decreases, the search accepts fewer worsening moves and increasingly exploits promising regions. section 5.2.5
- Setting acceptance probability to zero resembles hill climbing; setting it to one produces highly exploratory, random-search-like behavior. section 5.2.3
A hand-worked rejection
Suppose the current solution has cost 14.06, a candidate has cost 23.23, and T = 5. Then Δf = 9.17 and p = e^(−9.17/5) = 0.1597. If the random threshold is r = 0.37, the candidate is rejected because p is smaller than r. section 5.3
