Búsqueda tabú

La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de búsqueda local mediante el uso de estructuras de memoria: una vez que una potencial solución es determinada, se la marca como "tabú" de modo que el algoritmo no vuelva a visitar esa posible solución. La búsqueda tabú es atribuida a Fred Glover.

Detalles Básicos

La búsqueda tabú es un algoritmo metaheurístico que puede utilizarse para resolver problemas de optimización combinatoria, tales como el problema del viajante (TSP, del inglés Travelling Salesman Problem). La búsqueda tabú utiliza un procedimiento de búsqueda local o por vecindades para moverse iterativamente desde una solución $x$ hacia una solución $x'$ en la vecindad de $x$, hasta satisfacer algún criterio de parada. Para poder explorar regiones del espacio de búsqueda que serían dejadas de lado por el procedimiento de búsqueda local (ver óptimo local), la búsqueda tabú modifica la estructura de vecinos para cada solución a medida que la búsqueda progresa. Las soluciones admitidas para $N^{*}(x)$, el nuevo vecindario, son determinadas mediante el uso de estructuras de memoria. La búsqueda entonces progresa moviéndose iterativamente de una solución $x$ hacia una solución $x'$ en $N^{*}(x)$.

Quizás la estructura de memoria más importante usada para determinar las soluciones permitidas a un $N^{*}(x)$, sea la lista tabú. En su forma más simple, una lista tabú es una memoria de corto plazo que contiene las soluciones que fueron visitadas en el pasado reciente (menos de $n$ iteraciones atrás, donde $n$ es el número de soluciones previas que van a ser almacenadas ($n$ también es llamado el tenor del tabú)). La búsqueda tabú excluye las soluciones en la lista tabú de $N^{*}(x)$. Una variación de la lista tabú prohíbe soluciones que tienen ciertos atributos (i.e., soluciones al problema del viajante de comercio (TSP) que incluyen aristas no deseadas) o prevenir ciertos movimientos (i.e., un arco que fue agregado a un recorrido del TSP no puede ser eliminado en los siguientes $n$ movimientos). Los atributos seleccionados de las soluciones recientemente visitadas son denominados "tabú-activos." Las posibles soluciones que contengan elementos tabú-activos son "tabú".

Las listas tabú que contienen atributos pueden ser más efectivas para algunos dominios, pese a que presentan un nuevo problema. Cuando solo un atributo es marcado como tabú, esto por lo general resulta en que más de una solución es marcada como tabú. Algunas de estas soluciones, que ahora deben ser evitadas, podrían ser de excelente calidad y no serían visitadas. Para mitigar este problema, se introducen los "criterios de aspiración": estos pueden modificar el estado de tabú de una solución, por lo tanto incluyendo la antes excluida solución en el conjunto de soluciones permitidas. Un criterio de aspiración muy utilizado es admitir soluciones que son mejores que la mejor solución conocida al momento.

Ejemplo: Problema del Viajante

El problema del viajante (TSP), es comúnmente utilizado para mostrar la funcionalidad de la búsqueda tabú. El TSP requiere buscar un orden en el cual viajar entre ciudades, tal que la distancia recorrida sea minimizada. Por ejemplo, si las ciudades A y B están una al lado de la otra, mientras que la ciudad C está más lejos, la distancia total recorrida será más corta si las ciudades A y B son visitadas una después de la otra, antes de visitar C. Como encontrar un orden óptimo para visitar las ciudades en el TSP es un problema NP-difícil. los métodos de aproximación basados en heurísticas son útiles para lograr la optimalidad.

La búsqueda tabú puede utilizarse para encontrar una solución satisfactoria para el TSP. Primero, la búsqueda tabú comienza con una solución inicial, que puede ser generada con el algoritmo del vecino más cercano. Para crear nuevas soluciones, el orden en que dos ciudades son visitadas es intercambiado. La distancia total recorrida entre todas las ciudades es utilizada para juzgar cuánto mejor es una solución que otra. Para prevenir ciclos y para salir de los óptimos locales, una solución es agregada a la lista tabú si es que es aceptada en N*(x), el vecindario de soluciones. Se continúan creando nuevas soluciones hasta que se cumple algún criterio de parada, como por ejemplo un número arbitrario de iteraciones. Una vez que la búsqueda tabú se detiene, la mejor solución es aquella que cuya distancia total a recorrer entre las ciudades es la menor.

Véase también

• Simulated annealing
• Algoritmos genéticos
• GRASP, o Greedy Randomized Adaptive Search Procedure (Procedimiento de Búsqueda Goloso, Aleatorio y Adaptativo)
• Búsqueda local dirigida

Bibliografía

• Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer, Norwell, MA.
• Glover, F. "Tabu Search — Part I", ORSA Journal on Computing 1989 1: 3, 190-206.
• Glover, F. "Tabu Search — Part II", ORSA Journal on Computing 1990 2: 1, 4-32.
• Cvijovic, D.; Klinowski, J. "Taboo search - an approach to the multiple minima problem". Science 1995 267, 664-666.

Enlaces externos

• ParadisEO Archivado el 5 de agosto de 2015 en Wayback Machine. un poderoso framework de C++ dedicado al diseño reutilizable de metaheurísticas, incluidos algoritmos de búsqueda local tales como la búsqueda tabú

• Datos: Q1424540