1

Suppose, from the current state C it is possible to move to D different neighbouring states. In simulated annealing, we select a neighbouring state $D_i$ randomly and then accept it with probability $(D_i) = exp(\frac{−Δ_i}{})$ if $Δ_i\ge0$ and $(D_i) = 1$ if $Δ_i<0$. However, instead of doing that if I were to simply sample from the probability distribution $P(D_i) = \frac{1}{Z} exp(\frac{−Δ_i}{})$ where, z = $ \sum_{D_i} exp(\frac{−Δ_i}{})$ and move to that state; will it still be considered simulated annealing or a Metropolis Method?
Note: $Δ_i = f(D_i)- f(C)$

Santo
  • 41
  • 2

1 Answers1

2

Since the chain moves with probability one to a new state, it is a random walk walk. Which is either transient or recurrent depending on the dimension of the state space and on the values of the $\Delta_i$. But it is neither a Metropolis-Hastings [no rejection] nor a simulated annealing algorithm [no temperature schedule].

Even if the current state is included within the states $D_i$, the move selects to stay at the current point with (apparently) a probability that depends on the total number of states: $$\exp\{f(C)\}\Big/\exp\{f(C)\}+\sum_{D_i\ne C}\exp\{f(D_i)\}$$ A proper Metropolis step would accept a move with probability $$\frac{\exp\{f(D_i)\}}{\exp\{f(C)\}}\Big/\left\{\frac{\exp\{f(D_i)\}}{\sum_{D_j\ne C}\exp\{f(D_j)\}}\big/\rho(C|D_i)\right\}$$ where $\rho(C|D_i)$ denotes the probability to select $C$ among the neighbours of $D_i$.

Xi'an
  • 90,397
  • 9
  • 157
  • 575
  • Thank you for your answer. You say it is not simulated annealing algorithm because there is no temperature schedule. Suppose, here $P(D_i)=\frac{1}{} exp(\frac{-Δ_}{})$ where $Z = \sum_{D_i} exp(\frac{-Δ_}{})$ ,T is scheduled temperature. What happens then? – Santo Nov 29 '19 at 07:39
  • Here we do have a rejection probability since $P(C) = \frac{1}{Z} exp(\frac{0}{T}) =\frac{1}{Z} $ – Santo Nov 29 '19 at 08:47