6.3 Recocido Simulado

La analogía es la siguiente:

• Las soluciones corresponden a estados del sistema físico.
• El costo de la solución corresponde a la energía del estado.
• Se introduce un parámetro de control que corresponde a la temperatura.

El algoritmo de recocido simulado se puede ver como una iteración de algoritmos de Metrópolis (ver tabla 6.2).

Si se baja la temperatura suficientemente lento se puede alcanzar el equilibrio térmico en cada temperatura. Esto se hace mediante la generación de varias transiciones en cada temperatura.

Se puede demostrar que bajando suficientemente lento el parámetro asociado a la temperatura y generando suficientes transiciones en cada temperatura se puede alcanzar la configuración óptima.

La probabilidad de aceptación se expresa como sigue:

$$P_c\{\mbox{acepta } j\} = \left\{ \begin{array}{ll} 1 & \mbox... ...(i) - f(j)}{c}) & \mbox{ si } f(j) > f(i) \end{array} \right .$$

donde $c \in {\cal R}^+$ denota el parámetro de control.

Una transición consiste en (i) aplicación del mecanismo de generación, y (ii) aplicación del mecanismo de aceptación.

Inicialmente valores grandes de $c$ aceptan cualquier estado. Al tender $c$ a cero, se dejan de aceptar estados.

Tabla 6.2: Algoritmo de Recocido Simulado.

La velocidad de convergencia del algoritmo está determinada por $L_k$ y $c_k$.

Búqueda local se puede ver como quenching.

Un sistema físico de muchas particulas puede verse como un ``ensamble'' estadístico.

Si el ensable es estacionario, el cual se logra en equilibrio térmico, su densidad es función de la energía del sistema y la probabilidad de estar en un estado $i$ con energía $E_i$ está dado por la distribución de Boltzmann.

Dada una instancia de un problema combinatorio y una estructura de vecinos adecuada, después de un número de transiciones suficientemente largo para un valor fijo de $c$, aplicando el criterio de aceptación, el algoritmo de recocido simulado encuentra una solución $i \in S$ con probabilidad igual a:

$$P_c\{X = i\} \equiv q_i(c) = \frac{1}{N_0(c)} exp(- \frac{f(i)}{c})$$

donde $X$ es una variable estocástica denotando la solución actual y

$$N_0(c) = \sum_{j \in S} exp(- \frac{f(j)}{c})$$

denota una constante de normalización.

Dada una instancia de un problema de optimización combinatoria, una estructura de vecindad adecuada y una distribución estacionaria equivalente a la distribución de Boltzmann, entonces:

$$lim_{c \rightarrow 0} q_i(c) \equiv q_i^* = \frac{1}{\mid {\cal S}_{opt}\mid} \chi_{(S_{opt})}(i)$$

donde ${\cal S}_{opt}$ denota el conjunto de soluciones óptimas globales, y $\chi_{A'}(a)$ es la función característica definida como:

$$\chi_{(A')}(a) = \left\{ \begin{array}{ll} 1 & \mbox{si } a \in A' \\ 0 & \mbox{de otra forma} \end{array} \right .$$

El resultado es importante porque garantiza una convergencia asintótica hacia el conjunto de soluciones óptimas del algoritmo de recocido simulado bajo la condición que la distribución estacionaria se obtenga para cada valor de $c$.

La probabilidad de encontrar la solución óptima incrementa monotónicamente al decrementar $c$.