Saltar al contenido
Volver a los resultados

Recocido simulado — Optimización probabilística

Año
1983
Tipo
Probabilistic metaheuristic / local search

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

El recocido simulado es una metaheurística probabilística de búsqueda local introducida por Kirkpatrick, Gelatt y Vecchi en 1983.

Modela el proceso físico de recocido en metalurgia —donde un material se calienta y luego se enfría lentamente para alcanzar un estado cristalino de baja energía— y utiliza esta analogía para escapar de los óptimos locales en problemas de optimización combinatoria y continua.

La intuición detrás del método

Imagine que intenta encontrar el punto más bajo en un paisaje montañoso con los ojos vendados. Una búsqueda puramente codiciosa siempre desciende y se queda atascada en el primer valle que encuentra, que puede no ser el más profundo. El recocido simulado introduce una aleatoriedad controlada: al principio, cuando la 'temperatura' es alta, el algoritmo está dispuesto a subir ocasionalmente, aceptando una peor solución por azar. A medida que la temperatura disminuye según un programa de enfriamiento, el algoritmo se vuelve cada vez más selectivo, convergiendo en una solución. Esta disposición a aceptar movimientos peores a alta temperatura es lo que permite al método escapar de óptimos locales poco profundos y explorar el paisaje de manera más exhaustiva.

Historia

El recocido simulado fue introducido por Kirkpatrick, Gelatt y Vecchi en su influyente artículo de 1983 en Science, que estableció una analogía explícita entre el recocido termodinámico de los sólidos y la optimización combinatoria. La misma idea fue propuesta independientemente por Cerny (1985) en el contexto del problema del viajante. van Laarhoven y Aarts (1987) proporcionaron el primer tratamiento teórico riguroso, demostrando propiedades de convergencia bajo varios programas de enfriamiento. Desde entonces, el método se ha convertido en una de las metaheurísticas más estudiadas y aplicadas, utilizada en diseño de ingeniería, investigación de operaciones, diseño de VLSI y ajuste de hiperparámetros de aprendizaje automático.

Cuándo usarlo

El recocido simulado es aplicable a cualquier problema donde se pueda definir una estructura de vecindario sobre el espacio de soluciones, independientemente de si la función objetivo es diferenciable, convexa o incluso expresable analíticamente. Es particularmente adecuado para problemas combinatorios (programación, enrutamiento, problemas de grafos) y optimización continua de caja negra. No se requieren datos de entrenamiento ni suposiciones de normalidad. El programa de enfriamiento y la estructura del vecindario deben ajustarse al problema; ejecutar menos de aproximadamente 1000 iteraciones corre el riesgo de una convergencia prematura a un óptimo local, en cuyo caso se debería preferir una búsqueda local determinista más simple.

Limitaciones y consideraciones

  • La calidad de la solución es sensible al programa de enfriamiento; un programa deficiente puede producir resultados no mejores que la búsqueda aleatoria.
  • La estructura del vecindario debe diseñarse para cada clase de problema, lo que requiere experiencia en el dominio.
  • La convergencia al óptimo global requiere un enfriamiento extremadamente lento en la práctica, lo que hace que el tiempo de ejecución sea largo para garantías de alta calidad.
  • No aprovecha la información de gradiente o estructural, por lo que los métodos basados en gradiente lo superan en problemas suaves y diferenciables.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Puede escapar de óptimos locales a través de la aceptación probabilística de peores soluciones, a diferencia de la escalada pura.
  • Se aplica a prácticamente cualquier tipo de problema —combinatorio, continuo, mixto— siempre que se defina una estructura de vecindario.
  • No requiere información de gradiente y es indiferente a la estructura matemática de la función objetivo.
  • Tiene una garantía teórica de convergencia al óptimo global bajo un enfriamiento suficientemente lento (Hajek 1988).
  • Pocos hiperparámetros: temperatura inicial, tasa de enfriamiento y estructura del vecindario.

Aplicaciones

  • Problemas de programación y horarios combinatorios donde el espacio de soluciones es demasiado grande para la búsqueda exhaustiva.
  • Problemas del viajante y de enrutamiento de vehículos en logística e investigación de operaciones.
  • Diseño de circuitos VLSI y planificación de chips en ingeniería eléctrica.
  • Problemas de plegamiento de proteínas y conformación molecular en biología computacional.
  • Optimización de hiperparámetros para modelos de aprendizaje automático cuando la información de gradiente no está disponible.
  • Problemas de asignación y distribución de recursos en ingeniería y ciencias de la gestión.

Cómo funciona

Cómo funciona

1

El algoritmo comienza con una solución inicial —cualquier punto factible en el espacio de búsqueda— y una temperatura inicial alta. La solución inicial puede ser aleatoria o específica del problema; la temperatura inicial se establece típicamente lo suficientemente alta como para que casi cualquier solución vecina sea aceptada al principio.

2

Se genera una solución vecina aplicando un pequeño cambio aleatorio (un 'movimiento') a la solución actual. La estructura del vecindario debe adaptarse al problema: para un problema de programación, un movimiento podría intercambiar dos tareas; para una función continua, podría agregar una pequeña perturbación aleatoria al vector de parámetros actual.

3

Se calcula la diferencia en el valor objetivo entre la solución nueva y la actual. Si la nueva solución es mejor, siempre se acepta. Si es peor, se acepta con una probabilidad que decae con el tamaño del deterioro y la temperatura actual —típicamente exp(−ΔE / T). Esta aceptación probabilística es el mecanismo central que previene la convergencia prematura.

4

Después de cada iteración (o después de un número fijo de movimientos a la misma temperatura), la temperatura se reduce según un programa de enfriamiento —comúnmente un programa geométrico T ← α·T donde α es ligeramente inferior a 1. La elección del programa de enfriamiento afecta fuertemente la calidad de la solución: enfriar demasiado rápido atrapa la búsqueda en un óptimo local; enfriar demasiado lento desperdicia tiempo computacional.

5

El algoritmo se detiene cuando la temperatura cae por debajo de un umbral mínimo, se alcanza un número máximo de iteraciones o la solución no ha mejorado durante un número especificado de pasos. La mejor solución encontrada durante toda la ejecución —no solo el estado final— se devuelve como resultado.

Errores comunes

  • Ejecutar muy pocas iteraciones (aproximadamente menos de 1000) impide que el programa de enfriamiento funcione correctamente y deja la búsqueda atrapada en un óptimo local; prefiera la búsqueda tabú o una búsqueda local determinista si el tiempo de ejecución es muy limitado.
  • Establecer la temperatura inicial demasiado baja significa que el algoritmo se comporta inmediatamente como una escalada codiciosa y pierde su capacidad de escapar de los óptimos locales.
  • Establecer la tasa de enfriamiento de manera demasiado agresiva (por ejemplo, α por debajo de 0.9) provoca una convergencia prematura; verifique la calidad de la solución final reiniciando desde múltiples soluciones iniciales.
  • Aplicar un movimiento de vecindario diseñado para un tipo de problema a un problema diferente puede hacer que los movimientos sean inviables o sin sentido; siempre verifique que cada vecino generado sea una solución válida.
  • Informar solo el estado final en lugar de la mejor solución encontrada durante la ejecución puede pasar por alto el verdadero óptimo encontrado en un paso intermedio.

Preguntas frecuentes

¿Cómo elijo el programa de enfriamiento?

El programa geométrico T ← α·T con α entre 0.90 y 0.99 es el punto de partida más común. Un enfoque práctico es establecer la temperatura inicial lo suficientemente alta como para que aproximadamente el 80% de los movimientos se acepten al principio, luego reducirla hasta que se acepten menos del 1% de los movimientos ascendentes. Si la calidad de la solución final es pobre, ralentice la tasa de enfriamiento (aumente α); si el tiempo de ejecución es demasiado largo, acelérelo. Ejecute siempre el algoritmo varias veces desde diferentes soluciones iniciales para evaluar la robustez.

¿Cómo se diferencia el recocido simulado de los algoritmos genéticos o la optimización por enjambre de partículas?

El recocido simulado mantiene una única solución y explora el vecindario a través de perturbaciones aleatorias, aceptando peores soluciones probabilísticamente. Los algoritmos genéticos y la optimización por enjambre de partículas mantienen una población de soluciones y utilizan cruce, mutación o movimiento de enjambre para evolucionar la población. El recocido simulado es generalmente más simple de implementar para problemas con una estructura de vecindario natural, mientras que los métodos basados en población pueden ser más efectivos para problemas continuos de alta dimensión.

¿Está garantizado el óptimo global?

Teóricamente sí, bajo la condición de que la temperatura disminuya lo suficientemente lentamente (enfriamiento logarítmico). En la práctica, dicho enfriamiento es computacionalmente inviable, por lo que el algoritmo encuentra una solución casi óptima. La calidad del resultado mejora con un enfriamiento más lento y más iteraciones, pero no hay garantía de tiempo finito. Ejecutar múltiples reinicios y mantener la mejor solución encontrada es una forma práctica de aumentar la confianza.

¿Cuándo debería preferir la búsqueda tabú o un algoritmo genético en su lugar?

Elija la búsqueda tabú cuando necesite una búsqueda determinista guiada por memoria que evite revisitar soluciones recientes y pueda explotar la estructura del problema de manera eficiente en un tiempo de ejecución más corto. Elija un algoritmo genético u optimización por enjambre de partículas cuando el problema sea de alta dimensión y continuo, o cuando se necesite una población de soluciones diversas para mapear el paisaje óptimo. El recocido simulado es una opción predeterminada sólida para problemas combinatorios con una estructura de vecindario clara y cuando la simplicidad de implementación es importante.

Métodos relacionados

Fuentes

  1. Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.

    Abrir referencia DOI
    Copiado.
  2. van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.

    ISBN: 9789027725431
    Copiado.