Búsqueda tabú

Búsqueda tabú

Búsqueda tabú

Para otros usos de este término, véase Búsqueda.

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 atribuída a Fred Glover.

Contenido

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 sólo 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 cuanto mejor es una solución de 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 continuan creando nuevas soluciones hasta que algún criterio de parada, como por ejemplo un número arbirtrario de iteraciones, es encontrado. 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
  • Algorítmos 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

Obtenido de "B%C3%BAsqueda tab%C3%BA"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Búsqueda — Saltar a navegación, búsqueda Búsqueda puede hacer referencia a: Busca, acción de buscar. Motor de búsqueda, sistema informático que indexa archivos almacenados en servidores web gracias a su «spider» (o Web crawler). Búsqueda binaria o Algoritmo …   Wikipedia Español

  • Tabú — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar al autor pri …   Wikipedia Español

  • Ingeniería del software basada en búsqueda — (ISBB), proviene del término originario inglés Search Based Software Engineering (SBSE). Alude a la aplicación de técnicas de optimización ya utilizadas en otros campos de la ingeniería y de la ciencia, como algoritmos genéticos, simulated… …   Wikipedia Español

  • Alimentos tabú — Gula, una de las secciones de la Mesa de los pecados capitales, de Hieronymus Bosch. Cuatro personajes, en la escena: a la mesa hay un hombre gordo comiendo; a la derecha, de pie, otro que bebe ansiosamente, directamente de la jarra; a la… …   Wikipedia Español

  • Algoritmo hormiga — El algoritmo hormiga o algoritmo de las hormigas es una técnica probabilística utilizada para solucionar problemas de cómputo; este algoritmo está inspirado en el comportamiento que presentan las hormigas para encontrar las trayectorias desde la… …   Wikipedia Español

  • Anexo:Episodios de Numb3rs — La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada (2005 2006) …   Wikipedia Español

  • Episodios de Numb3rs — Anexo:Episodios de Numb3rs Saltar a navegación, búsqueda La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada ( …   Wikipedia Español

  • Metaheurística — Una metaheurística es un método heurístico para resolver un tipo de problema computacional general, usando los parámetros dados por el usuario sobre unos procedimientos genéricos y abstractos de una manera que se espera eficiente. Normalmente,… …   Wikipedia Español

  • Incesto — Existen desacuerdos sobre la neutralidad en el punto de vista de la versión actual de este artículo o sección. En la página de discusión puedes consultar el debate al respecto …   Wikipedia Español

  • Buck-Tick — Saltar a navegación, búsqueda Información de fondo Origen Japón javascript:sinrelevancia() Género (s) Rock Años 1984 Presente activos Label (s) BMG Japan Www.buck Web tick.com Miembros Atsushi Sakurai Hisashi Imai Hidehiko Hoshino Yutaka Higuchi… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”