En el anterior post sobre búsqueda, hablamos sobre la utilización de la temperatura para hacer converger nuestro sistema a un mínimo global que permita encontrar la solución óptima. También hemos dicho, en diversas ocasiones, que intentar analizar todos los casos del espacio Ω es inviable, debido a su magnitud. Lo ideal es encontrar una forma para que se seleccionen las mejores soluciones, y solamente evaluar éstas. El algoritmo Metrópolis se encarga de esto.

En primer lugar vamos a suponer que la temperatura T es constante. Lo primero que debemos hacer es asignar una configuración inicial C0, y despues vamos a estar interesados en generar una serie de configuraciones C1, C2 … hasta que consigamos encontrar la configuración de mínima energía para esa temperatura. Lo que podríamos hacer es evaluar todas las configuraciones en función de P(C), asumiendo que las mejores configuraciones van a tener mayor posibilidad de salir; el problema es que si el número de configuraciones es excesivamente grande, y este número es un numero significativamente menor que Ω, esto no es lo más óptimo.

Sin embargo, nosotros vamos a evitar evaluar las configuraciones directamente a través de P(C), ya que resulta mucho más fácil modelar la secuencia como una Cadena de Márkov (una secuencia de eventos donde el evento siguiente depende del anterior), porque evaluaremos una función P(C[t+1] | C[t]), pero no aseguraremos que esta probabilidad converge a la distribución de P(C), en este caso a la distribución de Gibbs, si el numero de muestras es suficientemente elevado.

El algoritmo Metrópolis aporta una estrategia de muestreo de este tipo y se caracteriza por dos aspectos básicos:

• La configuración de C[t+1] se consigue a través de C[t], de forma que C[t+1] es una configuración vecina o localmente próxima a C[t]. En el caso del viajante de comercio es coger una ramificación, lo que se traduce en permutar dos ciudades.
• La nueva configuración C[t+1] no se acepta directamente, sino que se acepta con una cierta probabilidad definida como:

  

  Siendo P(C) una disribución de Gibbs, y como tenemos una T fija:

  

  
  Si la variación de energía es menor o igual que cero, entonces la configuración C[t+1] se coge sin duda, ya que significa una disminución de energía. En caso contrario, entonces la probabilidad de que esta nueva configuración nos lleve a la óptima decae exponencialmente con el empeoramiento del balance energético, y dicho decaimiento está atenuado por T. Se debe elegir umbral que decida a partir de qué probabilidad q se debe aceptar una configuración. Este umbral es r.

El algoritmo Metrópolis termina cuando satisface una condición de equilibrio, que en la práctica se traduce en un determinado número de muestras. En el siguiente post, después de haber comentado todas las herramientas que utilizamos para el simulated annealing, describiremos este algoritmo y cómo utiliza el algoritmo Metrópolis para obtener la solución óptima.