5.2 Algoritmo

El algoritmo se muestra en la tabla 5.1.

Tabla 5.1: Algoritmo de Búsqueda Tabú.

Figura 5.1: Ejemplo sencillo de búsqueda Tabú.

La figura 5.1 muestra un ejemplo sencillo del funcionamiento de búsqueda Tabú. Supongamos que en cada punto solo pueden hacerse dos movimientos, hacia un estado con un número anterior o a un estado con un número posterior y supongamos que nuestra lista tabú es de tamaño 3.

Supongamos que inicialmente estamos puestos en el punto marcado con el número 1 en la figura 5.1. De ahí se pueden hacer dos movimientos (hacia 0 y hacia 2). Se elige el mejor (hacia 2), denotemoslo como $mov(1,2)$ y se actualiza la lista tabú (inicialmente vacía). Registramos el movimiento inverso en la lista ($mov(2,1)$) para evitarlo en el futuro.

De ahí nos movemos hacia el estado 3 (el mejor y el permitido dada nuestra lista tabú actual) y después al 4, con lo que la lista tabú se llena con tres elementos: { $mov(4,3), mov(3,2), mov(2,1)$}.

El siguiente movimiento es peor en la función objetivo ($mov(4,5)$), pero es el mejor dentro de los permitidos por la lista tabú y por nuestro esquema de vecindad utilizado. Tambén provoca que se elimine el elemento más viejo que tiene la lista tabú (por estar llena). La lista tabú queda como: { $move(5,4), mov(4,3), mov(3,2)$}.

Este proceso continua hasta que finalmente salimos del mínimo local al movernos del estado 8 al 9.

Puntos:

• Las soluciones dependen de como se actualiza $T$.
• No hay condición de óptimo local.
• Se busca la ``mejor'' solución en cada paso (función OPTIMO), en lugar de alguna opción que mejore la solución.

OPTIMO puede ser:

$$c(s_k(x)) = \mbox{ m\'{\i}nimo}(c(s(x)): s \in S(x) - T)$$

OPTIMO da la mejor solución o la menos peor sujeta a la lista tabú.

En principio, se podría tomar alguna solución que mejore (en caso de que sea difícil encontrar la mejor), pero normalmente se sigue la estrategia más agresiva.

La razón principal es que los óptimos locales no presentan problemas.

Normalmente la lista tabú se implementa como una lista circular, añadiendo elementos en la posición 1 y eliminando los que sobrepasen la posición $t$ (para una $t$ fija).

Una forma efectiva de implementar la lista $T$ sería:

$$T = \{ s^{-1}: s = s_h \mbox{ para } h > k - t\}$$

donde $k$ es el número de iteración y $s^{-1}$ es el movimiento inverso de $s$.

Por lo que el paso de actualización de $T$ sería: $T := T - s^{-1}_{k-t} + s^{-1}_k$.

En general, lo que se trata de evitar en caer en estados solución previos.

Esto no quiere decir que se tenga que escoger una $t$ muy grande.

En la práctica $T$ no toma la forma anterior: (i) $s^{-1}$ previene un conjunto más grande de movidas, (ii) por consideraciones de memoria es deseable guardar sólo un subconjunto de atributos que caracterizan el movimiento.

Bajo estas condiciones, la lista tabú representa una colección de movidas $C_h$.

Cuando la lista $S - T = \emptyset$ se pueden eliminar los elementos más viejos de $T$ para permitir continuar con el proceso.