Algoritmo de recocido simulado

Simulated annealing (SA) o recocido simulado es un algoritmo de búsqueda meta-heurística para problemas de optimización global; el objetivo geneneral de este tipo de algoritmos es encontrar una buena aproximación al valor óptimo de una función en un espacio de búsqueda grande. A este valor óptimo se lo denomina "óptimo global"

El nombre e inspiración viene del proceso de recocido del acero y cerámicas, una técnica que consiste en calentar y luego enfriar lentamente el material para variar sus propiedades físicas. El calor causa que los átomos aumenten su energía y que puedan así desplazarse de sus posiciones iniciales (un mínimo local de energía); el enfriamiento lento les da mayores probabilidades de recristalizar en configuraciones con menor energía que la inicial (mínimo global).​

El método fue descrito independientemente por Scott Kirkpatrick, C. Daniel Gelatt y Mario P. Vecchi en 1983,​ y por Vlado Černý en 1985.​ El método es una adaptación del algoritmo Metropolis-Hastings, un método de Montecarlo utilizado para generar muestras de estados de un sistema termodinámico.​

Iteración básica

En cada iteración, el simulated annealing 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 uno o varios átomos se consideraría como un estado vecino del primero. 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 dado.

Vecindario de un estado

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 mas 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.

Los algoritmos meta-heuristicos, en cambio, pueden escoger estados vecinos peores que el estado actual. En teoría, un algoritmo como el simulated annealing operando durante un tiempo infinito, encontrará siempre la solución óptima.

Probabilidad de transición

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. Sin embargo, la probabilidad de transición P es siempre distinta de cero, aún cuando δE sea positivo, 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. 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.

Enlaces externos

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