Skip to main content
Cross Validated

Return to Question

edited body
Source Link
user138668
user138668
  • 121
  • 1
  • 5

My understanding of simulated annealing (SA) is that at any iteration $t$, a new sample $Y_t$ is generated, which, if the objective function $E$ is improved, i.e., $E(Y_t)<E(X_{t-1})$, then $Y_t$ is accepted, that is, $X_t=Y_t$, and the iteration moves on. Otherwise, the new sample is accepted by the following probability: $P(X_t=Y_t)=\exp(E(X_{t-1})-E(Y_t))\le1$. This setting is the same as in the Hastings-Metropolis (HM) algorithm, where detailed balance equation is indeed satisfied for the underlying Boltzmann distribution $\exp(-E(X)/T)$, assuming the proposal density is symmetric, e.g., a random walk.

However, in a number of papers, including this and this, which are popular papers, the acceptance probability seems to be set as $\frac{1}{1+\exp(E(X_{t-1})-E(Y_t))}$$\frac{1}{1+\exp(E(Y_t)-E(X_{t-1}))}$, which is $\le\frac{1}{2}$ for the case $E(Y_t)\ge E(X_{t-1})$. Under this acceptance probability, the Metropolis' detailed balance equation no longer holds. I believe this is also the default setting for Matlab's implementation of SA.

Can somebody explain to me why do these authors use such an acceptance rate? I spent an entire weekend surveying a number of papers, none of them explain with any clarity.

My understanding of simulated annealing (SA) is that at any iteration $t$, a new sample $Y_t$ is generated, which, if the objective function $E$ is improved, i.e., $E(Y_t)<E(X_{t-1})$, then $Y_t$ is accepted, that is, $X_t=Y_t$, and the iteration moves on. Otherwise, the new sample is accepted by the following probability: $P(X_t=Y_t)=\exp(E(X_{t-1})-E(Y_t))\le1$. This setting is the same as in the Hastings-Metropolis (HM) algorithm, where detailed balance equation is indeed satisfied for the underlying Boltzmann distribution $\exp(-E(X)/T)$, assuming the proposal density is symmetric, e.g., a random walk.

However, in a number of papers, including this and this, which are popular papers, the acceptance probability seems to be set as $\frac{1}{1+\exp(E(X_{t-1})-E(Y_t))}$, which is $\le\frac{1}{2}$ for the case $E(Y_t)\ge E(X_{t-1})$. Under this acceptance probability, the Metropolis' detailed balance equation no longer holds. I believe this is also the default setting for Matlab's implementation of SA.

Can somebody explain to me why do these authors use such an acceptance rate? I spent an entire weekend surveying a number of papers, none of them explain with any clarity.

My understanding of simulated annealing (SA) is that at any iteration $t$, a new sample $Y_t$ is generated, which, if the objective function $E$ is improved, i.e., $E(Y_t)<E(X_{t-1})$, then $Y_t$ is accepted, that is, $X_t=Y_t$, and the iteration moves on. Otherwise, the new sample is accepted by the following probability: $P(X_t=Y_t)=\exp(E(X_{t-1})-E(Y_t))\le1$. This setting is the same as in the Hastings-Metropolis (HM) algorithm, where detailed balance equation is indeed satisfied for the underlying Boltzmann distribution $\exp(-E(X)/T)$, assuming the proposal density is symmetric, e.g., a random walk.

However, in a number of papers, including this and this, which are popular papers, the acceptance probability seems to be set as $\frac{1}{1+\exp(E(Y_t)-E(X_{t-1}))}$, which is $\le\frac{1}{2}$ for the case $E(Y_t)\ge E(X_{t-1})$. Under this acceptance probability, the Metropolis' detailed balance equation no longer holds. I believe this is also the default setting for Matlab's implementation of SA.

Can somebody explain to me why do these authors use such an acceptance rate? I spent an entire weekend surveying a number of papers, none of them explain with any clarity.

Source Link
user138668
user138668
  • 121
  • 1
  • 5

Simulated annealing acceptance probability puzzle

My understanding of simulated annealing (SA) is that at any iteration $t$, a new sample $Y_t$ is generated, which, if the objective function $E$ is improved, i.e., $E(Y_t)<E(X_{t-1})$, then $Y_t$ is accepted, that is, $X_t=Y_t$, and the iteration moves on. Otherwise, the new sample is accepted by the following probability: $P(X_t=Y_t)=\exp(E(X_{t-1})-E(Y_t))\le1$. This setting is the same as in the Hastings-Metropolis (HM) algorithm, where detailed balance equation is indeed satisfied for the underlying Boltzmann distribution $\exp(-E(X)/T)$, assuming the proposal density is symmetric, e.g., a random walk.

However, in a number of papers, including this and this, which are popular papers, the acceptance probability seems to be set as $\frac{1}{1+\exp(E(X_{t-1})-E(Y_t))}$, which is $\le\frac{1}{2}$ for the case $E(Y_t)\ge E(X_{t-1})$. Under this acceptance probability, the Metropolis' detailed balance equation no longer holds. I believe this is also the default setting for Matlab's implementation of SA.

Can somebody explain to me why do these authors use such an acceptance rate? I spent an entire weekend surveying a number of papers, none of them explain with any clarity.