La búsqueda tabú (TS) es un método de búsqueda metaheurística que emplea métodos de búsqueda locales utilizados 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 vecindario) toman una posible solución a un problema y verifican sus vecinos inmediatos (es decir, soluciones que son similares excepto por muy pocos detalles menores) con la esperanza de encontrar una solución mejorada. Los métodos de búsqueda local tienden 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 empeoran si no hay ningún movimiento mejorado disponible (como cuando la búsqueda está estancada en un mínimo local estricto ). Además, se introducen prohibiciones (de ahí el término tabú ) para disuadir 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 período de corto plazo determinado o si ha violado una regla, se marca como " tabú " (prohibido) para que el algoritmo no considere esa posibilidad repetidamente.
La palabra tabú proviene de la palabra tongana 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 espacial, distribución de energía, ingeniería molecular, logística, clasificación de patrones , fabricación flexible, gestión de residuos, exploración mineral, análisis biomédico, conservación del medio ambiente y decenas de otros. En los últimos años, revistas de una amplia variedad de campos han publicado artículos tutoriales y estudios computacionales que documentan los éxitos de la búsqueda tabú en la ampliación de la frontera de los problemas que pueden manejarse eficazmente, generando soluciones cuya calidad a menudo supera significativamente la obtenida mediante métodos aplicados anteriormente. Puede encontrar una lista completa de aplicaciones, incluidas descripciones resumidas de los beneficios obtenidos 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 locales a menudo se atascan en áreas con puntuaciones bajas o en áreas donde las puntuaciones se estancan. Para evitar estos errores y explorar regiones del espacio de búsqueda que quedarían inexploradas por otros procedimientos de búsqueda locales, 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 avanza pasando iterativamente de la solución actual a una solución mejorada en formato .
La búsqueda tabú tiene varias similitudes con el recocido simulado , ya que ambos implican posibles movimientos cuesta abajo. De hecho, el recocido simulado podría verse como una forma especial de TS, mediante la cual utilizamos "tenencia graduada", es decir, un movimiento se vuelve tabú con una probabilidad específica.
Estas estructuras de memoria forman lo que se conoce como lista tabú, un conjunto de reglas y soluciones prohibidas que se utilizan para filtrar qué soluciones serán admitidas en el vecindario para ser exploradas por 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 (menos que hace iteraciones, donde está el número de soluciones anteriores que se almacenarán; también se denomina tenencia tabú). Más comúnmente, una lista tabú consta de soluciones que han cambiado mediante el proceso de pasar de una solución a otra. Para facilitar la descripción, es conveniente entender que una “solución” está codificada y representada por 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, los recuerdos a corto, medio y largo plazo pueden superponerse. Dentro de estas categorías, la memoria se puede diferenciar aún más mediante medidas como la frecuencia y el impacto de los cambios realizados. Un ejemplo de una estructura de memoria a plazo intermedio es aquella que prohíbe o fomenta soluciones que contienen ciertos atributos (p. ej., soluciones que incluyen valores indeseables o deseables para ciertas variables) o una estructura de memoria que previene o induce ciertos movimientos (p. ej., basados en la memoria de frecuencia). aplicado a soluciones que comparten características en común con soluciones atractivas o poco atractivas encontradas en el pasado). En la memoria a corto plazo, los atributos seleccionados en las soluciones visitadas recientemente están etiquetados como "tabu-activos". 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 en el conjunto permitido (siempre que la solución sea "suficientemente buena" según una medida de calidad o diversidad). Un criterio de aspiración simple y comúnmente utilizado es permitir soluciones que sean mejores que la mejor solución conocida actualmente.
La memoria a corto plazo por sí sola puede ser suficiente para lograr soluciones superiores a las encontradas mediante métodos de búsqueda local convencionales, pero las estructuras a mediano y 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 la 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 la búsqueda de dispersión, [8] [9] una clase de procedimientos basados en población que tiene raíces en común con la búsqueda tabú y que 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ú como se describe anteriormente. Esta implementación tiene una memoria a corto plazo rudimentaria, pero no contiene estructuras de memoria a medio o largo plazo. El término "aptitud" se refiere a una evaluación de la solución candidata, incorporada en una función objetivo para la optimización matemática.
sMejor ← s0 mejor candidato ← s0 Lista tabú ← [] listatabú . empujar ( s0 )mientras ( sin pararCondición ()) sNeighborhood ← getNeighbors ( mejorCandidato ) mejorCandidatoFitness ← - ∞ para ( sCandidato en sNeighborhood ) if ( ( no tabuList . Contiene ( sCandidate )) y ( fitness ( sCandidate ) > bestCandidateFitness ) ) mejorCandidato ← sCandidato mejorCandidatoFitness ← fitness ( mejorCandidato ) fin fin si ( bestCandidateFitness es - ∞ ) romper ; fin if ( mejorCandidatoFitness > fitness ( sBest )) sMejor ← mejorCandidato fin listatabú . empujar ( mejor candidato ) si ( listaTabu . tamaño > maxTabuSize ) listatabú . eliminarPrimero () finfindevolver sBest Las líneas 1 a 4 representan una configuración inicial, creando respectivamente una solución inicial (posiblemente elegida al azar), estableciendo esa solución inicial como la mejor vista hasta la fecha e inicializando 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 central comienza en la línea 5. Este bucle continuará buscando una solución óptima hasta que se cumpla una condición de parada 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). Se verifican las soluciones vecinas en busca de elementos tabú en la línea 9. Además, el algoritmo realiza un seguimiento de la mejor solución en la vecindad, 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 cuando se encuentra un nuevo espacio de búsqueda. [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), algunos elementos podrán caducar (línea 23). Generalmente, los elementos caducan de la lista en el mismo orden en que se agregan. El procedimiento seleccionará al 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 cual se devuelve la mejor solución vista durante el proceso de búsqueda (línea 26).
El problema del viajante (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 tras otra antes de visitar la ciudad C. Desde encontrar una solución óptima Es NP-duro , los métodos de aproximación basados en heurísticas (como las búsquedas locales) son útiles para diseñar soluciones cercanas a las óptimas. Para obtener buenas soluciones TSP, es fundamental explotar la estructura del gráfico. El valor de explotar la estructura del problema es un tema recurrente en los métodos metaheurísticos, y la búsqueda tabú se adapta bien a esto. Una clase de estrategias asociadas con la búsqueda tabú denominada métodos de cadena de expulsión ha permitido obtener soluciones TSP de alta calidad de manera eficiente [10]
Por otro lado, se puede utilizar una búsqueda tabú simple para encontrar una solución satisfactoria para el problema del viajante (es decir, una solución que satisfaga un criterio de adecuación, aunque no con la alta calidad obtenida al explotar la estructura del gráfico). La búsqueda comienza con una solución inicial, que puede generarse aleatoriamente o según algún tipo de algoritmo del 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 quedar atrapado en óptimos locales , se agrega una solución a la lista tabú si se acepta en la vecindad de soluciones .
Se crean nuevas soluciones hasta que se cumple algún criterio de parada, 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.