Busqueda Tabu


La búsqueda Tabú surge, en un intento de dotar de “inteligencia” a los
algoritmos de búsqueda local. Según Fred Glover, su primer definidor, “la
búsqueda tabú guía un procedimiento de búsqueda local para explorar el
espacio de soluciones más allá del óptimo local”. La búsqueda tabú toma de la Inteligencia Artificial el concepto de memoria y lo implementa mediante estructuras simples con el objetivo de dirigir la búsqueda teniendo en cuenta la historia de ésta, es decir, el procedimiento trata de extraer información de lo sucedido y actuar en consecuencia. En este sentido puede decirse que hay un cierto aprendizaje y que la búsqueda es inteligente. La búsqueda tabú permite moverse a una solución aunque no sea tan buena como la actual, de modo que se pueda escapar de óptimos locales y continuar estratégicamente la búsqueda de soluciones aún mejores.

Algoritmo

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. 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.

Problema

Bueno como en el otro , post he puesto un ejemplo que he encontrado en la Wikipedia.

El problema del Agente viajero es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente fácil, y en la práctica presentan un gran problema.

La respuesta al problema es conocida, es decir se conoce la forma de resolverlo, pero sólo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado (Para una mayor profundidad en el tema ver el artículo NP-completos).

El problema del viajante (también conocido como problema del viajante de comercio o por sus siglas en inglés: TSP) es uno de los problemas más famosos (y quizás el mejor estudiado) en el campo de la optimización combinatoria computacional. A pesar de la aparente sencillez de su planteamiento, el TSP es uno de los más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otros problemas aparentemente mucho más complejos que han retado a los matemáticos desde hace siglos.

Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante. Es decir, encontrar una permutación P = {c0,c2,…,cn − 1} tal que d_P=\sum_{i=0}^{N-1}{d[c_i,c_{i+1mod(N)}]} sea mínimo. La distancia entre cada ciudad viene dada por la matriz D: NxN, donde d[x, y] representa la distancia que hay entre la ciudad X y la ciudad Y

La solución más directa es la que aplica la fuerza bruta: evaluar todas las posibles combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor distancia. El problema reside en el número de posibles combinaciones que viene dado por el factorial del número de ciudades (N!) y esto hace que la solución por fuerza bruta sea impracticable para valores de N incluso moderados con los medios computacionales actualmente a nuestro alcance. Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinación en un microsegundo, tardaría algo más 3 segundos en resolver el problema para 10 ciudades, algo más de medio minuto en resolver el problema para 11 ciudades y… 77.146 años en resolver el problema para sólo 20 ciudades.

Por ejemplo las rutas posibles entre 12 ciudades son (479 millones) 479.001.600 combinaciones y los caminos individuales entre ciudades son el sumatorio de las 12-1 ciudades es decir 66.

Se puede demostrar que el requerimiento de volver a la ciudad de partida no cambia la complejidad computacional del problema.

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:

s \in S(x) - T) \end{displaymath}

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:

s = s_h \mbox{ para } h > k - t\} \end{displaymath}

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 - 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.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s