6.4 Convergencia Asintótica y Cadenas de Markov

El algoritmo de recocido simulado puede ser modelado matemáticamente usando cadenas de Markov.

Una cadena de Markov es una secuencia de eventos, donde la probabilidad del resultado de un evento depende sólo del resultados del evento anterior.

Sea $X(k)$ una variable estocástica que denota el resultado del $k$-ésimo evento. Entonces la transición de probabilidad en el $k$-ésimo evento para cada par $i, j$ de resultados se define como:

$$P_{ij}(k) = {\bf P}\{X(k) = j \mid X(k-1) = i\}$$

La matriz $P(x)$ cuyos elementos están dados por la fórmula de arriba se llama la matriz de transición.

Denotemos a $a_i(k)$ como la probabilidad del resultado $i$ en el $k$-ésimo evento, osea: $a_i(k) = {\bf P}\{X(k) = i\}$.

Entonces $a_i(k)$ se define como:

$$a_i(k) = \sum_l a_l(k-1)P_{li}(k)$$

Mencionemos algunas propiedades de cadenas de Markov. Una cadena de Markov se dice:

• Finita si tiene un conjunto finito de resultados.
• No homogénea si las probabilidades de transición dependen del número del evento $k$.
• Homogénea si las probabilidades de transición son independientes del número del evento.
• Irreducible si para cada par de soluciones $i,j \in S$ existe una probabilidad positiva de alcanzar $j$ a partir de $i$ en un número finito de eventos.

En recocido simulado, un evento corresponde a una transición y los resultados posibles corresponden al conjunto de soluciones posibles.

Las probabilidades de transición del algoritmo de recocido simulado están definidas como:

$$\forall i,j \in S : P_{ij}(k) = P_{ij}(c_k) = \left\{ \begin{... ..., l \neq i} P_{il}(c_k) & \mbox{si } i = j \end{array}\right .$$

donde:

$G_{ij}(c_k)$ denota la probabilidad de generación (la probabilidad de generar una solución $j$ a partir de una solución $i$).

$$\forall i,j \in S : G_{ij}(c_k) = G_{ij} = \frac{1}{\Theta} \chi_{(S_i)}(j)$$

donde $\Theta = \mid S_i \mid$, para toda $i \in S$.

$A_{ij}(c_k)$ denota la probabilidad de aceptación (la probabilidad de aceptar la solución $j$ una vez que fué generada a partir la solución $i$).

$$\forall i,j \in S : A_{ij}(c_k) = exp( - \frac{(f(j) - f(i))^+}{c_k})$$

donde, $\forall a \in {\cal R}, a^+ = a$ si $a > 0$ y $a^+ = 0$ de otra forma.

Lo que queremos probar es que, bajo ciertas condiciones, el algritmo de recocido simulado converge asintóticamente al conjunto de soluciones óptimas, i.e.,:

$$lim_{k \rightarrow \infty} P\{X(k) \in S_{opt}\} = 1$$

Una parte escencial para la prueba de convergencia es la existencia de una distribución estacionaria única. Tal distribución existe sólo si se cumplen ciertas condiciones en la cadena de Markov asociada al algoritmo.

Una distribución estacionaria de una cadena de Markov finita con matriz de transición $P$ se define como un vector q cuyo $i$-ésimo componente está dado por:

$$q_i = lim_{k \rightarrow \infty} {\bf P}\{ X(k) = i \mid X(0) = j\}, \mbox{ para toda } j$$

Si existe esa distribución estacionaria, entonces,

$$\begin{array}{lcl} lim_{k \rightarrow \infty} a_i(k) & = & l... ...)=j) P(X(0)=j) \\ & = & q_i \sum_j P(X(0)=j) = q_i \end{array}$$

Teniamos que:

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

Por lo que:

$$lim_{c \rightarrow 0} lim_{k \rightarrow \infty} P(X(k)=i) = lim_{c \rightarrow 0} q_i(c) = q^*_i$$

$$lim_{c \rightarrow 0} lim_{k \rightarrow \infty} P(X(k) \in S_{opt}) = 1$$

Aunque no es propiamente una prueba, lo de arriba indica algunas de las ideas principales que se usan en la prueba de convegencia.

Todas las pruebas usan la condición de reversibilidad o también llamada de balance detallado. Lo que dice es que si tenemos una matriz de transición $P$ asociada a una cadena de Markov finita, irreducible, aperiódica y homogénea. Entonces una distribución es estacionaria para la cadena de Markov si satisface:

$$q_i P_{ij} = q_j P_{ji}, \mbox{ para toda } i, j \in S$$

Las pruebas de convergencia nos dicen que el algoritmo de recocido simulado requiere un número infinito de transiciones para aproximarse lo suficiente a una distribución estacionaria en cada temperatura.

Esto involucraría la generación de secuencias infinitas para valores descendientes del parámetro de control $c$.

Sin embargo, podemos formular el algoritmo de recocido simulado como una secuencia de cadenas de Markov de longitud finita que converge al conjunto de soluciones óptimas si el enfriamiento se hace lo suficientemente lento.

El proceso se puede describir mediante la combinación de cadenas de Markov homogeneas en una solo cadena de Markov no-homogena. Dicho de otra forma, la secuencia de cadenas de Markov homogenas infinitamente largas se reducen a una sola cadena de Markon no homogenas infinita.