Recocido simulado

La idea

Un buscador local puro solo acepta movimientos que mejoran, así que en cuanto cae en un mínimo local se queda atrapado. El recocido simulado se inspira en la metalurgia: cuando un metal se enfría despacio, sus átomos tienen tiempo de reorganizarse en una red de baja energía, mientras que un enfriamiento brusco congela los defectos. El algoritmo imita ese proceso con una temperatura T que va bajando.

En cada iteración se genera un vecino del estado actual y se calcula Δ = f(vecino) − f(actual). Si Δ < 0 (mejora) se acepta siempre. Si Δ > 0 se acepta con probabilidad e^(−Δ/T), el criterio de Metropolis: al principio, con T grande, casi todo se acepta y la búsqueda explora libremente el paisaje; al final, con T pequeña, solo se aceptan mejoras y el método se comporta como un descenso local que refina la solución. Esa transición controlada de exploración a explotación es la clave del método.

El esquema de enfriamiento decide el éxito. El más usado es el geométrico Tₖ₊₁ = α Tₖ con α entre 0,90 y 0,999; existe un resultado teórico que garantiza convergencia al óptimo global con el enfriamiento logarítmico Tₖ = c / log(1 + k), demasiado lento en la práctica. Hay que elegir también T₀ (de modo que al inicio se acepte en torno al 80 % de los movimientos), el generador de vecinos y el número de iteraciones. El algoritmo no necesita derivadas ni continuidad, por lo que se aplica igual a funciones rugosas que a problemas combinatorios donde «vecino» significa intercambiar dos elementos.

Fórmulas clave

• Criterio de MetropolisP(aceptar) = 1 si Δ ≤ 0; e^(−Δ/T) si Δ > 0
• Variación de energíaΔ = f(x_nuevo) − f(x_actual)
• Enfriamiento geométricoTₖ₊₁ = α Tₖ, 0,9 ≤ α < 1
• Enfriamiento logarítmicoTₖ = c / log(1 + k) (convergencia garantizada)
• Distribución de BoltzmannP(x) ∝ e^(−f(x)/T)
• Temperatura inicialT₀ ≈ Δ̄ / ln(1/p₀) con p₀ ≈ 0,8

Dónde se aplica

El diseño de circuitos integrados usa recocido simulado desde los años ochenta para colocar bloques y trazar pistas minimizando longitud de cable y retardo. En logística resuelve versiones grandes del problema del viajante y del diseño de rutas de reparto, donde los vecinos son intercambios de dos ciudades. Los operadores de redes móviles asignan frecuencias y ángulos de antena con esta técnica, y en bioinformática se emplea para predecir el plegamiento de proteínas y para alinear secuencias, siempre que el espacio de soluciones es enorme y lleno de mínimos locales.

Con programación (Python)

import math, random

# Funcion de Rastrigin 1D: muchos minimos locales, global en x = 0
def f(x):
    return 10 + x * x - 10 * math.cos(2 * math.pi * x)

random.seed(7)
x = 4.2
T = 5.0
alfa = 0.999
mejor_x, mejor_f = x, f(x)
aceptados_peores = 0
for k in range(4000):
    cand = max(-5.12, min(5.12, x + random.gauss(0, 0.4)))
    delta = f(cand) - f(x)
    if delta <= 0 or random.random() < math.exp(-delta / T):
        if delta > 0:
            aceptados_peores += 1
        x = cand
        if f(x) < mejor_f:
            mejor_x, mejor_f = x, f(x)
    T *= alfa
    if (k + 1) % 1000 == 0:
        print("iter %4d   T = %7.4f   x = %+8.4f   f = %9.5f" % (k + 1, T, x, f(x)))

print("Movimientos peores aceptados:", aceptados_peores)
print("Mejor solucion: x = %.5f   f = %.6f" % (mejor_x, mejor_f))
print("Optimo global: x = 0, f = 0")

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Método Monte Carlo · Descenso del gradiente · Algoritmos genéticos