174
6: Teerasit Kasetkasem
1. The propose step: A new configuration Xl is proposed by sampling a PDF
G(x2,xd onA.
2. The acceptance step: If Epost (xd :::: Epost (X2) then Xl is accepted as a new
configuration with probability one. However, if Epost (XI) > Epost (X2) then
Xl is accepted with probability
a(x2, Xl) = exp [ -~ (Epost (xd - Epost(X2»)] .
(6.23)
The matrix G is called the proposal or exploration matrix. A new configuration Xl is not automatically rejected if it is less favorable than the current
configuration X2. Instead, a new configuration Xl is accepted with probability that decreases with the increment of difference in energies Epost (X2) -
Epost (XI). This procedure allows the algorithm to escape from the local minimum points.
The obvious difference between the SA and the Metropolis algorithms is
that the SA algorithm needs to compute the probabilities associated with
all possible configurations at a given site while the Metropolis algorithm
only requires the difference between energies of the current and proposed
configurations in order to update the configuration of the site of interest.
This makes the Metropolis algorithm more efficient when a configuration
Initial Image
Find visiting scheme
{S],S2,"'}' set T=
To and h = 1.
Randomly propose
a new configuration
Xnew
Accept with probability.
exp {(Epo,!{old)- Epo,,(new))/T}
h=h+1.
Fig. 6.4. Block diagram of the Metropolis algorithm
Reduce Tusing a
predetermined
schedule.
Move to a new site
NO