Algoritmo de recocido simulado

En cada iteración, el método de recocido simulado evalúa algunos vecinos del estado actual s y probabilísticamente decide entre efectuar una transición a un nuevo estado s' o quedarse en el estado s. En el ejemplo de recocido de metales descrito arriba, el estado s se podría definir en función de la posición de todos los átomos del material en el momento actual; el desplazamiento de un átomo se consideraría como un estado vecino del primero en este ejemplo. Típicamente la comparación entre estados vecinos se repite hasta que se encuentre un estado óptimo que minimice la energía del sistema o hasta que se cumpla cierto tiempo computacional u otras condiciones.

El vecindario de un estado s está compuesto por todos los estados a los que se pueda llegar a partir de s mediante un cambio en la conformación del sistema. Los estados vecinos son generados mediante métodos de Montecarlo.

El método de evaluación de estados vecinos es fundamental para encontrar una solución óptima global al problema dado. Los algoritmos heurísticos, basados en buscar siempre un estado vecino mejor (con energía más baja) que el actual se detienen en el momento que encuentran un mínimo local de energía. El problema con este método es que no puede asegurar que la solución encontrada sea un óptimo global, pues el espacio de búsqueda explorado no abarca todas las posibles variaciones del sistema.

La probabilidad de hacer la transición al nuevo estado s es una función P(δ E, T) de la diferencia de energía δE=E(s')-E(s) entre los dos estados, y de la variable T, llamada temperatura por analogía con el concepto físico de temperatura.

Si δE es negativo, es decir, la transición disminuye la energía, el movimiento es aceptado con probabilidad P=1. Es importante remarcar que la condición de que el sistema siempre pase a un sistema de menor energía cuando se encuentra una no es en absoluto necesaria para el éxito del método. Cuando δE es positivo la probabilidad de transición P es siempre distinta de cero, aún , es decir, el sistema puede pasar a un estado de mayor energía (peor solución) que el estado actual. Esta propiedad impide que el sistema se quede atrapado en un óptimo local.

A medida que la temperatura tiende al mínimo, la probabilidad de transición a un estado de mayor energía tiende a cero asintóticamente. Cuando T llega a cero, el algoritmo solo aceptará cambios a estados con menor energía. Debido a esta propiedad, la temperatura juega un papel muy importante en el control de la evolución del sistema. A temperaturas altas, el sistema tenderá a saltos de energía grandes entre los estados, mientras que a temperaturas más bajas, los cambios en energía serán menores.

Así, en cada iteración el algoritmo tiende a encontrar estados con menor energía total. Hay muchas maneras de disminuir la temperatura, siendo la más usual la exponencial, donde T disminuye por un factor α<1 en cada paso.

Como el nombre del algoritmo sugiere, la variación de la temperatura durante la computación es una característica distintiva de este método. El algoritmo comienza con un valor de T muy alto, que va decreciendo en cada iteración siguiendo un cierto protocolo de recocido, que puede ser diferente para cada problema, pero que siempre debe terminar con T=0. Así el sistema será libre inicialmente de explorar una gran porción del espacio de búsqueda, ignorando pequeñas variaciones de la energía entre los estados vecinos evaluados, para más tarde centrarse en regiones con estados de baja energía y, al final, cambiar solo a estados con energía menor que la inicial, hasta alcanzar un mínimo.

Ejemplo ilustrando la importancia del protocolo de enfriamiento: El problema consiste en disponer los píxeles en la imagen de tal manera que se minimice una función de energía potencial que causa que los colores similares se atraigan a distancias cortas y se repelan a distancias largas. En cada iteración se intercambian las posiciones de dos píxeles adyacentes. La imagen de la izquierda es obtenida con un protocolo de enfriado rápido, en el que la temperatura desciende rápidamente, y la de la derecha, con un protocolo lento, equiparables a los procesos de formación de sólidos amorfos y cristalinos respectivamente.

La probabilidad de que el algoritmo acabe encontrando el mínimo global para un problema dado se aproxima a 1 a medida que el protocolo de recocido se extiende.[5]

Empieza en un estado s₀ y sigue hasta un máximo de k_max pasos o hasta que se encuentra un estado con energía menor o igual que e_min. La función vecino(s) genera aleatoriamente un vecino de un estado dado s; la función azar(0, 1) devuelve un valor aleatorio uniformemente distribuido en el intervalo [0, 1]; véase Distribución uniforme. El proceso de recocido (enfriado) se expresa mediante temperatura(r), que da la temperatura en función de la fracción r del tiempo que ya ha trascurrido.

• Sea s = s₀
• Para k = 0 hasta k_max (exclusive):
  • T ← temperatura(k ∕ k_max)
  • s_nue ← vecino(s)
  • Si P(E(s), E(s_nue), T) ≥ azar(0, 1):
    • s ← s_nue
• Salida: estado final s

La probabilidad de aceptación originalmente propuesta es

• si ${\displaystyle e'<e}$, entonces ${\displaystyle P(e,e',T)=1}$
• si ${\displaystyle e'>e}$, entonces ${\displaystyle P(e,e',T)=\exp(-(e'-e)/T)}$

Este algoritmo se ha aplicado con éxito en varias áreas; ver por ejemplo las de la liga siguiente (Simulated annealing). Algunas de dichas aplicaciones son:

• el campo de la optimización de estructuras de hormigón.[6][7]
• para resolver instancias del problema ([[Job Shop Scheduling]])

El nombre del algoritmo se debe a la similitud con el concepto metalúrgico de recocido, en el que la temperatura de un material se hace descender lentamente para facilitar la formación de configuraciones de baja energía. No debe utilizarse para el algoritmo el término templado porque se trata del proceso metalúrgico opuesto, en el que la temperatura se hace descender de forma abrupta.

• MATLAB implementaciones de algoritmos de optimización global: SIMPSA (combinación de SA y SIMPLEX), SCA, PSO.

• Esta obra contiene una traducción parcial derivada de «Simulated annealing» de Wikipedia en inglés, concretamente de esta versión, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.