La búsqueda tabú (TS) es un método de búsqueda metaheurística que emplea métodos de búsqueda locales para la optimización matemática . Fue creado por Fred W. Glover en 1986 [1] y formalizado en 1989. [2] [3]
Las búsquedas locales (de vecindad) toman una solución potencial para un problema y verifican sus vecinas inmediatas (es decir, soluciones que son similares salvo por unos pocos detalles menores) con la esperanza de encontrar una solución mejorada. Los métodos de búsqueda local tienen una tendencia a quedarse estancados en regiones subóptimas o en mesetas donde muchas soluciones son igualmente adecuadas.
La búsqueda tabú mejora el rendimiento de la búsqueda local al relajar su regla básica. En primer lugar, en cada paso se pueden aceptar movimientos que empeoren si no hay movimientos que mejoren (como cuando la búsqueda se queda estancada en un mínimo local estricto ). Además, se introducen prohibiciones (de ahí el término tabú ) para disuadir a la búsqueda de volver a soluciones visitadas anteriormente.
La implementación de la búsqueda tabú utiliza estructuras de memoria que describen las soluciones visitadas o conjuntos de reglas proporcionados por el usuario. [2] Si una solución potencial ha sido visitada previamente dentro de un cierto período corto o si ha violado una regla, se marca como " tabú " (prohibido) para que el algoritmo no considere esa posibilidad repetidamente.
La palabra tabú proviene del término tongano para indicar cosas que no se pueden tocar porque son sagradas. [4]
La búsqueda tabú es un algoritmo metaheurístico que se puede utilizar para resolver problemas de optimización combinatoria (problemas en los que se desea un ordenamiento y selección óptimos de opciones).
Las aplicaciones actuales de TS abarcan las áreas de planificación de recursos , telecomunicaciones, diseño VLSI , análisis financiero, programación, planificación del espacio, distribución de energía, ingeniería molecular, logística, clasificación de patrones , fabricación flexible, gestión de residuos, exploración minera, análisis biomédico, conservación ambiental y muchas otras. En los últimos años, revistas en una amplia variedad de campos han publicado artículos tutoriales y estudios computacionales que documentan los éxitos de la búsqueda tabú en la extensión de la frontera de problemas que se pueden manejar de manera efectiva, produciendo soluciones cuya calidad a menudo supera significativamente la obtenida por los métodos aplicados anteriormente. Se puede encontrar una lista completa de aplicaciones, incluidas descripciones resumidas de las ganancias logradas a partir de implementaciones prácticas, en [5].
La búsqueda tabú utiliza un procedimiento de búsqueda local o de vecindad para pasar iterativamente de una solución potencial a una solución mejorada en la vecindad de , hasta que se haya satisfecho algún criterio de detención (generalmente, un límite de intentos o un umbral de puntuación). Los procedimientos de búsqueda local a menudo se atascan en áreas de baja puntuación o áreas donde las puntuaciones se estancan. Para evitar estos obstáculos y explorar regiones del espacio de búsqueda que quedarían inexploradas por otros procedimientos de búsqueda local, la búsqueda tabú explora cuidadosamente la vecindad de cada solución a medida que avanza la búsqueda. Las soluciones admitidas en la nueva vecindad, , se determinan mediante el uso de estructuras de memoria. Usando estas estructuras de memoria, la búsqueda progresa pasando iterativamente de la solución actual a una solución mejorada en .
La búsqueda tabú tiene varias similitudes con el recocido simulado , ya que ambos implican posibles movimientos descendentes. De hecho, el recocido simulado podría considerarse como una forma especial de búsqueda tabú, en la que utilizamos una "permanencia graduada", es decir, un movimiento se vuelve tabú con una probabilidad específica.
Estas estructuras de memoria forman lo que se conoce como la lista tabú, un conjunto de reglas y soluciones prohibidas que se utilizan para filtrar qué soluciones se admitirán en el vecindario que se explorará mediante la búsqueda. En su forma más simple, una lista tabú es un conjunto a corto plazo de las soluciones que se han visitado en el pasado reciente (hace menos de iteraciones, donde es el número de soluciones anteriores que se almacenarán; también se denomina tenencia tabú). Más comúnmente, una lista tabú consiste en soluciones que han cambiado mediante el proceso de pasar de una solución a otra. Es conveniente, para facilitar la descripción, entender que una "solución" se codifica y representa mediante dichos atributos.
Las estructuras de memoria utilizadas en la búsqueda tabú se pueden dividir aproximadamente en tres categorías: [6]
En la práctica, las memorias de corto, mediano y largo plazo pueden superponerse. Dentro de estas categorías, la memoria puede diferenciarse además mediante medidas como la frecuencia y el impacto de los cambios realizados. Un ejemplo de una estructura de memoria de mediano plazo es una que prohíbe o fomenta soluciones que contienen ciertos atributos (por ejemplo, soluciones que incluyen valores indeseables o deseables para ciertas variables) o una estructura de memoria que impide o induce ciertos movimientos (por ejemplo, basada en la memoria de frecuencia aplicada a soluciones que comparten características en común con soluciones atractivas o poco atractivas encontradas en el pasado). En la memoria de corto plazo, los atributos seleccionados en las soluciones visitadas recientemente se etiquetan como "tabú-activas". Las soluciones que contienen elementos tabú-activos están prohibidas. Los criterios de aspiración se emplean para anular el estado tabú de una solución, incluyendo así la solución excluida de otro modo en el conjunto permitido (siempre que la solución sea "suficientemente buena" de acuerdo con una medida de calidad o diversidad). Un criterio de aspiración simple y de uso común es permitir soluciones que sean mejores que la mejor solución conocida actualmente.
La memoria de corto plazo por sí sola puede ser suficiente para lograr soluciones superiores a las encontradas por los métodos de búsqueda local convencionales, pero las estructuras intermedias y de largo plazo suelen ser necesarias para resolver problemas más difíciles. [7] La búsqueda tabú a menudo se compara con otros métodos metaheurísticos , como el recocido simulado , los algoritmos genéticos , los algoritmos de optimización de colonias de hormigas , la optimización de búsqueda reactiva, la búsqueda local guiada o la búsqueda adaptativa aleatoria codiciosa . Además, la búsqueda tabú a veces se combina con otras metaheurísticas para crear métodos híbridos. El híbrido de búsqueda tabú más común surge al unir TS con búsqueda dispersa, [8] [9] una clase de procedimientos basados en la población que tiene raíces en común con la búsqueda tabú, y a menudo se emplea para resolver grandes problemas de optimización no lineal.
El siguiente pseudocódigo presenta una versión simplificada del algoritmo de búsqueda tabú descrito anteriormente. Esta implementación tiene una memoria de corto plazo rudimentaria, pero no contiene estructuras de memoria intermedia o de largo plazo. El término "aptitud" se refiere a una evaluación de la solución candidata, tal como se materializa en una función objetivo para la optimización matemática.
sMejor ← s0 mejorCandidato ← s0 tabuList ← [] listaTab.push ( s0 )mientras ( no stopCondition ()) sNeighborhood ← getNeighbors ( mejor candidato ) mejorCandidatoFitness ← - ∞ para ( Candidato en el barrio ) si ( ( no tabuList . contiene ( sCandidate )) y ( fitness ( sCandidate ) > bestCandidateFitness ) ) mejorCandidato ← sCandidato mejorCandidatoFitness ← fitness ( mejorCandidato ) fin fin si ( bestCandidateFitness es - ∞ ) romper ; fin si ( mejorCandidatoAptitud > aptitud ( sMejor )) sBest ← mejorCandidato fin tabuList . push ( mejorCandidato ) si ( tabuList . tamaño > maxTabuSize ) tabuList .removeFirst ( ) finfinDevolver sBest Las líneas 1 a 4 representan una configuración inicial, que consiste en crear una solución inicial (posiblemente elegida al azar), establecer esa solución inicial como la mejor vista hasta la fecha e inicializar una lista tabú con esta solución inicial. En este ejemplo, la lista tabú es simplemente una estructura de memoria a corto plazo que contendrá un registro de los elementos de los estados visitados.
El bucle algorítmico principal comienza en la línea 5. Este bucle continuará buscando una solución óptima hasta que se cumpla una condición de detención especificada por el usuario (dos ejemplos de tales condiciones son un simple límite de tiempo o un umbral en la puntuación de aptitud). Las soluciones vecinas se verifican en busca de elementos tabú en la línea 9. Además, el algoritmo realiza un seguimiento de la mejor solución en el vecindario, que no es tabú.
La función de aptitud es generalmente una función matemática, que devuelve una puntuación o se satisfacen los criterios de aspiración; por ejemplo, un criterio de aspiración podría considerarse como un nuevo espacio de búsqueda encontrado. [4] Si el mejor candidato local tiene un valor de aptitud más alto que el mejor actual (línea 18), se establece como el nuevo mejor (línea 19). El mejor candidato local siempre se agrega a la lista tabú (línea 21), y si la lista tabú está llena (línea 22), se permitirá que algunos elementos expiren (línea 23). Generalmente, los elementos expiran de la lista en el mismo orden en que se agregan. El procedimiento seleccionará el mejor candidato local (incluso si tiene peor aptitud que el mejor actual) para escapar del óptimo local.
Este proceso continúa hasta que se cumple el criterio de detención especificado por el usuario, momento en el que se devuelve la mejor solución vista durante el proceso de búsqueda (línea 26).
El problema del viajante de comercio (TSP) se utiliza a veces para mostrar la funcionalidad de la búsqueda tabú. [7] Este problema plantea una pregunta sencilla: dada una lista de ciudades, ¿cuál es la ruta más corta que visita todas las ciudades? Por ejemplo, si la ciudad A y la ciudad 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 se visitan una después de la otra antes de visitar la ciudad C. Dado que encontrar una solución óptima es NP-hard , los métodos de aproximación basados en heurísticas (como las búsquedas locales) son útiles para idear soluciones cercanas a las óptimas. Para obtener buenas soluciones TSP, es esencial explotar la estructura del grafo. El valor de explotar la estructura del problema es un tema recurrente en los métodos metaheurísticos, y la búsqueda tabú es muy adecuada para esto. Una clase de estrategias asociadas con la búsqueda tabú llamadas métodos de cadena de expulsión han hecho posible obtener soluciones TSP de alta calidad de manera eficiente [10].
Por otra parte, se puede utilizar una búsqueda tabú simple para encontrar una solución satisfactoria para el problema del viajante de comercio (es decir, una solución que satisface un criterio de adecuación, aunque no con la alta calidad obtenida al explotar la estructura del grafo). La búsqueda comienza con una solución inicial, que puede generarse aleatoriamente o de acuerdo con algún tipo de algoritmo de vecino más cercano . Para crear nuevas soluciones, se intercambia el orden en que se visitan dos ciudades en una solución potencial. La distancia total de viaje entre todas las ciudades se utiliza para juzgar qué tan ideal es una solución en comparación con otra. Para evitar ciclos, es decir, visitar repetidamente un conjunto particular de soluciones, y evitar quedarse estancado en óptimos locales , se agrega una solución a la lista tabú si es aceptada en el vecindario de soluciones .
Se crean nuevas soluciones hasta que se cumple un criterio de detención, como un número arbitrario de iteraciones. Una vez que se detiene la búsqueda tabú simple, devuelve la mejor solución encontrada durante su ejecución.