Un método probabilístico de optimización global que explora el espacio de soluciones mediante perturbaciones aleatorias y acepta cambios según una probabilidad dependiente de la temperatura (criterio de Metropolis), de modo que se pueden aceptar movimientos peores al principio para escapar de óptimos locales y el programa de temperatura reduce la aceptación con el tiempo para concentrarse en los mínimos.

Principio

Imitar el recocido físico: controlar la exploración mediante un parámetro de temperatura que disminuye gradualmente; aceptar movimientos ascendentes con probabilidad exp(-ΔE/T) para atravesar barreras energéticas, con convergencia al óptimo global bajo un programa de enfriamiento suficientemente lento (teóricamente).

Demostración

Optimizar una instancia del problema del viajante intercambiando aleatoriamente dos ciudades (operador de vecindad). A alta temperatura se aceptan muchos intercambios, permitiendo escapar de ciclos locales; al disminuir la temperatura se aceptan menos intercambios peores, refinando hacia un recorrido de bajo coste. En optimización continua, perturbar vectores de parámetros y aceptar según la regla de Metropolis.

Aplicación incorrecta

Usar un enfriamiento demasiado rápido (la temperatura baja demasiado rápido) provoca convergencia prematura a mínimos locales pobres; una temperatura inicial demasiado alta o ejecuciones demasiado largas desperdician tiempo; operadores de vecindario pobres hacen que la exploración sea inefectiva.

Consecuencia

Heurística flexible capaz de escapar de muchos mínimos locales y con frecuencia encontrar soluciones aproximadas de alta calidad en dominios discretos y continuos; el intercambio es resultados estocásticos y sensibilidad al ajuste del programa de temperatura y del vecindario.

Inversión

Hill-climbing codicioso que solo acepta mejoras y por tanto se queda atrapado con facilidad en óptimos locales, sin el mecanismo probabilístico para escapar.

Límite

Aplicable a problemas de optimización discretos y continuos cuando se define una estructura de vecindario y una función objetivo; no garantiza encontrar el óptimo global con programas de enfriamiento prácticos, y la eficiencia depende del diseño del vecindario y del programa de temperatura.

Tensión semántica

Tensión entre exploración (alta temperatura, movimientos grandes) y explotación (baja temperatura, movimientos finos), y entre recocido simulado y métodos estocásticos basados en poblaciones (p. ej. algoritmos genéticos) que emplean mecanismos diferentes para mantener diversidad y escapar de mínimos.

Síntesis

El recocido simulado equilibra la exploración aleatoria con la aceptación controlada por temperatura para atravesar barreras energéticas y concentrarse en regiones de bajo coste; con un programa de enfriamiento y un vecindario bien diseñados es una heurística robusta para problemas difíciles de optimización global, aunque los resultados son estocásticos y sensibles a la parametrización.