En el anterior post explicamos el algoritmo Metrópolis y por qué era tan importante para resolver el problema del viajante de comercio. En éste vamos a explicaros qué es el algoritmo simulated annealing y cómo se codifica para poder utilizarlo en cualquier aplicación.

Recordaréis que el algoritmo Metrópolis devuelve una serie de configuraciones. Esto sucede así hasta que llega a una situación de equilibrio, que habitualmente consiste en alcanzar un número de configuraciones determinado. En cada ciclo, el algoritmo Metrópolis nos devuelve una muestra de la distribución de Gibbs para una determinada temperatura. Para saber si dicha muestra es un mínimo global, hay que repetir los muestreos disminuyendo de manera monótona la temperatura, hasta que el valor se aproxime a 0. Esta sucesión de muestreos es lo que llamamos simulated annealing. El pseudocódigo del algoritmo es el siguiente:

comienzo SIMULATED_ANNEALING {
     C[0] = INI_CONFIGURACION ( );
     T = INI_TEMPERATURA ( );
     t = 0;
     repetir {
          C = C[t];
          repetir {
               auxC = GEN_CONFIGURACION(C);
               ∆E = E(auxC)-E(C);
               q = mín{1, e^(-∆E/T)};
               si (ALEATORIO(0,1)< q) entonces { C = auxC;  } ;
          } hasta( TEST_EQUILIBRIO );
          t = t +1;
          C[t] = C;
          T = ENFRIAR (T, t);
     }hasta (T ≈ 0);
     devolver C[t] = C* = arg mín E(C);
}

Tenemos que realizar las siguiente aclaraciones:

• Las funciones INI_CONFIGURACION y INI_TEMPERATURA, proporcionan una configuración inicial (normalmente aleatoria) y la temperatura inicial, respectivamente.
• La función GENERAR devuelve una configuración local a la dada.
• La función ALEATORIO devuelve un valor uniformemente distribuido entre los límites que se pasan por el argumento.
• El control de convergencia de algoritmo Metrópolis lo realiza la función TEST_EQULIBRIO, el cual lo que hace es comprobar en qué ciclo se encuentra y escapar del bucle cuando satisfaga la restricción.
• La función ENFRIAR merece un capítulo sólo para ella, ya que ésta es la que se encarga de reducir la temperatura de manera monótona, y es la que permite que el sistema funcione.

La característica más interesante de este algoritmo es su capacidad para evitar los mínimos locales, lo cual se debe a la cuidadosa gestión del parámetro T. En el siguiente post os contaremos cómo debemos desarrollar la función de ENFRIAR. Ya casi hemos resuelto el problema.

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.

En el último post sobre búsqueda definimos las dimensiones del problema del viajante de comercio, y definimos una función de energía que nos sirve de medida para saber si la solución es óptima.

Ya conocemos la función de coste:

Nos damos cuenta de que la función de coste E(C) ≥ 0 para todo C perteneciente a Ω. Para poder aplicar nuestro algoritmo de búsqueda, en este caso el algoritmo Simulated Annealing (Templado Simulado), asumimos que la probabilidad de una determinada configuración C decae exponencialmente con su coste siguiendo la distribución de Gibbs:

Z es un factor de normalización denominado función de partición, y T un parámetro de control denominado temperatura. Cuando T tiende a infinito, resulta que la probabilidad de una determinada configuración C es uniforme, de tal manera que todas las configuraciones tienden a ser equiprobables independientemente de su coste. Sin embargo, si T tiende a 0, P(C) se concentra en los picos de la distribución de Gibbs, de tal manera que sólo las configuraciones de mínimo coste tienen configuración no nula. En conclusión, para una misma temperatura, la probabilidad de una determinada configuración decae exponencialmente con su coste, y dicho decaimiento es atenuado por la temperatura; es decir, la configuraciones que tienen mínimo coste son más probables que el resto.

¿Y qué tendrá que ver todo esto con el viajante de comercio? estamos hablando de probabilidades, de funciones de coste, pero no sabemos qué vamos a hacer con todo ello. Calma, os dije que esta parte no iba ser fácil.

Todo este modelo probabilístico que he propuesto se relaciona con la búsqueda de la configuración de mínimo coste, mediante una analogía entre la resolución de un problema de optimización y la solución de un proceso de templado del metal. Para templar un metal, lo primero que hacemos es exponerlo a temperaturas muy elevadas, y despues descender esta temperatura hasta encontrar la configuración de mínima energía, que es cuando el metal alcana estructuras reticulares, extrema su resistencia y su dureza. Pero al realizar el templado, tenemos que tener en cuenta el ritmo con el que enfriamos el metal. Un ritmo demasiado rápido alcanzara configuraciones de baja energía, que no se corresponderán a estructura reticulares, sino a estructuras amorfas que harán que el metal pierda su resistencia y su dureza. Esto es debido a que no se alcanzado un mínimo de energía global, sino uno local que no es el óptimo, y que puede estar muy alejado de la solución del problema. Pero si se elige una buena velocidad de descenso de temperatura que permita saltarse esos mínimos locales, se garantiza la convergencia al estado óptimo global. El algoritmo Simulated Annealing garantiza esta convergencia y se aplica para problema combinatoriales, como es el caso del viajante de comercio.

En el próximo post, describiremos el proceso de Muestreo a través del algoritmo Metrópolis. Este algoritmo genera una secuencia de configuraciones que utilizará el algoritmo Simulated Annealing para alcanzar la configuración óptima. Empieza lo interesante.