5.5 The Reactive Tabu Search

La búsqueda tabú reactiva (RTS) adapta el tamaño de la lista a las propiedades del problema de optimización.

Se almacenan las configuraciones visitadas y sus números de iteración, por lo que se puede calcular el número de repeticiones de una configuración y el intervalo entre dos visitas.

El mecanismo de reacción básico aumenta la lista tabú cuando se repiten configuraciones y lo reduce cuando no se necesita aumentar.

Se añade un mecanismo de diversificación de memoria a largo plazo cuando se sospecha de un atractor fuerte.

Para entender los atractores, los mínimos locales se pueden ver como atractores en la dinámica de la política de máxima pendiente.

Por otro lado, también se pueden tener ciclos, que se repiten continuamente.

Una tercera posibilidad es que la trayectoria esté restringida a una cierta área del espacio de búsqueda (atractores caóticos).

Existe en sistemas dinámicos el concepto del exponente de Lyapunov. Si tenemos una función $g$ que mapea un punto en el paso $n$ a un punto en el paso $n + 1$, $g^k(x)$ se define como el mapeo obtenido al interactuar $g, k$ veces.

Si se empieza con configuraciones cercanas $x_0$ y $x_0 + \epsilon$, el exponente de Lyapunov $\lambda$ se define por la relación:

$$\epsilon e^{n \lambda} \approx \mid\mid g^n (x_0 + \epsilon) - g^n (x_o) \mid\mid$$

Si $\lambda > 0$, los puntos inciales divergen exponencialmente, y si las trayectorias se mantienen dentro de una región en el espacio, uno obtiene lo que se llama cáos determinístico.

La trayectoria parece aleatoria pero el sistema es determinístico. En tal caso, aunque no se tienen ciclos, sólo se visita una región pequeña del espacio.

El evitar ciclos no debe de ser la única meta, se tienen que continuar estimulando el descubrimiento de soluciones de mejor calidad.

Algoritmo:

1. Se evaluan todos los posibles movimiento elementales a partir de la configuración actual.
2. Se busca la última configuración y se decide si se hace un mecanismo de escape.
3. Si no hay escape, se realiza el mejor movimiento.
4. Si hay escape, el sistema entra en un ciclo de movimientos aleatorios cuya duración depende del promedio de los movimientos en ciclos detectados.

Cuando se hace una repetición, el mecanismo básico de reacción aumenta el tamaño de la lista tabú. Después de un número suficiente de repeticiones se elimina cualquier tipo de ciclo.

Esto no es suficiente para evitar trampas caóticas. Para ésto, se tiene otro mecanismo más lento que cuenta el número de configuraciones que son repetidas. Cuando el número es mayor a una cierta constante se entra al mecanismo de diversificación.

Por otro lado, también se tiene un proceso lento que reduce la lista tabú si el número de iteraciones es más grande que el promedio de movimientos entre ciclos desde el último cambio.

Cuando la lista tabú es tan grande que todos los movimientos son tabú y ningúno satisface el criterio de aspiración, entonces se reduce la lista tabú.

La estrategia de escape se basa en realizar un conjunto de movimientos aleatorios proporcionales al número promedio de movimientos entre ciclos.

Para evitar regresar a la región, todos los movimientos aleatorios se vuelven tabú.

En experimentos realizados, si se elimina el mecanismo de escape, el sistema frecuentemente queda atrapado y no encuentra la solución óptima.