6.2 Algoritmo de Metropolis

La idea principal puede verse en la tabla 6.1 (Metropolis et al. 1953) donde $T$ denota la temperatura y $k_B$ la constante de Boltzmann.

Tabla 6.1: Algoritmo de Metropolis.

Lo que hace el algoritmo de Metropolis es generar un vecino, calcularle su energía (i.e., función de costo en problemas de optimización) y aceptar ese vecino si tiene menor energía o aceptarlo con mayor energía pero con cierta probablidad que depende de la temperatura ($T$).

Se puede probar que si se realiza este proceso durante muchas transiciones se puede llegar a lo que se conoce como un equilibrio térmico.

El equilibrio térmico está caracterizado por la distribución de Boltzmann.

La distribución da la probabilidad de que el sólido esté en el estado $i$ con energía $E_i$ a temperatura $T$ y está dada por:

$$P_T\{X = i\} = \frac{1}{Z(T)} exp(\frac{-E_i}{k_BT})$$

donde $X$ es la variable estocástica denotando el estado actual del sólido, y $Z(T)$ es la función de partición definida como:

$$Z(T) = \sum_j exp(\frac{-E_j}{k_BT})$$